VP 2022 ICPC 沈阳

The 2022 ICPC Asia Shenyang Regional Contest (The 1st Universal Cup, Stage 1: Shenyang)

这个题解怎么和 Claris 一个 slides 板子,给我看 ptsd 了(

Problems AC
A. Absolute Difference 待补
B. Binary Substrings
C. Clamped Sequence
D. DRX vs. T1
E. Graph Completing
F. Half Mixed
G. Meet in the Middle 待补
H. P-P-Palindrome 待补
I. Quartz Collection
J. Referee Without Red
K. Security at Museums
L. Tavern Chess
M. Vulpecula

D 签到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void solve() {
string s;
cin >> s;

int x = 0;
int y = 0;

for (auto ch : s) {
if (ch == 'D') {
x++;
}
if (ch == 'T') {
y++;
}

if (x > 2 or y > 2) {
break;
}
}

if (x > 2) {
puts("DRX");
} else {
puts("T1");
}
}

C

赛时秒出思路但是吃了发罚时,队友提醒了下发现 a[i] 作为上下界都可以,但是忘了枚举其中一种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
void solve() {
int n = read(), d = read();
int ans = 0;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}

for (int i = 1; i <= n; i++) {
int L = a[i], R = a[i] + d;

int res = 0;
for (int j = 1; j < n; j++) {
int x = a[j];
int y = a[j + 1];
x = max(x, L);
x = min(x, R);
y = max(y, L);
y = min(y, R);
res += abs(x - y);
}

ans = max(ans, res);
}

for (int i = 1; i <= n; i++) {
int L = a[i] - d, R = a[i];

int res = 0;
for (int j = 1; j < n; j++) {
int x = a[j];
int y = a[j + 1];
x = max(x, L);
x = min(x, R);
y = max(y, L);
y = min(y, R);
res += abs(x - y);
}

ans = max(ans, res);
}

cout << ans << '\n';
}

L

炉管题,队友做了。

F 贪心,构造

太神必了这题。

子矩形数量是 $\frac{n(n + 1)}{2} \times \frac{m(m + 1)}{2}$,如果这个数量是奇数则显然无解。
否则 $\frac{n(n + 1)}{2}$ 和 $\frac{m(m + 1)}{2}$ 至少有一个是偶数。不妨设后者是偶数。

赛时打表发现可以将问题转化到一维上去,然后堆叠起来。也就是解决 $1 \times m$ 的问题然后堆叠 $n$ 行。

对于一个 $1 \times m$ 的矩形,子矩形数量是 $\frac{m(m + 1)}{2}$,设每一个同色区间的长度是 $a_i$。那么纯色子区间数量就是 $\sum_{i = 1}^k{\frac{a_i(a_i + 1)}{2}}$,则问题转化为解下列方程组:

  • $\sum_{i = 1}^{k} a_i = m$
  • $\sum_{i = 1}^k{\frac{a_i(a_i + 1)}{2}} = \frac{m(m + 1)}{4}$

不难证明一定存在一组解,构造时贪心让每个 $a_i$ 尽可能大即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
void solve() {
int n, m;
cin >> n >> m;

vector<int> a(n, 1);
int h = 0, t = n - 1;
int tar = n * (n - 1) / 2;
int val = n;

while (h < t and val < tar) {

int nval = val - a[h] * a[h] + (a[h] + 1) * (a[h] + 1) - 1;

if (val < nval and nval <= tar) {
val = nval;
a[h] += 1;
t--;
} else {
h++;
}
}

if (val == tar) {
puts("Yes");

for (int i = 0, k = 0; i <= t; i++, k ^= 1) {
for (int rj = 1; rj <= a[i]; rj++) {
for (int j = 1; j <= m; j++) {
cout << k << " \n"[j == m];
}
}
}
return;
}

std::swap(n, m);

a.assign(n, 1);
h = 0, t = n - 1;
tar = n * (n - 1) / 2;
val = n;

while (h <= t and val < tar) {

int nval = val - a[h] * a[h] + (a[h] + 1) * (a[h] + 1) - 1;
if (val < nval and nval <= tar) {
val = nval;
a[h]++;
t--;
} else {
h++;
}
}

std::swap(n, m);

if (val == tar) {
puts("Yes");

for (int i = 1; i <= n; i++) {
for (int j = 0, k = 0; j <= t; j++, k ^= 1) {
for (int rj = 1; rj <= a[j]; rj++) {
cout << k << " \n"[j == t and rj == a[j]];
}
}
}
return;
}
puts("No");
}

I 贪心、线段树

