Loading... ## A. Polycarp and Sums of Subsequences ### 题意 给定一个数列$b$长度为$7$，为数列$a(len=3)$的全部子序列和。求一个可能的$a$。 ### 分析 一开始想的是枚举，写完之后才发现笨比了。 显然$b[1]$和$b[2]$一定是$a[1]$和$a[2]$，那么$b[3]$可能恰好是子串和$a[1:2]$，这种情况下，$a[3]=b[4]$，否则$a[3]=b[3]$。 ### 代码 ```cpp int a[10]; int main() { int t; cin >> t; while (t--) { for (int i = 1; i <= 7; i++) cin >> a[i]; printf("%d %d ", a[1], a[2]); if (a[3] == a[1] + a[2]) cout<<a[4]<<endl; else cout<<a[3]<<endl; } return 0; } ``` ## B. Missing Bigram ### 题意 有一个字符串$str=\{a,b\}*length$，现顺序给出$len-2$个bigram（长度为2的子串）——也就是说缺少一个。请给出一个可能的$str$。 ### 分析 考虑相邻的两个bigram，如果首尾能够相连，那么他们有可能中间是没有其他字符的（在$str$中）。如果首位不能相连，比如$ab$和$ab$，那么中间一定是存在一个$ba$是被删掉的那个，那就把这个补出来就行了。如果一直能够首尾相连，那就在最后随便补个什么就好。 ### 代码 ```cpp int t, len; vector<string> v; void solve() { cout << v[0][0]; for (int i = 1; i < v.size(); i++) if (v[i].front() == v[i - 1].back()) cout << v[i].front(); else { cout << v[i - 1].back(); for (int j = i; j < v.size(); j++) cout << v[j].front(); cout << v[v.size() - 1].back(); return; } cout << v.back().back() << 'a'; } int main() { cin >> t; while (t--) { cin >> len; int bis = len - 2; v.clear(); for (int i = 0; i < bis; i++) { string s; cin >> s; v.push_back(s); } solve(); cout << endl; } return 0; } ``` ## C. Paint the Array ### 题意 给你一个数组$a$，求一个$k$使得奇数位置构成的子串（称奇子串）和偶数位置构成的子串（称偶子串）一个都能被$k$整除，一个**都不能**。 ### 分析 对于一个串，若都能被$k$整除，则$k$必为这个串的公因数。而若$a|b$，则$b|m\rightarrow a|m$，反之不成立。所以我们要尽量使另一个串里的数不能被整除，则这个$k$显然应该选择串的最大公因数。 然后两个串都求gcd然后试除另一个串即可。 ### 代码 ```cpp int t; ll arr[1000]; int main() { cin >> t; while (t--) { int n; cin >> n; ll oddgcd = 0, evengcd = 0; FOR(i, 1, n) { cin >> arr[i]; if (i & 1) oddgcd = __gcd(oddgcd, arr[i]); else evengcd = __gcd(evengcd, arr[i]); } auto f = [&](ll x, int b) -> bool { for (; b <= n; b += 2) if (arr[b] % x == 0) return false; return true; }; if (f(oddgcd, 2)) cout << oddgcd << endl; else if (f(evengcd, 1)) cout << evengcd << endl; else cout << 0 << endl; } return 0; } ``` ## D. Array and Operations ### 题意 给一个串$a$，给$k$次操作，每次操作取出两个数字$a_i,a_j$从$a$中删去，然后把$\left\lfloor\frac{a_{i}}{a_{j}}\right\rfloor$给加到得分里去，得分再加上最后的$\Sigma a$。求最小得分。 ### 分析 首先要注意到取出两个数字肯定是小数字除以大数字，那么商就是$1$或者$0$。考虑$\Sigma a$，那么显然应该取出较大的$2k$个去操作。为什么这样是最优呢？考虑不这样选，使用较小的某个数字替代$\max _{2k} $中的某个，那么最多让$\left\lfloor\frac{a_{i}}{a_{j}}\right\rfloor$减小$1$，而$\Sigma a$则**至少**增大$1$，所以必然是不优的。那么选最大的$2k$个就是最优解了。 再考虑最大的$2k$个要怎么除呢？一个数越大，放在分母上就越不可能让商为$1$，那么就要让大数在分母上，小数在分子上，然后顺序对应相除就行了。 ### 代码 ```cpp int t, n, k; vector<int> arr; int main() { cin >> t; while (t--) { cin >> n >> k; int score = 0; arr.clear(); FOR(i, 1, n) { int x; cin >> x; arr.emplace_back(x); } sort(arr.begin(), arr.end(), greater<int>()); for (int i = 0; i < k; i++) score += arr[i + k] / arr[i]; for (int i = 2 * k; i < n; i++) score += arr[i]; cout << score << endl; } return 0; } ``` ## E. Singers' Tour ### 题意 赛时没看到是恰好一圈，感觉不太可做就跳了。但因为有这个条件所以其实很简单。 环上有$n$个歌手，每个歌手顺次向递增方向移动，**恰好一圈**回到各自起点。第$i$歌手在自己的城市$i$能唱$a_i$分钟，然后每走一步就能多唱$a_i$分钟，也就是说他能在走$k$步之后的城市唱$(k+1)a_i$分钟。现在给数组$\{b_1...b_n\}$代表每个城市响起过多久的歌声，求一组可能的$\{a_1...a_n\}$。 ### 分析 容易写出$b_i=\Sigma_{j=0}^{n}{(j+1)a_{(i+j-1 \mod n)+ 1}}$ 这种稠密的$\Sigma k_ia_i$的形式，直觉上应当注意它的和式和差式。那么容易推出 $$ \Sigma b = (1+2+...+n)\Sigma a_i=\frac{n(n+1)}{2}\Sigma a \tag{1} $$ 和 $$ \Delta b_{i}=b_{i}-b_{i-1}=\Sigma{a}-na_{i} \tag{2} $$ 由$(1)$显然知道有解的条件是$\frac{n(n+1)}{2}|\Sigma b$，同时能求出来$\Sigma a$。那么结合$(2)$式就能直接求出每个$a_i$来。需要注意的是在求$a_i$的时候要随时判断整除和positive条件。 ### 代码 ```######cpp typedef long long ll; #define int ll int t, n; #define N 40004 int b[N], db[N]; signed main() { cin >> t; while (t--) { cin >> n; int sb = 0; FOR(i, 1, n) { cin >> b[i]; sb += b[i]; } int k = n * (n + 1) / 2; if (sb % k) { cout << "NO" << endl; continue; } int sa = sb / k; for (int i = 2; i <= n; i++) db[i] = b[i] - b[i - 1]; db[1] = b[1] - b[n]; vector<int> ans; ans.clear(); FOR(i, 1, n) { if ((sa - db[i]) % n || (sa - db[i]) / n < 1) { cout << "NO" << endl; break; } ans.push_back((sa - db[i]) / n); } if (ans.size() == n) { cout << "YES" << endl; FOR(i, 0, n-1) cout << ans[i] << " "; cout << endl; } } return 0; } ``` ## F. Reverse ### 题意 给定二进制串$x$，支持两种操作： 1. 在最右端添加$1$，然后翻转 2. 在最右端添加$0$，然后翻转 注意翻转时不保留前导零。 求$x$是否可以变换为另一给定串$y$。 ### 分析 注意到由于前导零不会被保留，因此第二个操作等价于单纯翻转。而操作次序和数量没有限制，从而串可以随时翻转。那么就可以在**左右各种添$1$**。而如果要在高位添$1$，则先需要一次翻转，这会导致： 1. 最低位的$0$全都消失，或者 2. 最低位也必须添加$1$。 也就是说，去掉后缀零之后的$x$可以在左右任意添$1$。而想要保留后缀零，那么就必须在低位先添一个$1$才行，然后左右任意添$1$。综上，$x$在$y$中出现的位置，必须左右全部被$1$包裹，这两种子串及他们的$reverse$一共四种子串，去$y$里查找然后判断就可以了。 由于串长度$len \le \log_210^{18}<60$很小，因此枚举可以写的比较暴力。 这题细节还是挺烦人的，一个是要注意区间，有全为1的特例，所以不能l和r相遇即停止。然后有相等的特例，只有这种情况下可以最右端为0，需要提前特判。 ### 代码 ```cpp ll x, y; vector<int> re(const vector<int> &arg) { vector<int> ans; for (auto it = arg.rbegin(); it != arg.rend(); it++) ans.push_back(*it); return ans; } vector<int> to_binary(ll x) { vector<int> ans; while (x) { ans.push_back(x & 1); x >>= 1; } return re(ans); } int l, r; bool check(vector<int> s, vector<int> t) { for (int i = max(r - (int)s.size(), 0); i <= l + 1 && i + s.size() - 1 < t.size(); i++) { auto nn = vector<int>(t.begin() + i, t.begin() + i + s.size()); if (s == nn) return true; } return false; } int main() { cin >> x >> y; auto s = to_binary(x), t = to_binary(y); if (s == t || re(s) == t) { cout << "YES" << endl; return 0; } for (l = -1; l + 1 < t.size(); l++) if (!t[l + 1]) break; for (r = t.size(); r; r--) if (!t[r - 1]) break; if (r == t.size()) { cout << "NO" << endl; return 0; } auto s2 = s; while (!s2.back()) s2.pop_back(); if (check(s, t) || check(s2, t) || check(re(s), t) || check(re(s2), t)) cout << "YES" << endl; else cout << "NO" << endl; return 0; } ``` ## G. Trader Problem ### 题意 A和B各自有一些货物价值分别为$\{a_i\}$和$\{b_i\}$，A可以进行无限次交换，每次都可以用任意货物$a_i$换取B的任意价值不超过$a_i+k$的货物。每次询问给你一个$k$，请给出这个条件下A最终最大的货物总价值。 ### 分析 把两组货物放到一起去考虑，称之为$\{c_i\}$，将其按价值排序，则我们说任意满足$(\forall i \in [l,r))(c_{i+1}-c_i\le k)$的区间$[l,r]$为一个范围，则A可以把任意范围中自己有的货物换成最大的那几个。依次枚举$c_i$，依次计算连续区间即可。 接下来问题是多组询问，那么我们考虑对于任意$k_x<k_y$，如果某个区间在$k_x$下为一个范围，则在$k_y$下也必为一个范围。那么如果任意两个$k_x$下的范围如果相隔不超过$k_y$的话，那么它们连同其间隔可以在$k_y$下合并为一个大范围。那么，把所有询问**离线下来**，按照$k$从小到大排序处理每个询问即可。处理一个询问的时候，对范围依次**枚举间隔**就可以了。 中途需要用到排序后某个区间货物总价值，显然前缀和可以解决。 第一遍写的时候是枚举的范围，不幸T了。显然如果不进行合并，那么每次都要考虑所有范围，时间复杂度退化到$\Omega((n+m)q)$，显然会炸。 所以需要枚举间隔，因为间隔可以排个序保证单调，摊还分析就知道单次处理均摊是$\Omega(1)$了。 间隔可以标记间隔的左右范围，这样范围用vector存储，合并的时候懒删除一个就行了。但是因为进行了懒删除，而间隔大小单调但是范围在多次询问中的访问不单调，所以还需要用一个类似于并查集的树状结构（我就是直接用的并查集）维护每个范围被合并到哪儿去了，下一次合并的时候才能找到真正需要合并的区间。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; int n, m, q; #define N 400005 int ans[N]; struct good { int val, belong; bool operator<(const good &g) const { return val < g.val; } good() = default; good(int v, int b) : val(v), belong(b) {} }; struct que { int k, pos; bool operator<(const que &q) const { return k < q.k; } que() = default; que(int k, int pos) : k(k), pos(pos) {} }; vector<good> goods; vector<que> ques; ll preval[N], prehave[N]; ll prt[N]; int fa[N]; int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); } void uni(int x, int y) { x = find(x); y = find(y); fa[x] = y; } int main() { cin.sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; int t; FOR(i, 1, n) { cin >> t; goods.emplace_back(t, 1); } FOR(i, 1, m) { cin >> t; goods.emplace_back(t, 0); } sort(goods.begin(), goods.end()); preval[0] = goods[0].val; FOR(i, 1, n + m - 1) preval[i] = preval[i - 1] + goods[i].val; FOR(i, 1, q) { int k; cin >> k; ques.emplace_back(k, i); } sort(ques.begin(), ques.end()); struct space { int l, r, ln, rn, del; space() = default; space(int l, int r, int ln, int rn) : l(l), r(r), ln(ln), rn(rn) { del = r - l; } }; struct myg : binary_function<space, space, bool> { bool operator()(const space &lhs, const space &rhs) const { return lhs.del > rhs.del || lhs.del == rhs.del && lhs.ln > rhs.ln; } }; struct block { mutable int l, r, have; mutable ll val; bool operator<(const block &b) const { return l < b.l; } block() = default; block(int l, int r, int have, ll val) : l(l), r(r), have(have), val(val) {} }; priority_queue<space, vector<space>, myg> spc; vector<block> blks; ll ans = 0; for (int i = 0; i < goods.size(); i++) { blks.emplace_back(i, i, goods[i].belong, goods[i].belong ? goods[i].val : 0); fa[i] = i; ans += goods[i].belong ? goods[i].val : 0; if (i) spc.emplace(goods[i - 1].val, goods[i].val, i - 1, i); } for (auto v : ques) { while (!spc.empty() && spc.top().del <= v.k) { auto s = spc.top(); spc.pop(); s.rn = find(s.rn); //并查集解决向已合并区间归并的问题。 auto &_new = blks[s.rn]; //因为同间隔是从左到右遍历的，所以把左边的合并到右边去就行了。 _new.l = blks[s.ln].l; _new.have += blks[s.ln].have; ans -= blks[s.ln].val + blks[s.rn].val; _new.val = preval[_new.r] - preval[_new.r - _new.have]; ans += _new.val; uni(s.ln, s.rn); //合并区间 } prt[v.pos] = ans; } FOR(i, 1, q) cout << prt[i] << '\n'; return 0; } ``` ## 笔记 * 从E题知道，形如$\Sigma k_ia_i$的数列求和式，其和式和差分一般都有意义，可以先求一求。 * 推上下界什么的最好手画一下...会快而且不容易出错。 * G题小区间逐渐归并到大区间然后解决询问属于经典题型。这种枚举间隔来保证均摊复杂度的思想，以及懒删除时候需要用并查集找真正区间位置的技巧需要学习。 © 允许规范转载 打赏 赞赏作者 赞 1 如果觉得我的文章对你有用，请随意赞赏