A.连续1的个数，0用来分割，注意连续的0。
#include<bits/stdc++.h> using namespace std; int n; string s; int main() { ios::sync_with_stdio(0); cin >> n >> s; int now = 0,flag = 0; for(int i = 0;i < n;i++) { if(s[i] == '1') now++,flag = 0; else { cout << now; now = 0; flag = 1; } } if(now || flag) cout << now; cout << endl; return 0; }
B.暴力每个点放X，判断即可。
#include<bits/stdc++.h> using namespace std; string s[15]; bool ok() { for(int i = 1;i <= 10;i++) { for(int j = 1;j <= 10;j++) { if(i <= 6) { int flag = 1; for(int ii = i;ii < i+5;ii++) { if(s[ii][j] != 'X') flag = 0; } if(flag) return 1; } if(j <= 6) { int flag = 1; for(int jj = j;jj < j+5;jj++) { if(s[i][jj] != 'X') flag = 0; } if(flag) return 1; } if(i <= 6 && j <= 6) { int flag = 1; for(int ii = i,jj = j;ii < i+5;ii++,jj++) { if(s[ii][jj] != 'X') flag = 0; } if(flag) return 1; } if(i >= 5 && j <= 6) { int flag = 1; for(int ii = i,jj = j;ii > i-5;ii--,jj++) { if(s[ii][jj] != 'X') flag = 0; } if(flag) return 1; } } } return 0; } int main() { ios::sync_with_stdio(0); for(int i = 1;i <= 10;i++) { cin >> s[i]; s[i] = ' '+s[i]; } for(int i = 1;i <= 10;i++) { for(int j = 1;j <= 10;j++) { if(s[i][j] != '.') continue; s[i][j] = 'X'; if(ok()) { cout << "YES" << endl; return 0; } s[i][j] = '.'; } } cout << "NO" << endl; return 0; }
C.排序后模拟。
#include<bits/stdc++.h> using namespace std; int n,k,a[1005]; int main() { ios::sync_with_stdio(0); cin >> n >> k; for(int i = 1;i <= n;i++) cin >> a[i]; sort(a+1,a+1+n); int ans = 0; for(int i = 1;i <= n;i++) { while(k*2 < a[i]) { k *= 2; ans++; } k = max(k,a[i]); } cout << ans << endl; return 0; }
D.模拟，给字母少的先分配。
#include<bits/stdc++.h> using namespace std; string s1,s2; map<char,int> mp; int main() { ios::sync_with_stdio(0); cin >> s1 >> s2; for(int i = 0;i < s1.length();i++) mp[s1[i]]++; int now = 0; for(int i = 0;i < s1.length();i++) { if(s1[i] != '?') continue; now = (now+1)%s2.length(); if(mp[s2[now]]) { mp[s2[now]]--; i--; } else s1[i] = s2[now]; } cout << s1 << endl; return 0; }
E.优先队列逆向拓扑排序。
#include<bits/stdc++.h> using namespace std; int n,m,in[200005] = {0},ans[200005]; vector<int> v[200005]; int main() { ios::sync_with_stdio(0); cin >> n >> m; while(m--) { int x,y; cin >> x >> y; v[y].push_back(x); in[x]++; } priority_queue<int> q; for(int i = 1;i <= n;i++) { if(!in[i]) q.push(i); } int cnt = n; while(!q.empty()) { int now = q.top(); q.pop(); ans[now] = cnt--; for(int i = 0;i < v[now].size();i++) { int t = v[now][i]; if(--in[t] == 0) q.push(t); } } for(int i = 1;i <= n;i++) cout << ans[i] << " "; cout << endl; return 0; }
F.预处理最长公共前缀，dp枚举最小串。
#include<bits/stdc++.h> using namespace std; string s; int lcp[8005][8005] = {0},dp[8005],cnt[8005]; int main() { ios::sync_with_stdio(0); cin >> s; int n = s.length(); memset(dp,0x3f,sizeof(dp)); for(int i = 1;i <= 9;i++) cnt[i] = 1; for(int i = 10;i <= 99;i++) cnt[i] = 2; for(int i = 100;i <= 999;i++) cnt[i] = 3; for(int i = 1000;i <= 8000;i++) cnt[i] = 4; for(int i = n-1;i >= 0;i--) { for(int j = n-1;j >= i;j--) { if(s[i] == s[j]) lcp[i][j] = lcp[i+1][j+1]+1; else lcp[i][j] = 0; } } dp[0] = 0; for(int i = 0;i < n;i++) { for(int j = 1;i+j <= n;j++) { for(int k = i+j,t = 1;k <= n;k += j,t++) { if(lcp[i][k-j] < j) break; dp[k] = min(dp[k],dp[i]+j+cnt[t]); } } } cout << dp[n] << endl; return 0; }
G.记录一个最小的点即可。
#include<bits/stdc++.h> using namespace std; int n,q,ans[1000005]; vector<int> v[1000005]; int dfs(int now,int pre) { for(int i = 0;i < v[now].size();i++) { int t = v[now][i]; if(t == pre) continue; ans[t] = min(t,ans[now]); dfs(t,now); } } int main() { ios::sync_with_stdio(0); cin >> n >> q; int x,y; for(int i = 1;i < n;i++) { cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } int lastt = 0; cin >> x >> y; y = (lastt+y)%n+1; ans[y] = y; dfs(y,-1); int minn = y; while(--q) { int x,y; cin >> x >> y; y = (y+lastt)%n+1; if(x == 1) minn = min(minn,ans[y]); else { lastt = min(ans[y],minn); cout << lastt << endl; } } return 0; }