比赛链接 / 官方题解链接
紫名留念！
A. Little Artem
Solution
构造题，染色成棋盘，若 $n\times m$ 是偶数就再挑一个白色染成黑色即可。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T, n, m;
int main(){
read(T);
while(T--){
read(n, m);
if((n * m) & 1){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if((i + j) & 1) putchar('W');
else putchar('B');
}
puts("");
}
continue;
}
else{
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i == 1 && j == 1){
putchar('B');
continue;
}
if((i + j) & 1) putchar('B');
else putchar('W');
}
puts("");
}
continue;
}
}
return 0;
}
|
B. Kind Anton
Solution
$\forall i\in[1,n]$：
若 $a[i]<b[i]$，则必须 $\exists j\in[1,i-1] (a[j]=1)$；
若 $a[i]>b[i]$，则必须 $\exists j\in[1,i-1] (a[j]=-1)$.
不满足上述条件输出 NO，满足输出 YES.
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 100005;
int T, n;
LL a[N], b[N];
bool e[10];
int main(){
read(T);
while(T--){
read(n);
e[0] = e[1] = e[2] = 0;
for(int i = 1; i <= n; i++) read(a[i]);
for(int i = 1; i <= n; i++) read(b[i]);
bool ok = true;
for(int i = 1; i <= n; i++){
if(a[i] < b[i]){
if(!e[2]){
ok = false;
break;
}
}
else if(a[i] > b[i]){
if(!e[0]){
ok = false;
break;
}
}
e[a[i]+1] = 1;
}
puts(ok ? "YES" : "NO");
}
return 0;
}
|
C. Eugene and an array
Solution
求出前缀和，逆序枚举区间左端点，需要求出值与当前节点相同的节点最小位置，并且与最小的 $0$ 区间右端点取 $\min$，统计答案。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
int n;
LL a[N], s[N], ans, mnpos;
map<LL, LL> pos;
int main(){
read(n);
mnpos = n + 1;
for(int i = 1; i <= n; i++){
read(a[i]);
s[i] = s[i-1] + a[i];
}
for(int i = n; i >= 1; i--){
pos[s[i]] = i;
if(pos[s[i-1]] == 0) ans += mnpos - i;
else{
mnpos = min(mnpos, pos[s[i-1]]);
ans += mnpos - i;
}
}
printf("%lld\n", ans);
return 0;
}
|
D. Challenges in school №41
Solution
每个 $L$ 都会与它前面的所有 $R$ 交换一次，所以最大时间就是最多交换次数 $=\sum\limits_{s[i]==L}i之前R的数量$， 如果 $k$ 大于这个数无解；然后我们按最小时间的方案模拟过程，即每个时间把所有相邻的 $RL$ 都给交换了。如果 $k$ 小于最小时间则无解，否则，把同一时间进行的操作拆开补满 $k$ 比最小时间多出来的部分。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 3005;
int n, k, id;
char s[N];
LL maxk, mink;
vi v, ans[N*N];
int main(){
read(n, k);
scanf("%s", s+1);
LL cnt = 0;
for(int i = 1; i <= n; i++){
cnt += s[i] == 'R';
if(s[i] == 'L') maxk += cnt;
}
if(k > maxk) return puts("-1"), 0;
for(int i = 1; i < n; i++)
if(s[i] == 'R' && s[i+1] == 'L')
v.pb(i);
cnt = 0;
while(!v.empty()){
id++;
vi tmp;
while(!v.empty()){
int cur = v.back(); v.pop_back();
ans[id].pb(cur);
s[cur] = 'L', s[cur+1] = 'R';
if(s[cur+2] == 'L') tmp.pb(cur+1);
if(s[cur-1] == 'R') tmp.pb(cur-1);
}
while(!tmp.empty())
v.pb(tmp.back()), tmp.pop_back();
}
mink = id;
if(k < mink) return puts("-1"), 0;
k -= mink;
for(int i = 1; i <= id; i++){
while(k && !ans[i].empty()){
printf("1 %d\n", ans[i].back());
ans[i].pop_back();
if(!ans[i].empty()) k--;
}
if(!k && !ans[i].empty()){
printf("%d ", (int)ans[i].size());
for(auto t: ans[i]) printf("%d ", t);
puts("");
}
}
return 0;
}
|
E. Road to 1600
Solution
【参看dls的视频讲解吧～：链接】
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int n, tot, ans[505][505];
void solve(int m, int k){
if(m == 3){
ans[2][2] = ++tot, ans[2][3] = ++tot, ans[3][3] = ++tot;
ans[3][1] = ++tot, ans[2][1] = ++tot, ans[1][3] = ++tot;
ans[1][2] = ++tot, ans[1][1] = ++tot, ans[3][2] = ++tot;
return;
}
if(!k){
for(int i = 1; i <= m; i++) ans[m][i] = ++tot;
for(int i = m-1; i >= 1; i--) ans[i][m] = ++tot;
if(m == 4) swap(ans[1][m], ans[2][m]);
}
else{
for(int i = 1; i <= m; i++) ans[i][m] = ++tot;
for(int i = m-1; i >= 1; i--) ans[m][i] = ++tot;
if(m == 4) swap(ans[m][1], ans[m][2]);
}
solve(m - 1, k ^ 1);
}
int main(){
read(n);
if(n == 1 || n == 2) return puts("-1"), 0;
solve(n, 0);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
printf("%d ", ans[i][j]);
puts("");
}
return 0;
}
|
F. Kate and imperfection
Solution
【参考博客】首先把所有质数丢进集合，然后考虑加入合数，先加入与当前集合内的数的最大公因数为 $2$ 的所有合数，再加入最大公因数为 $3$ 的所有合数……于是每加入一个合数，答案就是其最大因数。处理出所有数的最大因数（质数为 $1$），排序后输出即可。
Code
>folded1
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>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 500005;
int n, ans[N];
int main(){
read(n);
for(int k = 2; k <= n; k++){
if(!ans[k]) ans[k] = 1;
for(int j = 2; k * j <= n; j++)
ans[k*j] = k;
}
sort(ans+2, ans+n+1);
for(int i = 2; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}
|