B The Game
容易想到是贪心，一共要操作 \(n-m\) 次，最后剩 \(m\) 个数，肯定是剩最大的 \(m\) 个。
所以拿 \(a\) 数组最大的 \(m\) 个和 \(b\) 数组比较一下，就知道有多少次需要加在这 \(m\) 个数上面。设需要加 \(d_2\) 次，因此就有 \(d_1=n-m-d_2\) 次加在最小值上面。
模拟这个操作，先执行 \(d_1\) 次加在最小值上面的操作。但是过程中可能会加到最大的 \(m\) 个数上面去，此时不算加在了最小值上面，需要判断一下。因此策略就是，\(a\) 数组排序之后，每次给最后一个最小值加一，如果这个位置是前 \(m\) 大里的，令 \(d_2-1\)，否则令 \(d_1-1\)，直到 \(d_1=0\)。剩下的判断是否合法和构造方案就简单了。
复杂度 \(\mathcal O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010;
int T, n, m, a[maxn], b[maxn], ans[maxn], len;
inline void solve() {cin >> n >> m, len = 0;for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= m; ++i) cin >> b[i];sort(a + 1, a + 1 + n), sort(b + 1, b + 1 + m);int d1 = n - m, d2 = 0;for(int i = 0; i < m; ++i) {if(a[n - i] > b[m - i]) return cout << "-1\n", void();else d2 += b[m - i] - a[n - i];}if(d1 < d2) return cout << "-1\n", void();d1 -= d2;int now = 1;while(d1) {int pos = upper_bound(a + 1, a + 1 + n, a[now]) - a - 1;ans[++len] = a[pos], ++a[pos], ++now;if(pos > n - m) --d2;else --d1;}if(d2 < 0) return cout << "-1\n", void();for(int i = 0; i < m; ++i) {if(a[n - i] > b[m - i]) return cout << "-1\n", void();else {if(d2 < b[m - i] - a[n - i]) return cout << "-1\n", void();while(a[n - i] < b[m - i]) ans[++len] = a[n - i], ++a[n - i], --d2;}}cout << len << '\n';for(int i = 1; i <= len; ++i) cout << ans[i] << ' ';cout << '\n';
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> T;while(T--) solve();return 0;
}C Master of Both IV
无论怎么异或都不会大于等于最大值的两倍，所以 \(\text{lcm}\) 要么是集合的最大值要么是 \(0\)。
第一种情况就枚举这个最大值，然后将所有因子加进线性基计数；第二种情况就把所有数加进线性基计数。
问题就变成了 \(n\) 个数，组成的线性基秩为 \(r\)，要表示出 \(x\) 有多少种方案。可以发现每一种方案都可以表示成这种形式：非线性基中的数随便选，再从线性基里选出相应的数让异或和等于 \(x\)。所以方案数就是 \(2^{n-r}\)。
复杂度 \(\mathcal O(n\ln n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010, mod = 998244353;
int T, n, a[maxn], pw[maxn], cnt[maxn], f[maxn];
class BinaryLinearSpace {
public:BinaryLinearSpace() { memset(bas, 0, sizeof bas), r = 0; }inline void insert(int x) {for(int i = 19; i >= 0; --i) if(x >> i & 1) {if(bas[i]) x ^= bas[i];else {bas[i] = x, ++r;break;}}}int bas[20], r;
}bls[maxn];
inline void solve() {cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= n; ++i) cnt[i] = 0;for(int i = 1; i <= n; ++i) ++cnt[a[i]];for(int i = 0; i <= n; ++i) bls[i] = BinaryLinearSpace();for(int i = 1; i <= n; ++i) bls[0].insert(a[i]);int ans = pw[n - bls[0].r];for(int i = 1; i <= n; ++i) f[i] = 0;for(int i = 1; i <= n; ++i) if(cnt[i]) for(int j = i; j <= n; j += i) if(cnt[j]) bls[j].insert(i), f[j] += cnt[i];for(int i = 1; i <= n; ++i) if(cnt[i]) ans = (ans + pw[f[i] - bls[i].r]) % mod;ans = (ans + mod - 1) % mod;cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);pw[0] = 1;for(int i = 1; i <= 200000; ++i) pw[i] = (pw[i - 1] << 1) % mod;cin >> T;while(T--) solve();return 0;
}E Prefix Mahjong
首先有一个贪心，在不考虑雀头的情况下，每种牌尽量组成刻子，再考虑去组顺子。
先考虑单次操作。将麻将从小到大排序，设 \(f_{i,0/1,0/1/2,0/1/2}\) 表示当前大小为 \(i\)，是否有雀头，从 \(i-1\) 开始的顺子有几个，从 \(i\) 开始的顺子有几个，这种情况下是否能胡牌。每个 \(i\) 一共就有 \(18\) 种状态。转移容易写成矩乘的形式，最后就是看 \(f_{max,1,0,0}\) 是否是 \(1\)。
这个转移的本质上是看某个状态是否能到达，所以可以设 \(f_{0,0,0,0}=1\)。由于有的时候有 \(i\) 不一定有 \(i-1\)，所以可以把所有 \(a_i+1\) 都加进来，如果没出现过那就是出现次数为 \(0\) 对应的转移矩阵。对于前缀的询问，维护一个线段树支持单点修改整体查询就行。然后由于状态数只有 \(18\)，dp 值只有 \(0/1\)，可以状压。
复杂度 \(\mathcal O(18^2n\log n)\)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int T, n, a[maxn], b[maxn], tot, cnt[maxn];
class matrix {
public:matrix() { memset(row, 0, sizeof row), memset(col, 0, sizeof col); }matrix(int val) {memset(row, 0, sizeof row), memset(col, 0, sizeof col);for(int Eyes1 = 0; Eyes1 < 2; ++Eyes1) {for(int Chow1 = 0; Chow1 < 3; ++Chow1) {for(int Chow2 = 0; Chow2 < 3; ++Chow2) {int now = Eyes1 * 9 + Chow1 * 3 + Chow2;for(int Eyes2 = Eyes1; Eyes2 < 2; ++Eyes2) {int rst = val - Chow1 - Chow2;if(!Eyes1 && Eyes2) rst -= 2;if(rst < 0) continue;int nxt = Eyes2 * 9 + Chow2 * 3 + rst % 3;this->set(nxt, now);}}}}}void set(int r, int c) { row[r] |= 1 << c, col[c] |= 1 << r; }matrix operator * (const matrix &m) {matrix res;for(int i = 0; i < 18; ++i) for(int j = 0; j < 18; ++j) if(row[i] & m.col[j]) res.set(i, j);return res;}int row[18], col[18];
}t[maxn << 2];
void build(int d, int l, int r) {t[d] = matrix(0);if(l == r) return;int md = l + r >> 1;build(d << 1, l, md), build(d << 1 | 1, md + 1, r);
}
void modify(int d, int l, int r, int des, int val) {if(l == r) return t[d] = matrix(val), void();int md = l + r >> 1;if(des <= md) modify(d << 1, l, md, des, val);else modify(d << 1 | 1, md + 1, r, des, val);t[d] = t[d << 1] * t[d << 1 | 1];
}
inline void solve() {cin >> n, tot = 0;for(int i = 1; i <= n; ++i) cin >> a[i], b[++tot] = a[i], b[++tot] = a[i] + 1;sort(b + 1, b + 1 + tot), tot = unique(b + 1, b + 1 + tot) - b - 1;for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;build(1, 1, tot);for(int i = 1; i <= tot; ++i) cnt[i] = 0;for(int i = 1; i <= n; ++i) {modify(1, 1, tot, a[i], ++cnt[a[i]]);if(t[1].row[9] & 1) cout << 1;else cout << 0;}cout << '\n';
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> T;while(T--) solve();return 0;
}G Hard Brackets Problem
发现如果合法的话，直接照着结果打就可以打出来。不合法的情况就是模拟到最后还有未匹配的左括号。
#include <bits/stdc++.h>
using namespace std;
int T;
string s;
inline void solve() {cin >> s;string ans;int now = 0;for(int i = 0; i < s.size(); ++i) {if(s[i] == '(') ++now, ans += '(';else {if(now) --now;ans += ')';}}if(now) cout << "impossible\n";else cout << ans << '\n';
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> T;while(T--) solve();return 0;
}H Sweet Sugar
容易有一个贪心思路：dfs 一遍，当前子树能凑出 \(k\) 时，就凑一个 \(k\)。
在一般情况下，随便换个根这种思路的答案就变了。但这题发现 \(0\leq c\leq 2\)，可以推导出如果子树中能表示出的最大的与 \(k\) 同奇偶的数大于等于 \(k\)，则一定能凑出 \(k\)，进而推导出这种贪心思路是正确的。
所以思路就是，设 \(f_{u,0/1}\) 表示 \(u\) 的子树中，能表示出的最大奇数/偶数是多少。如果 \(f_{u,k\% 2}\geq k\)，则答案加一并将 \(f_u\) 重置。注意重置的时候应该置为一个特殊值 \((-1)\) 并且转移的时候特判，而不能简单地置 \(0\)，否则可能会出现“最大的奇数是 \(2\)”这种情况。
复杂度 \(\mathcal O(n)\)。
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
int f[N][2],a[N],n,k,ans;
vector<int> g[N];
void dfs(int x,int fa){int y=a[x]%2;f[x][y]=a[x];f[x][y^1]=-1;for(int v:g[x]){if(v==fa){continue;}dfs(v,x);int tmp[2]={f[x][0],f[x][1]};if(~f[v][0] && ~tmp[0]) f[x][0]=max(f[x][0],tmp[0]+f[v][0]);if(~f[v][0] && ~tmp[1]) f[x][1]=max(f[x][1],tmp[1]+f[v][0]);if(~f[v][1] && ~tmp[0]) f[x][1]=max(f[x][1],tmp[0]+f[v][1]);if(~f[v][1] && ~tmp[1]) f[x][0]=max(f[x][0],tmp[1]+f[v][1]);}if(f[x][k&1]>=k){++ans;f[x][0]=f[x][1]=-1;}
}
inline void solve(){cin>>n>>k;for(int i=1;i<=n;++i){cin>>a[i];}for(int i=1;i<n;++i){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);}dfs(1,0);cout<<ans<<'\n';ans=0;for(int i=1;i<=n;++i){g[i].clear();f[i][0]=f[i][1]=0;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){solve();}
}I Barkley II
转化为枚举每个数没有出现的极大区间，计算区间中数的个数-这个数。可以发现如果这个数并不是区间 \(\text{mex}\)，答案会小于枚举到真实 \(\text{mex}\) 的情况，而且一定能够枚举到真实的 \(\text{mex}\)。所以直接这么做就行。最后需要特判 \(\text{mex}\) 在 \(a\) 中没出现过的情况。
复杂度 \(\mathcal O(n\log n)\)。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, maxn = 500010;
int pre[maxn];
class BIT : public vector<int> {
public:BIT() {}BIT(int n) : vector<int>(n + 1) {}void mdf(int x, int v) { for(; x < this->size(); x += x & -x) (*this)[x] += v; }int ask(int x, int ans = 0) {for(; x; x -= x & -x) ans += (*this)[x];return ans;}
};
inline void solve() {int n, m;cin >> n >> m;vector<int> a(n + 1);for(int i = 1; i <= n; ++i) cin >> a[i];BIT bit(n);int ans = -inf;for(int i = 1; i <= n; ++i) {if(pre[a[i]] < i - 1) ans = max(ans, bit.ask(i - 1) - bit.ask(pre[a[i]]) - a[i]);if(pre[a[i]]) bit.mdf(pre[a[i]], -1);pre[a[i]] = i, bit.mdf(i, 1);}for(int i = 1; i <= n; ++i) if(pre[a[i]] < n) ans = max(ans, bit.ask(n) - bit.ask(pre[a[i]]) - a[i]);for(int i = 1; i <= m + 1; ++i) if(!pre[i]) {ans = max(ans, bit.ask(n) - i);break;}cout << ans << '\n';for(int i = 1; i <= n; ++i) pre[a[i]] = 0;
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);int T;cin >> T;while(T--) solve();return 0;
}J The Phantom Menace
容易想到是建图然后跑欧拉回路，但就是很难写。
首先判断不用循环移位就能相等的情况。那就是将 \(a,b\) 中的字符串分别排序，从小到大判断是否对应相等即可。
否则，枚举循环移位了几位，假设是 \(d\) 位，那么将 \(a\) 中所有长度为 \(m-d\) 的后缀和 \(b\) 中所有长度为 \(m-d\) 的前缀拿出来排序去重，去重之后将每种字符串作为一个新点，将对应的 \(a\) 中的串连一条边过来，再向 \(b\) 中对应的字符串连一条边出去。类似地，对 \(a\) 中长度为 \(d\) 的前缀和 \(b\) 中长度为 \(d\) 的后缀也做相同的处理，只不过是从 \(b\) 连到这些字符串再连到 \(a\)。然后跑欧拉回路就行。
上述的排序都可以用后缀数组实现，复杂度 \(\mathcal O(nm\log nm)\)。在 \(\text{QOJ}\) 上跑 \(1s\)，在 \(cf\) 上却 \(\text{TLE}\) 了……
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010, maxm = maxn * 4;
int T, n, m, len, s[maxm];
vector<int> sa, rk, t, x, y, ht, lg, st[22];
int posa[maxn], posb[maxn], pos[maxn * 2], fa[maxn * 2], id[maxn * 2];
int p[maxn], q[maxn], ansp[maxn], ansq[maxn];
string a[maxn], b[maxn];
vector<int> g[maxm];
int head[maxm], deg[maxm], stk[maxm], tp;
inline void sa_init() {sa.resize(max(len, n * 2 + 26) + 1);rk.resize(len + 1);t.resize(max(len, n * 2 + 26) + 1);x.resize(len + 1);y.resize(len + 1);ht.resize(len + 1);lg.resize(len + 1);for(int i = 0; i < 22; ++i) st[i].resize(len + 1);int cnt = n * 2 + 26;for(int i = 1; i <= cnt; ++i) t[i] = 0;for(int i = 1; i <= len; ++i) ++t[x[i] = s[i] + 1];for(int i = 1; i <= cnt; ++i) t[i] += t[i - 1];for(int i = len; i; --i) sa[t[x[i]]--] = i;for(int k = 1; k <= len; k <<= 1) {for(int i = 1; i <= cnt; ++i) t[i] = 0;for(int i = 1; i <= len; ++i) ++t[x[i]];for(int i = 1; i <= cnt; ++i) t[i] += t[i - 1];int cnt2 = 0;for(int i = len - k + 1; i <= len; ++i) y[++cnt2] = i;for(int i = 1; i <= len; ++i) if(sa[i] > k) y[++cnt2] = sa[i] - k;for(int i = len; i; --i) sa[t[x[y[i]]]--] = y[i];for(int i = 1; i <= len; ++i) y[i] = 0;swap(x, y), x[sa[1]] = cnt2 = 1;for(int i = 2; i <= len; ++i) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? cnt2 : ++cnt2;if(cnt2 == len) break;else cnt = cnt2;}cnt = 0;for(int i = 1; i <= len; ++i) rk[sa[i]] = i;for(int i = 1; i <= len; ++i) if(rk[i] > 1) {if(cnt) --cnt;int j = sa[rk[i] - 1];while(i + cnt <= len && j + cnt <= len && s[i + cnt] == s[j + cnt]) ++cnt;ht[rk[i]] = cnt;}for(int i = 2; i <= len; ++i) st[0][i] = ht[i], lg[i] = lg[i >> 1] + 1;for(int j = 0; j < 21; ++j) for(int i = (1 << j + 1) | 1; i <= len; ++i) st[j + 1][i] = min(st[j][i], st[j][i - (1 << j)]);
}
inline int LCP(int x, int y) {if(x == y) return len - x + 1;x = rk[x], y = rk[y];if(x > y) swap(x, y);int l = lg[y - x];return min(st[l][x + (1 << l)], st[l][y]);
}
int getfa(int x) {if(fa[x] == x) return x;return fa[x] = getfa(fa[x]);
}
inline void add(int u, int v) { g[u].push_back(v), ++deg[u], --deg[v]; }
void dfs(int u) {for(int i = head[u]; i < g[u].size(); i = head[u]) ++head[u], dfs(g[u][i]);stk[++tp] = u;
}
inline void solve() {cin >> n >> m, len = 0;for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= n; ++i) cin >> b[i];for(int i = 1; i <= n; ++i) {posa[i] = len + 1;for(int j = 0; j < m; ++j) s[++len] = a[i][j] - 'a';s[++len] = 25 + i;}for(int i = 1; i <= n; ++i) {posb[i] = len + 1;for(int j = 0; j < m; ++j) s[++len] = b[i][j] - 'a';s[++len] = 25 + n + i;}sa_init();for(int i = 1; i <= n; ++i) p[i] = q[i] = i;sort(p + 1, p + 1 + n, [&](int x, int y) {int lcp = LCP(posa[x], posa[y]);return lcp < m && a[x][lcp] < a[y][lcp];});sort(q + 1, q + 1 + n, [&](int x, int y) {int lcp = LCP(posb[x], posb[y]);return lcp < m && b[x][lcp] < b[y][lcp];});bool flag = true, flag2 = false;for(int i = 1; i <= n; ++i) if(LCP(posa[p[i]], posb[q[i]]) < m) flag = false;if(flag) for(int i = 1; i <= n; ++i) ansp[i] = p[i], ansq[i] = q[i];else {for(int d = 1; d < m; ++d) {for(int i = 1; i <= 4 * n; ++i) g[i].clear();memset(head, 0, sizeof(int) * (4 * n + 10));memset(deg, 0, sizeof(int) * (4 * n + 10));int tot = 0;for(int i = 1; i <= 2 * n; ++i) fa[i] = i;for(int i = 1; i <= n; ++i) pos[i] = rk[posa[i] + d], pos[i + n] = rk[posb[i]];sort(pos + 1, pos + 1 + 2 * n);for(int i = 2; i <= n * 2; ++i) if(LCP(sa[pos[i]], sa[pos[i - 1]]) >= m - d) fa[getfa(i)] = getfa(i - 1);for(int i = 1; i <= n * 2; ++i) if(fa[i] == i) id[i] = ++tot;for(int i = 1; i <= n * 2; ++i) {int num = (sa[pos[i]] + m) / (m + 1);if(num <= n) add(num, id[getfa(i)] + n * 2);else add(id[getfa(i)] + n * 2, num);}for(int i = 1; i <= 2 * n; ++i) fa[i] = i;for(int i = 1; i <= n; ++i) pos[i] = rk[posa[i]], pos[i + n] = rk[posb[i] + m - d];sort(pos + 1, pos + 1 + 2 * n);for(int i = 2; i <= n * 2; ++i) if(LCP(sa[pos[i]], sa[pos[i - 1]]) >= d) fa[getfa(i)] = getfa(i - 1);for(int i = 1; i <= n * 2; ++i) if(fa[i] == i) id[i] = ++tot;for(int i = 1; i <= n * 2; ++i) {int num = (sa[pos[i]] + m) / (m + 1);if(num <= n) add(id[getfa(i)] + n * 2, num);else add(num, id[getfa(i)] + n * 2);}bool flag3 = false;for(int i = 1; i <= n * 2 + tot; ++i) if(deg[i]) flag3 = true;if(flag3) continue;tp = 0, dfs(1);if(tp < 4 * n + 1) continue;flag2 = true, reverse(stk + 1, stk + 1 + tp);for(int i = 1; i <= tp; i += 4) ansp[(i + 3) / 4] = stk[i], ansq[(i + 3) / 4] = stk[i + 2] - n;break;}}if(!flag && !flag2) return cout << "-1\n", void();for(int i = 1; i <= n; ++i) cout << ansp[i] << ' '; cout << '\n';for(int i = 1; i <= n; ++i) cout << ansq[i] << ' '; cout << '\n';
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> T;while(T--) solve();return 0;
}K Randias Permutation Task
注意到 \(nm\leq 180\)，所以当 \(m<9\) 时，类似于背包那样做，枚举每一个 \(A\)，再枚举所有的排列，看之前出现的排列通过 \(A\) 能转移出哪些排列。复杂度 \(\mathcal O(nm\times m!\log m!)\)。
当 \(m\geq 9\) 时，\(n\leq 20\)，换成枚举二进制状态，看能做出哪些排列，再去个重。复杂度 \(\mathcal O(2^n\times nm)\)。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 210;
int n, m, a[maxn][maxn];
inline void solve() {cin >> m >> n;for(int i = 0; i < n; ++i) for(int j = 1; j <= m; ++j) cin >> a[i][j];set<vector<int>> st;vector<int> p(m + 1), q(m + 1);if(m >= 9) {for(int s = 1; s < (1 << n); ++s) {for(int i = 1; i <= m; ++i) p[i] = i;for(int i = 0; i < n; ++i) if(s >> i & 1) {for(int j = 1; j <= m; ++j) q[j] = p[a[i][j]];p = q;}st.insert(p);}} else {for(int i = 0; i < n; ++i) {vector<vector<int>> vec;for(auto &p : st) {for(int j = 1; j <= m; ++j) q[j] = p[a[i][j]];vec.push_back(q);}for(auto &p : vec) st.insert(p);for(int j = 1; j <= m; ++j) p[j] = a[i][j];st.insert(p);}}cout << st.size() << '\n';
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}M Flipping Cards
二分答案，然后做类似于最大子段和的事情即可。复杂度 \(\mathcal O(n\log a_i)\)。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010, inf = 0x3f3f3f3f;
int n, a[maxn], b[maxn], s[maxn];
inline bool check(int x) {for(int i = 1; i <= n; ++i) {if(a[i] >= x && b[i] >= x) s[i] = 0;else if(a[i] >= x) s[i] = -1;else if(b[i] >= x) s[i] = 1;else s[i] = 0;}for(int i = 1; i <= n; ++i) s[i] += s[i - 1];int mn = 0, ans = 0;for(int i = 1; i <= n; ++i) ans = max(ans, s[i] - mn), mn = min(s[i], mn);for(int i = 1; i <= n; ++i) ans += a[i] >= x;return ans >= (n + 1) / 2;
}
int main() {ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];int mn = inf, mx = 0;for(int i = 1; i <= n; ++i) mx = max({mx, a[i], b[i]}), mn = min({mn, a[i], b[i]});int l = mn, r = mx, res = 0;while(l <= r) {int md = l + r >> 1;if(check(md)) res = md, l = md + 1;else r = md - 1;}cout << res << '\n';return 0;
}
