2020 统一省选 Day1 题解

金老师给的任务。

icefire

题解

多于一种场地温度,显然双方消耗的总能量是能参赛的冰系战士能量和与能参赛的火系战士能量和的最小值。

设场地温度为 \(x\) 时,能参赛的冰系战士能量和为 \(f(x)\),能参赛的火系战士能量和为 \(g(x)\)

\(f(x)\) 单调不减,\(g(x)\) 单调不增。所以能使 \(g(x) \ge f(x)\) 的最大的 \(x\)\(f(x) \ge g(x)\) 的最小的 \(x\) 中一定有一个能使 \(\min(f(x),g(x))\) 取到最大值。

离散化一下,用数据结构维护 \(g(x)-f(x)\),支持快速询问大于等于 \(0\) 的最大位置和小于等于 \(0\) 的最小位置即可。很容易用线段树做到一个 \(\log\) 。(听 ZJC 说可以 BIT 上二分,但我不会 BIT TAT)由于题目要找最高的场地温度,如果存在 \(f(x)\ge g(x)\)\(x\) 使得 \(\min(f(x),g(x))\) 取到最大值,那么我们还需要找一下这个 \(x\) 之后最大的位置 \(y\) 使得 \(g(x)=g(y)\)

时间复杂度 \(\mathcal O(n\log n)\),用线段树维护差分来避免打标记,经过卡常在 CCF 的机器上可以通过。

代码

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2000010;

int sz, s0, s1;
int tmp[maxn];//, pos[maxn];

namespace Querys {
int op[maxn], arg1[maxn], arg2[maxn], arg3[maxn];
}

int Q, sum1[maxn << 2], sumc[maxn << 2];

/*void build(int l, int r, int rt) {
if (l == r) {
pos[l] = rt;
return;
}
int m = (l + r) >> 1;
build(l, m, rt<<1);
build(m+1, r, rt<<1|1);
}*/

void upd1(int p, int v) {
int l = 1, r = sz, rt = 1;
while (l != r) {
int m = (l + r) >> 1;
if (p <= m) {
r = m;
rt = rt << 1;
} else {
l = m+1;
rt = rt << 1 | 1;
}
}
sum1[rt] += v;
while (rt != 1) {
rt >>= 1;
sum1[rt] = sum1[rt<<1] + sum1[rt<<1|1];
}
}

void updc(int p, int v) {
int l = 1, r = sz, rt = 1;
while (l != r) {
int m = (l + r) >> 1;
if (p <= m) {
r = m;
rt = rt << 1;
} else {
l = m+1;
rt = rt << 1 | 1;
}
}
sumc[rt] += v;
while (rt != 1) {
rt >>= 1;
sumc[rt] = sumc[rt<<1] + sumc[rt<<1|1];
}
}

void upd_fire(int x, int v) {
// 0 .. x ok
s0 += v;
if (x + 1 <= sz) updc(x + 1, - v), upd1(x + 1, - v);
s1 += v;
}

void upd_ice(int x, int v) {
// x .. sz ok
updc(x, - v);
}

int ret1 = 0, retc = 0, leaf;

// s + x >= 0, last x ?
int cal1(int s, int l, int r, int rt) {
if (l == r) {
if (s + sumc[rt] >= 0) {
//cout << rt << endl;
ret1 += sum1[rt], retc += sumc[rt];
return l;
}
return -1;
}
int m = (l + r) >> 1;
if (s + sumc[rt<<1] >= 0) {
int res = cal1(s + sumc[rt<<1], m+1, r, rt<<1|1);
ret1 += sum1[rt<<1], retc += sumc[rt<<1];
if (res == -1) {
// << pos[m] << endl;
return m;
} else {
return res;
}
} else return cal1(s, l, m, rt<<1);
}

// s + x <= 0, first x ?
int cal2(int s) {
int l = 1, r = sz, rt = 1;
while (l != r) {
int m = (l + r) >> 1;
if (s + sumc[rt<<1] <= 0) {
r = m; rt = rt << 1;
} else {
ret1 += sum1[rt<<1], retc += sumc[rt<<1];
s += sumc[rt<<1];
l = m+1; rt = rt<<1|1;
}
}
ret1 += sum1[rt], retc += sumc[rt];
if (s + sumc[rt] <= 0) return l;
else return -1;
}

