比较毒瘤的一场。但据说 F 是个智障题？做 D 选手大失败…
Problem A
题意：
定义邻居指矩阵中上下左右相邻的格子。
要求构造一个由 B 和 W 组成的 $n\times m$ 矩阵，使得矩阵中有 W 邻居的 B 数量 $=$ 有 B 邻居的 W 数量 $+1$。
$2 \leq n,m \leq 100$
做法：
在左上角留下一个 W，其它全部填 B 即可。
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
| # include <bits/stdc++.h>
# define rr register
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(),m=read();
for(rr int i=1;i<=n;++i){
for(rr int j=1;j<=m;++j){
if(i==1&&j==1){
putchar('W');
}else{
putchar('B');
}
}
puts("");
}
}
return 0;
}
|
Problem B
题意：
给定数组 $a_1,a_2,…,a_n$， 和数组 $b_1,b_2,…,b_n$。每次可以选择 $i,j(i<j)$，并把 $a_j$ 变成 $a_i+a_j$。问经过若干次操作后是否可能变成数组 $b$。
$1 \leq n \leq 10^5,a_i\in \{-1,0,1\},-10^9 \leq b_i \leq 10^9$
做法：
从前往后扫一遍，看 $b_i$ 是否可以被前面的某个 $a_j$ 经过若干次操作后得到。
$b_i$ 能够被前面的某个 $a_j$ 经过若干次操作后得到，当且仅当以下条件中至少满足一个：
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
| # include <bits/stdc++.h>
# define rr register
# define int long long
const int N=100010,INF=0x3f3f3f3f;
int T;
int a[N],b[N];
int n;
bool d[10];
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;
}
signed main(void){
T=read();
while(T--){
n=read();
for(rr int i=1;i<=n;++i){
a[i]=read();
}
for(rr int i=1;i<=n;++i){
b[i]=read();
}
d[1]=0,d[2]=0;
if(a[1]!=b[1]){
puts("NO");
continue;
}
for(rr int i=1;i<=n;++i){
if((a[i]==b[i])||(a[i]<b[i]&&d[1])||(a[i]>b[i]&&d[2])){
if(a[i]==-1)
d[2]=true;
if(a[i]==1)
d[1]=true;
}else{
puts("NO");
goto End;
}
}
puts("YES");
End:;
}
return 0;
}
|
Problem C
题意：
给定数组 $a_1,a_2,…,a_n$。
定义 $a$ 的一个连续子数组是 good subarray，当且仅当这个子数组的任何一个连续子数组之和都不为 $0$。
求出 $a$ 数组中 good subarray 的数量。
$1 \leq n \leq 2\cdot 10^5,-10^9 \leq a_i \leq 10^9$
做法：
考虑从 $1$ 到 $n$ 依次考虑以 $i$ 结尾的 good subarray 的数量。
如果存在一个 $j$，并且有以它开头的并且在一个 $\leq i$ 位置结尾的 bad subarray（与 good subarray 相对），那么很显然，$\leq j$ 的位置都不可能成为以 $i$ 结尾的 good subarray 的开头。
所以扫过去，顺便维护下最大的 $j$ 就行了。 std::map 瞎搞搞就好。
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
| # include <bits/stdc++.h>
# define rr register
# define int long long
const int N=200010,INF=0x3f3f3f3f;
std::map <int,int> Map;
int a[N];
int n;
int ans=0;
int sum[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;
}
signed main(void){
n=read();
for(rr int i=1;i<=n;++i){
a[i]=read();
}
int last=0;
Map[0]=1;
for(rr int i=1;i<=n;++i){
if(a[i])
++ans;
sum[i]=sum[i-1]+a[i];
last=std::max(last,Map[sum[i]]);
ans+=std::max(0ll,(i-1)-last);
Map[sum[i]]=i+1;
}
printf("%I64d",ans);
return 0;
}
|
Problem D
题意：
给定一个长度为 $n$ 的字符串，由 L 和 R 组成。你可以执行 $k$ 次操作。每次操作时，你可以选择任意对相邻的 RL，把它们改成 LR。
如果无法选择至少一对 RL，那么操作结束。
你需要给出一个操作顺序，使得正好 $k$ 次操作后操作结束。
如果无法操作，输出 $-1$。
$n \leq 3000,k \leq 3 \cdot 10^6$
做法：
显然，最小的操作次数是在每次操作时选择尽可能多的对。
显然，最大的操作次数是在最小的操作次数基础上，将所有选择的对拆开来操作。
显然，如果最小的操作次数 $>k$，或者最大的操作次数 $<k$，那么只能输出 $-1$。
输出照着 Codeforces 1329 A 就好了。
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
| # include <bits/stdc++.h>
# define rr register
const int N=3010,INF=0x3f3f3f3f;
std::vector <int> p[N];
int n,k;
char s[N];
int m;
int cnt;
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){
n=read(),k=read();
scanf("%s",s+1);
for(rr int i=1;i<=n;++i){
bool flag=false;
for(rr int j=1;j<=n-1;++j){
if(s[j]=='R'&&s[j+1]=='L'){
p[i].push_back(j);
std::swap(s[j],s[j+1]);
flag=true;
++cnt;
++j;
}
}
if(!flag){
m=i-1;
break;
}
}
if(cnt<k||m>k){
printf("-1");
return 0;
}
int ret=cnt-k;
for(rr int i=1;i<=m;++i){
if(ret>=(p[i].size()-1)){
printf("%d ",p[i].size());
for(rr int j=0;j<p[i].size();++j){
printf("%d ",p[i][j]);
}
puts("");
ret-=(p[i].size()-1);
}else{
if(ret){
printf("%d ",ret+1);
for(rr int j=0;j<=ret;++j){
printf("%d ",p[i][j]);
}
puts("");
for(rr int j=ret+1;j<p[i].size();++j){
printf("1 %d\n",p[i][j]);
}
ret=0;
}else{
for(rr int j=0;j<p[i].size();++j){
printf("1 %d\n",p[i][j]);
}
}
}
}
return 0;
}
|