A. Wallet Exchange
签到，某个人操作的时候只要一方有金币就行，所以最终赢的应该是拿到最后一个硬币的人，当 \(a + b \equiv 1 \pmod 2\) 的时候Alice获胜，否则Bob获胜。
时间复杂度 \(\mathcal{O}(1)\)。
code for A
#include <bits/stdc++.h>
using namespace std;
inline void solve() {
long long a, b; cin >> a >> b;
if((a + b) % 2 == 0) cout << "Bob" << '\n';
else cout << "Alice" << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
B. Plus-Minus Split
签到题。假如最终分成的一堆子区间中的某个子区间同时含有 \(-1\) 和 \(1\)，那么一定含有某一对 \(-1\) 和 \(1\) 是相邻的，将这两个数独立出来变成一个和为 \(0\) 的子区间，对答案的贡献是 \(0\)，剩下的被割开，一定更优。
现在剩下一堆全为 \(1\) 或 \(-1\) 的区间，将一堆 \(1\)（或 \(-1\)）合起来显然不如单独成为一堆长度为 \(1\) 的序列。设 \(a\) 为序列中 \(1\) 的数量，\(b\) 为 \(-1\) 的数量，答案就是 \(|a-b|\)（取出来了 \(\min(a,b)\) 个 \(-1\) 和 \(\min(a,b)\) 个 \(1\) ，消除了它们对答案的贡献）。
时间复杂度 \(\mathcal{O}(n)\)。
code for B
#include <bits/stdc++.h>
using namespace std;
inline void solve() {
int n; cin >> n;
string s; cin >> s; s = "$" + s;
int c = 0;
for(int i = 1; i <= n; i ++)
c += s[i] == '+';
cout << abs(c - (n - c)) << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
C. Grouping Increases
贪心
从左到右扫一遍序列 \(a\)，不断将扫到的元素添加到 \(s\) 或 \(t\) 的末尾。我们只需要知道序列 \(s,t\) 的最后一个数字而非整个序列就可以得到当前添加的元素对答案的贡献了。
分类讨论，不妨设 \(s\) 的最后一个数字为 \(x\)，\(t\) 的最后一个数字为 \(y\)，同时 \(x \le y\)，新加入的数字是 \(z\)。
- 若 \(z \le x\)，将 \(z\) 放到 \(s\) 的末尾。
- 若 \(x < z \le y\)，将 \(z\) 放到 \(t\) 的末尾。
- 若 \(z > y\)，将 \(z\) 放到 \(s\) 的末尾。
正确性读者自证不难，时间复杂度 \(\mathcal{O}(n)\)。
dp
还是从左到右扫，设当前扫到了 \(a_i\)，那么 \(f_{j}\) 表示当前一个序列的末尾元素是 \(a_{i-1}\)，另一个序列的末尾元素是 \(j\) 的最小答案。将 \(a_i\) 放到两个序列中时有转移：
\[\begin{aligned} &f'_j \leftarrow f_j + [a_i > a_{i-1}]\newline &f'_{a_{i-1}} \leftarrow \min_{j=1}^{n} f_j + [j < a_i] \end{aligned}\nonumber \]用一个区间求 \(\min\)，区间加的线段树维护即可，时间复杂度 \(\mathcal{O}(n \log n)\)。
code for C
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int n, A[N];
namespace SegmentTree {
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
long long C[N << 2], tag[N << 2];
inline void maintain(int u) {
C[u] = min(C[lc], C[rc]);
}
inline void Tag(int u, long long x) {
tag[u] += x, C[u] += x;
}
inline void pushdown(int u) {
if(!tag[u]) return;
Tag(lc, tag[u]), Tag(rc, tag[u]);
tag[u] = 0;
}
void Build(int u, int l, int r) {
C[u] = INF, tag[u] = 0;
if(l != r) {
Build(lc, l, mid), Build(rc, mid + 1, r);
maintain(u);
} else if(l == n) C[u] = 0;
}
void Add(int u, int l, int r, int L, int R, long long val) {
if(l >= L && r <= R) return Tag(u, val);
pushdown(u);
if(mid >= L) Add(lc, l, mid, L, R, val);
if(mid < R) Add(rc, mid + 1, r, L, R, val);
maintain(u);
}
long long Ask(int u, int l, int r, int L, int R) {
if(l >= L && r <= R) return C[u];
pushdown(u);
if(mid >= R) return Ask(lc, l, mid, L, R);
if(mid < L) return Ask(rc, mid + 1, r, L, R);
return min(Ask(lc, l, mid, L, R), Ask(rc, mid + 1, r, L, R));
}
#undef lc
#undef rc
#undef mid
}
inline void solve() {
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> A[i];
if(n <= 2) {cout << "0" << '\n'; return; }
SegmentTree::Build(1, 1, n);
for(int i = 2; i <= n; i ++) {
long long x = min(A[i] - 1 >= 1 ? SegmentTree::Ask(1, 1, n, 1, A[i] - 1) + 1 : 1ll * INF, SegmentTree::Ask(1, 1, n, A[i], n));
if(A[i] > A[i - 1])
SegmentTree::Add(1, 1, n, 1, n, 1);
if(x < SegmentTree::Ask(1, 1, n, A[i - 1], A[i - 1]))
SegmentTree::Add(1, 1, n, A[i - 1], A[i - 1], x - SegmentTree::Ask(1, 1, n, A[i - 1], A[i - 1]));
}
cout << SegmentTree::Ask(1, 1, n, 1, n) << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
D. 01 Tree
注意到对于一棵给定的合法树，我们总是可以将某两个深度相同的相邻叶子合并，即删掉 \(a\) 更大的那个（它比较小的那个恰好多 \(1\)），同时改变叶子的相邻关系，直到剩下一个结点，它的 \(a\) 为 \(0\)。
倒过来考虑，每次挑出来一个 \(a\) 最大的叶子 \(u\) 使得：
- 存在一个和 \(u\) 相邻的结点使得其 \(a\) 恰好比 \(u\) 的 \(a\) 少 \(1\)。
然后删掉 \(u\)，不断操作直到剩下一个结点，同时其 \(a\) 为 \(0\)，就可以将该过程逆过来构造出合法的树。假如中途删不动了或者剩下来的结点的 \(a\) 不为 \(0\)，无解。
用堆维护目前可以被删的结点，链表维护相邻关系，时间复杂度 \(\mathcal{O}(n)\)。
code for D
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, A[N], pre[N], nxt[N], in[N];
inline bool check(int u) {
return u >= 1 && u <= n && (A[pre[u]] == A[u] - 1 || A[nxt[u]] == A[u] - 1);
}
inline string solve() {
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> A[i];
for(int i = 1; i <= n; i ++)
pre[i] = i - 1, nxt[i] = i + 1, in[i] = 0;
nxt[0] = 1, pre[n + 1] = n, A[0] = A[n + 1] = -2;
priority_queue<pair<int, int>> Q;
for(int i = 1; i <= n; i ++)
if(check(i)) Q.push({A[i], i}), in[i] = 1;
while(!Q.empty()) {
int u = Q.top().second; Q.pop();
pre[nxt[u]] = pre[u], nxt[pre[u]] = nxt[u];
if(!in[pre[u]] && check(pre[u])) in[pre[u]] = 1, Q.push({A[pre[u]], pre[u]});
if(!in[nxt[u]] && check(nxt[u])) in[nxt[u]] = 1, Q.push({A[nxt[u]], nxt[u]});
}
int siz = 0, minv = n;
for(int i = 1; i <= n; i ++)
minv = min(minv, A[i]), siz += !in[i];
return (siz == 1 && minv == 0 ? "Yes" : "No");
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) cout << solve() << '\n';
return 0;
}
E. Counting Prefixes
考虑先把 \(p_n\) 的那一串 \(1\) 抽出来（原序列一定可以表述为([] 1 [] 1 [] 1 ... [] 1) + (-1 -1 1 ...) 的形式，其中每个[]表示一个和为 \(0\) 的串，我们抽出来的就是左边小括号内、中括号外的那 \(p_n\) 个 \(1\)）。
\(\mathcal{O}(n)\) 枚举右边的和是多少（一定不是正数，同时它加上 \(p_n\) 一定不小于 \(p_1\)，由此得到范围），只需要 \(\mathcal{O}(n)\) 算出此时合法的方案数，就可以 \(\mathcal{O}(n^2)\) 算出来答案了。
首先 \(p\) 的值域肯定要连续，先特判掉不连续的情况，答案为 \(0\)，否则设值域为 \([L,R]\)。
从 \(R\) 到 \(L\) 满足每个值 \(x\) 的出现次数：在某个前缀和为 \(x\) 的位置后面加入-1 1即可让 \(x-1\) 的出现次数加一，\(x\) 的出现次数同时也加一，同时没有改变 \(x+1\) 的出现次数，同时所有的方案都可以被这样生成出来。
于是设目前有 \(t\) 个位置前缀和为 \(x\)，还需要多 \(d\) 个位置，那么隔板法求出来方案数就是 \(\binom{t+d-1}{d-1}\)。
同时，若 \(d < 0\)，无解。
预处理组合数，时间复杂度 \(\mathcal{O}(n^2)\)。
code for E
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, MOD = 998244353;
inline int Plus(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + MOD : a - b; }
inline int ksm(long long a, int b) {
long long r = 1;
for(; b; b >>= 1, a = a * a % MOD)
if(b & 1) r = r * a % MOD;
return r;
}
int fac[N], ifac[N];
inline int C(int a, int b) {return a >= b && b >= 0 ? 1ll * fac[a] * ifac[b] % MOD * ifac[a - b] % MOD : 0; }
int n, p[N], pool[N], *c = pool + (N / 2);
int pool2[N], *d = pool2 + (N / 2);
inline int F(int a, int b) {
return C(b + a - 1, a - 1);
}
inline int calc(int R) {
for(int i = -n - 1; i <= n + 1; i ++) d[i] = 0;
for(int i = 0; i <= max(0, p[n]); i ++) d[i] ++;
for(int i = max(0, p[n]) - 1; i >= max(0, p[n]) - R; i --) d[i] ++;
// for(int i = -n; i <= n; i ++) cerr << d[i] << " \n"[i == n];
int ans = 1;
for(int i = max(0, p[n]); i >= min(0, p[1]); i --) {
if(d[i] > c[i]) return 0;
if(d[i] == c[i]) continue;
ans = 1ll * ans * F(d[i], c[i] - d[i]) % MOD;
d[i - 1] += c[i] - d[i];
}
if(d[min(0, p[1]) - 1] != 0) return 0;
return ans;
}
inline void solve() {
cin >> n;
for(int i = 1; i <= n; i ++) cin >> p[i];
for(int i = -n; i <= n; i ++) c[i] = 0;
for(int i = 1; i <= n; i ++) c[p[i]] ++;
c[0] ++; int minv = min(0, p[1]), maxv = max(0, p[n]);
if(minv == maxv) {cout << "0" << '\n'; return; }
for(int i = minv; i <= maxv; i ++)
if(c[i] == 0) {cout << "0" << '\n'; return; }
int ans = 0;
for(int i = 0; maxv - i >= minv; i ++)
ans = Plus(ans, calc(i));
cout << ans << '\n';
}
inline void init() {
fac[0] = 1;
for(int i = 1; i < N; i ++) fac[i] = 1ll * fac[i - 1] * i % MOD;
ifac[N - 1] = ksm(fac[N - 1], MOD - 2);
for(int i = N - 1; i >= 1; i --) ifac[i - 1] = 1ll * ifac[i] * i % MOD;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
init();
int T; cin >> T;
while(T --) solve();
return 0;
}
F1. Wine Factory (Easy Version)
最终答案就是 \(a\) 的和减去最终剩下的水的数量，而最终剩下的水的数量为
\[\max_{i=1}^{n}\sum_{j=i}^{n}a_j-b_j\nonumber \]用区间加的线段树维护最大值，时间复杂度 \(\mathcal{O}((n+q) \log n)\)。
code for F1
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, q;
long long a[N], b[N], c[N], v[N];
namespace SegmentTree {
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
long long C[N << 2], tag[N << 2];
inline void Tag(int u, long long x) {C[u] += x, tag[u] += x; }
inline void pushdown(int u) {Tag(lc, tag[u]), Tag(rc, tag[u]), tag[u] = 0; }
void Build(int u, int l, int r) {
tag[u] = 0;
if(l != r) {
Build(lc, l, mid), Build(rc, mid + 1, r);
C[u] = max(C[lc], C[rc]);
} else C[u] = v[l];
}
void Add(int u, int l, int r, int L, int R, long long x) {
if(l >= L && r <= R) return Tag(u, x);
pushdown(u);
if(mid >= L) Add(lc, l, mid, L, R, x);
if(mid < R) Add(rc, mid + 1, r, L, R, x);
C[u] = max(C[lc], C[rc]);
}
long long Ask() {return C[1]; }
#undef lc
#undef rc
#undef mid
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> q;
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 ++) cin >> c[i];
for(int i = 1; i <= n; i ++) v[i] = a[i] - b[i];
for(int i = n; i >= 1; i --) v[i] += v[i + 1];
SegmentTree::Build(1, 1, n);
long long sum = 0;
for(int i = 1; i <= n; i ++) sum += a[i];
while(q --) {
int p; long long x, y, z; cin >> p >> x >> y >> z;
SegmentTree::Add(1, 1, n, 1, p, (x - y) - (a[p] - b[p]));
sum = sum - a[p] + x, a[p] = x, b[p] = y;
cout << sum - max(0ll, SegmentTree::Ask()) << '\n';
}
return 0;
}
F2. Wine Factory (Hard Version)
画成下图所示网络流的形式，答案就是 \(S\) 到 \(T\) 的最大流，等于 \(S\) 到 \(T\) 的最小割。
考虑维护这个东西的最小割，先证一个引理：
引理： 一定存在一种最小割，使得每个点 \(u \in [1,n]\)，\(S \to u\) 和 \(u \to T\) 的两边恰有一条被割。
证明： 两条都不被割显然不可以，若必须两条边都被割：
- 只割 \(u \to T\) 不可以，那么必然是有流量从 \(u \to u+1 \to \cdots \to T\)，此时我们就选择只割 \(S \to u\)，必然合法——因为原先的割合法已经保证了不存在 \(u-1 \to u\) 的流量（如果有，这个流量可以顺着之前我们考虑的 \(u \to u + 1 \to \cdots T\) 使 \(S\) 和 \(T\) 连通）。
- 只割 \(u \to T\) 可以，得到方案。
证毕！
于是可以做dp，设 \(f_{l,r,0/1,0/1}\) 表示点 \([l,r]\)，\(l\) 点割了哪条边，\(r\) 点割了哪条边，最小的代价，合并时直接合并，但当左区间的右端点割去了到 \(T\) 的边而右区间的左端点割去了从 \(S\) 的边时，代价需要加上一个 \(c\)，因为有一个 \(S\) 到左区间右端点到右区间左端点到 \(T\) 的一个流量。
线段树维护，时间复杂度 \(\mathcal{O}((n+q) \log n)\)。
code for F2
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, q;
long long a[N], b[N], c[N];
namespace SegmentTree {
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
struct node {
long long A[4]; int l, r;
// 0:= A, A
// 1:= A, B
// 2:= B, A
// 3:= B, B
};
node operator + (const node &lhs, const node &rhs) {
node res; res.l = lhs.l, res.r = rhs.r;
res.A[0] = min({INF, lhs.A[0] + rhs.A[0], lhs.A[0] + rhs.A[2], min(INF, lhs.A[1] + rhs.A[0]) + c[lhs.r], lhs.A[1] + rhs.A[2]});
res.A[1] = min({INF, lhs.A[0] + rhs.A[1], lhs.A[0] + rhs.A[3], min(INF, lhs.A[1] + rhs.A[1]) + c[lhs.r], lhs.A[1] + rhs.A[3]});
res.A[2] = min({INF, lhs.A[2] + rhs.A[0], lhs.A[2] + rhs.A[2], min(INF, lhs.A[3] + rhs.A[0]) + c[lhs.r], lhs.A[3] + rhs.A[2]});
res.A[3] = min({INF, lhs.A[2] + rhs.A[1], lhs.A[2] + rhs.A[3], min(INF, lhs.A[3] + rhs.A[1]) + c[lhs.r], lhs.A[3] + rhs.A[3]});
return res;
}
node C[N << 2];
void Build(int u, int l, int r) {
if(l != r) {
Build(lc, l, mid), Build(rc, mid + 1, r);
C[u] = C[lc] + C[rc];
} else C[u].l = C[u].r = l, C[u].A[0] = a[l], C[u].A[1] = INF, C[u].A[2] = INF, C[u].A[3] = b[l];
}
void Update(int u, int l, int r, int p) {
if(l == r) {C[u].A[0] = a[l], C[u].A[3] = b[l]; return; }
if(p <= mid) Update(lc, l, mid, p);
else Update(rc, mid + 1, r, p);
C[u] = C[lc] + C[rc];
}
inline node Ask() {return C[1]; }
#undef lc
#undef rc
#undef mid
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> q;
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 ++) cin >> c[i];
SegmentTree::Build(1, 1, n);
while(q --) {
int p; cin >> p; cin >> a[p] >> b[p] >> c[p];
SegmentTree::Update(1, 1, n, p);
auto T = SegmentTree::Ask();
cout << min({T.A[0], T.A[1], T.A[2], T.A[3]}) << '\n';
}
return 0;
}
G. Tree LGM
记 \(\operatorname{son}_r(u)\) 表示当 \(r\) 为根时 \(u\) 的儿子构成的集合，\(\operatorname{tree}_r(u)\) 表示当 \(r\) 为根时 \(u\) 的子树（包含 \(u\)）构成的集合。
给了树的形态和根，求每个结点的答案是容易的：对于一个结点 \(u\)，\(u\) 先手必败（值为 \(0\)）当且仅当对 \(u\) 的所有儿子 \(v\) 都有 \(v\) 先手必胜（值为 \(1\)），初始值为叶子结点均必败。
引理： \(\exists i,\ \text{s.t. } s_{i, u} \ne s_{u,u} \Longrightarrow s_{u,u}=1\)。
证明： 若 \(s_{u,u}=0\)，那么说明 \(\forall\ j \in \operatorname{son}_u(u),s_{u,j}=1\)，那么任意换根为 \(r\)，仍然有 \(\forall\ j \in \operatorname{son}_r(u),s_{r,j}=1\)，因此对任意根 \(r\) 都有 \(s_{r,u}=0\)。
另一方面，\(\exists i,\ \text{s.t. } s_{i, u} \ne s_{u,u}\)，那么必然恰有一个 \(v \in \operatorname{son}_u(u)\) 使得 \(s_{u,v}=0\)，否则若有多个，那么任意换根，\(u\) 总有一个儿子必败，那么 \(u\) 应当永远必胜，不会有 \(s_{i,u} \ne s_{u,u}\)。
和刚刚的分析一样，若恰有一个 \(v \in \operatorname{son}_u(u)\) 满足 \(s_{u,v}=0\)，那么 \(s_{i,u} \ne s_{u,u}\) 当且仅当 \(i \in \operatorname{tree}_u(v)\)，这是因为只有这时 \(u\) 剩下的儿子都是必败的，值为 \(0\)。
确定了 \(u\) 之后我们看怎样找到这个 \(v\)，\(v\) 应当满足：
- \(s_{v,v}=1\)，这是因为 \(s_{v,u}=0\)。
- \(\forall\ i \in \operatorname{son}_u(v),\ s_{i,u}=0\)。
- \(s_{i,v}=0 \Longleftrightarrow i \notin \operatorname{tree}_u(v)\)，对于任意 \(t \in \operatorname{tree}_u(v),t \ne v\)，\(t\) 都不满足本限制。
于是我们就可以唯一确定出这个 \(v\) 并连边 \((u,v)\)，这条边将整棵树划分为了两个连通块，递归下去处理。
最终剩下的情况是对于所有点 \(u\) 都有：\(\forall\ r_1,r_2,\ s_{r_1,u}=s_{r_2,u}\)，考虑一个 \(s_{u,u}=1\) 的点，它要么不连其它任何一个点，要么至少连上两个 \(s=0\) 的点。最优的构造方案显然是0-1-0-1-...-1-0的形式，若 \(0\) 点不够则无解，否则剩余的 \(0\) 点随便挂在 \(1\) 点上面就行。
最后考虑一下 \(i,j\) 在不同联通块时 \(s_{i,j}\) 是否正确即可。如果用异或哈希来找 \(v\)，时间复杂度 \(\mathcal{O}(n^2)\)。
code for G
#include <bits/stdc++.h>
using namespace std;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5010;
int n; char S[N][N];
unsigned long long val[N], hsh[N], tot;
bool done[N];
inline void init() {
for(int i = 0; i < n; i ++) if(S[i][i] != '1') {
for(int j = 0; j < n; j ++)
if(S[j][i] != S[i][i]) {
cout << "No" << '\n';
exit(0);
}
}
for(int i = 0; i < n; i ++) val[i] = Rand();
for(int i = 0; i < n; i ++) tot ^= val[i];
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
if(S[i][j] == '1') hsh[j] ^= val[i];
}
vector<pair<int, int>> ans;
bool solve(vector<int> &P) {
int pl = -1, pr = -1;
vector<int> zero, one;
for(auto u : P) {
if(S[u][u] == '0' || done[u] || hsh[u] == tot) continue;
zero.clear(), one.clear();
for(auto v : P)
(S[v][u] == '0' ? zero : one).emplace_back(v);
if(!zero.empty()) {pr = u; break; }
}
if(pr == -1) {
// 每一列都相等，构造方案
vector<int> linked; zero.clear(), one.clear();
for(auto u : P) {
if(done[u]) linked.emplace_back(u);
else if(S[u][u] == '0') zero.emplace_back(u);
else one.emplace_back(u);
}
for(int i = 1; i < linked.size(); i ++) ans.push_back({linked[i - 1], linked[i]});
if(zero.empty() && one.empty()) return true;
if(one.size() >= zero.size()) return false;
if(one.empty()) return zero.size() <= 1 && linked.empty();
for(int i = 0; i < one.size(); i ++) {
ans.push_back({zero[i], one[i]});
ans.push_back({zero[i + 1], one[i]});
}
for(int i = one.size() + 1; i < zero.size(); i ++)
ans.push_back({zero[i], one[0]});
if(!linked.empty()) ans.push_back({linked[0], one[0]});
return true;
} else {
int u = pr;
for(int v : zero) {
if(S[v][v] == '0' || done[v] || ((hsh[v] ^ hsh[u]) != tot)) continue;
vector<int> T;
for(auto i : P) if(S[i][v] == '0') T.emplace_back(i);
if(T == one) {pl = v; break; }
}
if(pl == -1) return false;
int v = pl;
for(auto i : zero) for(auto j : one) {
if(i != v && S[j][i] != S[v][i]) return false;
if(j != u && S[i][j] != S[u][j]) return false;
}
ans.push_back({u, v}), done[u] = done[v] = true;
return solve(zero) && solve(one);
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for(int i = 0; i < n; i ++)
cin >> S[i];
init();
vector<int> vec(n); iota(vec.begin(), vec.end(), 0);
if(solve(vec)) {
cout << "Yes" << '\n';
for(auto pr : ans)
cout << pr.first + 1 << ' ' << pr.second + 1 << '\n';
} else cout << "No" << '\n';
return 0;
}
H. Tree Diameter
以下讨论中，查询时没有说明的边权均为 \(1\)。
随便找一个边作为根，不妨设为 \(1\) 号边，然后对其它的边用 \(n-2\) 次询问 \(2\) 查出它们到根的距离，设 \(c_d\) 为距离为 \(d\) 的边构成的集合。
按照深度从小到大一层一层处理所有边：处理 \(c_d\) 中的边时，对每一个 \(c_d\) 中的边，设其权值为 \(10^9\)，\(c_{d-1}\) 中边的权值为 \(n,2n,3n,\cdots ,(|c_{d-1}|-1)n,(|c_{d-1}|-1)n\)（注意有两个 \((|c_{d-1}|-1)n\) 而没有 \(|c_d|n\)），查询直径。显然直径必然经过了这个 \(c_d\) 中的边、其父边、另一条权值为 \(|c_{d-1}-1|n\) 的边。设直径为 \(D\)，那么其父边就是权值为
\[{\Big(} \left\lfloor \frac{D-10^9}{n} \right\rfloor - (|c_{d-1}|-1) {\Big)} \times n\nonumber \]但是假如算出来父边的权值为 \((|c_{d-1}|-1)n\)，我们无法确定到底是哪条边（有两条权值为 \((|c_{d-1}|-1)n\) 的边）。将某一条权值为 \((|c_{d-1}|-1)n\) 边在一开始就换为 \(|c_{d-1}|n\) 是不行的，这样做的话，直径必然都穿过了 \(|c_{d-1}|n\) 这条边，我们无法区分该边的子边和其它边。
先来看两条权值相同的边同构的情况，此时我们枚举到了一个 \(u \in c_d\) 的父边权为 \((|c_{d-1}|-1)n\)，将其父亲定为任意一个权值为 \((|c_{d-1}|-1)n\) 的边。
剩余的 \(c_d\) 中没有确定父亲的边就不能按照刚才的套路来了，我们应该这样确定它们的父边：
- 将该边（设为 \(v\)）的权值定为 \(10^9\)，将边 \(u\) 的权值定为 \(10^9\)，其中 \(u\) 为 \(c_d\) 中枚举到的第一个父边权为 \(|c_{d-1}-1|n\) 的边。
- \(c_{d-1}\) 中边的权值和之前一样设定为 \(n,2n,3n,\cdots ,(|c_{d-1}|-1)n,(|c_{d-1}|-1)n\)。
- 询问 \(1\) 求出此时树的直径 \(D\)，若 \(\left\lfloor \frac{D-2 \times 10^9}{n} \right\rfloor > 0\)，说明 \(v\) 和 \(u\) 的父亲不同，其父亲的权值是 \({\Large(}\left\lfloor \frac{D-2 \times 10^9}{n} \right\rfloor - (|c_{d-1}|-1){\Large)} n\)，这是唯一确定的；否则 \(u,v\) 的父亲相同，也是可以唯一确定 \(v\) 的父亲的。
上述所有确定 \(c_d\) 中边的父亲的过程只用了 \(|c_d|\) 次询问 \(1\)。
现在考虑两条权值为 \((|c_{d-1}|-1)n\) 的边不同构的情况，由于我们已经有了同构情况的解法，所以一个策略是尽量避免不同构的情况出现。为了方便，下面称每一层的这两条权值相同的边为特殊边。
一开始只有 \(1\) 号边时两个端点是同构的（我们将 \(1\) 号边看作两个特殊边，包含两个不同的端点）。若 \(c_{d-1}\) 的两个特殊边是同构的，设它们为 \(a,b\)，开始分类讨论。
- 若 \(a\) 或 \(b\) 的儿子个数 \(\ge 2\)，那么钦定 \(c_d\) 的两个特殊边均在那个儿子个数 \(\ge 2\) 的特殊边的儿子中，两条边仍然同构。
- 否则若 \(a\) 和 \(b\) 均有一个儿子，将 \(c_d\) 的两个特殊边亲定为这两个儿子，它们仍然同构。
否则不妨设 \(a\) 没有儿子，再次根据 \(b\) 有几个儿子分类讨论：
- 若 \(b\) 没有儿子，那么我们就找到了两个叶子边。在接下来的查询中，我们钦定查询边的权值为 \(10^9\)，某个叶子边的权值为 \(10^9\)，\(c_{d-1}\) 中边的权值为 \(n,2n,\cdots ,|c_{d-1}-1|n,|c_d|n\)，那么直径必然经过查询边、其父亲以及叶子边，并且只经过一条 \(c_{d-1}\) 中的边。由于 \(c_{d-1}\) 中边的权值两两不同且 \(\ge n\)，所以可以唯一确定。
- 若 \(b\) 有一个儿子，我们可以简单地钦定 \(a\) 作为一个叶子，做上面的操作吗？不可以。因为我们在连接 \(b\) 的儿子时没有区分 \(a\) 和 \(b\)，换句话说，它的父亲是在 \(a\) 和 \(b\) 中随便选出的，实际上它的父亲有可能是 \(a\) 才对，此时 \(a\) 就不是叶子了。
- 此时我们需要知道它的父亲到底是 \(a\) 还是 \(b\)：只需要做一次询问 \(2\)，得到它和 \(a\) 之间的距离，如果是 \(0\)，说明父亲是 \(a\)，否则就是 \(1\)，说明父亲是 \(b\)。
- 之后就可以得到一个叶子边，按照 \(b\) 没有儿子时的解法做了。
总共只用了 \(n-2\) 次询问 \(1\)（除了 \(1\) 号边以外的每条边只问了一次）和至多 \(n-1\) 次询问 \(2\)（一开始问了 \(n-2\) 次，不同构时再问一次）。
code for H
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 1e9;
int n, tot; vector<int> E[N];
int a[N];
inline int Ask() {
cout << "? 1";
for(int i = 1; i <= n - 1; i ++)
cout << ' ' << a[i];
cout << endl;
int res; cin >> res; return res;
}
vector<int> son[N];
int node[N];
// node[i]:= i 号边深度较大的端点
// son[i]:= i 号点的子结点
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for(int i = 2; i <= n - 1; i ++) {
cout << "? 2 1 " << i << endl;
int x; cin >> x; E[x].emplace_back(i);
}
int dep = 0, leaf = 0; vector<int> last_E; // last_E := 上一层的边，顺序与权值对应
last_E.emplace_back(1), last_E.emplace_back(1); tot = 2;
for(dep = 0; dep <= n && !E[dep].empty(); dep ++) {
// 处理第 dep 层的边
for(int i = 1; i <= n - 1; i ++) a[i] = 1;
for(int i = 0; i < last_E.size() - 1; i ++) a[last_E[i]] = (i + 1) * n;
a[last_E.back()] = ((int)last_E.size() - 1) * n;
vector<int> vec = E[dep];
int flag = 0;
while(!vec.empty()) {
int e = vec.back(); vec.pop_back();
a[e] = INF; int D = (Ask() - INF) / n - ((int)last_E.size() - 1); a[e] = 1;
if(dep == 0 || D == (int)last_E.size() - 1) {flag = e; break; }
node[e] = ++tot; son[node[last_E[D - 1]]].emplace_back(tot);
}
if(flag) {
vector<int> A, B; node[flag] = ++tot, A.emplace_back(flag);
a[flag] = INF;
while(!vec.empty()) {
int e = vec.back(); vec.pop_back();
a[e] = INF; int D = (Ask() - INF - INF) / n; a[e] = 1;
if(D == 0) node[e] = ++tot, A.emplace_back(e);
else if(dep == 0 || D - ((int)last_E.size() - 1) == ((int)last_E.size() - 1)) node[e] = ++tot, B.emplace_back(e);
else node[e] = ++tot, son[node[last_E[D - ((int)last_E.size() - 1) - 1]]].emplace_back(tot);
}
if(B.size() > A.size()) swap(A, B);
int u, v; // 两个特殊边
if(A.size() == 1) {
if(B.size() == 0) {
cout << "? 2 " << A[0] << ' ' << last_E.back() << endl;
int T; cin >> T;
if(T == 0) son[dep ? node[last_E[last_E.size() - 2]] : 1].emplace_back(node[A[0]]), leaf = last_E[last_E.size() - 2];
else son[dep ? node[last_E[last_E.size() - 1]] : 2].emplace_back(node[A[0]]), leaf = last_E.back();
dep ++; break;
} else {
// B.size() == 1
son[dep ? node[last_E[last_E.size() - 2]] : 1].emplace_back(node[A[0]]);
son[dep ? node[last_E[last_E.size() - 1]] : 2].emplace_back(node[B[0]]);
u = A[0], v = B[0];
}
} else {
for(auto x : A) son[dep ? node[last_E[last_E.size() - 2]] : 1].emplace_back(node[x]);
for(auto x : B) son[dep ? node[last_E[last_E.size() - 1]] : 2].emplace_back(node[x]);
u = A[0], v = A[1];
}
last_E.clear();
for(auto e : E[dep])
if(e != u && e != v) last_E.emplace_back(e);
last_E.emplace_back(u), last_E.emplace_back(v);
} else {leaf = last_E.back(), dep ++; break; } // 两个特殊边是叶子
}
if(leaf) {
for(; dep <= n && !E[dep].empty(); dep ++) {
for(int i = 1; i <= n - 1; i ++) a[i] = 1;
for(int i = 0; i < E[dep - 1].size(); i ++)
a[E[dep - 1][i]] = (i + 1) * n;
a[leaf] = INF;
for(auto e : E[dep]) {
a[e] = INF; int D = (Ask() - INF - INF) / n - 1; a[e] = 1;
node[e] = ++tot, son[node[E[dep - 1][D]]].emplace_back(node[e]);
}
}
}
cout << "!" << '\n';
cout << "1 2" << '\n';
for(int i = 1; i <= tot; i ++)
for(auto x : son[i])
cout << i << ' ' << x << '\n';
cout << flush;
return 0;
}