抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

今日、海を見た。もう怖くない

补题链接:https://codeforces.com/contest/1519

记录

竟然足足一周没有正经的训练了…… 唉,这样可不行啊

这一场的话 ABC 肯定是没啥问题的,D 能不能做出来心里还真的没底;毕竟正式 CF 也不会允许我打了三个题然后出去吃顿饭什么的,所以只能说悬(

题解

A - Red and Blue Beans

有手就行没手不行(

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int T, r, b, d;
for (input, T; T --;) {
input, r, b, d;
longs times = min(r, b);
longs delta = abs(r - b);
bool ok = delta <= times * d;
output, ok ? "YES" : "NO", endl;
}

return 0;
}

记得开 long long

B - The Cake Is a Lie

稍微手玩一会就会发现其实答案是固定的值;所以只需要计算答案之后比较大小就行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const auto null = nullptr;
int sum[105];

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

for (int i = 1; i < 105; ++ i)
sum[i] = sum[i - 1] + i;
int n, m, k, T;
for (input, T; T --;) {
input, n, m, k;
int sq = min(n, m);
int cost = abs(n - m) * sq;
cost += sum[sq] * 2 - sq - 1;
bool ok = cost == k;
output, ok ? "YES" : "NO", endl;
}

return 0;
}

手玩正方形,发现固定显然;再手玩长方形,发现多余的部分安哪里都一样,所以(

C - Berland Regional

n2105n \leq 2\cdot10^5 个学生,每个学生都有自己所属的大学uiu_i 和实力sis_i;设一组有kk 人,第jj 所大学一共有#j\#j 人:那么每个大学将会派出自己所属的实力最强的#jkk\lfloor \frac{\#j}k\rfloor \cdot k 人参加比赛;设比赛的影响力是所有参赛者的实力之和,求出k[1,n]k \in [1, n] 时赛站的实力。

对于某个大学,它只能对k[1,#j]k \in [1, \# j] 的比赛做出贡献——直接计算后累加就可以了;但是因为还要对每个大学的所有学生的实力进行排序,所以总复杂度是O(nlogn)\mathcal{O}(n\log n) 的。

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
const int N = 1e5 + 5;
int h[N], ans[N];

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int T = $.nextInt(), n, m, x;
priority_queue<pair<longs, int>> heap;
while (T --) {
$(n, m, x).nextArray(h + 1, h + 1 + n);
sort(h + 1, h + 1 + n);
for (int i = 0; i < m; ++ i) {
ans[n - i] = i + 1;
heap.push({ -h[n - i], i + 1 });
}
for (int i = n - m; i; -- i) {
auto [value, id] = heap.top();
heap.pop();
ans[i] = id, value -= h[i];
heap.push({ value, id });
}
longs mi = INT64_MAX, ma = 0;
while (!heap.empty()) {
auto [value, id] = heap.top();
minimize(mi, -value);
maximize(ma, -value);
heap.pop();
}
if (ma - mi <= x) $.put("YES").putArray(ans + 1, ans + 1 + n);
else $.put("NO");
}

return 0;
}

答案其实挺显然的,但是我还是想了半天(

D - Maximum Sum of Products

给了长度为n5000n \leq 5000 的数组aabb,现在你可以翻转数组aa 的一个连续子区间,问i=1naibi\sum_{i = 1}^n a_i \cdot b_i 的最大值

暴力枚举反转区间[i,j][i, j],时间复杂度是O(n3)\mathcal{O}(n^3) 的;考虑字符串算法中处理回文串的一些做法,我们可以枚举中间位置ii,然后左右拓展翻转的区间,这样就可以使翻转的复杂度降维;总复杂度O(n2)\mathcal{O}(n^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
const int N = 2e5 + 5;
int ll[N], rr[N], lc[N], rc[N];

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int T = $.nextInt(), n, l, r;
while (T --) {
$(n, l, r).nextArray(ll + 1, ll + 1 + l)
.nextArray(rr + 1, rr + 1 + r);
memset(lc, 0, sizeof(int) * (n + 1));
memset(rc, 0, sizeof(int) * (n + 1));
for (int i = 1; i <= l; ++ i) ++ lc[ll[i]];
for (int i = 1; i <= r; ++ i) ++ rc[rr[i]];
int lp = 0, rp = 0, lct = 0, rct = 0;
for (int i = 1; i <= n; ++ i) {
int ded = min(lc[i], rc[i]);
lc[i] -= ded, rc[i] -= ded;
lp += lc[i] / 2, lct += lc[i];
rp += rc[i] / 2, rct += rc[i];
}
int ded = min(lp, rp), ans = 0;
lct -= ded * 2, rct -= ded * 2;
lp -= ded, rp -= ded, ans += ded * 2;
if (lct > rct) swap(lct, rct), swap(lp, rp);
int more = rct - lct;
ded = min(more / 2, rp);
ans += ded, more -= ded * 2, rct -= ded * 2, rp -= ded;
if (rct > lct) {
ded = more / 2, more = 0;
rct -= ded, lct += ded, ans += ded;
}
ans += rct;
$.put(ans);
}

return 0;
}

比赛中的话我真的能写出来吗?应该把,应该把(

E - Off by One

二维平面的第一象限上有n2105n \leq 2\cdot10^5 个点;每次操作,你可以选择两个没有被选中过的点,分别将它们向右或者向上移动一个单位,如果这两个点和原点三点共线,那么这次操作是有效的。问你最多可以执行的有效操作数量,并输出一种可能的操作序列。

看起来很没有办法,但是涉及到简单平面几何,能想到的关键字也就那么多。但是即使这样,我也属实没有考虑到这实际上是一个暴力搜索的题目(

我们将每个点经过两种不同的移动之后得到的位置计算出来;那么,如果两个点可以进行一次有效的操作,就等价于它们变换得到的一个位置到原点的斜率是相等的;一个点可以进行两种不同的移动,就意味这一个点可以关联两种不同的斜率:这样,我们就得到了一张以斜率为点,而以每个可操作节点为边的图。

那么,问题就变成了找到最多的边对,它们之间共享了一个端点;或者说将每一条边分给一个端点,令端点ii 分到的边数为viv_i,那么答案就是vi2\sum\lfloor\frac{v_i}2\rfloor;这是一个非常经典的问题,一种解决思路就是 DFS:对于点ii,如果viv_i 是奇数,就把从父亲到自己的边给自己,否则就给父亲;这样就完成了对树边的分配:

那么 DFS 树中的其他边呢?因为这是一个无向图,对于其中的每一个连通块而言,其 DFS 都是一个生成树,也就是说不存在跨越边——剩下的边对于父亲来说是前向边,对于后代来说是后向边。那么对于这些边,为了实现方便,全部都给父亲即可——而且这样也可以显然得到,这种方案只会在总边数为奇数的时候,在根节点处浪费一条边。

很经典,就是利用到父亲的边平衡子树的奇偶性;最多浪费的那条边也就是连通块生成树的根节点,他没有父亲,所以如果真的不能匹配也就只能浪费掉了。

实现

因为斜率是铁分数,所以需要离散化(标号)

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
const int N = 2e5 + 5;
using Frac::frac;
pair<frac, frac> p[N];
array<int, N> vis;
vector<vector<pair<int, int>>> g;
vector<pair<int, int>> ans;

int dfs(int u) {
vis[u] = 1;
int cur = -1;
for (auto [v, ii] : g[u]) {
if (vis[v] == 1) continue;
int now = ii;
if (!vis[v]) {
int tmp = dfs(v);
if (tmp != -1) {
ans.emplace_back(now, tmp);
now = -1;
}
}
if (now != -1)
if (cur != -1) {
ans.emplace_back(cur, now);
cur = -1;
} else cur = now;
else;
}
return vis[u] = 2, cur;
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

int n = $.nextInt(), a, b, c, d;
g.resize(2 * n + 1);
map<frac, int> id;
int tot = 0;
const auto one = frac(1);
for (int i = 1; i <= n; ++ i) {
$(a, b, c, d);
auto x = frac(a, b), y = frac(c, d);
p[i] = pair(x.reduce(), y.reduce());
auto k1 = (y + one) / x, k2 = y / (x + one);
k1.normal(), k2.normal();
if (!id[k1]) id[k1] = ++ tot;
if (!id[k2]) id[k2] = ++ tot;
g[id[k1]].emplace_back(id[k2], i);
g[id[k2]].emplace_back(id[k1], i);
}
for (int i = 1; i <= tot; ++ i)
if (!vis[i]) dfs(i);
$.put(ans.size());
for (auto [a, b] : ans) $.put(a, b);

return 0;
}

实现意外简单(

F - Chests and Keys

nn 个宝箱,其中第ii 个包含了aia_i 个硬币;有mm 把钥匙,其中第jj 把可以卖bjb_j 个硬币。这些钥匙分别对应了不同种类的锁;如果要在第ii 个箱子上安装可以用第jj 把钥匙打开的锁,需要ci,jc_{i, j} 的成本;如果一个箱子上挂了多把锁,那么只有持有所有的这些钥匙才可以打开宝箱。

现在,Alice 持有这些宝箱和钥匙,并付出一定的成本来为箱子上锁;随后,Bob 会花一些硬币购买钥匙,并打开可以打开的所有宝箱以拿走其中的硬币;如果最后 Bob 的净利润严格大于 0,Bob 胜利;否则 Alice 胜利;现在,要求求出 Alice 必定胜利所需要付出的最少成本。

数据范围:1n,m61\leq n, m \leq 61ai,bj41\leq a_i, b_j \leq 41ci,j1071\leq c_{i, j} \leq 10^7

只能说看到这个题目,是非常的没有想法了;但是数据又很小,像极了乱搞……那么问题就是怎么乱搞了(

首先,在解决这个问题之前,我们先解决一个经过劣化后的问题—— 如果 Alice 上锁的方式已经确定,那么 Bob 要怎么购买钥匙才能获得最大的收益呢?

为了解决这个劣化后的问题,我们对题目中描述的模型进行建模:将宝箱全部看作连接了源点的节点,且和源点连边容量为aia_i;将钥匙全部看作链接了汇点的节点,且连边的容量为bjb_j;根据宝箱的上锁情况,从宝箱出发到对应的钥匙连边,边权是\infin;这样,我们就将上面的问题变成了一个网络流的问题。

那么,这个网络流的含义是什么呢?首先,我们可以获得的最大的收益是所有箱子的硬币之和,我们所支出的成本最多是所有的钥匙的价格之和;每当上锁,我们就相当于增加一个箱子打开的门槛—— 对于一个具体的箱子,我们打开它的成本是它所使用到的锁的钥匙的价格总和,但是不超过箱子能提供的硬币数量—— 没有人会去做一件亏本的事情。初始情况下,我们可以免费打开所有的箱子,但是因为上锁,所以我们需要付出额外的成本:因此,连边就代表了上锁带来的额外成本——这个箱子的成本需要由它上的锁对应的钥匙分担;综上所述,确定了上锁方案的情况下,Bob 得到的最大收益是:

i=1naimaxFlow\sum_{i = 1}^n a_i - \text{maxFlow}

如果一个箱子的收益完全被需要用来开它的钥匙抵消了,那么就没有开的价值了;但是如果一把钥匙承担了超过它本身价值的收益的话,那么这把钥匙就有买的必要;一种达到这个最大收益的办法是购买所有出边满流的钥匙,但是购买的钥匙数量未必是最少的。

虽然,这种建模方法和常见的裸的网络流并不一样:因为钥匙和箱子的关系是 & 的,因此如果按照代价建模的话,网络流可以恰好地考虑到钥匙开锁的性质和成本。

但是,即使数据范围像本题这样小,上锁方案还是有nmnm 种;如果要枚举所有的上锁方案,其时间复杂度是O(2nm)\mathcal{O}(2^{nm}) 的;因此,我们回到这个问题本身:注意到,如果 Bob 总是按照最大收益来进行操作的话,那么 Bob 的收益是不可能为负数的——因为 Bob 总是可以选择不购买任何钥匙,不打开任何的箱子,这样最后的总收入是 0;那么带入到上面的网络流模型中,就是所有的宝箱的价值都作为成本流量流入了汇点;换句话说,这个网络流的一个最小割是源点和其他所有节点。

那么考虑上述的网络流中没有任何上锁的连边,我们现在来考虑在这张图中连边;我们用状态[F1..n,L,R,P][F_{1..n}, L, R, P] 来表示当前的网络流图的连边状态:FiF_i 代表从源点到宝箱ii 的连边流出的成本,LL 表示当前考虑的宝箱,RR 表示当前考虑的钥匙编号jjPP 表示从钥匙jj 到汇点的连边流入的成本;现在,我们考虑所有的iji \to j 的连边,进行动态规划:

  • 跳过iji \to j:也就是这条边不上锁
  • 利用这条边转移一些成本:这条边上锁,但是转移的一部分流量

如果使用这条边转移流量,那么需要满足SiS \to ijTj \to T 的边都还有足够的流量剩余;更新状态之后,若所有的FiF_i 都已经满流了,则说明成本已经足够抵消所有的宝箱了,更新答案;同时,按照一个特定的顺序考虑[L,R][L, R],将下一对要考虑的点对更新到状态中。如果状态合法,就更新到 dp 数组中。

简单地说,因为数据范围小,我们枚举所有满足了约束条件的转移方法导致的状态,并计算所有的流空的状态的花费的最小值。因为流量最多为44,而最多的情况下也只有3636 条边,在考虑到每条边容量的约束条件,实际上状态数是相当有限的。

实现

一些小细节:我们考虑[L,R][L, R] 的顺序是先改变LL 再改变RR,这需要体现到映射函数中。

此外,因为考虑使用边运输流量的过程,一定是SS 流出的递增的过程,所以在映射函数中这一部分的值总是在最高位;

因为每次要将所有的[L,R][L, R] 的状态考虑周全,所以流出流量PP 在映射函数中是最低位的。

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
int n, m, a[10], b[10], c[10][10];
const int F = 4e7, inf = 0x3f3f3f3f;
int dp[F];

struct state {
vector<int> flow{};
int lf{}, rt{}, push{};

state() = default;
state(const vector<int> &flow, int lf, int rt, int push)
: flow(flow), lf(lf), rt(rt), push(push) {}
};

template <>
struct std::hash<vector<int>> :
public __hash_base<size_t, vector<int>> {
size_t operator()(const vector<int> &x) const noexcept {
size_t _hashcode = 0;
for (auto el : x) _hashcode = _hashcode * 5 + el;
return _hashcode;
}

vector<int> operator[](size_t hashcode) const noexcept {
vector<int> _ret(n);
for (int i = n - 1; i >= 0; -- i)
_ret[i] = int(hashcode % 5), hashcode /= 5;
return _ret;
}
};

template <>
struct std::hash<state> :
public __hash_base<size_t, state> {
size_t operator()(const state &x) const noexcept {
size_t _hashcode = hash<vector<int>>{}(x.flow);
_hashcode = _hashcode * 6 + x.rt;
_hashcode = _hashcode * 6 + x.lf;
_hashcode = _hashcode * 5 + x.push;
return _hashcode;
}

state operator[](size_t hashcode) const noexcept {
auto _push = int(hashcode % 5);
auto _lf = int((hashcode /= 5) % 6);
auto _rt = int((hashcode /= 6) % 6);
return state(
hash<vector<int>>{}[hashcode /= 6],
_lf, _rt, _push);
}
};

signed main() {
ios::sync_with_stdio(false);
cin.tie(null), cout.tie(null);

$(n, m).nextArray(a, a + n).nextArray(b, b + m);
const vector<int> va(a, a + n), vb(b, b + m);
for (int i = 0; i < n; ++ i)
$.nextArray(c[i], c[i] + m);
memset(dp, 0x3f, sizeof dp);
int ans = inf; dp[0] = 0;
for (int i = 0; i < F; ++ i) {
if (dp[i] == inf) continue;
auto s = hash<state>{}[i];
for (auto f : {0, 1, 2, 3, 4}) {
if (s.flow[s.lf] + f > a[s.lf] ||
s.push + f > b[s.rt]) break;
int pay = !f ? 0 : c[s.lf][s.rt];
auto now = s;
now.flow[s.lf] += f, now.push += f;
if (s.lf + 1 == n) {
now.lf = now.push = 0;
now.rt = s.rt + 1;
} else now.lf = s.lf + 1;
if (now.flow == va) minimize(ans, dp[i] + pay);
if (now.rt < m) {
auto id = hash<state>{}(now);
minimize(dp[id], dp[i] + pay);
}
}
}
$.put(ans == inf ? -1 : ans);

return 0;
}

只能说从网络流建模,到最后的那个 DP 求解,没有一个是现在的我能想出来的()图论,网络流,恐怖如斯——这也不是我近来第一次被网络流题目锤了== 得想点办法才行。

实际上,这个题涉及到的东西远不止这篇题解胡说八道的这么点,与之相关的知识点比想象中还是要多出许多的。

后记

没什么特别想说的,一周不写代码手感属实全无了== 实际上 E 也不算是什么难题虽然我也没有想到极角排序什么的,但是为什么每一次遇到这种题(不管是我自己打 cf 还是在线下训练中遇到了)都做的非常的费劲呢——还是做题思维的问题吧,ACM 之所以我这种人也能勉强打打,就是因为比起 OI 而言它会更加的注重思维水平;所以还是得多想多学(

此外,我的图论属实有些拉跨——这个 F 实际上还有很多关键词相关联:比如什么最大权闭合子图啊,什么霍尔定理啊,什么二分图匹配啊之类的,但是十分恐怖的是我都不会;就算是偏向思维的比赛,也是要建立在你有足够的知识积累的基础上,只能说这样属实不行()得花个专门的时间搞搞图论才行啊 ==

评论