跟我一起大喊：kimo！
毒瘤场。
Problem A
题意：
将 $n$ 个正整数 $2^1,2^2,…,2^n$ 分成两组，每组数的个数相同，求两组数和的最小差。
$1 \leq n \leq 30,2|n$
做法：
我也不知道怎么做。
手玩了一下，答案是 $2^{\frac n2+1}+2$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| # include <bits/stdc++.h>
# define rr
const int N=100010,INF=0x3f3f3f3f;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
int T=read();
while(T--){
int n=read(),a=0,b=0;
printf("%d\n",(1<<(n/2+1))-2);
}
return 0;
}
|
Problem B
题意：
有一个长为 $n$ 的数组 $a$。你需要在数组中插入至多 $10^4$ 个元素，使得该数组任意长为 $k$ 的子数组之和都相同。
$1 \leq k \leq n \leq 100,1 \leq a_i \leq n$
做法：
显然，当最终数组是一个长为 $k$ 的数组循环而成的，那么该数组任意长为 $k$ 的子数组之和都相同。
设数组 $b$ 为 $a$ 中元素去重之后的数组，其长度为 $m$。如果 $m>k$，那我们显然无法构造出这样的数组 —— 因为让 $b$ 中元素都出现一次至少需要 $m$ 的长度，已经大于循环节长度 $k$。
如果 $m<k$，可以在 $b$ 的末尾补上任意数，使其长度变为 $k$。赛时代码中写的是循环补充，例如 $b=[2,3,1],k=9$ 时，补足后的 $b$ 变为 $b=[2,3,1,2,3,1,2,3,1]$。
最后将 $b$ 循环输出 $n$ 次即可。
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
| # include <bits/stdc++.h>
# define rr
const int N=100010,INF=0x3f3f3f3f;
int T;
int a[N];
int n,m;
int b[N],len;
int v[N],size;
int cnt[N];
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
int T=read();
while(T--){
n=read(),m=read();
for(rr int i=1;i<=n;++i){
a[i]=read();
v[i]=a[i];
}
std::sort(v+1,v+1+n);
if((size=std::unique(v+1,v+1+n)-(v+1))>m){
puts("-1");
continue;
}
printf("%d\n",n*m);
for(rr int i=1;i<=n;++i){
for(rr int j=1;j<=m;++j){
printf("%d ",v[(j-1)%size+1]);
}
}
puts("");
End:;
}
return 0;
}
|
Problem C
题意：
给定一个长度为 $n$ 的字符串 $s$。你需要把这个字符串中的字符重新分配给 $k$ 个字符串（不能有空字符串），使得字典序最大的字符串最小。求出最优情况下，字典序最大的字符串。
对于字符串 $x,y$，$x$ 的字典序 $<y$ 当且仅当满足以下条件至少一个：
- $x$ 是 $y$ 的前缀
- $\exists 1 \leq i \leq \min\{|x|,|y|\}$，使得 $x_i<y_i$
$1 \leq k \leq n \leq 10^5$。
做法：
容易想到把字典序前 $k$ 小的字符拿出来当作每个字符串的第一个字符。
此时若每个字符串的第一个字符不同，则我们把剩下的部分全部接到字典序最小的字符串后，答案是字典序最大的那个字符。
若每个字符串的第一个字符相同，则分两种情况讨论：
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
| # include <bits/stdc++.h>
# define rr
const int N=100010,INF=0x3f3f3f3f;
int cnt[30];
char s[N];
int n,k;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
int T=read();
while(T--){
n=read(),k=read();
scanf("%s",s+1);
memset(cnt,0,sizeof(cnt));
for(rr int i=1;i<=n;++i){
++cnt[s[i]-'a'+1];
}
std::string x="";
int rt=k;
bool flag=true;
int tot=0;
for(rr int i=1;i<=26;++i){
if(!cnt[i]){
continue;
}
if(cnt[i]>=rt){
x+=(char)(i+'a'-1);
cnt[i]-=rt;
break;
}else{
rt-=cnt[i];
cnt[i]=0;
flag=false;
}
}
if(!flag){
std::cout<<x<<std::endl;
continue;
}
std::cout<<x;
for(rr int i=1;i<=26;++i){
if(cnt[i]){
++tot;
}
}
if(tot==1){
for(rr int i=1;i<=26;++i){
while(cnt[i]>0){
std::cout<<(char)(i+'a'-1);
cnt[i]-=k;
}
}
std::cout<<std::endl;
}else{
for(rr int i=1;i<=26;++i){
while(cnt[i]>0){
std::cout<<(char)(i+'a'-1);
--cnt[i];
}
}
puts("");
}
}
return 0;
}
|