int ask1(int p) {
int ret = 0, l = 1, r = sz, rt = 1;
while (l != r) {
int m = (l + r) >> 1;
if (p <= m) {
r = m;
rt = rt<<1;
} else {
ret += sum1[rt<<1];
l = m+1;
rt = rt<<1|1;
}
}
//cout << rt << endl;
return ret + sum1[rt];
}

int askc(int p) {
int ret = 0, l = 1, r = sz, rt = 1;
while (l != r) {
int m = (l + r) >> 1;
if (p <= m) {
r = m;
rt = rt<<1;
} else {
ret += sumc[rt<<1];
l = m+1;
rt = rt<<1|1;
}
}
//cout << rt << endl;
return ret + sumc[rt];
}

int W;

int cal3(int s, int l, int r, int rt) {
if (l == r) {
if (s + sum1[rt] >= W) return l;
return -1;
}
int m = (l + r) >> 1;
if (s + sum1[rt<<1] >= W) {
int res = cal3(s + sum1[rt<<1], m+1, r, rt<<1|1);
if (res == -1) return m;
else return res;
} else return cal3(s, l, m, rt<<1);
}

int getInt() {
// int x; scanf("%d", &x);
// return x;
int ret = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
ret = ret * 10 + (c - '0');
c = getchar();
}
return ret;
}

int main() {
freopen("icefire.in", "r", stdin);
freopen("icefire.out", "w", stdout);
scanf("%d", &Q);
for (int i = 1; i <= Q; i++) {
Querys::op[i] = getInt();
if (Querys::op[i] == 1) {
Querys::arg1[i] = getInt(), Querys::arg2[i] = getInt(), Querys::arg3[i] = getInt();
tmp[++ sz] = Querys::arg2[i];
} else {
Querys::arg1[i] = getInt();
}
}
// build(1, sz, 1);
sort(tmp + 1, tmp + sz + 1);
for (int i = 1; i <= Q; i++) if (Querys::op[i] == 1) Querys::arg2[i] = int (lower_bound(tmp + 1, tmp + sz + 1, Querys::arg2[i]) - tmp);
for (int i = 1; i <= Q; i++) {
if (Querys::op[i] == 1) {
int t = Querys::arg1[i], x = Querys::arg2[i], y = Querys::arg3[i];
if (t == 0) upd_ice(x, y);
else upd_fire(x, y);
} else {
int k = Querys::arg1[i];
int t = Querys::arg1[k], x = Querys::arg2[k], y = Querys::arg3[k];
if (t == 0) upd_ice(x, -y);
else upd_fire(x, -y);
}
int ans = 0, bp = -1;
// cal ans
ret1 = retc = 0;
int p1 = cal1(s0, 1, sz, 1);
if (p1 != -1) {
int vc = s0 + retc;
int v1 = s1 + ret1;
//cout << retc << " " << ret1 << endl;
//cout << askc(p1) << " " << ask1(p1) << endl;
//if (retc != askc(p1) || ret1 != ask1(p1)) {
// puts("???");
//}
int v2 = v1 - vc;
int v = min(v1, v2);
if (v > ans) {
ans = v;
bp = p1;
}
}
ret1 = retc = 0;
int p2 = cal2(s0);
if (p2 != -1) {
int vc = s0 + retc;
int v1 = s1 + ret1;
int v2 = v1 - vc;
int v = min(v1, v2);
if (v >= ans) {
ans = v;
bp = p2;
}
}
W = ans;
if (ans != -1) bp = cal3(s1, 1, sz, 1);
if (!ans) puts("Peace");
else printf("%d %d\n", tmp[bp], 2 * ans);
}
return 0;
}

problem

题解

考虑如何对给定的 \(n,c,x\) 计算 \(\sum_k k^c x^k \binom n k\)

把它看成关于 \(x\) 的多项式。设

\[ F_c(x)=\sum_k k^c x^k \binom n k \]

那么 \(F_0(x)=(1+x)^n\)

