A.Balanced Bitstring
题解:找性质题
注意到如果要使每个长为$k$的子串中$0,1$数量相等,则$a[i]=a[i+k],i \in [1,n-k]$
于是如果有$a[i%k]$互不相等,则无解
这样我们就有了一段长为$k$的字符串
统计它之中$0,1$的个数
如果$>k/2$则无解
否则一定有解
#include <bits/stdc++.h> using namespace std; int n, k, sum1, sum2; string a; int f[300011]; void solve() { scanf("%d%d", &n, &k); cin >> a; memset(f, -1, sizeof(f)); for(int i = 0; i < n; i++) { if(a[i] != '?') { if(f[i%k] == -1) f[i % k] = a[i] - '0'; else if(f[i%k] != (int)(a[i] - '0')) { cout << "NO" << endl; return; } } } sum1 = sum2 = 0; for(int i = 0; i < k; i++) { sum1 += (f[i] == 0); sum2 += (f[i] == 1); } if(sum1 > k/2 || sum2 > k/2) cout << "NO" << endl; else cout << "YES" << endl; } int main() { int T; scanf("%d", &T); while(T--) solve(); return 0; }
B.Tree Tag
题解:我们考虑什么情况下Alice可以获胜
如果$dis_{a,b} \leq da$,则Alice可以一步就追上Bob
如果Alice处在一个能覆盖整棵树的点,即$da*2+1 \geq$树的直径,那么Bob也无处可走了
其它情况下,Alice会一步一步逼近Bob,并一定能把Bob逼近某棵子树
如果当前Alice占据一个点,使Bob无论怎么走都还在Alice的控制范围内,那么Alice必胜
此时条件即为$2da \geq db$
除以上条件外,Bob获胜
#include <bits/stdc++.h> using namespace std; int n, a, b, da, db, dis[100011]; vector <int> e[100011]; void dfs(int w, int fa) { dis[w] = dis[fa] + 1; for(int i = 0; i < (int)e[w].size(); i++) { int ver = e[w][i]; if(ver != fa) dfs(ver, w); } } void solve() { scanf("%d%d%d%d%d", &n, &a, &b, &da, &db); for(int i = 1; i <= n; i++) e[i].clear(); for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); e[u].push_back(v); e[v].push_back(u); } dfs(1, 0); int maxw = 0; for(int i = 1; i <= n; i++) if(dis[maxw] < dis[i]) maxw = i; dfs(maxw, 0); maxw = 0; for(int i = 1; i <= n; i++) if(dis[maxw] < dis[i]) maxw = i; if(dis[maxw] <= da*2+1) { printf("Alice\n"); return; } dfs(a, 0); if(dis[b] <= da+1) { printf("Alice\n"); return; } if(2*da >= db) { printf("Alice\n"); return; } printf("Bob\n"); } int main() { int t; scanf("%d", &t); while(t--) solve(); return 0; }