题目大意
题目分析
不难想到贪心策略：
保证字典序最小，即让第一段尽量小，其次让第二段尽量小……
但是“尽量小”的方案是不好维护的，因此不妨倒过来考虑：让最后一段尽量长，其次让倒数第二段尽量长…..
这样构造出来的方案一定字典序最小。
对于$K=1$的情况，只需要倒着枚举分割点$j$，每到达一个数先枚举$d$，检查$d^2-a[j]$是否在之前的$Hash$表中出现过，若出现过，$j$与$j+1$必须分开，否则将$a[j]$加入$Hash$表，将$j$往前移。
对于$K=2$，不难发现题目要求的是最长形成的二分图。
同样可以倒着枚举分割点$j$，暴力染色检查是否形成二分图进行处理。
经测试，该算法在考试中得到了$64$分。
然而每次都重新判断二分图，时间效率低下，我们需要维护一个数据结构支持：
- 动态加点
- 询问是否是二分图
这样的数据结构，正好可以使用并查集实现。
类似$2-sat$的思想，对$i$点拆分成$i$与$i’$两个点，分别表示染色$1$与染色$2$。
每新加一个点，找到矛盾关系$i$与$j$，在并查集中查看$i,j$或$i’,j’$是否分在同一个集合，若是则无法构成二分图，必须拆分，否则将$i$与$j’$，$i’$与$j$连边，继续将指针前移。
注意并查集的撤销。
代码
本题原数据有误，$std$没有判断矛盾的数是否出现了重复，现已更正。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=131072+5;
int n,k,a[maxn],Max=0;
vector<int>ans;
namespace K_is_1 {
int vst[maxn];
bool check(int pos) {
for(int d=1; d*d-a[pos]<=Max; d++) {
int u=d*d-a[pos];
if(u<=0)continue;
if(vst[u])return false;
}
return true;
}
void solve() {
int next=n;
for(int i=n; i>=1; ) {
bool bj=1;
while(next>=1) {
if(!check(next))break;
vst[a[next--]]=1;
}
if(!next)break;
ans.push_back(next);
while(i>next)vst[a[i--]]=0;
}
}
}
namespace K_is_2 {
bool sqr[2*maxn];
int cnt[maxn],father[2*maxn];
void Sqr_Table() {
for(int i=1; i<=sqrt(2*Max); i++)sqr[i*i]=1;
}
bool check_double(int pos) {
if(cnt[a[pos]]==2&&sqr[2*a[pos]])return false; //已经出现过两个
if(cnt[a[pos]]==1&&sqr[2*a[pos]])
for(int d=1; d*d-a[pos]<=Max; d++) {
int u=d*d-a[pos];
if(u<=0)continue;
if(d*d!=2*a[pos]&&cnt[u])return false;
}
return true;
}
int Get_Father(int x) {
if(father[x]<0)return x;
return father[x]=Get_Father(father[x]);
}
void merge(int x,int y) {
if(x!=y) {
if(father[x]>father[y])swap(x,y); //x集合更小
father[x]+=father[y];
father[y]=x;
}
}
bool color(int x,int y) {
int x1=Get_Father(x),x2=Get_Father(x+Max),y1=Get_Father(y),y2=Get_Father(y+Max);
if(x1==y1||x2==y2)return true;
merge(x1,y2);
merge(x2,y1);
return false;
}
bool check(int pos) {
if(cnt[a[pos]])return true;
for(int d=1; d*d-a[pos]<=Max; d++) {
int u=d*d-a[pos];
if(u<=0||u==a[pos])continue;
if(cnt[u]==2&&sqr[2*u])return false;
if(cnt[u]&&color(u,a[pos]))return false;
}
return true;
}
void solve() {
Sqr_Table();
for(int i=1; i<=Max*2; i++)father[i]=-1;
int next=n;
for(int i=n; i>=1; ) {
bool bj=1;
while(next>=1) {
if(!check_double(next)||!check(next))break;
cnt[a[next]]++;
next--;
}
if(!next)break;
ans.push_back(next);
while(i>next) {
father[a[i]]=father[a[i]+Max]=-1;
cnt[a[i--]]=0;
}
}
}
}
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
Max=max(Max,a[i]);
}
if(k==1)K_is_1::solve();
else K_is_2::solve();
printf("%d\n",ans.size()+1);
reverse(ans.begin(),ans.end());
for(int i=0; i<ans.size(); i++)printf("%d ",ans[i]);
putchar('\n');
return 0;
}
特别声明
本题解已获得$fstqwq$授权，原作者使用CC BY-NC-ND 4.0协议进行共享。
转载本套题请联系$fstqwq(QQ:849199382)$。
