A.扫一遍。
#include<bits/stdc++.h> using namespace std; int n; string s; int main() { cin >> n; getchar(); getline(cin,s); int ans = 0,maxx = 0; for(int i = 0;i < n;i++) { if(s[i] == ' ') maxx = 0; else { if(s[i] >= 'A' && s[i] <= 'Z') maxx++; ans = max(ans,maxx); } } cout << ans << endl; return 0; }
B.暴力判断两种情况。
#include<bits/stdc++.h> using namespace std; int n,m; string s[105],ss[105]; int main() { cin >> n >> m; for(int i = 1;i <= n;i++) { cin >> s[i]; s[i] = ' '+s[i]; } int flag = 0; if(n%3 == 0) { int t1 = n/3+1,t2 = n/3*2+1; char a = s[1][1],b = s[t1][1],c = s[t2][1]; if(a != b && b != c && a != c) { int ok = 1; for(int i = 1;i < t1;i++) { for(int j = 1;j <= m;j++) { if(s[i][j] != a) ok = 0; } } for(int i = t1;i < t2;i++) { for(int j = 1;j <= m;j++) { if(s[i][j] != b) ok = 0; } } for(int i = t2;i <= n;i++) { for(int j = 1;j <= m;j++) { if(s[i][j] != c) ok = 0; } } if(ok) flag = 1; } } if(m%3 == 0) { int t1 = m/3+1,t2 = m/3*2+1; char a = s[1][1],b = s[1][t1],c = s[1][t2]; if(a != b && b != c && a != c) { int ok = 1; for(int i = 1;i < t1;i++) { for(int j = 1;j <= n;j++) { if(s[j][i] != a) ok = 0; } } for(int i = t1;i < t2;i++) { for(int j = 1;j <= n;j++) { if(s[j][i] != b) ok = 0; } } for(int i = t2;i <= m;i++) { for(int j = 1;j <= n;j++) { if(s[j][i] != c) ok = 0; } } if(ok) flag = 1; } } if(flag) cout << "YES" << endl; else cout << "NO" << endl; return 0; }
C.暴力取两辆，判断是否可行。
#include<bits/stdc++.h> using namespace std; int n,a,b,x[105],y[105]; bool ok(int i,int j) { if(x[i]+y[j] <= a && max(y[i],x[j]) <= b) return 1; if(x[i]+y[j] <= b && max(y[i],x[j]) <= a) return 1; if(x[i]+x[j] <= a && max(y[i],y[j]) <= b) return 1; if(x[i]+x[j] <= b && max(y[i],y[j]) <= a) return 1; if(y[i]+y[j] <= b && max(x[i],x[j]) <= a) return 1; if(y[i]+y[j] <= a && max(x[i],x[j]) <= b) return 1; if(y[i]+x[j] <= b && max(x[i],y[j]) <= a) return 1; if(y[i]+x[j] <= a && max(x[i],y[j]) <= b) return 1; return 0; } int main() { ios::sync_with_stdio(0); cin >> n >> a >> b; for(int i = 1;i <= n;i++) cin >> x[i] >> y[i]; int ans = 0; for(int i = 1;i <= n;i++) { for(int j = i+1;j <= n;j++) { if(ok(i,j)) ans = max(ans,x[i]*y[i]+x[j]*y[j]); } } cout << ans << endl; return 0; }
D.dp。
#include<bits/stdc++.h> using namespace std; int n,k,cnt1[205] = {0},cnt2[205] = {0},dp[205][6005]; long long a[205]; int main() { ios::sync_with_stdio(0); cin >> n >> k; for(int i = 1;i <= n;i++) cin >> a[i]; for(int i = 1;i <= n;i++) { while(a[i]%2 == 0) { a[i] /= 2; cnt2[i]++; } while(a[i]%5 == 0) { a[i] /= 5; cnt1[i]++; } } memset(dp,-1,sizeof(dp)); dp[0][0] = 0; for(int i = 1;i <= n;i++) { for(int j = k;j >= 1;j--) { for(int t = 6000;t >= cnt1[i];t--) { if(dp[j-1][t-cnt1[i]] != -1) dp[j][t] = max(dp[j][t],dp[j-1][t-cnt1[i]]+cnt2[i]); } } } int ans = 0; for(int i = 0;i <= 6000;i++) ans = max(ans,min(i,dp[k][i])); cout << ans << endl; return 0; }
E.有很多次操作，只会把b减一，我们对于每一次gcd != 1之前，对a的每个因子取模统计 gcd == 1的次数，统一减。另外，已经被b约去的因子，可以在之后的步骤不考虑。
#include<bits/stdc++.h> using namespace std; long long a,b; int main() { ios::sync_with_stdio(0); cin >> a >> b; long long t = __gcd(a,b); a /= t; b /= t; vector<long long> v; for(long long i = 2;i*i <= a;i++) { while(a%i == 0) { a /= i; v.push_back(i); } } if(a > 1) v.push_back(a); long long ans = 0; while(b) { long long t = b; for(auto it = v.begin();it != v.end();it++) t = min(t,b%(*it)); ans += t; b -= t; vector<long long> vv; for(auto it = v.begin();it != v.end();it++) { long long t = *it; if(b%t == 0) b /= t; else vv.push_back(t); } v = vv; } cout << ans << endl; return 0; }