杂题乱做3
都是学长的推题！
P12421 【MX-X12-T4】「ALFR Round 5」游戏
注意到 \(n\) 个点的树，最多只能查询 \(n - 1\) 次，所以考虑每次至少排除一个点的做法。
考虑每次对着叶子操作，那么如果返回的是距离，就可以排除这个叶子或者确定这个叶子是答案；否则如果向叶子走了一步，就说明除这个叶子外的其它叶子都不是答案，就可以排除掉很多点。
然后变成模拟题，代码有点恶心，注意特判 \(n = 1\)。
const int N = 100010;
int T, n, m, degs[N], fa[N];
bool vis[N];
vector<int> G[N];
queue<int> q;
void addedge(int a, int b) {
G[a].push_back(b); degs[a] ++;
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) G[i].clear();
memset(degs, 0, sizeof degs);
for (int i = 1; i < n; i ++) {
int a, b; cin >> a >> b;
addedge(a, b); addedge(b, a);
}
while (!q.empty()) q.pop();
for (int i = 1; i <= n; i ++) if (degs[i] == 1) q.push(i);
if (q.size() < 1) {
cout << "! 1" << endl;
int res; cin >> res;
if (res == 1) return;
else exit(0);
return;
}
// for (int i = 1; i <= n; i ++) cout << degs[i] << ' ';
while(q.size() > 1) {
int t = q.front(); q.pop();
cout << "? " << t << endl;
int op; cin >> op;
if (op == 1) {
vector<int> p;
while (!q.empty()) {
int u = q.front();
for (auto v : G[u])
if (-- degs[v] == 1)
p.push_back(v);
q.pop();
}
q.push(t); for (auto x : p) q.push(x);
} else {
int d; cin >> d;
if (d == 0) {
cout << "! " << t << endl;
int res; cin >> res;
if (res == 1) return;
else exit(0);
}
for (auto v : G[t])
if (-- degs[v] == 1)
q.push(v);
}
}
cout << "! " << q.front() << endl;
int res; cin >> res;
if (res == 1) return;
else exit(0);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> T;
while (T --) solve();
return 0;
}
CF2101C 23 Kingdom
考虑对于一个数 \(x\)，它的贡献是 \(\max(x) - \min(x)\)，其中 \(\max(x)\) 为 \(x\) 最后一次出现的位置，\(\min(x)\) 同理。
所以答案类似于 \((\max(x) + \max(y) + \max(z)) - (\min(x) + \min(y) + \min(z))\)。注意到 \(x, y, z\) 一定是按照 \(1, 2, 3, ...\) 的顺序取的，否则不优。
于是我们考虑处理出 \(pre_k\) 表示 \(1 \sim k\) 需要 \(a\) 中的前多少个数才能表示出来，\(suf_k\) 同理。计算时考虑贪心，对于每个 \(a_i\) 取 \(\leq a_i\) 的第一个没取过的数，然后就可以算答案了。
const int N = 200010;
int T, n, a[N], pre[N], suf[N];
void solve() {
n = read();
for (int i = 1; i <= n; i ++) a[i] = read();
for (int i = 1; i <= n; i ++) pre[i] = suf[i] = 0;
set<int> s; int u = 0;
for (int i = 1; i <= n; i ++) s.insert(i);
for (int i = 1; i <= n; i ++) {
auto it = s.upper_bound(a[i]);
if (it == s.begin()) continue;
pre[++ u] = i; s.erase(-- it);
}
u = 0; s.clear();
for (int i = 1; i <= n; i ++) s.insert(i);
for (int i = n; i >= 1; i --) {
auto it = s.upper_bound(a[i]);
if (it == s.begin()) continue;
suf[++ u] = i; s.erase(-- it);
}
LL ans = 0;
for (int i = 1; i <= n; i ++) {
if (pre[i] >= suf[i]) break;
ans += suf[i] - pre[i];
}
printf("%lld\n", ans);
}
int main() {
T = read();
while (T --) solve();
return 0;
}
CF2097C Bermuda Triangle
这个折射很明显很困难，硬做的话就变成计算几何了，而且也不好做，我们不妨进行对称，这是一个很妙的套路。
这是 CF 的官图，我懒得画就这样了，容易发现我们只要计算在到达一个顶点前经过多少条边即可。
考虑先计算出顶点，设顶点坐标为 \((x + v_x \times T, y + v_y \times T)\)，那么有 \(n | x + v_x \times T\) 且 \(n | y + v_y \times T\)。
容易通过 exgcd 分别求出两个方程的特解 \(T_1, T_2\)，那么通过同余方程的通解形式容易有：
\[T_1 + k_1 \times \frac{n}{\gcd(n, v_x)} = T_2 + k_2 \times \frac{n}{\gcd(n, v_y)}
\]
你会发现这个东西可以写成 \(ax + by = c\) 的形式，于是继续 exgcd 即可。
然后你就求出来了顶点坐标 \((n \times a, n \times b)\)，于是只需要计算答案即可。
计算答案简单分类讨论一下，分为两种对角线，横边和竖边，公式我懒得写，看代码吧。
注意爆 long long，需要 __int128。
#include <bits/stdc++.h>
using namespace std;
#define int __int128
typedef long long LL;
int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
int T, n, x, y, vx, vy;
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1, y = 0; return; }
exgcd(b, a % b, x, y);
int _x = x, _y = y;
x = _y, y = _x - a / b * _y;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int mabs(int a) { return a > 0 ? a : -a; }
void solve() {
n = read(), x = read(), y = read(), vx = read(), vy = read();
int g = gcd(vx, vy); vx /= g, vy /= g;
int gx = gcd(vx, n), gy = gcd(vy, n);
if (x % gx != 0 || y % gy != 0) { puts("-1"); return; }
int tx, ty, px, py; exgcd(vx / gx, n / gx, tx, px); exgcd(vy / gy, n / gy, ty, py);
tx *= -x / gx, ty *= -y / gy;
if (mabs(ty - tx) % gcd(n / gx, n / gy) != 0) { puts("-1"); return; }
int G = gcd(n / gx, n / gy);
int k, p; exgcd(n / gx / G, n / gy / G, k, p);
p = -p, k *= (ty - tx) / G;
int T = tx + n / gx * k; T = (T % n + n) % n;
int X = vx * T + x, Y = vy * T + y;
LL ans = X / n - 1 + Y / n - 1 + (X / n + Y / n) / 2 + mabs(X / n - Y / n) / 2;
printf("%lld\n", ans);
}
signed main() {
T = read();
while (T --) solve();
return 0;
}
CF2097D Homework
首先发现题目给出的操作相当于异或，不妨设 \(n = mk\)，其中 \(m\) 是把 \(n\) 不断分到长度为奇数为止后的长度。
然后你会发现交换两个相邻的段 \(x_1, x_2\)是容易的，但这个性质很弱，考虑将它推广。不妨大胆猜想可以任意交换。
证明我们考虑采用类似二进制分解的方法交换，我们这里先证明 \(i\) 可以异或到 \(i + 2^{k - 1}\)，即对于 \(a_0, a_1, ... |b_0, b_1, ...\) 可以将 \(b_0\) 赋值成 \(a_0 \oplus b_0\)（对于 \(i\) 的情况只要再与 \(0\) 进行一下交换即可）。
先归纳一下，当 \(k = 1\) 时成立。现在证明对于 \(k > 1\) 的情况。
\[a_0, a_1, ... |b_0, b_1, ...
\]
\[a_0 \oplus a_1, a_0, ... |b_0, b_1, ...
\]
\[a_0 \oplus a_1, a_0, ... |b_0 \oplus a_0 \oplus a_1, b_1 \oplus a_0, ...
\]
\[a_0 \oplus a_1, a_0, ... |b_0 \oplus b_1 \oplus a_1, b_1 \oplus a_0, ...
\]
\[a_0 \oplus a_1, a_0, ... |b_0 \oplus b_1 \oplus a_0, b_1, ...
\]
\[a_0, a_1, ... | b_0 \oplus a_0, b_1, ...
\]
得证。
所以我们不妨考虑将 \(s\) 和 \(t\) 写成 \(m \times k\) 的矩阵，这样子操作就相当于矩阵变换，我们直接高斯消元后判断两个矩阵是否相等即可。
const int N = 1000010;
int T, n, m, l;
char s[N], t[N];
inline int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a;
b >>= 1; a = a * a;
}
return res;
}
void solve() {
l = n = read(); scanf("%s%s", s, t);
m = 0; while (n % 2 == 0) m ++, n /= 2; m = qmi(2, m); swap(n, m);
vector<vector<int>> a(n, vector<int>(m)), b(n, vector<int>(m));
for (int i = 0; i < l; i ++) a[i / m][i % m] = s[i] - '0', b[i / m][i % m] = t[i] - '0';
int p = 0;
for (int i = 0; i < m; i ++) {
int q = p;
while (q < n && !a[q][i]) q ++;
if (q >= n) continue;
swap(a[p], a[q]);
for (int j = 0; j < n; j ++)
if (a[j][i] && j != p)
for (int k = i; k < m; k ++)
a[j][k] ^= a[p][k];
p ++;
}
p = 0;
for (int i = 0; i < m; i ++) {
int q = p;
while (q < n && !b[q][i]) q ++;
if (q >= n) continue;
swap(b[p], b[q]);
for (int j = 0; j < n; j ++)
if (b[j][i] && j != p)
for (int k = i; k < m; k ++)
b[j][k] ^= b[p][k];
p ++;
}
bool flag = true;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (a[i][j] != b[i][j]) flag = false;
puts(flag ? "Yes" : "No");
}
int main() {
T = read();
while (T --) solve();
return 0;
}
P11954 「ZHQOI R1」删边
边界情况恶心的要死的神秘构造题。
首先对于一个有环图来说把环断开即可，如果无法断开环满足题目条件就无解。然后会发现如果是一棵树就会出问题。对于树，找一条两头度数都大于 \(1\) 的边删掉即可。所以菊花就无解。
然后还有一个情况是 \(n \leq 3\) 时就无解。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 500010;
int n, m;
int h[N], e[N << 1], ne[N << 1], idx, degs[N];
bool vis[N];
vector<int> p;
bool st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++, degs[b] ++;
}
void dfs1(int u, int fa) {
vis[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i]; if (v == fa || vis[v]) continue;
dfs1(v, u);
}
}
bool valid() {
dfs1(1, 0);
bool f = false;
for (int i = 1; i <= n; i ++) {
if (!vis[i]) return false;
if (!degs[i]) f = true;
}
return f;
}
bool flower() {
for (int i = 1; i <= n; i ++)
if (degs[i] == n - 1) return true;
return false;
}
void dfs2(int u) {
p.push_back(u); st[u] = true;
bool f = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i]; if (st[v]) continue;
if (--degs[v] == 0) f = false;
}
if (!f) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i]; if (st[v] || degs[v]) continue;
dfs2(v);
}
}
}
int main() {
n = read(), m = read(); memset(h, -1, sizeof h);
for (int i = 1; i <= m; i ++) {
int a = read(), b = read();
add(a, b); add(b, a);
}
if (n <= 3) { puts("-1"); return 0; }
else {
if (valid()) { puts("0"); return 0; }
else if (m == n - 1) {
if (flower()) { puts("-1"); return 0; }
for (int i = 0; i < idx; i += 2) {
int b = e[i], a = e[i ^ 1];
if (degs[a] == 1 || degs[b] == 1) continue;
puts("1");
printf("%d %d\n", a, b);
return 0;
}
} else {
dfs2(1);
if (p.size() >= n - 1) { puts("-1"); return 0; }
if (p.size() == 1) {
for (int i = h[1]; ~i; i = ne[i]) {
int v = e[i]; if (st[v]) continue;
dfs2(v);
if (p.size() < n - 1) break;
p.clear(); p.push_back(1);
}
}
vector<PII> ans;
map<PII, bool> H;
for (auto u : p) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i]; if (st[v] || H.count({u, v})) continue;
ans.push_back({u, v}); H[{u, v}] = true;
}
}
printf("%d\n", ans.size());
for (auto x : ans) printf("%d %d\n", x.first, x.second);
}
}
return 0;
}
P12543 [APIO2025] Rotating Lines
考虑当 \(n = 2\) 时一定垂直更优，之后考虑加边，会发现每一条边对于垂直的两条线贡献和都是 \(90\)，所以之要让剩下的线最大化即可。容易发现终态一定是两两垂直。
然后考虑构造一个方案，将所有边按照辐角排序然后将 \(i + \frac{n}{2}\) 调整和 \(i\) 垂直，这样一定满足每次操作都不会变得更劣。
考虑证明，首先已经垂直的边不管怎样都是 \(90\)，那么我们考虑 \(i \sim \frac{n}{2}\) 和 \(i + \frac{n}{2} \sim n\)，此时把 \(i + \frac{n}{2}\) 转 \(\theta\) 度的后面一段全体贡献加上 \(\theta\)，前面一段有加有减，并且都不会超过 \(\theta\)，于是这么做一定不会更劣。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
void rotate(vector<int> t, int x);
const int N = 100010, Mod = 50000;
int n, a[N], p[N];
bool cmp(int x, int y) { return a[x] < a[y]; }
void energy(int _n, vector<int> v) {
n = _n;
for (int i = 1; i <= n; i ++) a[i] = v[i - 1], p[i] = i;
sort(p + 1, p + 1 + n, cmp);
for (int i = 1, j = n / 2 + 1; i <= n / 2; i ++, j ++) {
vector<int> t; t.push_back(p[j] - 1);
rotate(t, ((25000 - (a[p[j]] - a[p[i]])) % Mod + Mod) % Mod);
}
}
P12179 DerrickLo's Game (UBC002B)
有点诈骗。
由于我们只能增加，所以要将一段区间全部变成最大值。考虑操作 \(2\) 我们只会两个两个做，因为 \(4(len - 1) \leq len ^ 2\)。那么只有当一个位置上的数与最大值相差小于 \(4\) 时才会操作 \(1\)，所以答案就是 \(\sum_{i = l}^{r} \min(4, mx - a_i)\)。
\(log\) 查询显然要用数据结构维护，观察到 \(a_i\) 范围比较小于是考虑动态开点权值线段树，再开一棵线段树维护最大值。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 400010;
int n, q, w[N];
struct Node { int l, r, v; };
struct Segment_Tree {
Node tr[N << 2];
void pushup(int u) {
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r) {
tr[u] = {l, r, 0};
if (l == r) { tr[u].v = w[l]; return; }
int mid = l + r >> 1;
build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int x, int v) {
if (tr[u].l == tr[u].r) { tr[u].v = v; return; }
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].v;
int mid = tr[u].l + tr[u].r >> 1, res = 0;
if (l <= mid) res = max(res, query(u << 1, l, r));
if (r > mid) res = max(res, query(u << 1 | 1, l, r));
return res;
}
} sgt;
Node tr[N << 6];
int rt[N], idx;
void pushup(int u) {
tr[u].v = tr[tr[u].l].v + tr[tr[u].r].v;
}
void modify(int &u, int l, int r, int x, int v) {
if (!u) u = ++ idx;
if (l == r) { tr[u].v += v; return; }
int mid = l + r >> 1;
if (x <= mid) modify(tr[u].l, l, mid, x, v);
else modify(tr[u].r, mid + 1, r, x, v);
pushup(u);
}
int query(int u, int l, int r, int cl, int cr) {
if (!u) return 0;
if (cl <= l && r <= cr) return tr[u].v;
int mid = l + r >> 1, res = 0;
if (cl <= mid) res += query(tr[u].l, l, mid, cl, cr);
if (cr > mid) res += query(tr[u].r, mid + 1, r, cl, cr);
return res;
}
int main() {
n = read(), q = read();
for (int i = 1; i <= n; i ++) w[i] = read();
sgt.build(1, 1, n);
for (int i = 1; i <= n; i ++) modify(rt[w[i]], 1, n, i, 1);
while (q --) {
int op = read();
if (op == 1) {
int k = read(), x = read();
modify(rt[w[k]], 1, n, k, -1); w[k] = x;
modify(rt[w[k]], 1, n, k, 1);
sgt.modify(1, k, w[k]);
} else {
int l = read(), r = read();
int maxv = sgt.query(1, l, r), res = 4 * (r - l + 1);
// cout << maxv << endl;
for (int i = maxv; i >= max(maxv - 3, 1); i --) {
int k = 4 - (maxv - i);
res -= k * query(rt[i], 1, n, l, r);
// cout << k << ' ' << query(rt[i], 1, n, l, r) << endl;
}
printf("%d\n", res);
}
}
return 0;
}
P12002 吃猫粮的玉桂狗
考虑正着做要存储每个猫粮用了多少，太困难了。考虑做个容斥，算出所有的方案数减去放大于 \(c_i\) 的猫粮的方案数。此时你会发现由于 \(c_i \geq \lfloor \frac{n}{2} \rfloor\)，所以最多只可能有一种猫粮违反规则。不妨枚举这种猫粮，然后开始计数。
设 \(f_{u, x, c}\) 表示在 \(u\) 子树内，点 \(u\) 选了猫粮 \(x\)，然后要违反的猫粮选了 \(c\) 个。这是一个书上背包的形式，有 \(f_{u, x, c_1 + c_2} = \sum f_{u, x, c_1} \times f_{v, y, c_2}\)，注意这个 \(f_{u, x, c_1}\) 不是全局的方案而是当前算完 \(v\) 前面的子树得到的答案，同时还要注意 \((u, v)\) 要满足限制。
然后考虑所有的方案数计数，设 \(f_{u, x}\) 表示 \(u\) 子树内 \(u\) 选 \(x\) 的方案数，那么有 \(f_{u, x} = \prod_{v}\sum_{c = 1}^{m}f_{v, c}\)。注意这里的 \((u, v)\) 也要满足限制。
然后做完了，初值和递推顺序要稍微斟酌一下。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 55, Mod = 353442899;
int n, m, t;
int c[N], ban[N][N];
int g[N][N], f[N][N][N], sz[N];
int h[N], e[N << 1], ne[N << 1], idx;
inline int add(int a, int b) { return (a + b) % Mod; }
inline int mul(int a, int b) { return 1ll * a * b % Mod; }
void addedge(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs1(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i]; if (v == fa) continue;
dfs1(v, u);
}
for (int c = 1; c <= m; c ++) {
int res = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i], s = 0; if (v == fa) continue;
for (int p = 1; p <= m; p ++)
if (!ban[c][p]) s = add(s, g[v][p]);
res = mul(res, s);
}
g[u][c] = res;
}
}
void dfs2(int u, int fa, int x) {
sz[u] = 1;
for (int i = 1; i <= m; i ++) f[u][i][0] = 1;
f[u][x][1] = 1, f[u][x][0] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i]; if (v == fa) continue;
dfs2(v, u, x);
for (int p = 1; p <= m; p ++) {
vector<int> sf(sz[u] + sz[v] + 1, 0);
for (int q = 1; q <= m; q ++)
if (!ban[p][q])
for (int j = 0; j <= sz[u]; j ++)
for (int k = 0; k <= sz[v]; k ++)
sf[j + k] = add(sf[j + k], mul(f[v][q][k], f[u][p][j]));
for (int j = 0; j <= sz[u] + sz[v]; j ++) f[u][p][j] = sf[j];
}
sz[u] += sz[v];
}
}
int main() {
n = read(), m = read(), t = read();
for (int i = 1; i <= m; i ++) c[i] = read();
memset(h, -1, sizeof h);
for (int i = 1; i < n; i ++) {
int a = read(), b = read();
addedge(a, b); addedge(b, a);
}
while (t --) {
int a = read(), b = read();
ban[a][b] = 1;
}
dfs1(1, -1); int ans = 0;
for (int i = 1; i <= m; i ++) ans = add(ans, g[1][i]);
int S = 0;
for (int i = 1; i <= m; i ++) {
memset(f, 0, sizeof f);
dfs2(1, -1, i);
for (int p = 1; p <= m; p ++)
for (int j = c[i] + 1; j <= n; j ++)
S = add(S, f[1][p][j]);
}
ans = ((ans - S) % Mod + Mod) % Mod;
printf("%d\n", ans);
return 0;
}
P12009 【MX-X10-T5】[LSOT-4] Masuko or Haru？ - 洛谷
我感觉这个题真的很困难，我不敢说我写的一定是对的。
考虑先将区间异或转化成差分，变成两个单点的操作。然后非常有意思的一步，将单点操作的 \(l\) 向 \(r\) 连边，这样你会得到一个树形结构。你会发现如果同时存在 \((l, x)\) 和 \((l, y)\) 的话你就可以 拥有操作 \((x, y)\) 了，所以这相当于 \((l, x)\) 和 \((x, y)\) 同时连边。这样连下去你会发现可以从叶子结点开始决定一个连通块内每个结点的数值，但你没有办法操作根结点。
那么我们在判断两个串能否通过操作相等时只需要看看根节点是否一致即可。不妨将除根节点外的值变成 \(0\) 然后算个哈希即可。
至于维护这个树形结构用一个并查集即可。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
typedef unsigned long long ULL;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 10000010, P = 13331;
int n, m, q, t[N], rt[N];
char s[N];
ULL p[N], h[N];
struct DSU {
int fa[N], sz[N];
void init() {
for (int i = 1; i <= m + 1; i ++)
fa[i] = i, sz[i] = 0;
}
int find(int x) {
if (fa[x] == x) return fa[x];
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
fa[y] = x, sz[x] += sz[y], rt[x] |= rt[y];
}
} dsu;
int main() {
n = read(), m = read(), q = read(); dsu.init();
scanf("%s", s + 1);
p[0] = 1;
for (int i = 1; i <= m + 1; i ++) p[i] = p[i - 1] * P, rt[i] = i;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) t[(i - 1) * m + j] = s[(i - 1) * m + j] - '0';
for (int j = m; j > 1; j --) t[(i - 1) * m + j] = t[(i - 1) * m + j] != t[(i - 1) * m + j - 1];
h[i] = 0;
for (int j = 1; j <= m; j ++) h[i] = h[i] * P + t[(i - 1) * m + j];
}
while (q --) {
int op = read(), l = read(), r = read();
if (op == 1) {
l = dsu.find(l), r = dsu.find(r + 1);
if (l == r) continue;
if (rt[l] > rt[r]) swap(l, r);
int x = rt[l], y = rt[r]; rt[l] = 0; dsu.merge(l, r);
for (int i = 1; i <= n; i ++) {
if (t[(i - 1) * m + x]) {
h[i] -= t[(i - 1) * m + x] * p[m - x];
t[(i - 1) * m + x] ^= 1;
if (y <= m) {
h[i] -= t[(i - 1) * m + y] * p[m - y];
t[(i - 1) * m + y] ^= 1;
h[i] += t[(i - 1) * m + y] * p[m - y];
}
}
}
} else {
puts(h[l] == h[r] ? "Masuko" : "Haru");
}
}
return 0;
}
P12444 [COTS 2025] 发好奖 / Hijerarhija - 洛谷
注意到每个人得到的奖金只可能是 \(0\) 或 \(1\) 或 \(c_i\)，设 \(F_{u, j}\) 为点 \(u\) 选 \(j\)，直接 \(O(n ^ 3)\) 的 DP 是容易的，但是发现很难优化。
这时候有一个很神秘的技巧，你会发现一个点能选需要它到根节点的链上都至少选 \(1\)，于是我们考虑处理出 DFS 序。
设 \(F_{i, j}\) 为 DFS 序在 \([1, i]\) 中的点代价为 \(j\) 的最大值。那么如果当前 \(i\) 填 \(0\) 就直接跳过这棵子树到 \(F_{i + sz_i, j}\)，否则如果至少填了 \(1\) 就可以转移到 \(F_{i + 1, j}\)。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 5010;
int n, k, p[N], c[N];
vector<int> G[N];
int dfn[N], sz[N], f[N][N], timestamp;
void add(int a, int b) { G[a].push_back(b); }
void dfs(int u) {
dfn[++ timestamp] = u, sz[u] = 1;
for (auto v : G[u]) dfs(v), sz[u] += sz[v];
}
int main() {
n = read(), k = read();
for (int i = 2; i <= n; i ++) add(read(), i);
for (int i = 1; i <= n; i ++) p[i] = read();
for (int i = 1; i <= n; i ++) c[i] = read();
dfs(1);
memset(f, -0x3f, sizeof f); f[1][0] = 0;
for (int i = 1; i <= n; i ++) {
int u = dfn[i];
for (int j = 0; j <= k; j ++) {
f[i + sz[u]][j] = max(f[i + sz[u]][j], f[i][j]);
if (j + 1 <= k) f[i + 1][j + 1] = max(f[i + 1][j + 1], f[i][j]);
if (j + c[u] <= k) f[i + 1][j + c[u]] = max(f[i + 1][j + c[u]], f[i][j] + p[u]);
}
}
int ans = 0;
for (int i = 0; i <= k; i ++) ans = max(ans, f[n + 1][i]);
printf("%d\n", ans);
return 0;
}
P11225 [COTS 2019] 疏散 Sklonište - 洛谷
首先对于每个 \(A_i\) 拆成 \(S_i\) 个容量为 \(1\) 的点，然后就变成了一个二分图的问题。
然后考虑预处理出最短路径后进行二分，每次只连小于限制的边，转化为判定问题。即我们以所有非关键点为左部点，拆完点后的关键点为右部点，要求一个完美匹配。
根据 Hall 定理，对于每个左部点集 \(S\) 和它们的邻域集合 \(N(S)\) 则存在完美匹配当且仅当对于所有的 \(S\) 都有 \(|N(S)| \geq |S|\)。
直接枚举左部点集合不好做，但你会发现对于 \(S\) 的邻域要么不包含，要么完全包含拆完点后的某个 \(A_i\) 。这样子右部点的数量 \(\leq 17\) 所以直接枚举右部点，对于每个右部点集合找出包含它的最大左部点集合。这可以通过一个 SOSDP 也就是状压 DP 解决。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 1000010, M = 20;
int n, m, k;
int h[N], e[N], ne[N], w[N], idx;
int d[N][M], f[1 << M], vis[N], a[N], s[N];
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
void dijkstra(int st) {
priority_queue<PII, vector<PII>, greater<PII>> q;
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; i ++) d[i][st] = 1e18;
d[a[st]][st] = 0; q.push({0, a[st]});
while (q.size()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (d[v][st] > d[u][st] + w[i]) {
d[v][st] = d[u][st] + w[i];
q.push({d[v][st], v});
}
}
}
}
bool check(int limit) {
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++) {
int state = 0;
for (int j = 1; j <= k; j ++)
if (d[i][j] <= limit) state |= 1 << (j - 1);
f[state] ++;
}
for (int i = 1; i <= k; i ++)
for (int j = 0; j < (1 << k); j ++)
if (j >> (i - 1) & 1) f[j] += f[j ^ (1 << (i - 1))];
for (int i = 0; i < (1 << k); i ++) {
int res = 0;
for (int j = 1; j <= k; j ++)
if (i >> (j - 1) & 1) res += s[j];
if (f[i] > res) return false;
}
return true;
}
signed main() {
n = read(), m = read(), k = read();
memset(h, -1, sizeof h); idx = 0;
while (m --) {
int a = read(), b = read(), c = read();
add(a, b, c); add(b, a, c);
}
for (int i = 1; i <= k; i ++) a[i] = read(), s[i] = read(), dijkstra(i);
int l = 0, r = 1e18;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%lld\n", r);
return 0;
}
P11316 [RMI 2021] 去 M / NoM - 洛谷
极好的计数题，看到第一眼就两眼翻白只能喵喵叫了。
直接算不好算，先做个容斥算所有不合法也就是存在距离为 \(M\) 倍数的点对。设 \(dp_i\) 为有 \(i\) 对不合法的点对，但直接算是不好算的。
但我们会发现距离为 \(M\) 的倍数也就是模 \(M\) 的余数得相同。所以我们不妨考虑算出 \(f_{i, j}\) 表示当前算到模 \(M\) 余 \(i\) 的情况，已经得到了 \(j\) 组点对（余数不一定是 \(i\)）。那么显然有 \(f_{i, j} = \sum_{k}f_{i - 1, j - k}A_{L_i}^{2k}C_{n - (j - k)}^{k}\)。
全部处理完后 \(dp\) 其实也算出来了。但注意我们这么算完后对于每个 \(dp_i\) 除这 \(2i\) 个位置以外其它位置可以随便选，所以方案数还要再乘 \((2n - 2i)!\)。
最后就算总方案数时你会发现 \(dp_0 = (2n)!\) 也就是总方案数，所以答案就是 \(\sum_{i = 0}^{n}(-1)^{i}dp_i\) 。
哦，对了，这样做复杂度其实不是 \(O(n^3)\)，你会发现 \(k\) 有上界 \(\frac{n}{m}\) 总复杂度就是 \(O(m \times n \times \frac{n}{m}) = O(n^2)\)。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 4010, Mod = 1e9 + 7;
int n, m, f[N], fac[N], infac[N], s[N];
IL int add(int a, int b) { return ((a + b) % Mod + Mod) % Mod; }
IL int mul(int a, int b) { return (1ll * a * b % Mod + Mod) % Mod; }
IL int qmi(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = mul(res, a);
b >>= 1; a = mul(a, a);
}
return res;
}
IL int A(int n, int m) { return mul(fac[n], infac[n - m]); }
IL int C(int n, int m) { return mul(mul(fac[n], infac[m]), infac[n - m]); }
int main() {
n = read(), m = read();
fac[0] = infac[0] = 1;
for (int i = 1; i <= n * 2; i ++) fac[i] = mul(fac[i - 1], i), infac[i] = qmi(fac[i], Mod - 2);
for (int i = 1; i <= m; i ++) s[i] = n * 2 / m + (i <= n * 2 % m);
f[0] = 1;
for (int i = 1; i <= m; i ++)
for (int j = n; j >= 0; j --)
for (int k = 1; k <= min(j, s[i] / 2); k ++)
f[j] = add(f[j], mul(mul(f[j - k], A(s[i], 2 * k)), C(n - j + k, k)));
for (int i = 0; i <= n; i ++) f[i] = mul(f[i], fac[n * 2 - i * 2]);
int k = 1, ans = 0;
for (int i = 0; i <= n; i ++, k = -k) ans = add(ans, k * f[i]);
printf("%d\n", ans);
return 0;
}
P11221 [COTS 2019] 序列操作 K-ti - 洛谷
做一个分块，对于每个块内维护模 \(k\) 余数的最大值，这样你每次跳 \(k\) 只会在相同余数上一直跳。然后再维护一个 \(cnt_i\) 为块内元素的个数处理下从一个块跳到另一个块的情况即可。
对于删除操作直接对块内重构一下即可。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define reg register
#define IL inline
typedef long long LL;
typedef std::pair<int, int> PII;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 510, B = 400;
int n, k, a[N * N];
int l[N], r[N], id[N * N], cnt[N], mx[N][N], p[N][N], vis[N * N];
int main() {
n = read(), k = read(); memset(l, -1, sizeof l);
for (int i = 0; i < n; i ++) {
a[i] = read(); id[i] = i / B + 1; cnt[id[i]] ++;
if (l[id[i]] == -1) l[id[i]] = i, r[id[i] - 1] = i - 1;
if (mx[id[i]][(i - l[id[i]] + 1) % k] < a[i])
mx[id[i]][(i - l[id[i]] + 1) % k] = a[i], p[id[i]][(i - l[id[i]] + 1) % k] = i;
}
r[id[n - 1]] = n - 1;
int q = n, m = id[n - 1];
while (q --) {
int x = k - 1, maxv = 0, P = 0;
for (int i = 1; i <= m; i ++) {
int tmp = ((k - x) % k + k) % k;
if (x + cnt[i] >= k && mx[i][tmp] > maxv) maxv = mx[i][tmp], P = p[i][tmp];
x = (x + cnt[i]) % k;
}
printf("%d\n", maxv);
cnt[id[P]] --, vis[P] = 1; x = 0;
for (int i = 0; i < B; i ++) mx[id[P]][i] = 0;
for (int i = l[id[P]]; i <= r[id[P]]; i ++) {
if (vis[i]) continue; x = (x + 1) % k;
if (mx[id[P]][x] < a[i]) mx[id[P]][x] = a[i], p[id[P]][x] = i;
}
}
return 0;
}
浙公网安备 33010602011771号