A 模拟+dfs暴搜
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 4; int vis[MAXN][MAXN][MAXN]; int xi[] = {1, 0, 0, 0, 0, -1}; int yi[] = {0, 1, 0, 0, -1, 0}; int zi[] = {0, 0, 1, -1, 0, 0}; string s; int dfs(int x, int y, int z, int dir, int cnt){ if(x > 3||x <= 0||y > 3||y <= 0||z > 3||z <= 0) return 0; else if(vis[x][y][z]) return 0; vis[x][y][z] = 1; if(cnt == 26) return 1; else if(s[cnt] == 'E'){ if(dfs(x+1, y, z, 0, cnt+1)) return 1; }else if(s[cnt] == 'I'){ if(dfs(x+xi[dir], y+yi[dir], z+zi[dir], dir, cnt+1)) return 1; }else { for(int i = 0; i < 6; i++){ if(i != dir) if(dfs(x+xi[i], y+yi[i], z+zi[i], i, cnt+1)) return 1; } } vis[x][y][z] = 0; return 0; } int main() { cin >> s; for(int i = 1; i <= 3; i++){ for(int j = 1; j <= 3; j++){ for(int k = 1; k <= 3; k++){ if(dfs(i, j, k, 0, 0)) return 0*printf("YES "); } } } printf("NO "); return 0; }
B 分别统计两个树的叶子节点奇偶的个数，如果存在A奇=B偶，或者A奇=B奇相等则为2，否则为3（代码略丑）
#include <bits/stdc++.h> using namespace std; typedef long long int LL; const int MAXN = 100005; vector<int>B[MAXN], Y[MAXN]; int boot1, boot2; int deg1[MAXN], deg2[MAXN]; int cnt1[2], cnt2[2]; vector<int>deg11, deg12, deg21, deg22; void Bdfs(int u, int fa, int ans) { if(deg1[u] == 1) { if(ans) deg11.push_back(u); else deg12.push_back(u); return; } for(auto v: B[u]) { if(v == fa) continue; Bdfs(v, u, 1^ans); } } void Ydfs(int u, int fa, int ans) { if(deg2[u] == 1) { if(ans) deg21.push_back(u); else deg22.push_back(u); return; } for(auto v: Y[u]) { if(v == fa) continue; Ydfs(v, u, 1^ans); } } int main() { int n, m, u, v; memset(deg1, 0, sizeof(deg1)); memset(deg2, 0, sizeof(deg2)); memset(cnt1, 0, sizeof(cnt1)); memset(cnt2, 0, sizeof(cnt2)); scanf("%d", &n); for(int i = 0; i < n-1; i++) { scanf("%d%d", &u, &v); B[v].push_back(u); B[u].push_back(v); deg1[v]++, deg1[u]++; if(!boot1 && deg1[v] > 1) boot1 = v; if(!boot1 && deg1[u] > 1) boot1 = u; } scanf("%d", &m); for(int i = 0; i < m-1; i++) { scanf("%d%d", &v, &u); deg2[v]++, deg2[u]++; Y[v].push_back(u); Y[u].push_back(v); if(!boot2 && deg2[v] > 1) boot2 = v; if(!boot2 && deg2[u] > 1) boot2 = u; } //printf("%d %d ", boot1, boot2); Bdfs(boot1, 0, 1); Ydfs(boot2, 0, 1); // printf("%d %d %d %d ", deg12.size(), deg11.size(), deg22.size(), deg21.size()); if(deg12.size() == deg22.size()) { printf("%d ", 2); for(int i = 0; i < deg12.size(); i++) { printf("%d %d ", deg12[i], deg22[i]); } for(int i = 0; i < deg11.size(); i++) { printf("%d %d ", deg11[i], deg21[i]); } } else if(deg12.size() == deg21.size()) { printf("%d ", 2); for(int i = 0; i < deg12.size(); i++) { printf("%d %d ", deg12[i], deg21[i]); } for(int i = 0; i < deg11.size(); i++) { printf("%d %d ", deg11[i], deg22[i]); } } else { printf("%d ", 3); for(int i = 0; i < deg11.size(); i++) { deg12.push_back(deg11[i]); } for(int i = 0; i < deg21.size();i++) { deg22.push_back(deg21[i]); } for(int i = 0; i < deg12.size(); i++) { printf("%d %d ", deg12[i], deg22[i]); } } return 0; }
C dp+滚动数组
#include <bits/stdc++.h> using namespace std; const int MAXN = 101; int n, m; bool dp[2][MAXN][MAXN*2][MAXN*2]; char s[MAXN][MAXN]; int main() { memset(dp, 0, sizeof(dp)); scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%s", s[i]+1); memset(dp[0], false, sizeof(dp[0])); dp[0][1][0][0] = true; for(int i = 1; i <= n; i++){ memset(dp[i&1], false, sizeof(dp[i&1])); for(int j = 1; j <= m; j++){ for(int k = 0; k <= i+j-2; k++){ for(int l = 0; l+k <= i+j-2; l++){ if(dp[i&1][j-1][k][l] || dp[~i&1][j][k][l]){ if(s[i][j] == '>') dp[i&1][j][k+1][l] = true; else if(s[i][j] == '|') dp[i&1][j][k][l+1] = true; else dp[i&1][j][k][l] = true; } } } } } int ans = 0; for(int k = 0; k <= n+m-1; k++){ for(int l = 0; l+k <= n+m-1; l++){ if(dp[n&1][m][k][l]) ans = max(ans, min(k, min(l, n+m-1-l-k))); } } printf("%d ", ans); return 0; }
D 二分
#include <bits/stdc++.h> using namespace std; typedef long long int LL; LL n, x, y; bool slove(LL time){ LL k = time/x+time/y; if(k >= n) return true; return false; } int main() { cin >> n >> x >> y; LL l = 0, r = 1e18+5; while(l < r){ LL mid = (l+r)>>1; if(slove(mid)) r = mid; else l = mid+1; } cout << l << endl; return 0; }
E 枚举点的个数
#include <bits/stdc++.h> using namespace std; int a[7], vis[7]; int main() { for(int i = 0, x; i < 6; i++){ scanf("%d", &x); a[x]++; } int cnt = 0; for(int i = 0; i <= 6; i++){ if(a[i]) cnt++; } if(cnt == 6 || cnt == 5) printf("%d ", 6); else if(cnt == 4) printf("%d ", 4); else printf("%d ", 3); return 0; }
G概率dp+二分
#include <bits/stdc++.h> using namespace std; int s[100008]; double fail[100008], sum[100008]; bool cmp(const int &a, const int &b) {return a > b;} int main() { int n, Sa; scanf("%d%d", &n, &Sa); for(int i = 1; i <= n; i++) scanf("%d", &s[i]); for(int i = 1; i <= n; i++) scanf("%lf", &fail[i]); for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + fail[i]; double ans = 0; for(int i = 1; i <= n; i++){ int l = upper_bound(s+1, s+i, s[i]+Sa, cmp) - s; int r = lower_bound(s+1, s+i, s[i], cmp) - s; ans += (sum[r-1] - sum[l-1])*(1-fail[i]); } printf("%.9f ", ans); return 0; }
H排序
#include <bits/stdc++.h> using namespace std; typedef long long int LL; int a[100005]; LL sum = 0, ans = 0; int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); sum += a[i]; } sort(a, a+n); for(int i = 0; i < n; i++){ sum -= a[i]; ans += sum; } printf("%lld ", ans); return 0; }