比赛链接 / 官方题解链接
A. Odd Selection
Solution
直接枚举奇数个数，避免讨论，好写好调。
Code
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
| #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, x;
int main(){
for(read(T); T; T--){
read(n, x);
int cnt = 0;
for(int i = 1; i <= n; i++){
int a; read(a);
if(a & 1) cnt++;
}
bool ok = false;
for(int i = 0; i <= x; i++){
if((i + 2 * (x - i)) % 2 == 0) continue;
if(i <= cnt && x - i <= n - cnt){
ok = true;
break;
}
}
puts(ok ? "Yes" : "No");
}
return 0;
}
|
B. Subsequence Hate
Solution
good string 一定形如 $00\cdots011\cdots1$ 或 $11\cdots100\cdots0$. 枚举分段位置，用前缀和来计算即可。
Code
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
| #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, sum[1005][2];
char s[1005];
int main(){
for(read(T); T; T--){
memset(sum, 0, sizeof sum);
scanf("%s", s+1);
int n = strlen(s+1);
for(int i = 1; i <= n; i++){
sum[i][0] = sum[i-1][0] + (s[i] == '0');
sum[i][1] = sum[i-1][1] + (s[i] == '1');
}
int ans = 1e9;
for(int i = 1; i <= n + 1; i++){
ans = min(ans, sum[i-1][0] + sum[n][1] - sum[i-1][1]);
ans = min(ans, sum[i-1][1] + sum[n][0] - sum[i-1][0]);
}
printf("%d\n", ans);
}
return 0;
}
|
C. Game On Leaves
Solution
如果根是叶子那么先手胜；否则，每个人的最优策略就是不要在根只剩下两个子树的时候选一个根的子节点，所以 $n$ 偶数则先手胜，$n$ 奇数则后手胜。
Code
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
| #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 = 1005;
int T, n, x, d[N];
int main(){
for(read(T); T; T--){
memset(d, 0, sizeof d);
read(n, x);
for(int i = 1; i < n; i++){
int u, v; read(u, v);
d[u]++, d[v]++;
}
if(d[x] <= 1){ puts("Ayush"); continue; }
n -= 3;
puts(n & 1 ? "Ayush" : "Ashish");
}
return 0;
}
|
D. Guess The Maximums
Solution
考虑整个数列中的最大值，除了包含这个数的子集以外（当然也有可能没有包含这个数的子集），其他子集的答案就是这个最大值。所以先把所有数拿出来问一遍得到最大值，接下来我们只需要确定这个最大值在哪个子集里。确定位置就是个二分，$1000$ 个子集最多问 $10$ 次就确定下来了。那对于这个子集，把其他数拿去问得到的最大值就是它的答案。前后各问 $1$ 次，二分最多 $10$ 次，总共不超过 $12$ 次。
a funny picture from Codeforces tutorial:
Code
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
| #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 = 1005;
int T, n, k, c[N];
vi s[N];
inline int ask(int l, int r){
vi a;
for(int i = l; i <= r; i++) for(auto k: s[i]) a.pb(k);
printf("? %d ", (int)a.size());
for(auto k: a) printf("%d ", k); puts(""); fflush(stdout);
int res = 0; read(res); return res;
}
int main(){
for(read(T); T; T--){
read(n, k);
for(int i = 1; i <= k; i++){
s[i].clear(); read(c[i]);
for(int j = 1; j <= c[i]; j++){
int x; read(x); s[i].pb(x);
}
}
int mxall = 0;
printf("? %d ", n);
for(int i = 1; i <= n; i++) printf("%d ", i);
puts(""); fflush(stdout);
read(mxall);
int l = 1, r = k;
while(l < r){
int mid = (l + r) >> 1;
if(ask(l, mid) == mxall) r = mid;
else l = mid + 1;
}
vi a;
vector<bool> b(n+5, false);
for(auto k: s[l]) b[k] = true;
for(int i = 1; i <= n; i++) if(!b[i]) a.pb(i);
printf("? %d ", (int)a.size());
for(auto k: a) printf("%d ", k); puts(""); fflush(stdout);
int ansforl = 0; read(ansforl); if(ansforl == -1) exit(0);
printf("! ");
for(int i = 1; i <= k; i++){
if(i == l) printf("%d ", ansforl);
else printf("%d ", mxall);
}
puts(""); fflush(stdout);
string feedback; cin >> feedback;
if(feedback == "Correct") continue;
else exit(0);
}
return 0;
}
|
E. Tree Shuffling
Solution
显然当前和需求的 $0,1$ 数量不同就无解，否则有解。
如果称当前值和需求值不同为“未匹配点”，反之为“匹配点”，那么观察可以得到一些性质：
- 只有“未匹配点”之间会交换，否则一个“未匹配点”与一个“匹配点”交换之后，“匹配点”变成“未匹配点”，终将与另一个“未匹配点”交换，划不着；
- 在以 $x$ 为根的子树中发生交换的两个点，其最小代价是 $x$ 的所有祖先（包括自己）的代价最小值。
根据上述第二条性质，我们进行预处理，把所有点的代价 $a$ 变成它祖先里面的最小的代价。于是现在从根沿一条路径到叶子，代价单调不增。
那么很容易贪心地知道能在某子树里交换的两个点就一定会在子树里交换，而不会上升到更高层再交换。
所以 $dfs$ 式地递归一次，每次把当前子树内能交换的点全都交换。
Code
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
| #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, cntb, cntc;
LL ans;
struct Node{
LL a;
int b, c;
}t[N];
vi edge[N];
void dfs(int x, int f, LL mncost){
t[x].a = mncost;
for(auto to: edge[x]){
if(to == f) continue;
dfs(to, x, min(mncost, t[to].a));
}
}
int one[N], zero[N];
void solve(int x, int f){
if(t[x].b == 0 && t[x].c == 1) one[x]++;
if(t[x].b == 1 && t[x].c == 0) zero[x]++;
for(auto to: edge[x]){
if(to == f) continue;
solve(to, x);
one[x] += one[to];
zero[x] += zero[to];
}
ans += t[x].a * 2 * min(one[x], zero[x]);
if(one[x] >= zero[x])
one[x] -= zero[x], zero[x] = 0;
else
zero[x] -= one[x], one[x] = 0;
}
int main(){
read(n);
for(int i = 1; i <= n; i++){
read(t[i].a, t[i].b, t[i].c);
cntb += t[i].b, cntc += t[i].c;
}
if(cntb ^ cntc) return puts("-1"), 0;
for(int i = 1; i < n; i++){
int u, v; read(u, v);
edge[u].pb(v), edge[v].pb(u);
}
dfs(1, 0, t[1].a);
solve(1, 0);
printf("%lld\n", ans);
return 0;
}
|
F. Rotating Substrings
Solution
【参考官方题解】重点：这个顺时针旋转操作可以看作把最后一个数挑出来插入到前面某个位置，挑出一个数的代价是 $1$。
如果 $s,t$ 含有字母种类或个数不同，显然无解；否则有解。
设 $dp[i][j]$ 表示使 $s[1\cdots i]$ 与 $t[1\cdots j]$ 匹配的最小代价，这里说的匹配是指用 $s[i+1\cdots n]$ 里面挑出的一些数去往 $s[1\cdots i]$ 里面插，最后插成跟 $t[1\cdots j]$ 一样，所以这里 $i\leq j$。
考虑 $dp[i][j]$ 可以从哪些状态转移过来：
- 如果我们把 $s[i]$ 挑出来在以后用，那么我们需要 $s[1\cdots i-1]$ 和 $t[1\cdots j]$ 匹配，所以可以从 $dp[i-1][j]$ 转移而来且代价加一；
- 如果 $s[i] == t[j]$，那么我们只需要 $s[1\cdots i-1]$ 和 $t[1\cdots j-1]$ 匹配就行了，随后 $s[i]$ 和 $t[j]$ 自然匹配上，所以这种情况下可以从 $dp[i-1][j-1]$ 转移而来；
- 如果 $s[i+1\cdots n]$ 里面有多余的 $t[j]$ 字母可供使用，就可以拿一个来和 $t[j]$ 匹配上，我们只需要关心 $s[1\cdots i]$ 和 $t[1\dots j-1]$ 的匹配，所以当 $s[i+1\cdots n]$ 中 $t[j]$ 的出现次数多于 $t[j+1\cdots n]$ 中的出现次数，就可以从 $dp[i][j-1]$ 转移而来。
边界条件：$dp[0][j]=0$，就是说 $s$ 为空的时候，要去匹配 $t[1\cdots j]$，只需要把挑出来待用的数一个个对应地填上去就行了。
综上，写作记忆化搜索式的 $dp$ 最为方便。
Code
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
| #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 = 2005;
int T, n;
char s[N], t[N];
int cnts[N][30], cntt[N][30];
int dp[N][N];
int DP(int i, int j){
if(i > j) return 0;
if(dp[i][j] != -1) return dp[i][j];
int res = 1e9;
if(i) res = min(res, DP(i-1, j) + 1);
if(i && j && s[i] == t[j])
res = min(res, DP(i-1, j-1));
if(j && cnts[i+1][t[j]-'a'] > cntt[j+1][t[j]-'a'])
res = min(res, DP(i, j-1));
return dp[i][j] = res;
}
int main(){
for(read(T); T; T--){
read(n);
scanf("%s%s", s+1, t+1);
for(int i = 1; i <= n + 1; i++)
for(int j = 0; j < 26; j++)
cnts[i][j] = cntt[i][j] = 0;
for(int i = n; i >= 1; i--){
for(int j = 0; j < 26; j++){
cnts[i][j] = cnts[i+1][j] + (s[i] == j + 'a');
cntt[i][j] = cntt[i+1][j] + (t[i] == j + 'a');
}
}
bool ok = true;
for(int j = 0; j < 26; j++){
if(cnts[1][j] != cntt[1][j]){
ok = false;
break;
}
}
if(!ok){ puts("-1"); continue; }
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
dp[i][j] = i == 0 ? 0 : -1;
printf("%d\n", DP(n, n));
}
return 0;
}
|