A.直接暴力就行了，先把能组合的按线性组合掉，再枚举剩下相邻没用过的。
#include<bits/stdc++.h> using namespace std; string s; int vis[105] = {0}; int main() { ios::sync_with_stdio(false); cin >> s; int ans = 0; for(int i = 1;i < s.length();i++) { if(vis[i-1] || vis[i]) continue; if(s[i-1] == 'V' && s[i] == 'K') { ans++; vis[i-1] = 1; vis[i] = 1; } } for(int i = 1;i < s.length();i++) { if(vis[i-1] || vis[i]) continue; if(s[i-1] == 'V' || s[i] == 'K') { ans++; break; } } cout << ans << endl; return 0; }
B.若存在，直接令y等于z就可以了。
#include<bits/stdc++.h> using namespace std; string s1,s2; int main() { ios::sync_with_stdio(false); cin >> s1 >> s2; string s3; int flag = 0; for(int i = 0;i < s1.length();i++) { if(s2[i] <= s1[i]) s3 = s3+s2[i]; else { flag = 1; } } if(flag) cout << -1<< endl; else cout << s3 << endl; return 0; }
C.二分，先判断是否能永久运行，若不行，二分答案。
#include<bits/stdc++.h> using namespace std; int n,p,a[100005],b[100005]; bool ok(double x) { double sum = 0; for(int i = 1;i <= n;i++) { if(a[i]*x > b[i]) sum += a[i]*x-b[i]; } if(sum < p*x) return 1; return 0; } int main() { ios::sync_with_stdio(false); cin >> n >> p; long long sum = 0; for(int i = 1;i <= n;i++) { cin >> a[i] >> b[i]; sum += a[i]; } if(sum <= p) { cout << -1 << endl; return 0; } double l = 0,r = 1e18; while(abs(l-r) > 1e-5) { double mid = (l+r)/2; if(ok(mid)) l = mid; else r = mid; } cout << l << endl; return 0; }
D.枚举每一组相邻3个顶点，取中间点到两边点构成直线的距离的最小值，再除以2。
#include<bits/stdc++.h> using namespace std; int n; double a[1005],b[1005]; double f(double x1,double y1,double x2,double y2,double x3,double y3) { double aa = y2-y1,bb = x1-x2,cc = x2*y1-x1*y2; return abs(aa*x3+bb*y3+cc)/sqrt(aa*aa+bb*bb); } int main() { ios::sync_with_stdio(false); cin >> n; for(int i = 1;i <= n;i++) cin >> a[i] >> b[i]; double ans = 1e18; for(int i = 1;i <= n;i++) { int j = i+1,k = j+1; if(j > n) j -= n; if(k > n) k -= n; ans = min(ans,f(a[i],b[i],a[j],b[j],a[k],b[k])); ans = min(ans,f(a[i],b[i],a[k],b[k],a[j],b[j])); ans = min(ans,f(a[j],b[j],a[k],b[k],a[i],b[i])); } cout << fixed << setprecision(8) << ans/2 << endl; return 0; }
E.令p[i]为第i次出现的前i个元素积(%m)，问题是如何构造最长的p序列。
设元素i,j，则①i可以向j转移的条件是gcd(m, i)丨gcd(m, j)
②i,j可以互相转移的条件是gcd(m, i)=gcd(m, j)
于是，我们把每一个gcd看成点，同一个gcd间的元素可以相互转化，然后构成图，dfs找最长路线。
有了p序列，pi-1*x%p==pi(P0=1)，求解每一个x输出即可，这个可以用扩展欧几里德解决。
0这个点可以放到最后特殊处理。
#include<bits/stdc++.h> #define LL long long using namespace std; int n,m,cantbe[200005] = {0},vis[200005] = {0},dp[200005],nextt[200005]; vector<int> v[200005]; LL ex_gcd(LL a,LL b,LL &x,LL &y) { int d = a; if(!b) { x = 1; y = 0; } else { d = ex_gcd(b,a%b,y,x); y -= (a/b)*x; } return d; } LL f(LL a,LL b,LL n) { LL d,x,y; d = ex_gcd(a,n,x,y); x = (x%n+n)%n; return (x*b/d)%n; } int dfs(int now) { if(dp[now] > 0) return dp[now]; dp[now] = v[now].size(); for(int i = now*2;i < m;i += now) { if(v[i].size() == 0) continue; int t = dfs(i); if(dp[now] < v[now].size()+t) { dp[now] = t+v[now].size(); nextt[now] = i; } } return dp[now]; } int main() { ios::sync_with_stdio(false); cin >> n >> m; for(int i = 1;i <= n;i++) { int x; cin >> x; cantbe[x] = 1; } for(int i = 1;i < m;i++) { if(!cantbe[i]) v[__gcd(i,m)].push_back(i); } memset(dp,0,sizeof(dp)); memset(nextt,-1,sizeof(nextt)); dfs(1); int now = max_element(dp,dp+m)-dp; cout << dp[now]+(cantbe[0] == 0) << endl; int last = 1; while(now != -1) { for(int i = 0;i < v[now].size();i++) { int t = v[now][i]; cout << f(last,t,m) << " "; last = t; } now = nextt[now]; } if(cantbe[0] == 0) cout << 0 << endl; else cout << endl; return 0; }