补题链接
A：Battle of Balls
把左右边界也看成点，如果球不能在两个点之间过去，就在点之间拉上一条警戒线，当警戒线把顶层和底层分割开来就说明球不可能到达顶层（PS：注意精度
#include<bits/stdc++.h>using namespace std;const int maxn = 1e3 + 50;int fa[maxn];double eps = 1e-8;int fnd(int x){if(x == fa[x]) return x;return fa[x] = fnd(fa[x]);}void link(int x, int y){int rx = fnd(x);int ry = fnd(y);if(rx != ry) fa[rx] = ry;}double x[maxn],y[maxn];double r;double dis(int i, int j){double d = (x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]);d = sqrt(d);return d;}int main(){int T;cin>>T;while(T--){int n;scanf("%d%lf", &n, &r);r *= 2;for(int i = 0; i <= n+1; ++i) fa[i] = i;for(int i = 1; i <= n; ++i) {scanf("%lf%lf",&x[i],&y[i]);if(x[i] - r < eps) link(0, i);if(x[i] + r - 100.0 > -eps) link(i, n+1);}for(int i = 1; i <= n; ++i){for(int j = i+1; j <= n; ++j){if(dis(i, j) - r < eps) link(i, j);}}if(fnd(0) == fnd(n+1)) printf("No\n");else printf("Yes\n");}}
B： Icebound and Sequence
另ai = q^i, Sn = a1 + a2 + … + an, 则有Sn = Sn-1 + qan-1, an = qan-1, 上矩阵快速幂。
#include<bits/stdc++.h>#define ll long longusing namespace std;ll n,q,mod;struct mt{ll a[2][2];mt(){memset(a,0,sizeof a);}mt(mt& x){for(int i = 0;i < 2;++i) for(int j = 0;j < 2;++j) a[i][j] = x.a[i][j];}mt operator * (mt& x){mt ans;for(int i = 0;i < 2;++i){for(int k = 0;k < 2;++k){for(int j = 0;j < 2;++j){ans.a[i][j] = (ans.a[i][j] + (ll)a[i][k] * x.a[k][j]%mod)%mod;}}}return ans;}};mt qm(mt A,int b){mt res;for(int i = 0;i < 2;++i) for(int j = 0;j < 2;++j) res.a[i][j] = (i == j);while(b){if(b&1) res = res*A;A = A*A;b>>=1;}return res;}ll sol(ll n){mt A;A.a[0][0] = 1;A.a[0][1] = A.a[1][1] = q;A = qm(A,n);ll ans = (A.a[0][1])%mod;ans = (ans + mod)%mod;return ans;}int main(){int T;cin>>T;while(T--){scanf("%lld%lld%lld",&q,&n,&mod);printf("%lld\n",sol(n));}}
C 分治
对于一个没被占领的[1, n]，占领i之后变成了两个独立的子问题 [1, i-1] 和 [i+1, r],区间dp即可。
#include<bits/stdc++.h>#define ll long longusing namespace std;const int maxn = 150;ll dp[maxn][maxn];ll c[maxn];int n;ll dfs(int l,int r){if(dp[l][r] != -1) return dp[l][r];if(l >= r) return 0;ll ans = c[l]*(r-l) + dfs(l+1, r);for(int i = l+1; i <= r; ++i){ans = min(c[i]*(r-l) + dfs(l,i-1) + dfs(i+1,r), ans);}dp[l][r] = ans;return ans;}int main(){int T;cin>>T;while(T--){memset(dp, -1, sizeof dp);scanf("%d",&n);for(int i = 1; i <= n; ++i){scanf("%d",&c[i]);}cout<<dfs(1,n)<<endl;}}
D 榜单
确认过眼神，是不想写的大模拟（写了也写不出来
E Paper Plane Fly Away
问题抽象成一个匹配好的二分图，求每条边和多少条边相交。考虑第i个男孩和第j个女孩配对，那么对于i左边的男孩中，目标女孩的编号大于j的会和它相交，i右边的男孩中目标女孩编号小于j会和它相交。从左到右，从右到左分别树状数组存一下出现过的目标女孩编号就可以算出上述两个东西。
#include<bits/stdc++.h>#define lowbit(x) (x&-x)using namespace std;const int maxn = 1e5 + 50;int a[maxn];void add(int i, int x){while(i < maxn) a[i] += x, i += lowbit(i);}int sum(int i){int res = 0;while(i) res += a[i], i -= lowbit(i);return res;}int to[maxn];int id[maxn];int ans[maxn];int main(){int n;cin>>n;for(int i = 1; i <= n ; ++i){int c;scanf("%d%d", &c, &to[i]);c -= n;id[c] = i;to[i] -= n;}for(int i = 1; i <= n; ++i) to[i] = id[to[i]];for(int i = 1; i <= n; ++i){add(to[i], 1);ans[i] += sum(n+1) - sum(to[i]);}memset(a, 0, sizeof a);for(int i = n; i > 0; --i){ans[i] += sum(to[i]);add(to[i], 1);}for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);}
F Take Apples
如果m <= s 或者m <= n，那么Alice都可以把局面变成只剩下两个苹果数相等的堆，必赢。
当n比m大
1.如果m是(s+1)的倍数，那么没有另外两个n的情况下Alice必输。而有n的情况下，如果n < s+1，那么Alice必输，因为Alice无法改变必输局面，而n > s+1,Alice 就可以从三堆中各拿走k*(s+1)的苹果，使得局面变成n < s+1且 m%(s+1)的必输情况，从而让Bob输掉。
2.如果m不是s+1的倍数，那Alice可以从三堆各拿走拿走m % （s+1) + k*(s+1)的苹果使得局面变成m%(s+1) == 0 && n < s+1的必败态让Bob输掉。
所以Bob获胜的情况只有 ：(m%(s+1)==0 && n <= s)
比赛的时候因为看错读入顺序导致WA到自闭……（赛场没有一个人过是不是看错题的不止我一个
#include<bits/stdc++.h>#define ll long longusing namespace std;int main(){ll n,m,s;while(cin>>s>>m>>n){if(m <= n || m <= s) printf("Alice\n");//开场去掉m else{//m > n if(m%(s+1) == 0){if(n >= s+1){printf("Alice\n");}else printf("Bob\n");continue;} else{printf("Alice\n");continue;}}}}
G 水题
H 水题
I Twinkle
不会写……
J 舔狗
贪心，每次优先给入度小的点分配对象。
#include<bits/stdc++.h>using namespace std;const int maxn = 1e6 + 50;int to[maxn];int du[maxn];int vis[maxn];struct node{int id, d;node(){}node(int a, int b) :id(a), d(b){}bool operator < (const node& x)const{return d > x.d;} };priority_queue<node> q;int main(){int n;scanf("%d",&n);for(int i = 1; i <= n; ++i) scanf("%d", &to[i]), du[to[i]]++;for(int i = 1; i <= n; ++i) {if(i != to[i]) q.push(node(i, du[i]));}int ans = n;while(q.size()){node t = q.top(); q.pop();int u = t.id;int v = to[u];if(vis[u] || vis[v]) continue;ans -= 2; vis[u] = vis[v] = 1; du[to[v]]--;q.push(node(to[v], du[to[v]]));}cout<<ans<<endl;}
K 河北美食
按照题意模拟
L smart robot
从1~100000暴力搜索，因为数据随机所以很快就找到了。
#include<bits/stdc++.h>#define ll long longusing namespace std;int n;int mp[51][51];inline int pro(int i,int j){return i*n + j;}vector<int> id[11];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool ok(int i, int j){if(i < 0 || i >= n || j < 0 || j >= n) return false;return true;}int a[10];bool dfs(int x, int y, int pos){if(pos < 0) return true;if(mp[x][y] != a[pos]) return false;for(int i = 0; i < 4; ++i){int xx = x + dx[i];int yy = y + dy[i];if(ok(xx, yy) && dfs(xx, yy, pos-1)) return true;}return false;}int main(){cin>>n;for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){scanf("%d",&mp[i][j]);//dp[pro(i,j)][mp[i][j]] = 1;id[mp[i][j]].push_back(pro(i,j));}}for(int i = 0; i < 10; ++i){if(!id[i].size()){cout<<i<<endl;return 0;}}int ans = 1000000;for(int i = 10; i < 1000000; ++i){int ok = 0;int t = i;int cnt = 0;while(t >= 10) a[cnt++] = t%10, t/=10;a[cnt++] = t;for(int j = 0; j < id[t].size(); ++j){int x = id[t][j]/n;int y = id[t][j]%n;if(dfs(x, y,cnt-1)){ok = 1; break;}}if(!ok){ans = i; break;}}printf("%d\n",ans);}
