A. DFS Order
签到题，最小值是深度，最大值是总点数减去子树大小，跑一个dfs就行。
code for A
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, dep[N], siz[N], ans[N][2];
vector<int> G[N];
void dfs(int u, int f) {
dep[u] = dep[f] + 1, siz[u] = 1;
for(auto v : G[u]) if(v != f) {
dfs(v, u), siz[u] += siz[v];
}
ans[u][0] = dep[u], ans[u][1] = n - siz[u] + 1;
}
inline void solve() {
cin >> n;
for(int i = 1; i < n; i ++) {
int a, b; cin >> a >> b;
G[a].emplace_back(b), G[b].emplace_back(a);
}
dfs(1, 0);
for(int i = 1; i <= n; i ++)
cout << ans[i][0] << ' ' << ans[i][1] << '\n';
for(int i = 1; i <= n; i ++) G[i].clear();
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
B. Beautiful String
套路串串，\(\sum |S| \le 3 \times 10^4\) 其实是假的，因为 \(|S| \le 5000\)，所以对于 \(\mathcal{O}(|S|^2)\) 的时间复杂度，最大也不过 \(6 \times 5000^2\)，再乘上一个 \(\frac{1}{2}\) 的常数，稳稳地过（实际上不乘这个 \(\frac{1}{2}\) 常数也行）。
具体的，设串长 \(|S|=n\)，先算出 \(lcp_{i,j}\) 表示 \(S[i..n]\) 与 \(S[j..n]\) 的最长公共前缀，用经典转移
\[lcp_{i,j}=[S_i=S_j](lcp_{i+1,j+1}+1)\nonumber \]即可做到 \(\mathcal{O}(n^2)\)。
然后枚举 \(s_2\) 的起始位置 \(i\)，再枚举 \(s_5\) 的起始位置 \(j\)，那么 \(\min(lcp_{i,j},i-j-2)\) 就是此时 \(s_2+s_3=s_5+s_6\) 的最大长度，然后对于每个 \(|s_2|\)，最大长度 \(\ge |s_2|\) 的 \(j\) 会对答案产生 \(1\) 的贡献，扫一遍加到答案里即可， 总时间复杂度 \(\mathcal{O}(\sum n^2)\)。
code for B
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, lcp[N][N], siz[N]; string S;
inline void solve() {
cin >> S; n = S.size(), S = "$" + S;
for(int i = 0; i <= n + 1; i ++) lcp[n + 1][i] = lcp[i][n + 1] = 0;
for(int i = n; i >= 1; i --) for(int j = n; j >= 1; j --)
lcp[i][j] = (S[i] == S[j] ? lcp[i + 1][j + 1] + 1 : 0);
long long ans = 0;
for(int i = 2; i <= n; i ++) {
for(int j = 0; j <= n - i + 2; j ++) siz[j] = 0;
for(int j = i + 3; j <= n; j ++)
if(lcp[i][j] >= 2) siz[min(lcp[i][j] - 1, j - i - 2)] ++;
long long sum = 0, cnt = 0;
for(int j = n - i + 1; j >= 1; j --) {
cnt += siz[j], sum += cnt;
if(j < i && lcp[i - j][i] >= j) ans += sum;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
C. String-dle Count
根据给出来的东西，可以得知每个位置被禁止填哪些字母、每个字母至多被填多少个（存在该字母的-且不存在该字母的x的时候）或者应该恰好被填多少个（存在该字母的x时），顺便判一下矛盾。
设字母 \(c\) 至少被填 \(L_c\) 个，至多被填 \(R_c\) 个（恰好的限制可以用 \(L=R\) 表述），首先判一下无解，就是存在 \(L_c > R_c\) 时，或 \(\sum L_c > k\) 时无解。
现在 \(\sum L_c\) 被压到了 \(19\)(\(k\) 最大为 \(19\))，可以用一个二进制串表示，然后dp。具体的，从前往后填每个位置，设 \(f_{i,state}\) 表示前 \(i\) 个位置，所填状态为 \(state\) 时的方案数。转移时不一定要将 \(state\) 的某个 \(0\) 变成 \(1\)，还可以是将某个已经填完「至少」的限制，但是还没有满足「至多」限制（此时这个至多限制一定是没有限制，因为至多限制都是恰好限制）的字符，因此分两类转移。
对于后者的转移，我们可以预处理一下做到 \(\mathcal{O}(k2^k)\)，总的时间复杂度可以做到 \(\mathcal{O}(k^22^k)\)。
代码如下，solve函数中的 \(T\) 表示题目描述中的 \(n\)，\(n\) 表示题目描述中的 \(k\)。
code for C
#include <bits/stdc++.h>
using namespace std;
const int N = 20, MOD = 1e9 + 7;
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 n, ban[N], L[26], R[26];
int f[N][1 << N];
inline int solve() {
int T; cin >> T >> n;
for(int i = 0; i < 26; i ++) L[i] = 0, R[i] = n;
while(T --) {
string A, B; cin >> A >> B;
vector<int> siz(26, 0);
for(int i = 0; i < n; i ++) if(B[i] == 'O') {
siz[A[i] - 'A'] ++;
ban[i] |= ((1 << 26) - 1) ^ (1 << A[i] - 'A');
}
for(int i = 0; i < n; i ++) if(B[i] != 'O') {
if(B[i] == '-') L[A[i] - 'A'] = max(L[A[i] - 'A'], ++siz[A[i] - 'A']);
else R[A[i] - 'A'] = min(R[A[i] - 'A'], siz[A[i] - 'A']);
ban[i] |= 1 << (A[i] - 'A');
}
for(int i = 0; i < 26; i ++) L[i] = max(L[i], siz[i]);
}
for(int i = 0; i < 26; i ++)
if(L[i] > R[i]) return 0;
int least = 0;
for(int i = 0; i < 26; i ++)
least += L[i];
if(least > n) return 0;
static int in[N], trans[1 << N];
for(int i = 0, tot = 0; i < 26; i ++) {
for(int j = 0; j < L[i]; j ++)
in[tot ++] = i;
}
memset(trans, 0, sizeof trans);
for(int mask = 0; mask < (1 << least); mask ++) {
for(int i = 0, tot = 0; i < 26; i ++) {
int siz = 0;
for(int j = 0; j < L[i]; j ++)
siz += (mask >> tot & 1), tot ++;
if(siz == L[i] && L[i] < R[i]) trans[mask] |= 1 << i;
}
}
f[0][0] = 1;
for(int i = 1; i <= n; i ++) {
for(int mask = 0; mask < (1 << least); mask ++) if(f[i - 1][mask]) {
for(int j = 0; j < least; j ++) if(!(mask >> j & 1) && (j == 0 || in[j] != in[j - 1] || (mask >> j - 1 & 1))) {
int ch = in[j]; if(ban[i - 1] >> ch & 1) continue;
f[i][mask | (1 << j)] = Plus(f[i][mask | (1 << j)], f[i - 1][mask]);
}
int T = trans[mask]; T = T ^ (T & ban[i - 1]);
f[i][mask] = Plus(f[i][mask], 1ll * f[i - 1][mask] * __builtin_popcount(T) % MOD);
}
}
return f[n][(1 << least) - 1];
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T = 1;// cin >> T;
while(T --)
cout << solve() << '\n';
return 0;
}
D. Two Walls
首先，假如 \(AB\) 和 \(CD\)、\(EF\) 均不相交，答案显然是 \(0\)，特判掉。
当没有线段 \(EF\) 时，答案显然不是 \(0\) 就是 \(1\)。
加上线段 \(EF\) 之后，假如 \(CD\)、\(EF\) 中的某个线段的一个端点恰在线段 \(AB\) 上，那么这个线段的限制可以直接忽略（从另一侧绕到 \(B\)），答案为 \(1\)；否则若只有一条线段与 \(AB\) 有交，答案同样为 \(1\)，因为这时另一条线段完全没用。
否则，两条线段均与 \(AB\) 有交，且交点均不为它们的端点，这时候 \(A\) 想要只转一次到达 \(C\)，当且仅当 \(A\)、\(B\) 和线段 \(CD,EF\) 在 \(AB\) 同一侧的两个点分别构成的直线交于 \(AB\) 的该侧，用叉积判断，若两侧均不可以，答案为 \(2\)，单次时间复杂度 \(\mathcal{O}(1)\)。
code for D
#include <bits/stdc++.h>
using namespace std;
struct Point {
long long x, y;
Point(long long _x = 0, long long _y = 0): x(_x), y(_y) {}
};
istream& operator >> (istream &in, Point &p) {in >> p.x >> p.y; return in; }
ostream& operator << (ostream& out, Point &p) {cout << p.x << ' ' << p.y; return out; }
typedef Point Vector;
Vector operator + (const Point lhs, const Vector rhs) {return Point(lhs.x + rhs.x, lhs.y + rhs.y); }
Vector operator - (const Point lhs, const Vector rhs) {return Point(lhs.x - rhs.x, lhs.y - rhs.y); }
inline long long Cross(const Vector lhs, const Vector rhs) {return lhs.x * rhs.y - lhs.y * rhs.x; }
inline bool direction(const Vector u, const Vector v) {return Cross(u, v) > 0; }
inline bool direction(const pair<Point, Point> L, const Point p) {return direction(L.second - L.first, p - L.first); }
inline int intersect(const pair<Point, Point> A, const pair<Point, Point> B) {
if(max(A.first.x, A.second.x) < min(B.first.x, B.second.x)) return 0;
if(max(A.first.y, A.second.y) < min(B.first.y, B.second.y)) return 0;
if(max(B.first.x, B.second.x) < min(A.first.x, A.second.x)) return 0;
if(max(B.first.y, B.second.y) < min(A.first.y, A.second.y)) return 0;
if((__int128)Cross(B.second - B.first, A.first - B.first) * Cross(B.second - B.first, A.second - B.first) > 0)
return 0;
if((__int128)Cross(A.second - A.first, B.first - A.first) * Cross(A.second - A.first, B.second - A.first) > 0)
return 0;
if(Cross(A.second - A.first, B.first - A.first) == 0 || Cross(A.second - A.first, B.second - A.first) == 0)
return 1;
else return 2;
}
inline bool check(const pair<Point, Point> L, const pair<Point, Point> T) {
return direction(T.first - L.first, T.second - L.second) && direction(T.second - L.first, T.first - L.second);
}
inline int solve() {
Point A, B, C, D, E, F;
cin >> A >> B >> C >> D >> E >> F;
int tot = intersect({A, B}, {C, D}) + intersect({A, B}, {E, F});
if(tot == 0) return 0;
else if(tot != 4) return 1;
if(direction({A, B}, D)) swap(C, D);
if(direction({A, B}, F)) swap(E, F);
return (check({A, B}, {C, E}) || check({B, A}, {D, F})) ? 1 : 2;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --)
cout << solve() << '\n';
return 0;
}
E. Prof. Pang and Poker
假如Alice只有一张牌或者Alice的牌全部不小于Pang，那么Bob获胜，因为Bob可以一直不出牌让Alice出完。
否则假如Bob手里有至少两个小于Pang的牌，那么Pang获胜，因为Bob手中小于Pang的牌必须最后一个出，使得Bob出完牌获胜，但此时两张牌是做不到同时出去的，Alice也可以一直跳过来让Bob手中只有小于Pang的牌（注意此时已经判掉Alice的牌全部不小于Pang的情况了，也就是这时候Alice一定可以出一张牌使得Bob必须出牌，然后Pang和Alice跳过，让Bob一直出）。
否则假如Bob手里没有小于Pang的牌，显然Bob获胜。
此时Bob手中恰有一张牌是小于Pang的，Bob的目标是让它最后一个被打出。
先判掉 \(m=1\) 的情况，此时Pang能获胜当且仅当Alice手中小于Pang的最大牌不小于Bob手中的牌（使得Bob只能跳过而Pang打出牌）。
否则Bob一定能赢吗？不是这样的。Alice手中假如有多于 \(1\) 个小于Pang的牌，那么他可以先打出去一张让Bob拿到先手，Bob显然会一直出大牌，把最小的那张小于Pang的牌留到最后，此时若Alice的最大牌可以压过Bob的最大牌，Alice就可以在Bob剩下那一张牌的时候把先手抢回来，此时若Alice可以出一张小于Pang但不小于Bob的牌，Pang就赢了（这同时还要求 \(n>3\)，因为Alice不能把牌全出完）。也就是说，此时若还有 \(n>3\) 且Alice手中有至少两张牌小于Pang，且最大牌比Bob大，且Alice手中小于Pang的最大牌不小于Bob手上小于Pang的牌，那么Pang获胜。
否则Bob获胜。
下面给出了单次询问 \(\mathcal{O}(n \log n)\) 的实现，实际上可以不用排序，做到线性。
code for E
#include <bits/stdc++.h>
using namespace std;
inline int get(char c) {
if(c >= '2' && c <= '9')
return c - '2';
if(c == 'T') return 8;
if(c == 'J') return 9;
if(c == 'Q') return 10;
if(c == 'K') return 11;
if(c == 'A') return 12;
assert(false); return -1;
}
inline string solve() {
int n, m;
cin >> n >> m;
vector<int> A(n), B(m); int C;
for(int i = 0; i < n; i ++) {
string str; cin >> str;
A[i] = get(str[0]);
}
for(int i = 0; i < m; i ++) {
string str; cin >> str;
B[i] = get(str[0]);
}
{
string str; cin >> str;
C = get(str[0]);
}
int minA = A[0], maxB = B[0];
for(int i = 0; i < n; i ++) minA = min(minA, A[i]);
for(int i = 0; i < m; i ++) maxB = max(maxB, B[i]);
int cnt = 0;
for(int i = 0; i < m; i ++)
cnt += B[i] < C;
if(minA >= C || n == 1) return "Shou";
if(cnt >= 2) return "Pang";
if(cnt == 0) return "Shou";
int passA = minA;
for(int i = 0; i < n; i ++)
if(A[i] < C) passA = max(passA, A[i]);
if(m == 1) return passA >= B[0] ? "Pang" : "Shou";
sort(A.begin(), A.end()), sort(B.begin(), B.end());
if(A.back() > B.back() && n > 3 && A[1] < C && passA >= B[0]) return "Pang";
return "Shou";
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) cout << solve() << '\n';
return 0;
}
F. Vacation
这种东西没有思路就先分个块就做完了。先把 \(n\) 补齐到 \(c\) 的倍数（实际上不补齐也行），然后设块大小就是 \(c\)，把整个 序列分成 \(\frac{n}{c}\) 块。
先在整个序列上建一个没有长度限制的，可以单点修改+区间查询最大子段和的线段树，然后再建一个序列长 \(\frac{n}{c}\) 的单点修改、查询区间 \(\max\) 的线段树，每个值表示相应块的最大子段和。
但是我们还忽略了跨越两个块的子段和，考虑往之前的做法里打补丁。对每个块边界，维护以它为左端点的，长度 \(\le c\) 的前缀和、以它为右端点的、长度 \(\le c\) 的后缀和，这两个数组有什么用？把某一个数组翻转一下，两个数组前缀 \(\max\) 的和就是前缀是某个长度的、穿过中间划分点的合法最大子段和。
形式化地，对于分割点 \(z\)，设 \(suf_i\) 表示 \(\sum_{j=1}^{c-i+1}a_{z+j-1}\)，\(pre_i=\sum_{j=1}^{i}a_{z-j}\)，那么 \(pre_i+suf_i\) 就表示一段长度为 \(c\) 的子段和。分割点 \(z\) 之前的被选元素个数不超过 \(t\) 的合法最大子段和就是
\[\max_{i=1}^{t}\Big( pre_i+\max_{j=i}^{c}suf_j \Big)\nonumber \]这个关于区间的式子是可以用线段树维护的，代表区间 \(\[l,r\]\) 的结点维护这段的 \(pre\)、\(suf\) 最大值还有 \(\max_{i=l}^{r}\Big( a_i+\max_{j=i}^{r}a_j \Big)\)，然后就可以合并了。
注意单点修改对 \(pre\)(或 \(suf\)) 的影响可以看作是区间加，这玩意是可以打 \(tag\) 维护的，然后我们就可以用这个线段树做到查询某个块边界往左的某个后缀（或者往右的某个前缀）能够拼出来的最大子段和。这样的线段树一共有 \(\frac{n}{c}\) 个，但是每个线段树的大小是 \(4c\)，所以不会炸。
最后的收尾工作就是再维护一个单点修改、查询区间 \(\max\) 的线段树来查询一段整块内部的、跨过块边界的合法最大子段和了。
修改操作对四类线段树分别维护，查询操作多分类讨论一下即可，详细实现可以看代码。总时间复杂度 \(\mathcal{O}(m \log n)\)。
code for F
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int n, m, c, A[N], B;
#define lc (u << 1)
#define rc (u << 1 | 1)
#define mid ((l + r) >> 1)
struct Max_Seg {
ll C[N << 2];
void Modify(int u, int l, int r, int p, ll x) {
if(l == r) return C[u] = x, void();
if(p <= mid) Modify(lc, l, mid, p, x);
else Modify(rc, mid + 1, r, p, x);
C[u] = max(C[lc], C[rc]);
}
ll Ask(int u, int l, int r, int L, int R) {
if(l >= L && r <= R) return C[u];
if(mid >= R) return Ask(lc, l, mid, L, R);
if(mid < L) return Ask(rc, mid + 1, r, L, R);
return max(Ask(lc, l, mid, L, R), Ask(rc, mid + 1, r, L, R));
}
} Block, Other;
namespace SegmentTree {
struct node {
ll l, r, s, v;
node(ll _v = 0) {l = r = v = max(_v, 0ll), s = _v; }
node(ll _l, ll _r, ll _s, ll _v): l(_l), r(_r), s(_s), v(_v) {}
};
node operator + (const node &lhs, const node &rhs) {
return node(max(lhs.l, lhs.s + rhs.l), max(rhs.r, rhs.s + lhs.r), lhs.s + rhs.s,
max(lhs.r + rhs.l, max(lhs.v, rhs.v)));
}
node T[N << 2];
void Build(int u, int l, int r) {
if(l != r)
Build(lc, l, mid), Build(rc, mid + 1, r), T[u] = T[lc] + T[rc];
else T[u] = node(A[l]);
}
void Modify(int u, int l, int r, int p, ll x) {
if(l == r) return T[u] = node(x), void();
if(p <= mid) Modify(lc, l, mid, p, x);
else Modify(rc, mid + 1, r, p, x);
T[u] = T[lc] + T[rc];
}
node Ask(int u, int l, int r, int L, int R) {
if(l >= L && r <= R) return T[u];
if(mid >= R) return Ask(lc, l, mid, L, R);
if(mid < L) return Ask(rc, mid + 1, r, L, R);
return Ask(lc, l, mid, L, R) + Ask(rc, mid + 1, r, L, R);
}
}
struct Little_SegTree {
struct node {
ll ans, pre, suf;
node(ll _ans = -INF, ll _pre = 0, ll _suf = 0): ans(_ans), pre(_pre), suf(_suf) {}
node operator + (const node &rhs) {
return node(max(this->pre + rhs.suf, max(this->ans, rhs.ans)), max(this->pre, rhs.pre), max(this->suf, rhs.suf));
}
};
node *T; ll *tag_pre, *tag_suf;
inline void init(int n) {
T = (node*)calloc(n << 2, sizeof(node));
tag_pre = (ll*)calloc(n << 2, sizeof(ll));
tag_suf = (ll*)calloc(n << 2, sizeof(ll));
}
void Build(int u, int l, int r, ll pre[], ll suf[]) {
tag_pre[u] = tag_suf[u] = 0;
if(l != r) {
Build(lc, l, mid, pre, suf), Build(rc, mid + 1, r, pre, suf);
T[u] = T[lc] + T[rc];
} else T[u] = node(pre[l] + suf[l], pre[l], suf[l]);
}
inline void Tag(int u, ll a, ll b) {
tag_pre[u] += a, tag_suf[u] += b;
T[u].pre += a, T[u].suf += b, T[u].ans += a + b;
}
inline void pushdown(int u) {
if(!tag_pre[u] && !tag_suf[u]) return;
Tag(lc, tag_pre[u], tag_suf[u]), Tag(rc, tag_pre[u], tag_suf[u]);
tag_pre[u] = tag_suf[u] = 0;
}
void Add(int u, int l, int r, int L, int R, ll a, ll b) {
if(l >= L && r <= R) return Tag(u, a, b);
pushdown(u);
if(mid >= L) Add(lc, l, mid, L, R, a, b);
if(mid < R) Add(rc, mid + 1, r, L, R, a, b);
T[u] = T[lc] + T[rc];
}
node Ask(int u, int l, int r, int L, int R) {
if(l >= L && r <= R) return T[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 Ask(lc, l, mid, L, R) + Ask(rc, mid + 1, r, L, R);
}
} Tree[N];
#undef lc
#undef rc
#undef mid
int L[N], R[N], ID[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m >> c;
for(int i = 1; i <= n; i ++) cin >> A[i];
n = (n + c - 1) / c * c, B = n / c;
SegmentTree::Build(1, 1, n);
for(int i = 1; i <= B; i ++) {
static long long pre[N], suf[N];
L[i] = (i - 1) * c + 1, R[i] = i * c;
for(int j = L[i]; j <= R[i]; j ++) ID[j] = i;
Block.Modify(1, 1, B, i, SegmentTree::Ask(1, 1, n, L[i], R[i]).v);
if(i > 1) {
pre[0] = suf[c] = 0;
for(int j = 1; j <= c; j ++) pre[j] = pre[j - 1] + A[L[i] - j];
for(int j = c - 1; j >= 0; j --) suf[j] = suf[j + 1] + A[L[i] + c - j - 1];
Tree[i].init(c + 1); Tree[i].Build(1, 0, c, pre, suf);
Other.Modify(1, 1, B, i, Tree[i].T[1].ans);
}
}
while(m --) {
int op, x, y; cin >> op >> x >> y;
if(op == 1) {
SegmentTree::Modify(1, 1, n, x, y);
Block.Modify(1, 1, B, ID[x], SegmentTree::Ask(1, 1, n, L[ID[x]], R[ID[x]]).v);
if(ID[x] > 1) {
Tree[ID[x]].Add(1, 0, c, 0, R[ID[x]] - x, 0, y - A[x]);
Other.Modify(1, 1, B, ID[x], Tree[ID[x]].T[1].ans);
}
if(ID[x] < B) {
Tree[ID[x] + 1].Add(1, 0, c, R[ID[x]] - x + 1, c, y - A[x], 0);
Other.Modify(1, 1, B, ID[x] + 1, Tree[ID[x] + 1].T[1].ans);
}
A[x] = y;
} else {
if(y - x + 1 > c) {
ll ans = max(SegmentTree::Ask(1, 1, n, x, x + c - 1).v, SegmentTree::Ask(1, 1, n, y - c + 1, y).v);
if(ID[x] + 1 < ID[y]) {
ans = max(ans, Block.Ask(1, 1, B, ID[x] + 1, ID[y] - 1));
if(ID[x] + 1 < ID[y] - 1) ans = max(ans, Other.Ask(1, 1, B, ID[x] + 2, ID[y] - 1));
ans = max(ans, Tree[ID[x] + 1].Ask(1, 0, c, 0, R[ID[x]] - x + 1).ans);
ans = max(ans, Tree[ID[y]].Ask(1, 0, c, R[ID[y]] - y, c).ans);
} else
ans = max(ans, Tree[ID[y]].Ask(1, 0, c, R[ID[y]] - y + 1, R[ID[x]] - x + 1).ans);
cout << ans << '\n';
} else cout << SegmentTree::Ask(1, 1, n, x, y).v << '\n';
}
}
return 0;
}
G. Check Pattern is Bad
把所有偶数列的颜色取反，那么就是要求不能有形如
WW BB
BB WW
这两种情况。
再把偶数行去反，形式就更简单了：不能形如
WW BB
WW BB
这两种情况。
显然，若某个 \(2 \times 2\) 的格子中有 \(3\) 个同色块，那么剩下的一个颜色是固定的，直接填上。
用一个bfs维护上面的过程，直到不能再填。如果发现了矛盾就直接结束。
接下来我们证明，此时不断重复以下操作，一定可以得到一个合法解：
- 随便找一个不知道颜色的位置
- 随便填上一个颜色
- 接着用 bfs 扩展
证明： 只需要证每次扩展bfs的时候不会出现矛盾即可。设钦定的随便填的格子为 \((x,y)\)，填了黑色。现在执行bfs，那么下一个可以钦定的位置，不失一般性地设为 \((x+1,y+1)\)，这要求 \((x+1,y)\) 和 \((x,y+1)\) 均为黑色，此时 \((x+1,y+1)\) 填好了白色。
发现 \((x+1,y+1)\) 也是只能向右下角方向扩展的，因为它的另外两侧均有异色。不断地扩展下去，出现矛盾当且仅当填完 \((x+k,y+k)\) 后发现它和 \((x+k+1,y+k),(x+k,y+k+1),(x+k+1,y+k+1)\) 同色，而这是不可能出现的（这三个颜色均不是在此次bfs内填的，因此我们本来就可以确定 \((x+k,y+k)\) 的颜色而不是新开启一轮bfs）。
证毕！
单组数据的时间复杂度是 \(\mathcal{O}(nm)\) 的。
code for G
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m; char S[N][N];
int A[N][N];
queue<pair<int, int>> Q;
inline void check(int x, int y) {
if(x <= 0 || y <= 0 || x >= n || y >= m) return;
int siz = A[x][y] + A[x + 1][y + 1] + A[x + 1][y] + A[x][y + 1];
if(abs(siz) == 3) {
if(A[x][y] == 0) A[x][y] = -A[x + 1][y + 1], check(x - 1, y - 1);
else if(A[x + 1][y] == 0) A[x + 1][y] = -A[x][y], check(x + 1, y - 1);
else if(A[x][y + 1] == 0) A[x][y + 1] = -A[x][y], check(x - 1, y + 1);
else A[x + 1][y + 1] = -A[x][y], check(x + 1, y + 1);
}
}
inline void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> (S[i] + 1);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
A[i][j] = (S[i][j] == '?' ? 0 : (S[i][j] == 'W') ? 1 : -1);
for(int i = 1; i <= n; i ++)
for(int j = 2; j <= m; j += 2) A[i][j] = -A[i][j];
for(int i = 2; i <= n; i += 2)
for(int j = 1; j <= m; j ++) A[i][j] = -A[i][j];
for(int i = 1; i < n; i ++)
for(int j = 1; j < m; j ++)
check(i, j);
for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++)
if(!A[i][j]) A[i][j] = 1, check(i, j), check(i - 1, j - 1), check(i - 1, j), check(i, j - 1);
bool flag = true;
for(int i = 1; i < n && flag; i ++)
for(int j = 1; j < m && flag; j ++) {
if(abs(A[i][j] + A[i + 1][j + 1] + A[i][j + 1] + A[i + 1][j]) == 4) flag = false;
}
if(flag) {
cout << "YES" << '\n';
for(int i = 1; i <= n; i ++)
for(int j = 2; j <= m; j += 2) A[i][j] = -A[i][j];
for(int i = 2; i <= n; i += 2)
for(int j = 1; j <= m; j ++) A[i][j] = -A[i][j];
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++)
cout << (A[i][j] == 1 ? 'W' : 'B');
cout << '\n';
}
} else cout << "NO" << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
H. Check Pattern is Good
还是像上一题一样，先把偶数行、列颜色取反，然后跑网络流。
具体的，把每个 \(2 \times 2\) 网格拆成两个点，一个表示全填W，另一个表示全填B。如果一个 \(2 \times 2\) 网格可以全填W，那么就从源点连向该 \(2 \times 2\) 网格的W点，容量为 \(1\)，如果可以全填B，就从B点连向汇点，容量为 \(1\)，同时每个 \(2 \times 2\) 网格的W点向B点连边，容量为 \(+\infty\)，同时把其它的矛盾关系也用 \(+\infty\) 边表述。
答案就是网络中容量为 \(1\) 的边的数量减去最小割。方案的构造就是最小割的方案。
code for H
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Dinic {
static const int N = 2e4 + 10;
struct edge {
int from, to, cap, flow;
edge(int u, int v, int c, int f): from(u), to(v), cap(c), flow(f) {}
};
vector<edge> edges; vector<int> G[N];
inline void AddEdge(int u, int v, int c) {
static int M;
edges.emplace_back(edge(u, v, c, 0)), edges.emplace_back(edge(v, u, 0, 0));
M = edges.size(); G[u].emplace_back(M - 2), G[v].emplace_back(M - 1);
}
inline void clear() {
edges.clear();
for(int i = 0; i < N; i ++) G[i].clear();
}
int s, t, cur[N], dist[N];
inline bool BFS() {
memset(dist, 0, sizeof dist);
dist[s] = 1; queue<int> Q; Q.push(s);
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(auto i : G[u]) {
edge &e = edges[i];
if(!dist[e.to] && e.flow < e.cap)
dist[e.to] = dist[e.from] + 1, Q.push(e.to);
}
}
return dist[t];
}
int dfs(int u, int F) {
if(u == t || F <= 0) return F;
int flow = 0;
for(int &i = cur[u]; i < G[u].size(); i ++) {
edge &e = edges[G[u][i]];
if(e.cap == e.flow || dist[e.to] != dist[e.from] + 1) continue;
int f = dfs(e.to, min(F, e.cap - e.flow));
flow += f, F -= f, e.flow += f, edges[G[u][i] ^ 1].flow -= f;
if(!F) break;
}
return flow;
}
int MaxFlow(int s, int t) {
this->s = s, this->t = t;
int ans = 0;
while(BFS()) {
memset(cur, 0, sizeof cur);
ans += dfs(s, INF);
}
return ans;
}
inline void make_array(int n, int m, int A[105][105]) {
static bool vis[N];
memset(vis, false, sizeof vis);
queue<int> Q; Q.push(s), vis[s] = true;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(auto i : G[u]) {
edge &e = edges[i];
if(e.cap == e.flow || vis[e.to]) continue;
if(!(e.to & 1)) {
int x = e.to / 2 / m, y = e.to / 2 % m;
A[x][y] = A[x + 1][y] = A[x][y + 1] = A[x + 1][y + 1] = 1;
}
vis[e.to] = true, Q.push(e.to);
}
}
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++)
if(A[i][j] == 0) A[i][j] = -1;
}
} solver;
const int N = 105;
int n, m, A[N][N];
char S[N][N];
inline int get(int x, int y) {return x * m + y; }
inline void Add(int a, int b) {
solver.AddEdge(a * 2, b * 2 + 1, INF);
solver.AddEdge(b * 2, a * 2 + 1, INF);
}
inline void solve() {
cin >> n >> m;
for(int i = 0; i < n; i ++) {
cin >> S[i];
for(int j = 0; j < m; j ++)
A[i][j] = (S[i][j] == '?' ? 0 : (S[i][j] == 'W' ? 1 : -1));
}
for(int i = 0; i < n; i += 2)
for(int j = 0; j < m; j ++)
A[i][j] = -A[i][j];
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j += 2)
A[i][j] = -A[i][j];
int S = get(n - 1, m - 1) * 2 + 2, T = S + 1, ans = 0;
for(int i = 0; i < n - 1; i ++) for(int j = 0; j < m - 1; j ++) {
bool P = true, Q = true;
P = (A[i][j] != -1 && A[i + 1][j] != -1 && A[i][j + 1] != -1 && A[i + 1][j + 1] != -1);
Q = (A[i][j] != 1 && A[i + 1][j] != 1 && A[i][j + 1] != 1 && A[i + 1][j + 1] != 1);
if(P) solver.AddEdge(S, get(i, j) * 2, 1), ans ++;
if(Q) solver.AddEdge(get(i, j) * 2 + 1, T, 1), ans ++;
solver.AddEdge(get(i, j) * 2, get(i, j) * 2 + 1, INF);
if(j < m - 2) Add(get(i, j), get(i, j + 1));
if(j > 0 && i < n - 2) Add(get(i, j), get(i + 1, j - 1));
if(i < n - 2) Add(get(i, j), get(i + 1, j));
if(j < m - 2 && i < n - 2) Add(get(i, j), get(i + 1, j + 1));
}
ans -= solver.MaxFlow(S, T);
cout << ans << '\n';
solver.make_array(n, m, A), solver.clear();
for(int i = 0; i < n; i += 2)
for(int j = 0; j < m; j ++)
A[i][j] = -A[i][j];
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j += 2)
A[i][j] = -A[i][j];
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++)
cout << (A[i][j] == 1 ? 'W' : 'B');
cout << '\n';
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
I. Future Coder
\[ab < a + b \Longleftrightarrow (a-1)(b-1) < 1 \nonumber \]将 \((a-1)(b-1) < 0\) 和 \((a-1)(b-1) = 0\) 分别考虑，前者就是 \(a_i-1 < 0\) 的是数量乘 \(a_i-1 > 0\) 的数量，后者也是容易统计的。单次询问时间复杂度 \(\mathcal{O}(n)\)。
code for I
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, A[N];
inline void solve() {
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> A[i], A[i] --;
int neg = 0, pos = 0, zero = 0;
for(int i = 1; i <= n; i ++) {
if(A[i] < 0) neg ++;
else if(A[i] == 0) zero ++;
else pos ++;
}
cout << 1ll * neg * pos + 1ll * zero * (neg + pos) + 1ll * zero * (zero - 1) / 2 << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
J. Elden Ring
根据 \(A,B\) 的大小关系分类讨论：
-
当 \(A=B\)，保留点 \(1\) 和 \(l_u < l_1\) 的那些点 \(u\)，跑 \(1\) 到 \(u\) 的最短路。
-
当 \(A<B\)，同样是最短路，区别在于Dijkstra扩展的时候，若到达点 \(v\) 时已经打不动该boss则不扩展。
-
当 \(A>B\)，先用一个堆找出来所有可以打的点，扩展时若点 \(v\) 无论如何也打不了就不扩展，否则用当前距离与至少需要在第几天的时候才可以打点 \(v\) 上的boss的较大值更新点 \(v\) 的最短路。
所以只需要跑一次最短路即可，单组数据的时间复杂度为 \(\mathcal{O}(m \log m)\)。
code for J
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 10, M = 4e5 + 10, INF = 0x3f3f3f3f;
int n, m, A, B, l[N], h[N], e[M], ne[M], idx;
inline void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++; }
namespace solver {
int dist[N]; bool st[N];
int C[N], Min[N];
inline void Dijkstra() {
memset(dist + 1, 0x3f, sizeof(int) * n);
memset(st + 1, false, sizeof(bool) * n);
dist[1] = 0;
priority_queue<pii, vector<pii>, greater<pii>> Q;
Q.push({dist[1], 1});
while(!Q.empty()) {
int u = Q.top().second; Q.pop();
if(st[u]) continue; st[u] = true;
for(int i = h[u]; i != -1; i = ne[i]) {
int v = e[i]; if(st[v] || dist[u] + 1 > C[v]) continue;
if(dist[v] > max(dist[u] + 1, Min[v])) {
dist[v] = max(dist[u] + 1, Min[v]);
Q.push({dist[v], v});
}
}
}
if(dist[n] == INF) cout << "-1" << '\n';
else cout << dist[n] << '\n';
}
}
namespace solver1 {
inline void main() {
for(int i = 2; i <= n; i ++)
solver::C[i] = (l[i] < l[1] ? n + 1 : -1);
for(int i = 2; i <= n; i ++)
solver::Min[i] = -1;
solver::Dijkstra();
}
}
namespace solver2 {
inline void main() {
for(int i = 2; i <= n; i ++)
solver::C[i] = (l[i] < l[1] ? (l[1] - l[i] + B - A - 1) / (B - A) : -1);
for(int i = 2; i <= n; i ++)
solver::Min[i] = -1;
solver::Dijkstra();
}
}
namespace solver3 {
bool vis[N], ok[N];
inline int get(int u) {
if(l[u] < l[1]) return -1;
return (l[u] - l[1] + 1 + A - B - 1) / (A - B) + 1;
}
void main() {
priority_queue<pii, vector<pii>, greater<pii>> Q;
int now = -1;
memset(vis + 1, false, sizeof(bool) * n);
memset(ok + 1, false, sizeof(bool) * n);
Q.push({-1, 1}), vis[1] = true;
while(!Q.empty()) {
auto u = Q.top(); Q.pop();
if(u.first > now + 1) break;
ok[u.second] = true, now ++;
for(int i = h[u.second]; i != -1; i = ne[i]) {
int v = e[i]; if(vis[v]) continue;
vis[v] = true; Q.push({get(v), v});
}
}
for(int i = 2; i <= n; i ++)
if(!ok[i]) solver::C[i] = -1;
else solver::C[i] = n + 1, solver::Min[i] = get(i);
solver::Dijkstra();
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) {
cin >> n >> m >> A >> B;
memset(h + 1, -1, sizeof(int) * n), idx = 0;
for(int i = 1; i <= m; i ++) {
int a, b; cin >> a >> b;
add(a, b), add(b, a);
}
for(int i = 1; i <= n; i ++) cin >> l[i];
for(int i = 2; i <= n; i ++) l[i] += B;
if(A == B) solver1::main();
else if(A < B) solver2::main();
else solver3::main();
}
return 0;
}
K. Vision Test
暂时不能给你明确的答复。
L. Fenwick Tree
对每个 \(i\) 求出来有几个 \(j\) 满足 \(j + \operatorname{lowbit}(j) = i\) 并且 \(s_j=1\)。从小到大考虑每个 \(i\)，显然若 \(f_i \ge 2\)，那么 \(s_i\) 无论是 \(0\) 还是 \(1\)，总可以被之前的操作满足。否则若 \(f_i=1\)，那么之前的操作必然会使 \(f_i\) 不为 \(0\)，此时若 \(s_i=0\)，就需要一个操作；如 \(f_i=0\)，此时若 \(s_i=1\) 就需要一个操作。
单租数据的时间复杂度为 \(\mathcal{O}(n)\)。
code for L
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n; string str;
inline void solve() {
cin >> n >> str; str = "$" + str;
int res = 0; vector<int> C(n + 1, 0);
for(int i = 1; i <= n; i ++) if(str[i] == '1') {
if(i + (i & -i) <= n) C[i + (i & -i)] ++;
}
for(int i = 1; i <= n; i ++) {
if(str[i] == '0' && C[i] == 1) res ++;
if(str[i] == '1' && C[i] == 0) res ++;
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}