「fstqwq的2017/10/07模拟题」分组 - 并查集+贪心 | Bill Yang's Blog

「fstqwq的2017/10/07模拟题」分组 - 并查集+贪心

题目大意





题目分析

不难想到贪心策略:
保证字典序最小,即让第一段尽量小,其次让第二段尽量小……
但是“尽量小”的方案是不好维护的,因此不妨倒过来考虑:让最后一段尽量长,其次让倒数第二段尽量长…..
这样构造出来的方案一定字典序最小。

对于$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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
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)$。

姥爷们赏瓶冰阔落吧~
0%