总的和是固定的,可以将游戏看作每块石头价值 $b_i$,但是先选的话就有 $a_i - b_i$ 的收益,后选的话收益为 $0$。

因此实际上双方就是按照 $a_i - b_i$ 从小到大分别选。A 拿第 0 个,B 拿第 1, 2 个,A 拿第 3, 4 个,以此类推,A 会拿 rank % 4 = 0 或 3 的。

因此维护一个权值线段树,下标是 $a_i - b_i$,维护区间内排名 % 4 相同的数的和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
struct SGT {
int cnt[N << 2];
int sum[N << 2][4];
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid (l + r >> 1)
void pushup(int p) {
cnt[p] = cnt[ls] + cnt[rs];
sum[p][0] = sum[p][1] = sum[p][2] = sum[p][3] = 0;
for (int i = 0; i < 4; i++) {
sum[p][i] += sum[ls][i];
sum[p][(cnt[ls] + i) % 4] += sum[rs][i];
}
}

void upd(int p, int l, int r, int pos, int val) {
if (l == r) {
if (val > 0) sum[p][cnt[p] % 4] += pos;
else sum[p][(cnt[p] - 1) % 4] -= pos;

cnt[p] += val;
return;
}

if (pos <= mid) upd(ls, l, mid, pos, val);
else upd(rs, mid + 1, r, pos, val);
pushup(p);
}
void upd(int pos, int val) {
upd(1, -1e5, 1e5, pos, val);
}
int qry(int p = 1) {
int res = sum[ls][0] + sum[ls][3];

if (cnt[ls] * 2 % 4 == 0) {
res += sum[rs][0] + sum[rs][2];
} else {
res += sum[rs][1] + sum[rs][3];
}

return res;
}

} seg;

void solve() {
int n = read(), m = read();

int sumb = 0;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
a[i] = read(), b[i] = read();

seg.upd(a[i] - b[i], 1);
sumb += b[i];
}

cout << sumb + seg.qry() << '\n';
for (int i = 1; i <= m; i++) {
int t = read(), x = read(), y = read();

sumb -= b[t], sumb += y;
seg.upd(a[t] - b[t], -1);
a[t] = x, b[t] = y;
seg.upd(a[t] - b[t], 1);
cout << sumb + seg.qry() << '\n';
}
}

A Calculus

\begin{aligned}
& \int_l^r \int_l^r |x-y| \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \int_0^{r-l} |(x + l)-(y + l)| \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \int_0^{r-l} |x-y| \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \left(\int_0^{x} (x - y) + \int_x^{r-l} (y - x) \right) \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \left(\int_0^{x}x - \int_0^{x}y + \int_x^{r-l}y - \int_x^{r-l}x \right) \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \left(\int_0^{x}x - \int_x^{r-l}x - \int_0^{x}y + \int_x^{r-l}y \right) \mathrm{d} x \mathrm{d} y\\
&= \int_0^{r-l} \left(x^2 - x(r - l - x) + \frac{1}{2} (r-l)^2 - x^2 \right) \mathrm{d} x\\
&= \int_0^{r-l} \left( x^2 - x(r - l) + \frac{1}{2} (r-l)^2\right) \mathrm{d} x\\
&= \frac{(r-l)^3}{3}\\
\end{aligned}

E 边双、容斥、TreeDP

给定一个 $n$ 个点 $m$ 条边的简单无向图,可以加入任意多条(包括 $0$ 条)边,使得这张图边双联通,求加边的方案数。

边双联通的定义:任意不同的两点存在至少两条没有重复边的简单路径。

对原图进行边双缩点,由于原图是连通的,缩点之后会得到一棵树。此时每加一条边 $(u, v)$ 就会对树上 $u$ 到 $v$ 的树上路径进行覆盖,当所有树边都被覆盖时就得到了一个边双连通图。

现在问题转化为:加若干条边,使得这棵树的每条树边都被新加的非树边覆盖至少一次。求方案数。

这个方案数不好求,考虑容斥:设至少有 $k$ 条边没被覆盖的方案数为 $g_k$,则答案为 $\sum_{k}(-1)^{k}g_k$。

把这个容斥扔到树上做 TreeDP。如果一些边被钦定了没被覆盖,那么这些边会把原树划分成若干连通块,连通块内任意连边。

设 $dp_{u, i}$ 表示以 $u$ 为根的子树的连通块大小为 $i$ 时子树内的方案数。转移时考虑一个子树 $v$ 是否连上来(即边 $(u, v)$ 是否被覆盖)。如果连上来的话就是乘上一个 $2^{siz_u + siz_v - 1}$ 的系数(减去的 1 是那条已经有的树边,除此之外的边都可以覆盖这条边),没连上来的话就是容斥系数 $-1$。

