本文共 11244 字，大约阅读时间需要 37 分钟。
转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：状态奇差，而且题目太毒瘤了，于是 B + A，rk 1600 滚去掉分。
赛后10min切C，1h切D……这次一改 Codeforces 一贯的结论贪心乱搞作风，开始枚举了。A: 字符串暴力B: 枚举暴力C: 贪心枚举D: 离散化枚举读懂题意需要一定的水平。? 字符可以替换为任意字符，求方案使得串 abacaba 恰好出现一次。
暴力模拟题。先对原串非 ? 字符匹配一遍，如果找到一个则将所有问号设置为 z 输出，若超过一个则输出 No，否则继续。带上 ? 进行匹配，如果匹配，则将当前匹配的带问号串设置为 abacaba 再对置换后的串进行严格扫描看出现次数，如果不超过 1 则是一种合法答案，否则回溯继续枚举。复杂度大概是 \(O(n^3)\) ?感觉卡满会锅，但似乎没那么容易卡满。然而我连WA两发，在1h20min才过掉这道题……#include#include #include const int bufSize = 1e6;inline char nc(){ #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; c != '?' && !isalpha(c); c = nc()); for (; c == '?' || isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}const int maxn = 60;int T;int n;char s[maxn];int save[maxn];char t[maxn];//abacabaint main(){ t[1] = 'a',t[2] = 'b',t[3] = 'a',t[4] = 'c',t[5] = 'a',t[6] = 'b',t[7] = 'a'; read(T); while(T--) { read(n); read(s + 1); int ans = 0; for(int i = 1;i<=n - 6;++i) { bool flag = 1; for(int j = 1;flag && j<=7;++j) if(!(s[i + j - 1] == t[j])) flag = 0; ans += flag; } if(ans > 1){puts("No");goto end;} if(ans == 1) { puts("Yes"); for (int i = 1; i <= n; ++i) if(s[i] == '?') putchar('z'); else putchar(s[i]); putchar('\n'); goto end; } for(int i = 1;i<=n;++i) { bool flag = 1; for(int j = 1;j<=7;++j) if(!(s[i+j-1] == t[j] || s[i+j-1] == '?')) flag = 0; if(flag) { for (int j = 1; j <= 7; ++j) save[i+j-1] = s[i+j-1],s[i + j - 1] = t[j]; int cnt = 0; for(int k = 1;k<=n;++k) { bool f = 1; for(int p = 1;p<=7;++p) if(s[k+p-1] != t[p]) f = 0; if(f) ++cnt; } if(cnt == 1) { puts("Yes"); for(int k = 1;k<=n;++k) if(s[k] == '?') putchar('z'); else putchar(s[k]); putchar('\n'); goto end; } for (int j = 1; j <= 7; ++j) s[i + j - 1] = save[i + j - 1]; } } puts("No"); end:; } return 0;}
应该是本场最简单的题了……然而也想了我20min。
求一个 \(m = n \times a + b - c\) 的 \((a,b,c)\)，其中 \(n\) 为正数。一开始胡乱分析想找特解，失败了之后，发现数据范围可以枚举。\(r - l \leq 10^5\)，且 \(T \leq 20\)，直接枚举 \(a\) 即可。枚举 \(a\) 后，计算出 \(n \times a \leq m\) 和 \(m \leq n \times a\) 对应的 \(n\)，计算出 \(b - c\)的值，判断 \(l - r \leq b - c \leq r - l\) 则有解，否则无解。#include#include #include const int bufSize = 1e6;inline char nc(){ #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}#define int long longint T;long long l,r,m,n,a,b,c,na,bc,x;inline bool check(){ na = n * a; bc = m - na; if(bc > x || bc < -x) return false; if(bc > 0) b = l + bc,c = l; else c = r,b = r + bc; return true;}signed main(){ read(T); while(T--) { read(l),read(r),read(m); x = r - l; for(a = l;a<=r;++a) { n = m / a; if(n && check()) { printf("%lld %lld %lld\n",a,b,c); break; } ++n; if(check()) { printf("%lld %lld %lld\n",a,b,c); break; } } } return 0;}
场上把我卡到自闭的题目。
可以贪心+排序+枚举求解。首先，只有一个元素会被取多次。否则的话，我们一定能重复取被取多次元素中 \(b\) 值最大的那个获取更优解。我们开两个数组： \(A\) 和 \(B\)，其中 \(A\) 按 \(a\) 降序排序， \(B\) 按 \(b\) 降序排序。枚举 \(B\) 数组的位置，找到 \(A_l.a > B_i.b\) 的最大 \(l\)。此时强制选 \(B_i\) 一个后，取 \(A\) 数组 \([1,l]\)，剩下的额度全取 \(B_i\) 即是当前最优解。依次枚举，即可获得所有的可能解。不难发现，过程中 \(l\) 单调递增，因此复杂度是线性的。算上排序，复杂度 \(O(n \log n)\)，可以通过本题。细节较多，注意判断边界，特判全部元素只取一次的解。#include#include #include const int bufSize = 1e6;inline char nc(){ #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}const int maxn = 1e5 + 100;struct node{ unsigned long long a,b,id;}A[maxn],B[maxn];bool cmp(const node &x,const node &y){return x.a > y.a;}bool cmp2(const node &x,const node &y){return x.b > y.b;}unsigned long long sum[maxn];int T,n,m;bool vis[maxn];int main(){ read(T); while(T--) { read(m),read(n); for (int i = 1; i <= n; ++i) read(A[i].a), read(A[i].b), B[i].a = A[i].a, B[i].b = A[i].b, A[i].id = B[i].id = i; std::sort(A + 1, A + 1 + n, cmp), std::sort(B + 1, B + 1 + n, cmp2); for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + A[i].a, vis[i] = 0; unsigned long long ans = 0; if (m <= n) ans = sum[m]; int l = 1; for (int i = 1; i <= n; ++i) { while (l <= n && l <= m && A[l].a > B[i].b) vis[A[l].id] = 1, ++l; if(l == m + 1) { if (vis[B[i].id]) ans = std::max(ans, sum[m]); else if (!vis[B[i].id]) ans = std::max(ans, sum[m - 1] + B[i].a); break; } if(l == n + 1) { ans = std::max(ans,sum[n] + (m - n) * B[i].b); break; } if (vis[B[i].id] && m - l + 1 >= 0) ans = std::max(ans, sum[l - 1] + (m - l + 1) * B[i].b); else if (!vis[B[i].id] && m - l >= 0) ans = std::max(ans, sum[l - 1] + (m - l) * B[i].b + B[i].a); } printf("%lld\n",ans); } return 0;}
这题的难点主要在于读懂题意，晦涩难懂的英语和混乱不清的边界实在是让人痛苦万分。
题目中到达时间只需要考虑分钟，小时完全无用。即选定一个 \(t\) 后，在 \((t - K,t)\) 和 \((t + half - K,t + half)\) 中的元素全部不合法。此外，固定给了一个整点发的车，因此 \([M - K,M-1]\) 也是不合法的。转化为闭区间，\([t - K + 1,t - 1]\) 和 \([t + half - K + 1,t + half - 1]\) 和 \([M - K,M - 1]\)。个人习惯让离散化前的数值都有严格对应的新值，这样似乎不容易出锅。那么对于离散化前的数值 \(x\)，将 \(x - 1\) 与 \(x - K + 1\) 同时插入即可。随后开个桶记录每个位置出现元素次数，做一遍前缀和方便求区间元素数，枚举 \(t\) 求解即可。边界、细节需要多加注意。我的实现有些冗杂。#include#include #include const int bufSize = 1e6;#define DEBUGinline char nc(){ #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;}inline void read(char *s){ static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0';}template inline T read(T &r){ static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag;}template inline T abs(const T &a){return a > 0 ? a : -a;}const int maxn = 1e5 + 100;int n,H,M,K,half;int num[maxn*6],tot;int h[maxn],m[maxn];int sum[maxn*6];inline void add(int x){ num[++tot] = x; num[++tot] = x - 1; num[++tot] = x - K + 1;}int main(){ read(n),read(H),read(M),read(K); half = M / 2; num[++tot] = -1,num[++tot] = 0,num[++tot] = M - 1; for (int i = 1; i <= n; ++i) { read(h[i]), read(m[i]); if(m[i] >= half) m[i] -= half; add(m[i]),add(m[i] + half); } std::sort(num + 1,num + 1 + tot); tot = std::unique(num + 1,num + 1 + tot) - num - 1; for (int i = 1; i <= n; ++i) m[i] = std::lower_bound(num + 1, num + 1 + tot, m[i]) - num, sum[m[i]]++; for (int i = 1; i <= tot; ++i) sum[i] += sum[i-1]; int ans = 1<<30,anst = 0; int end = std::lower_bound(num + 1,num + 1 + tot,M - 1) - num; int es = std::lower_bound(num + 1,num + 1 + tot,M - K) - num; int eans = sum[end] - sum[es - 1]; for (int i = 1; i <= tot; ++i) { int t = num[i]; if(t < 0) continue; if(t >= half) break; if(t >= K) { //[t - K + 1,t - 1] + [t + half - K + 1,t + half - 1] + [M - K,M - 1] int l1 = t - K + 1,r1 = t - 1; int l2 = t + half - K + 1,r2 = t + half - 1; l1 = std::lower_bound(num + 1,num + 1 + tot,l1) - num; r1 = std::lower_bound(num + 1,num + 1 + tot,r1) - num; l2 = std::lower_bound(num + 1,num + 1 + tot,l2) - num; r2 = std::lower_bound(num + 1,num + 1 + tot,r2) - num; int tans = eans + sum[r2] - sum[l2 - 1] + sum[r1] - sum[l1 - 1]; if(tans < ans) ans = tans,anst = i; } else { //[,t - 1] + [t + half - K + 1,t + half - 1] + [M - K,M - 1] int r1 = t - 1; int l2 = t + half - K + 1,r2 = t + half - 1; r1 = std::lower_bound(num + 1,num + 1 + tot,r1) - num; l2 = std::lower_bound(num + 1,num + 1 + tot,l2) - num; r2 = std::lower_bound(num + 1,num + 1 + tot,r2) - num; int tans = eans + sum[r1] + sum[r2] - sum[l2 - 1]; if(tans < ans) ans = tans,anst = i; } } printf("%d %d\n",ans,num[anst]); int t = num[anst]; if(t >= K) { int l1 = t - K + 1, r1 = t - 1; int l2 = t + half - K, r2 = t + half - 1; l1 = std::lower_bound(num + 1, num + 1 + tot, l1) - num; r1 = std::lower_bound(num + 1, num + 1 + tot, r1) - num; l2 = std::lower_bound(num + 1, num + 1 + tot, l2) - num; r2 = std::lower_bound(num + 1, num + 1 + tot, r2) - num; for (int i = 1; i <= n; ++i) if((m[i] >= l1 && m[i] <= r1) || (m[i] >= l2 && m[i] <= r2) || (m[i] >= es && m[i] <= end)) printf("%d\n",i); } else { int r1 = t - 1; int l2 = t + half - K + 1, r2 = t + half - 1; r1 = std::lower_bound(num + 1, num + 1 + tot, r1) - num; l2 = std::lower_bound(num + 1, num + 1 + tot, l2) - num; r2 = std::lower_bound(num + 1, num + 1 + tot, r2) - num; for (int i = 1; i <= n; ++i) if ((m[i] <= r1) || (m[i] >= l2 && m[i] <= r2) || (m[i] >= es && m[i] <= end)) printf("%d\n", i); } return 0;}