A：签到
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 1e3 + 5; const double eps = 1e-10; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;LL x = 0;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; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} void solve() { int L,r;L = read(),r = read(); int low = max(L,(r / 2 + 1)); int ans = r % low; printf("%d ",ans); } int main() { int ca;ca = read(); while(ca--) { solve(); } //system("pause"); return 0; }
B：python写的有点慢。
可以发现，如果里面出现了1,4,6,8,9，那么我们可以只留下这个数。
那么对于其他情况，显然只有2,3,5,7四种数出现，如果某个数出现了超过一次，我们就可以留下两个一样的数变成11的倍数。
所以，比较特殊的情况只有2,3,5,7四位数出现，对于这种情况暴力即可。
import math def check(x): m = int(math.sqrt(x)) for i in range(2,m + 1): if x % i == 0: return True return False ca = int(input()) while ca != 0: ca -= 1 k = int(input()) n = input() vis = [0 for i in range(10)] ans = "" pos = -1 for i in range(len(n) - 1,-1,-1): if int(n[i]) % 2 == 0 and int(n[i]) != 2 or int(n[i]) == 9 or int(n[i]) == 1: pos = i break if pos == -1: if len(n) > 9: for i in range(len(n)): x = ord(n[i]) - ord('0') if vis[x] == 1: ans = n[i] break vis[x] = 1 print("2") print(ans + ans) else: f = 0 for i in range(len(n)): if f != 0: break for j in range(i + 1,len(n)): tmp = n[i] + n[j] if check(int(tmp)): f = 1 ans = tmp for i in range(len(n)): if f != 0: break for j in range(i + 1,len(n)): for k in range(j + 1,len(n)): tmp = n[i] + n[j] + n[k] if check(int(tmp)): f = 1 ans = tmp for i in range(len(n)): if f != 0: break for j in range(i + 1,len(n)): for k in range(j + 1,len(n)): for q in range(k + 1,len(n)): tmp = n[i] + n[j] + n[k] + n[q] if check(int(tmp)): f = 1 ans = tmp print(len(ans)) print(ans) else: print("1") print(int(n[pos]))
C：我们对半看。
首先，如果前一半出现了一个0，那么我们就可以构造出两个一样的数，长的那个以0开头。
如果，后一半出现了一个0，那么我们可以构造出一个2倍的数，以0结尾。
如果上面两种情况都不存在，那么说明这个数全部都是1，那么错位构造两个一样的数即可。即1 ~ L,2 ~ L + 1.
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 1e3 + 5; const double eps = 1e-10; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;LL x = 0;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; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} void solve() { int n;scanf("%d",&n); string s;cin >> s; int pos = -1,hf = n / 2; for(int i = 1;i <= n;++i) { if(s[i - 1] == '0') { pos = i; break; } } if(pos == -1) printf("%d %d %d %d ",1,hf,2,hf + 1); else { if(pos <= hf) printf("%d %d %d %d ",pos,n,pos + 1,n); else printf("%d %d %d %d ",1,pos,1,pos - 1); } } int main() { int ca;ca = read(); while(ca--) { solve(); } // system("pause"); return 0; }
D1：已经猜到了应该只有0,1,2三种情况。
从D2可知。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 3e5 + 5; const int M = 1e3 + 5; const double eps = 1e-10; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;LL x = 0;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; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int sum[N]; void solve() { int n,q;n = read(),q = read(); string s;cin >> s; sum[0] = 0; for(int i = 1;i <= n;++i) { sum[i] = sum[i - 1]; if(s[i - 1] == '+' && i % 2 != 0 || s[i - 1] == '-' && i % 2 == 0) sum[i]++; else sum[i]--; } while(q--) { int L,r;L = read(),r = read(); int len = r - L + 1; int ma = sum[r] - sum[L - 1]; if(ma == 0) printf("0 "); else { if(len % 2 == 0) printf("2 "); else printf("1 "); } } } int main() { int ca;ca = read(); while(ca--) { solve(); } // system("pause"); return 0; }
D2：一定要弄明白每次的操作产生的贡献。
可以发现，我们选定一个位置pos,那么[pos + 1,r]的代价就会翻转了。
那么我们就可以有一个构造方法，对于奇数的和 = x,我们删去刚好 = x / 2 + 1的位置，那么后面都翻转，就形成了x , -x的情况。
对于偶数的方案，我们先删去L位置，那么和就是偶数的了，我们就可以对[L + 1,r]进行上诉操作。
如果单纯这样去操作还是很麻烦的。考虑一下等式。sum表示前缀和。
有sum[r] - sum[pos] = sum[pos - 1] - sum[L - 1] 即删去pos，左半边和右半边和一样。
那么移项,sum[pos - 1] + sum[pos] = sum[r] - sum[L - 1]。
所以我们只需要维护一个sum[pos - 1] + sum[pos]，然后去找满足和 = sum[r] - sum[L - 1] 且在区间内的即可。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 3e5 + 5; const int M = 1e3 + 5; const double eps = 1e-10; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;LL x = 0;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; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int sum[N]; void solve() { int n,q;n = read(),q = read(); string s;cin >> s; sum[0] = 0; map<int,set<int> > mp; for(int i = 1;i <= n;++i) { sum[i] = sum[i - 1]; if(s[i - 1] == '+' && i % 2 != 0 || s[i - 1] == '-' && i % 2 == 0) sum[i]++; else sum[i]--; } for(int i = 1;i <= n;++i) { mp[sum[i] + sum[i - 1]].insert(i); } while(q--) { int L,r;L = read(),r = read(); int ma = sum[r] - sum[L - 1]; if(ma == 0) printf("0 "); else { int len = r - L + 1; if(len % 2 != 0) printf("1 %d ",*mp[sum[r] + sum[L - 1]].lower_bound(L)); else printf("2 %d %d ",L,*mp[sum[r] + sum[L]].lower_bound(L + 1)); } } } int main() { int ca;ca = read(); while(ca--) { solve(); } // system("pause"); return 0; } /* 1 1 2 1 2 1 2 2 1 3 1 2 2 2 3 1 3 1 3 2 3 4 1 4 */
E：感觉这题也挺巧妙的。
首先如果选定一个后缀abc，那么他的所有前缀都可以选入，递增排列。
所以考虑dp[i] - 到以i为开头的后缀的最大代价。它本身的长度为n - i + 1//所有子串
考虑一下转移，如果s[以j为开头的后缀字符串] < s[以i为开头的后缀字符串]，那么i就可以从j转移来。
但是可能存在不合法情况：即abc < abcd
但是abcd的前缀a < abc。多试几个可以发现，他们的公共前缀满足 prefix(abcd) < (abc)
所以我们要减去不合法的数量即公共前缀。
所以dp[i] = dp[j] + n - i + 1 - f[i][j] //f[i][j]的公共前缀。
这里有个细节，就是判断两个后缀的大小关系，如果真的去存储字符串再去比较的话，复杂度会爆。
其实只需要比较第一个不同的位置的字符即可，即prefix + 1位置的字符。
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pii; const int N = 5e3 + 5; const int M = 1e3 + 5; const double eps = 1e-10; const LL Mod = 998244353; #define pi acos(-1) #define INF 1e18 #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int f = 1;LL x = 0;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; } inline long long ADD(long long x,long long y) {return (x + y) % Mod;} inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;} inline long long MUL(long long x,long long y) {return x * y % Mod;} int f[N][N],dp[N];//dp[i] - 以后缀i结尾的最大代价 char nxt[N],s[N]; void solve() { int n;n = read(); scanf("%s",s); f[n + 1][n] = f[n][n + 1] = f[n + 1][n + 1] = 0; for(int i = n;i >= 1;--i) { for(int j = i - 1;j >= 1;--j) { if(s[i - 1] != s[j - 1]) { f[i][j] = 0; } else { f[i][j] = f[i + 1][j + 1] + 1; } } } int ans = 0; for(int i = 1;i <= n;++i) { dp[i] = n - i + 1; for(int j = 1;j < i;++j) { if(s[j + f[i][j] - 1] < s[i + f[i][j] - 1]) { dp[i] = max(dp[i],dp[j] + n - i + 1 - f[i][j]); } } ans = max(ans,dp[i]); } printf("%d ",ans); } int main() { int ca;ca = read(); while(ca--) { solve(); } // system("pause"); return 0; }