A：水题
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, int> pii; const int N = 1e6 + 5; const int M = 2000 + 5; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO { inline LL read() { LL x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } } using namespace FASTIO; int main() { int n;n = read(); string s;cin >> s; for(int i = 1;i <= n;++i) { int x = s[i - 1] - 'a'; int len = i % 26; if(i & 1) { int ma = x + len; if(ma >= 26) { ma -= 26; } printf("%c",ma + 'a'); } else { int ma = x - len; if(ma < 0) { ma += 26; } printf("%c",ma + 'a'); } } //system("pause"); return 0; }
B：
我们从后向前看，如果当前是x开头，那么后面的下一个x开头的答案都可以用当前x开头来替换。
所以我们每个位置都继承当前以x开头的答案有多少。
那么对于一段x ~ x的区间，我们只需要找到里面比x多的数的答案就是前一个x比后一个x可以多的。
一开始开了longlong爆内存了，int就够了。
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, int> pii; const int N = 1e6 + 5; const int M = 2000 + 5; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO { inline LL read() { LL x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } } using namespace FASTIO; int sum[N][37]; int pos[40]; int cal(char c) { if(c >= '0' && c <= '9') return c - '0'; else { return c - 'A' + 10; } } int main() { string s;cin >> s; int n = s.size(); for(int i = n;i >= 1;--i) { int x = cal(s[i - 1]); sum[i][36] = pos[x]; pos[x] = i; } int x = cal(s[n - 1]); sum[n][x] = 1; for(int i = n - 1;i >= 1;--i) { for(int j = 0;j <= 35;++j) sum[i][j] = sum[i + 1][j]; int x = cal(s[i - 1]); if(sum[i][36] == 0) sum[i][x]++; for(int j = x + 1;j <= 35;++j) { sum[i][x] += sum[i][j] - sum[sum[i][36]][j]; } // for(int j = 0;j <= 35;++j) printf("sum[%d][%d] is %lld ",i,j,sum[i][j]); } LL ans = 0; for(int i = 0;i <= 35;++i) ans += sum[1][i]; printf("%lld ",ans); //system("pause"); return 0; }
C：
其实这题我感觉不难。
我们按字母来存位置，dfs来找大于当前位置的下一个位置。
只需要记住可以替换的这一原则，那么我们每次找后面的最靠近我们的肯定是最优的。
而已串最长也就36，所以dfs的复杂度其实不高。
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, int> pii; const int N = 1e6 + 5; const int M = 2000 + 5; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO { inline LL read() { LL x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } } using namespace FASTIO; vector<int> vec[40]; int cal(char c) { if(c >= '0' && c <= '9') return c - '0'; else { return c - 'A' + 10; } } string cha(int x) { string t = ""; if(x >= 0 && x <= 9) t += (x + '0'); else t += ('A' + x - 10); return t; } void dfs(int x,int pos,string s) { cout << s << " "; for(int i = x + 1;i <= 35;++i) { if(vec[i].size() != 0) { int pt = lower_bound(vec[i].begin(),vec[i].end(),pos) - vec[i].begin(); //printf("pos is %d i is %d pt is %d ",pos,i,pt); if(pt >= vec[i].size()) continue; dfs(i,vec[i][pt],s + cha(i)); } } } int main() { string s;cin >> s; int n = s.size(); for(int i = 1;i <= n;++i) { int x = cal(s[i - 1]); vec[x].push_back(i); } for(int i = 0;i <= 35;++i) { if(vec[i].size() != 0) { int pos = vec[i][0]; dfs(i,pos,cha(i)); } } // system("pause"); return 0; } /* AA0201B */
D：
这题一开始过于纠结bfs了。。
首先我们二分极差，然后枚举下限，dfs判断即可。
这里一开始一直觉得应该回溯dfs判断，所以觉得会超时。
其实当我们确定上下限的时候，对于x,y位置如果能到，那么我们就不关心里面的值是多少，只能说明存在一条路到x,y里面的值都在界限内。
所以如果到过一次就满足了，不需要回溯。
注意这里如果先枚举下限然后再二分极差，复杂度会高很多，因为不必要的多了。
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, int> pii; const int N = 1e5 + 5; const int M = 2000 + 5; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO { inline LL read() { LL x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } } using namespace FASTIO; int n,a[105][105],b[4][2] = {1,0,-1,0,0,1,0,-1}; int ans = INF,f = 0; bool vis[105][105]; void dfs(int x,int y,int low,int up) { if(f) return ; if(x == n && y == n) { f = 1; return ; } for(int i = 0;i < 4;++i) { int px = x + b[i][0]; int py = y + b[i][1]; if(px >= 1 && px <= n && py >= 1 && py <= n) { if(!vis[px][py] && a[px][py] >= low && a[px][py] <= up) { vis[px][py] = 1; dfs(px,py,low,up); } } } } int main() { n = read(); for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) a[i][j] = read(); int L = 0,r = 3000; while(L <= r) { int mid = (L + r) >> 1; f = 0; for(int i = 0;i <= 3000;++i) { int low = i,up = i + mid; if(a[1][1] >= low && a[1][1] <= up) { memset(vis,0,sizeof(vis)); vis[1][1] = 1; dfs(1,1,low,up); } if(f) break; } if(f) ans = mid,r = mid - 1; else L = mid + 1; } printf("%d ",ans); //system("pause"); return 0; }