注意每个子树根节点的初值应设为 $dp_{u, siz_u} = 2^{\frac{siz_u(siz_u - 1)}{2} - cnte_u}$,其中 $cnte_u$ 表示边双连通分量中的边数。

注意要写个光速幂,这样转移的时候可以少个快速幂的 log。

另,用的是哥哥的 EBCC 板子,发现那个板子算 cnte 好像是有问题的,debug 了半天。。。。而且看了眼哥哥的代码,写的有点过于神秘了,看不懂。。。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>
using i64 = long long;
#define int i64
using std::cerr;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
return f ? -x : x;
}

using pii = std::pair<int, int>;
struct EBCC {
int n, cur, cnt;
vector<vector<int>> adj;
vector<int> stk, dfn, low, bel;
EBCC() {}
EBCC(int n) { init(n); }
void init(int n) {
this->n = n;
adj.assign(n, {}), dfn.assign(n, -1);
low.resize(n), bel.assign(n, -1);
stk.clear(), cur = cnt = 0;
}
void addEdge(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); }
void dfs(int x, int p) {
dfn[x] = low[x] = cur++, stk.push_back(x);
for (auto y : adj[x]) {
if (y == p) continue;
if (dfn[y] == -1)
dfs(y, x), low[x] = std::min(low[x], low[y]);
else if (bel[y] == -1)
low[x] = std::min(low[x], dfn[y]);
}
if (dfn[x] == low[x]) {
int y;
do { y = stk.back(), bel[y] = cnt, stk.pop_back(); } while (y != x);
cnt++;
}
}
std::vector<int> work() { return dfs(0, -1), bel; }
struct Graph {
int n;
vector<pii> edges;
vector<int> siz, cnte;
};
Graph compress() {
Graph g; g.n = cnt;
g.siz.resize(cnt), g.cnte.resize(cnt);
for (int i = 0; i < n; i++) {
g.siz[bel[i]]++;
for (auto j : adj[i]) {
if (bel[i] < bel[j]) g.edges.emplace_back(bel[i], bel[j]);
else if (i < j and bel[i] == bel[j]) g.cnte[bel[i]]++;
}
}
return g;
}
};

template <class T>
constexpr T power(T a, i64 b) { T res {1}; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - (i64)(1.L * a * b / p) * p; res %= p; if (res < 0) res += p; return res; }
template <i64 P>
struct MInt {
i64 x;
constexpr MInt() : x {0} {}
constexpr MInt(i64 x) : x {norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() { return P > 0 ? P : Mod; }
constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
constexpr i64 val() const { return x; }
constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
constexpr MInt inv() const { return power(*this, getMod() - 2); }
constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(x, rhs.x, getMod()); return *this; }
constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; }
constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; }
constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;

void solve() {
int n = read(), m = read();

EBCC g(n);
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
u--, v--;
g.addEdge(u, v);
}
g.work();
auto G = g.compress();

vector<Z> pw(n + 1), comp(n + 1);
pw[0] = 1;
for (int i = 1; i <= n; i++) {
pw[i] = pw[i - 1] * 2;
}
comp[0] = 1;
for (int i = 1; i <= n; i++) {
comp[i] = comp[i - 1] * pw[n];
}

int N = n;
n = G.n;

auto pow2 = [&](int b) {
return pw[b % N] * comp[b / N];
};

vector<vector<int>> adj(n);
for (auto [x, y] : G.edges) {
adj[x].push_back(y);
adj[y].push_back(x);
}

vector dp(n, vector<Z>(N + 1));
vector<int> siz(n);
std::function<void(int, int)> dfs = [&](int u, int fa) {
siz[u] = G.siz[u];
dp[u][siz[u]] = pow2(siz[u] * (siz[u] - 1) / 2 - G.cnte[u]);

for (auto v : adj[u]) {
if (v == fa) continue;
dfs(v, u);

vector<Z> ndp(N + 1);
for (int i = 1; i <= siz[u]; i++) {
for (int j = 1; j <= siz[v]; j++) {
ndp[i + j] += dp[u][i] * dp[v][j] * pow2(i * j - 1);
ndp[i] -= dp[u][i] * dp[v][j];
}
}

dp[u] = std::move(ndp);
siz[u] += siz[v];
}
};
dfs(0, -1);

Z ans = 0;
for (int i = 1; i <= N; i++) {
ans += dp[0][i];
}

cout << ans << "\n";
}

signed main() {
solve();
return 0;
}
Author

TosakaUCW

Posted on

2024-10-18

Updated on

2024-11-07

Licensed under

Comments