比赛链接 / 官方题解链接
A. Sum of Odd Integers
Solution
先判断奇偶性，再判断是否 $n\geq1+3+\cdots(2k-1)=k^2$.
比赛时 $k^2$ 没开 long long WA 了一发……
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
| #include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
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;
long long T, n, k;
int main(){
read(T);
while(T--){
read(n, k);
if((n & 1) ^ (k & 1)) puts("NO");
else{
if(n < k * k) puts("NO");
else puts("YES");
}
}
return 0;
}
|
B. Princesses and Princes
Solution
先按题意模拟，如果有剩余没匹配上的就加上去；否则输出 OPTIMAL.
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
65
| #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
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;
const int N = 100005;
int T, n;
vector<int> v[N];
bool b[N], p[N];
inline void init(){
memset(b, 0, sizeof b);
memset(p, 0, sizeof p);
for(int i = 1; i <= n; i++) v[i].clear();
}
int main(){
read(T);
while(T--){
read(n);
init();
for(int i = 1; i <= n; i++){
int k; read(k);
for(int j = 1; j <= k; j++){
int t; read(t);
v[i].push_back(t);
}
}
int cnt = 0;
for(int i = 1; i <= n; i++){
for(auto k: v[i]){
if(!b[k]){
b[k] = p[i] = true;
cnt++;
break;
}
}
}
if(cnt == n) puts("OPTIMAL");
else{
puts("IMPROVE");
int k = 0;
for(k = 1; k <= n; k++)
if(!b[k])
break;
int t = 0;
for(t = 1; t <= n; t++)
if(!p[t])
break;
printf("%d %d\n", t, k);
}
}
return 0;
}
|
C. Game with Chips
Solution
把所有点堆到 $(1,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
31
| #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
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;
int n, m, k, t;
int main(){
read(n, m, k);
for(int i = 1; i <= k; i++) scanf("%*d%*d", &t, &t);
for(int i = 1; i <= k; i++) scanf("%*d%*d", &t, &t);
if(n == 1 && m == 1) return puts("0"), 0;
printf("%d\n", n * m + n + m - 3);
for(int i = 1; i < m; i++) putchar('L');
for(int i = 1; i < n; i++) putchar('U');
for(int i = 1; i <= n; i++){
for(int j = 1; j < m; j++) putchar((i & 1) ? 'R' : 'L');
if(i < n) putchar('D');
}
return 0;
}
|
D. Infinite Path
Solution
由于 $p[]$ 是一个排列，所以 $p[]$ 事实上构成了多个不交叉的有向环。$p$ 的 $k$ 层迭代其实就是走 $k$ 步能到达的节点。于是乎找出所有环，枚举环长度的因数，拆出小环，判断是否颜色相同，答案取 $\min$ 即可。
复杂度：$O(n\sqrt n)$
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
65
66
67
68
69
70
71
72
73
74
75
76
| #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
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;
const int N = 200005;
int T, n, p[N], c[N], ans = 1e9;
bool b[N];
vector<int> v[N];
inline void getAns(int i, vector<int> a){
for(int k = 0; k < i; k++){
bool ok = true;
for(int j = k; j < a.size(); j += i){
if(c[a[j]] != c[a[k]]){
ok = false;
break;
}
}
if(ok) ans = min(ans, i);
}
}
inline void solve(vector<int> a){
int t = a.size();
for(int i = 1; i * i <= a.size(); i++){
if(a.size() % i) continue;
while(t % i == 0 && i != 1) t /= i;
getAns(i, a);
if(i * i == a.size()) break;
getAns(a.size() / i, a);
}
if(t > 1) getAns(t, a);
}
inline void init(){
ans = 1e9;
memset(b, 0, sizeof b);
for(int i = 1; i <= n; i++) v[i].clear();
}
int main(){
read(T);
while(T--){
read(n);
init();
for(int i = 1; i <= n; i++){
read(p[i]);
v[i].emplace_back(p[i]);
}
for(int i = 1; i <= n; i++) read(c[i]);
for(int i = 1; i <= n; i++){
if(b[i]) continue;
vector<int> a;
int now = i;
while(!b[now]){
b[now] = true;
a.emplace_back(now);
now = p[now];
}
solve(a);
}
printf("%d\n", ans);
}
return 0;
}
|
E. Count the Blocks
Solution
推一波式子。
考虑某个长度为 $i$ 的块，有多少种序列能包含它。首先，若它被放在序列中间，则与它两端相邻的数字有 $9$ 种填法，剩余 $(n-i-2)$ 个数字有 $10$ 种填法，再乘上有 $10$ 种数字填充这个块，且这个块能被放到 $(n-i-1)$ 种中间位置上去，所以位于序列中间的长度为 $i$ 的块共有 $9^2\times10^{n-i-2}\times10\times(n-i-1)$ 种；若它被放到两端，则与它另一端相邻的数字有 $9$ 种填法，剩余 $(n-i-1)$ 个数字有 $10$ 种填法，再乘上有 $10$ 种数字填充这个块，且这个块能被放到 $2$ 种位置上去，所以位于两端的长度为 $i$ 的块共有 $9\times10^{n-i-1}\times10\times2$ 种填法；综上，长度为 $i$ 的块被
种序列所包含，答案即此。当然这是 $n-i-2\geq0$ 的时候，其他情况讨论更少、不再赘述。
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
| #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
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;
const int N = 200005;
const LL MOD = 998244353;
int n;
LL power[N] = {1};
int main(){
read(n);
for(int i = 1; i <= n; i++) power[i] = power[i-1] * 10 % MOD;
for(int i = 1; i <= n; i++){
if(n - i - 2 >= 0)
printf("%lld ", 9 * power[n - i - 1] % MOD * (9 * n - 9 * i + 11) % MOD);
else if(n - i - 1 >= 0)
printf("%lld ", 18 * power[n - i] % MOD);
else puts("10");
}
return 0;
}
|
F. AND Segments
Solution
参考博客
每一位可以单独考虑。题目给定的条件可以转化为：区间必须全为 $1$，或区间至少有 $1$ 个 $0$.
设 $dp[i]$ 表示最后一个 $0$ 填在第 $i$ 位时的方案数，则依次循环考虑每个数，若该位置可以填 $0$，则 $dp[i]$ 更新为 $\sum\limits_{j=f[i]}^{i-1}dp[j]$，其中 $f[i]$ 表示最大的整个区间都在第 $i$ 位之前且值为 $0$ 的区间左端点。因为如果 $j<f[i]$，说明 $j+1\sim i$ 这一段全填 $1$，与题目条件违背。
实现上，判断一个点是否必须填 $1$ 可采用差分数组+前缀和；而 $dp$ 转移方程中的求和可以用一个变量 $sum$ 存储——$sum$ 随时加上新的 $dp[i]$，减去不符合条件（ $j<f[i]$ ）的 $dp[j]$ 。
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
| #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;
const int N = 500005;
const LL MOD = 998244353;
int n, k, m;
LL ans = 1;
struct Node{
int l, r, x;
}a[N];
int main(){
read(n, k, m);
for(int i = 1; i <= m; i++)
read(a[i].l, a[i].r, a[i].x);
for(int b = 0; b < k; b++){
vector<LL> ones(n+5, 0);
vector<int> f(n+5, 0);
vector<LL> dp(n+5, 0);
for(int i = 1; i <= m; i++){
if((a[i].x >> b) & 1)
ones[a[i].l]++, ones[a[i].r+1]--;
else
f[a[i].r] = max(f[a[i].r], a[i].l);
}
dp[0] = 1;
LL sum = 1;
int pre = 0;
for(int i = 1; i <= n; i++){
ones[i] += ones[i-1];
if(!ones[i])
dp[i] = sum % MOD;
(sum += dp[i]) %= MOD;
while(pre < f[i]){
sum -= dp[pre];
((sum %= MOD) += MOD) %= MOD;
pre++;
}
}
(ans *= sum) %= MOD;
}
printf("%lld\n", ans);
return 0;
}
|