Steven_MengのBlog

传送门

模拟赛的$\rm T1$,感觉还是非常可做的。

考虑随机化(大雾),每次把没有用过的数组成的序列$S$打乱,从$S$依次取出数,加入答案集合,我们可以根据加进来的数得出最后一个数的大小,如果这个数还没有用过,那么将这个数加入答案集合,就得出了答案,直接退出。

目前这种做法还没有被卡掉,大概是数据水吧。。。

时间复杂度$O(玄学)$

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
#include <bits/stdc++.h>
#define MAXN 1000005
#define ll long long
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=(x*10)+(ch-'0');
ch=getchar();
}
return x*f;
}
inline void print(ll x){
if (x>=10ll) print(x/10ll);
putchar(x%10ll+48ll);
}
ll num[MAXN],vis[MAXN],vis2[MAXN],tot;
int main(){
ll S=1000000,n=(long long)read();
ll sum=0;
for (register int i=1;i<=n;++i){
ll x=(long long)read();
vis2[x]=true;
sum+=x-1;
}
for (register int i=1;i<=S;++i){
if (!vis2[i]) num[++tot]=i;
}
if (S>=sum){//特判
if (!vis2[S-sum]){
printf("%lld\n%lld\n",1ll,S-sum);
return 0;
}
}
for (register int t=1;t<=2000000;++t){
random_shuffle(num+1,num+1+tot);
memcpy(vis,vis2,sizeof(vis));
ll res=0;
for (register int i=1;i<tot;++i){
res+=(S-num[i]);
vis[num[i]]=true;
if (res>=sum){
break;
}
if (sum-res>S){
continue;
}
if (!vis[S-sum+res]){//没有用过
print((long long)i+1ll),putchar('\n');
for (register int j=1;j<=i;++j){
print(num[j]),putchar(' ');
}
print(S-sum+res),putchar('\n');
return 0;
}
}
}
}

 评论