对于 \(c > 0\),有 \(F_c(x)=xF'_{c-1}(x)\)

可以发现 \(F_c(x)\) 可以表示为 \(G_c(x)(1+x)^{n-c}\) 的形式,其中 \(G_c(x)\) 是一个 \(c\) 次多项式。我们可以模拟求导过程得到所有的 \(G_c(x)\),然后把题目中给定的 \(x\) 代入,就得到了 \(F_0(x),\ldots,F_c(x)\)。然后再按照题目中的式子计算答案即可。

时间复杂度 \(\mathcal O(m^2)\)

代码

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
#include <bits/stdc++.h>

using namespace std;

const int maxm = 1010;

// mod = 1 !!!

int n, x, mod, m, ans;
int pw[maxm], F[maxm][maxm], a[maxm];

inline int mo(int x) {
if (x >= mod) return x - mod;
return x;
}

int qpow(int x, int y) {
int ret = mo(1);
while (y) {
if (y & 1) ret = 1LL * ret * x % mod;
x = 1LL * x * x % mod;
y >>= 1;
}
return ret;
}

int main() {
freopen("problem.in", "r", stdin);
freopen("problem.out", "w", stdout);
scanf("%d%d%d%d", &n, &x, &mod, &m);
for (int i = 0; i <= m; i++) scanf("%d", &a[i]);
pw[0] = mo(1);
for (int i = 1; i <= m; i++) pw[i] = 1LL * pw[i-1] * x % mod;
F[0][0] = mo(1);
for (int i = 1; i <= m; i++) {
F[i][0] = 0;
for (int j = 1; j <= i; j++) {
F[i][j] = mo(1LL * j * F[i-1][j] % mod + 1LL * F[i-1][j-1] * (n - i + j) % mod);
}
}
for (int i = 0; i <= m; i++) {
int K = 1LL * qpow(mo(1+x), n-i) * a[i] % mod;
int sum = 0;
for (int j = 0; j <= i; j++) {
sum = mo(sum + 1LL * F[i][j] * pw[j] % mod);
}
ans = mo(ans + 1LL * sum * K % mod);
}
printf("%d\n", ans);
return 0;
}

shop

题解

问题相当于是给你了一个线性空间 \(V\),每个向量有一个初始权值,你要用最小的代价调整每个向量的权值使得一个给定的基是权值和最大的基,另一个给定的基是权值和最小的基。

为了方便,我们假设任意两个向量的权值不同。如果存在权值相同的向量,我们可以认为是给它加一个充分小的偏移量。

设一个向量 \(a \in V\) 的权值为 \(w(a)\),一个集合 \(S \subseteq V\) 的权值和为 \(w(S) = \sum_{a \in S} w(a)\)

引理 1 (交换性) 对于 \(A, B \subseteq V\),如果 \(A,B\) 线性无关,且 \(\lvert A \rvert < \lvert B \rvert\),则存在 \(x \in B \setminus A\),使得 \(A \cup \{x\}\) 线性无关。

证明 假设不存在这样的 \(x\),那么 \(B\) 中的所有元素都可以被 \(A\) 线性表出,从而 \(r(A) \ge r(B)\),又因为 \(A,B\) 线性无关,所以 \(\lvert A \rvert \ge \lvert B \rvert\),推出了矛盾。

下面的结论只依赖于拟阵的性质,所以对任意拟阵都成立。

引理 2:一个基 \(B\) 是权值和最大 (最小) 的基的充要条件是,不存在 \(x \notin B, y \in B\),使得 \(B + \{x\} - \{y\}\) 是一个权值和比 \(B\) 更大 (更小) 的基。

证明:只证最大。必要性是显然的。假设 \(B\) 不是权值和最大的基。设 \(B^*\) 为一组权值和最大的基,那么 \(w(B^*) \ge w(B)\)。设 \(x\)\(B \oplus B^*\) 中权值最大的元素。如果 \(x \in B\),考虑集合 \(S = \{a \mid a\in B, w(a) \ge w(x)\}\),显然 \(S\) 线性无关。如果 \(\lvert S \rvert < \lvert B^* \rvert\),根据引理 1,存在 \(a \in B^* \setminus S\) 使得 \(S \cup \{a\}\) 线性无关,把 \(a\) 加入 \(S\),然后重复这一过程。这样我们就得到了一组基 \(S\)\(\lvert B^* \setminus S \rvert = \lvert S \setminus B^* \rvert = 1\),且 \(w(S\setminus B^*) > w(B^* \setminus S)\),这与 \(B\) 是权值和最大的基矛盾,所以 \(x \in B^*\)。类似之前的过程,我们可以得到一组基 \(S\)\(\lvert B \setminus S\rvert = \lvert S\setminus B \rvert = 1\)\(S \setminus B = \{x\}\),设 \(B \setminus S = \{y\}\),那么 \(w(x) > w(y)\),从而 \(w(B+\{x\} - \{y\}) > w(B)\)

这样我们就可以把问题转化为这样的形式:有一个 \(n\) 个点,至多 \(128n\) 条边的有向图,一条边 \((u,v)\) 表示一个对点 \(u\) 的权值小于等于点 \(v\) 的限制。要求花费尽量少的代价修改点的权值使得所有限制被满足。

这是一个“保序回归”问题,下面简单描述一下做法。证明我先想一下,会了后可能会写一下。可以去看 18 年集训队论文。

假设你要在一个有向无环图 \(G\) 上做这个问题。所有点的最终权值都必须在 \([l,r]\) 中,\(l<r\),设 \(m=\lfloor \frac {l+r}2 \rfloor\)。假设每个点的权值都只能选 \(m\)\(m+1\),可以证明对于这个问题的一个最优方案,一定存在原问题的一个最优方案,使得这个问题选 \(m\) 的点在原问题的这个最优方案中权值在 \([l,m]\) 中,选 \(m+1\) 的点权值在 \([m+1,r]\) 中。这样我们就把问题转化为了两个子问题,把这个图分成两个子图,递归下去即可。

现在我们来解决如何求出每个点只能选 \(m\)\(m+1\) 时的最小代价。假设初始时所有点都选 \(m\),我们可以把一些点改成 \(m+1\)。那么我们可以求出改变每个点代价的变化量。我们希望所有改了的点的变化量之和尽量小,如果我们规定一个点的收益是改变它对代价的变化量的相反数,问题就变成了最大化收益和。这很容易用最大权闭合子图解决。

可以发现不缩点直接进行上述过程是等价的,也不需要传递闭包,因为如果在分治的过程中,点 \(u,v\) 出现了,那么它们之间任意路径上的点都会出现(因为权值要在 \(u\),\(v\) 之间)。(代码中可能有一些多余的步骤)

在 CCF 的机器上可以通过。

代码

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;

const int maxn = 1010;
const int maxm = 64;
const ll inf = 2e15;

ll ans = 0;

struct Edge {
int v, x;
ll c;
} E[maxn * maxn * 2];

int l[maxn], cur[maxn], L[maxn], Q[maxn], col[maxn], e;

struct netflow {
int S, T;
vector<int> vs;
void init() {
for (int i = 0; i < vs.size(); i++) {
int u = vs[i];
l[u] = -1;
col[u] = 0;
}
e = 0;
}
ll _find(int u, ll in) {
if (u == T) return in;
ll w = 0, t;
for (int &p = cur[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (L[v] == L[u] + 1 && E[p].c) {
if ((t = _find(E[p].v, min(E[p].c, in-w)))) {
E[p].c -= t;
E[p^1].c += t;
w += t;
if (w == in) break;
}
}
}
if (w < in) L[u] = -1;
return w;
}
int _bfs() {
for (int i = 0; i < vs.size(); i++) {
int u = vs[i];
L[u] = -1;
}
int s = 0, t = 0;
L[S] = 0; Q[t++] = S;
while (s < t) {
int u = Q[s++];
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (E[p].c && L[v] == -1) {
L[v] = L[u] + 1;
Q[t++] = v;
}
}
}
return L[T] != -1;
}
int dinic() {
ll res = 0, t;
while (_bfs()) {
for (int i = 0; i < vs.size(); i++) {
ll u = vs[i];
cur[u] = l[u];
}
while (t = _find(S, 0x3f3f3f3f)) res += t;
}
return res;
}
void addEdge(int u, int v, ll c) {
//cout << u << " " << v << " " << c << endl;
E[e].v = v, E[e].x = l[u], E[e].c = c, l[u] = e++;
E[e].v = u, E[e].x = l[v], E[e].c = 0, l[v] = e++;
}
void dfs(int u) {
col[u] = 1;
for (int p = l[u]; p >= 0; p = E[p].x) {
if (E[p].c) {
if (!col[E[p].v])
dfs(E[p].v);
}
}
}
} f;

int n, m;
ull c[maxn];
int a[maxn], b[maxn], val[maxn], v[maxn];
int vis[maxn];

vector<int> to[maxn], fr[maxn];

vector<pi> ed;

struct B {
ull b[65];
B() {for (int i = 0; i <= 64; i++) b[i] = 0;}
int check(ull x) {
for (int i = 64; i >= 0; i--) {
if (x & (ull(1) << i)) {
x ^= b[i];
}
}
return x == 0;
}
void add(ull x) {
for (int i = 64; i >= 0; i--) {
if (x & (ull(1) << i)) {
if (!b[i]) {
b[i] = x;
break;
} else x ^= b[i];
}
}
}
} b1[65], b2[65];

void dfs1(int u) {
vis[u] = 1;
for (int i = 0; i < to[u].size(); i++) {
if (!vis[to[u][i]]) dfs1(to[u][i]);
}
}

void dfs2(int u) {
vis[u] = 1;
for (int i = 0; i < fr[u].size(); i++) {
if (!vis[fr[u][i]]) dfs2(fr[u][i]);
}
}


ll cal(int a, int b) {
ll d = a - b;
return 1LL * d * d;
}

void solve(vector<int> vec, vector<pi> ve, int l, int r) {
f.vs.clear();
if (l == r) {
for (int i = 0; i < vec.size(); i++) {
val[vec[i]] = l;
}
return;
}
int mid = (l + r) >> 1;
f.vs = vec;
f.vs.push_back(n+1), f.vs.push_back(n+2);
f.S = n+1, f.T = n+2;
f.init();
for (int i = 0; i < ve.size(); i++) f.addEdge(ve[i].first, ve[i].second, inf);
ll w = 0, s = 0;
for (int i = 0; i < vec.size(); i++) {
int u = vec[i];
ll cost = cal(v[u], mid+1) - cal(v[u], mid);
w += cal(v[u], mid);
cost = -cost;
if (cost > 0) {f.addEdge(f.S, u, cost); s += cost;}
else f.addEdge(u, f.T, -cost);
}
ll res = f.dinic();
//cout << w - (s - res) << endl;
f.dfs(f.S);
vector<int> vs1, vs0;
vector<pi> ve1, ve0;
for (int i = 0; i < vec.size(); i++) {
int u = vec[i];
if (col[u] == 1) vs1.push_back(u);
else vs0.push_back(u);
}
for (int i = 0; i < ve.size(); i++) {
int u = ve[i].first, v = ve[i].second;
if (col[u] == col[v]) {
if (col[u] == 1) ve1.push_back(ve[i]);
else ve0.push_back(ve[i]);
}
}
solve(vs0, ve0, l, mid);
solve(vs1, ve1, mid+1, r);
}

int main() {
freopen("shop.in", "r", stdin);
freopen("shop.out", "w", stdout);
// do not use stdio
// ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 1; i <= m; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
if (j != i) {
b1[i].add(c[a[j]]);
b2[i].add(c[b[j]]);
}
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (j != a[i] && !b1[i].check(c[j])) {
ed.push_back(pi(a[i],j));
}
if (j != b[i] && !b2[i].check(c[j])) {
ed.push_back(pi(j,b[i]));
}
}
}
for (int i = 0; i < ed.size(); i++) {
to[ed[i].first].push_back(ed[i].second);
fr[ed[i].second].push_back(ed[i].first);
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) vis[j] = 0;
dfs1(a[i]);
for (int j = 1; j <= n; j++) if (vis[j] && j != a[i]) ed.push_back(pi(a[i], j));
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) vis[j] = 0;
dfs2(b[i]);
for (int j = 1; j <= n; j++) if (vis[j] && j != b[i]) ed.push_back(pi(j, b[i]));
}
int maxv = 0;
for (int i = 1; i <= n; i++) maxv = max(maxv, v[i]);
vector<int> vec;
for (int i = 1; i <= n; i++) vec.push_back(i);
sort(ed.begin(), ed.end()); ed.erase(unique(ed.begin(), ed.end()), ed.end());
solve(vec, ed, 0, maxv);
for (int i = 1; i <= n; i++) ans += 1LL * (v[i] - val[i]) * (v[i] - val[i]);
printf("%lld\n", ans);
return 0;
}