Loading... ## A - 记录一个 `flag` 变量,遇到 `(` 就变成 $1$ ,遇到 `)` 就变回 $0$ 。然后只在 $flag=0$ 的时候输出变量。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { string p; cin >> p; int n = p.size(); bool f = 0; for (int i = 0; i < n; ++ i) { if (p[i] == '(')\ f = 1; if (p[i] == ')') { f = 0; cout << '@'; continue; } if (f) continue; cout << p[i]; } return 0; } ``` ## B 观察数据范围发现,我们不能暴力去统计每个区间的和(这是$O(n^2)$的)。 题目保证了$X_i$为升序,所以我们可以使用**二分来找到区间的左右端点**:第一个大于等于$L_i$的数和第一个大于$R_i$的数往左一个。 然后还要快速的求出区间和,我们可以使用前缀和来$O(1)$的回答。 这样整体复杂度为$O(n\log n)$。 ```cpp #include <bits/stdc++.h> using namespace std; long long n, m, x[200005], c[200005], l[200005], r[200005], s[600005]; vector<long long> a; long long find(long long f) { long long l = 0, r = a.size() - 1; while (l < r) { long long mid = (l + r) / 2 + 1; if (a[mid] <= f) l = mid; else r = mid - 1; } return l + 1; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> x[i]; a.push_back(x[i]); } for (int i = 1; i <= n; i++) cin >> c[i]; cin >> m; for (int i = 1; i <= m; i++) { cin >> l[i] >> r[i]; a.push_back(l[i]); a.push_back(r[i]); } sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); for (int i = 1; i <= n; i++) s[find(x[i])] += c[i]; for (int i = 1; i <= a.size(); i++) s[i] += s[i - 1]; for (int i = 1; i <= m; i++) cout << s[find(r[i])] - s[find(l[i]) - 1] << '\n'; return 0; } ``` ## C 根据题目的约束条件,钥匙的数量最多为 $N \leq 15$。测试次数也不多:$M \leq 100$。此外,如题目描述,有 $2^N$ 种钥匙真假组合。 我们可以对所有 $2^N$ 种组合进行 $M$ 次测试,统计满足条件的组合数量。在这里,需要进行 $2^N \times M \leq 3.3 \times 10^6$ 次测试。即使每次测试进行 $N$ 次操作,总操作次数也限制在 $5 \times 10^7$ 以内,这足够快,可以通过这个问题。 为了暴力枚举 $2^N$ 种组合,我们使用按位枚举的方法。 例如,使用一个 for 循环遍历 $i=0,1,\ldots,2^N-1$。如果 $i$ 的第 $2^k$ 位是 $0$,我们认为第 $(k+1)$ 把钥匙是假的;如果是 $1$,我们认为它是真的。通过这种方式,我们可以穷举所有的组合。 ```cpp #include <bits/stdc++.h> using namespace std; const int SIZE = 20; const int SIZE_M = 1e2 + 5; int n, m, k; int bit[SIZE], c[SIZE_M], A[SIZE_M][SIZE_M], r[SIZE_M]; int main() { int tot = 0; scanf("%d %d %d", &n, &m, &k); for (int i = 1; i <= m; ++ i) { scanf("%d", &c[i]); for (int j = 1; j <= c[i]; ++ j) scanf("%d", &A[i][j]); char ch; cin >> ch; r[i] = ch == 'x' ? 0 : 1; tot += r[i]; } int ans = 0; for (int status = 0; status < (1 << n); ++ status) { for (int i = 0; i < n; ++ i) bit[i] = (status >> i) & 1; int flag = 1; for (int i = 1; i <= m; ++ i) { int cnt = 0; for (int j = 1; j <= c[i]; ++ j) { if (bit[A[i][j] - 1]) ++ cnt; } if ((cnt >= k && !r[i]) || (cnt < k && r[i])) { flag = 0; break; } } if (flag) { ++ ans; } } printf("%d\n", ans); return 0; } ``` ## D - 数据量都较小,各种做法均可轻松通过。以下做法采用结构体数组排序来解题。 - 统计每一种字母出现的次数,然后将字母和次数,两个键值打包为结构体,然后按照次数为第一关键字,字母顺序为第二关键字,进行排序,最后从前到后输出即可。 ```cpp #include <bits/stdc++.h> using namespace std; const int SIZE = 3e2 + 5; char s[SIZE]; //字符数组 int cnt[SIZE]; //出现频率 int main() { cin.getline(s,256); for (int i = 0; s[i] != '\0'; ++ i) { char c = s[i]; if ('A' <= c && c <= 'Z') ++ cnt[c]; else if ('a' <= c && c <= 'z') ++ cnt[c-32]; //小写字母 } for (int k = 250; k > 0; -- k) { //频率从高到低查找 for (char c = 'A'; c <= 'Z'; ++ c) { if (cnt[c] == k) printf("%c %d\n", c, k); } } return 0; } ``` ## E 考虑把操作倒过来,就变成每次加一个点。用并查集维护连通块以及其权值和即可。 注意开 long long,否则只会获得 50 分。 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; typedef vector < int > vec; const int SIZE = 4e5 + 5; int n, m; int a[SIZE], fa[SIZE], cnt[SIZE], vis[SIZE], ans[SIZE], del[SIZE]; vec edge[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } signed main() { // freopen("qd.in", "r", stdin); // freopen("qd.out", "w", stdout); n = read(), m = read(); for (int i = 1; i <= n; ++ i) a[i] = read(); for (int i = 1; i <= n; ++ i) fa[i] = i, cnt[i] = a[i]; for (int i = 1, u, v; i <= m; ++ i) { u = read(), v = read(); edge[u].emplace_back(v), edge[v].emplace_back(u); } for (int i = 1; i <= n; ++ i) vis[i] = read(); int res = 0; for (int i = 1; i <= n; ++ i) { int u = vis[n - i + 1]; for (int it: edge[u]) { int fx = find(u), fy = find(it); if (fx == fy || !del[it]) continue; cnt[fx] += cnt[fy], fa[fy] = fx; res = std::max(res, cnt[fx]); } res = std::max(res, cnt[find(u)]); del[u] = 1, ans[i] = res; } for (int i = n - 1; i; -- i) { printf("%lld\n", ans[i]); } return puts("0"), 0; } ``` ## F ### 测试点 1~4 5~8 直接暴力枚举 $i,j$,然后判断 $i^2+j^2\bmod m=0$ 。 复杂度 $O(n^2)$ 。 ### 测试点 9~10 直接输出 $\frac{1}{2}n(n+1)$ 。 ### 测试点 11~12 对于 $i$ 是奇数的情况, $i^2$ 一定是奇数,而 $i$ 是偶数则 $i^2$ 一定是偶数。 所以当 $i$ 是奇数时,$j$ 可以是任意一个 $\ge i$ 的奇数, $i$ 是偶数时,$j$ 可以是任意一个 $\ge i$ 的偶数。 ### 测试点 11~12 对于 $i$ 是奇数的情况, $i^2$ 一定是奇数,而 $i$ 是偶数则 $i^2$ 一定是偶数。 所以当 $i$ 是奇数时,$j$ 可以是任意一个 $\ge i$ 的奇数, $i$ 是偶数时,$j$ 可以是任意一个 $\ge i$ 的偶数。 ### 测试点 13~15 可以依次考虑每一个 $i^2\bmod m$ 是多少,然后记 $f_j$ 为 $i^2\bmod m=j$ 的这样的 $i$ 的个数。 那么如果不考虑 $i\le j$,答案就是 $\sum_{i=0}^{m-1}f_i\cdot f_{m-i\ \bmod\ m}$ 。 如何处理 $i\le j$,那么我们可以把 $i=j$ 的情况再算一次之后,把整个答案 除以 $2$ 。 如何计算 $2i^2\bmod m=0$ 的个数?实际上只有当 $i^2\bmod m=0$ 或 $\frac n 2$ 才可以,那么方案数就是 $f_0+f_{\frac n 2}$ 。 ### 测试点 16~18 19~20 发现难点在于得到 $f_i$ ,其实对于所有 $i\bmod m$ 相同的 $i$ ,其 $i^2\bmod m$ 的值也相同。 而满足 $i\bmod m=j$ 的 $i$ 的个数是好处理的。 所以就可以 $O(m)$ 的时间复杂度内解决此题。 ```cpp #include<bits/stdc++.h> #define ll long long #define db double #define mp make_pair #define fi first #define se second #define pii pair<int,int> using namespace std; int read(){ int sum=0,f=1;char st=getchar(); while(st<'0'||st>'9'){ if(st=='-')f=-1; st=getchar(); } while('0'<=st&&st<='9'){ sum=(sum<<3)+(sum<<1)+st-'0'; st=getchar(); } return sum*f; } const int maxn=1000010; ll cnt[maxn]; int n,m; int main(){ cin>>n>>m; int st=n%m; for(ll i=1;i<=m;++i)cnt[i*i%m]+=n/m+(i<=st); ll ans=cnt[0]*cnt[0]+cnt[0]; for(int i=1;i<m;++i)ans+=cnt[i]*cnt[m-i]; // for(int i=0;i<=m;++i) // cout<<"i="<<i<<" cnt[i]="<<cnt[i]<<endl; if(m%2==0)ans+=cnt[m/2]; cout<<ans/2<<endl; return 0; } ``` ## G 假如 $m=3$,情况很少,对于某一天你可能有这几种情况: * 对于`001`,`111`等情况,小C 可以翘 $1$ 节课,少在教学楼呆 $1$ 小时。 * 而对于 `101`的情况,小C 第一次可以选择翘 $1$ 节课,少在教学楼呆 $2$ 小时。 贪心的先选择少呆 $2$ 小时的情况,剩下的只能选少呆 $1$ 节课的情况。 **扩展上一个做法。** 对于每一天,小 C 可以选择翘 $1$ 节课,少呆 $r-l$ 个小时。 同样贪心的选择少呆时间长的课,最后如果还能翘课,那么都只能少呆 $1$ 个小时。 **进一步扩展上面的做法。** 对于一天,我们可以考虑每一节课选择翘或者不翘,暴力得到 $c_{i,j}$ ,表示第 $i$ 填翘 $j$ 节课的情况下小 C 要在教学楼里呆最少 $c_{i,j}$ 个小时。 然后就是一个分组背包。 时间复杂度为 $O(n2^m+nmk)$ 。 **再进一步** 我们不用暴力的考虑每一节课选择翘或者不翘,而只需要考虑这一天中最早的课和最晚的课是什么就可以(中间的课翘了也不会减少呆在教学楼的时间) 所以就可以枚举最早的课 $j$,最晚的课 $k$,计算一个要翘多少课,此时小 C 要在教学楼呆 $k-j+1$ 小时。 这样就可以 $O(nm^2)$ 的时间复杂度求出 $c_{i,j}$ 。 ```cpp #include<bits/stdc++.h> #define ll long long #define db double #define mp make_pair #define fi first #define se second #define pii pair<int,int> using namespace std; int read(){ int sum=0,f=1;char st=getchar(); while(st<'0'||st>'9'){ if(st=='-')f=-1; st=getchar(); } while('0'<=st&&st<='9'){ sum=(sum<<3)+(sum<<1)+st-'0'; st=getchar(); } return sum*f; } const int maxn=510; int n,m,q; int a[maxn][maxn]; int b[maxn][maxn],f[maxn]; int main(){ cin>>n>>m>>q; memset(b,0x3f,sizeof(b)); memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;++i){ int su=0; for(int j=1;j<=m;++j){ a[i][j]=read(); su+=a[i][j]; } b[i][su]=0; for(int j=1;j<=m;++j){ int st=0; for(int k=j;k<=m;++k){ st+=a[i][k]; b[i][su-st]=min(b[i][su-st],k-j+1); } } } f[0]=0; for(int i=1;i<=n;++i) for(int j=q;j>=0;--j){ f[j]=f[j]+b[i][0]; for(int k=j-1;k>=0;--k) f[j]=min(f[j],f[k]+b[i][j-k]); } int ans=1e9; for(int i=0;i<=q;++i) ans=min(ans,f[i]); cout<<ans<<endl; return 0; } ``` ## H 给出每个前缀的最小循环节长度相当于给出了 $nxt$ 数组。 相当于要实现一个“逆kmp”过程,可以类比kmp,从前往后增量地构造原串。 如果 $nxt_i \neq 0$,那么显然 $str_i = str_{nxt_i}$。 否则没有可以依赖的取值,但可以发现存在一些 $str_i \neq str_{j+1}$ 的限制,其中的 $j$ 是在从 $nxt_{i-1}$ 开始一路向前跳 $nxt$ 的过程中得到的(也就是kmp代码实现中的那个 $j$ )。 复杂度$O(n\sigma)$。 ```cpp #include<cstdio> #include<algorithm> using namespace std; int gi(){ int x=0,w=1;char ch=getchar(); while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); if (ch=='-') w=0,ch=getchar(); while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return w?x:-x; } const int N = 1e5+5; int n,nxt[N],a[N],vis[26]; int main(){ n=gi(); for (int i=1;i<=n;++i) nxt[i]=i-gi(); for (int i=2,j;i<=n;++i){ j=nxt[i-1]; while (j&&j+1!=nxt[i]) vis[a[j+1]]=i,j=nxt[j]; if (j+1==nxt[i]) a[i]=a[j+1]; else{ vis[a[1]]=i; for (int k=0;k<26;++k) if (vis[k]!=i) {a[i]=k;break;} } } for (int i=1;i<=n;++i) putchar(a[i]+'a'); puts("");return 0; } ``` 最后修改:2024 年 10 月 15 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