2021-team7-008

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2021-team7 返回]

== Rank和提交情况 ==
[[Image(Standing.jpg, 1000px)]]

Solved: 7/10

rank（校内）：~~10/12~~9/12

== 流水账 ==

by fr

开场签到，我签 F (1,9/1)，scl 签 D (2,20/1)，chy 签 B，因为没输出 Stuck WA 了一发 (3,26/2)。

chy 此前已开出 A 并发现这是一道简单的博弈论题，我上去打个 200 以内的表，没发现规律但发现 Bob 赢的情况非常少。于是直接用 5 min 打完 5000 的表，发现 Bob 赢只有 1359 种情况，直接把表交上去就过了 (4,58/1)。

然后榜上过的最多的是 H。我读完题就把它转化成“两个数之差不能整除 m”的正确方向，但我们随后就在想各种 DS 去维护这个信息（如 bitset，分块等）。在卡了 60 min 后，chy 提出可以用差卷积（洛谷上做过几乎一模一样套路的题！！为什么这么我长时间都没想到！！！！！！）维护这个东西，然后我抄了个板子就过了 (5,150/1)。

然后 G I 两题过的人较多，于是我们分别开这两道题。chy 想出 G 的贪心做法但不会证明，讨论一下觉得没问题就上去写了。因为特判没写 return 0 贡献一发 WA，改完就过了 (6,234/2)。

我按照套路推出 I 的 n^4^ 期望DP，但它难以优化，于是让他们再去开个 E。E 开完的同时 chy 提出可以把状态修改一下，它变成了 n^3^，再用树状数组优化变成了 n^2^logn，虽然这个复杂度过 n <= 5000 有点离谱但时间紧张我还是直接上去写了。调过样例后直接提交，在比赛结束前 6 分钟绝杀 I 题 (7,294/1)（1965ms卡脖子过的）。

这场如果 H 不卡住应该可以过 8 题的。

== 个人总结 ==

fr：差卷积这种经典套路没想到真的不应该。谢罪。

scl：又是只有签到的一天……至少还是提供了一点点I的状态思路？还是需要好好学习一下怎么分析复杂度，补题的时候发现暴搜都能打挂掉……练练练！

== 题解 ==

A: 打表（fr）

B: 几何（chy）

C: 

D: 签到（scl）

E: 

F: 签到（fr）

G：贪心（chy）

H: 差卷积（fr & chy sol）

I：期望 DP + 树状数组优化（fr）

J:

[/wiki/2021-team7 返回]

Rank和提交情况

Solved: 7/10

rank（校内）：10/129/12

流水账

by fr

开场签到，我签 F (1,9/1)，scl 签 D (2,20/1)，chy 签 B，因为没输出 Stuck WA 了一发 (3,26/2)。

chy 此前已开出 A 并发现这是一道简单的博弈论题，我上去打个 200 以内的表，没发现规律但发现 Bob 赢的情况非常少。于是直接用 5 min 打完 5000 的表，发现 Bob 赢只有 1359 种情况，直接把表交上去就过了 (4,58/1)。

然后榜上过的最多的是 H。我读完题就把它转化成“两个数之差不能整除 m”的正确方向，但我们随后就在想各种 DS 去维护这个信息（如 bitset，分块等）。在卡了 60 min 后，chy 提出可以用差卷积（洛谷上做过几乎一模一样套路的题！！为什么这么我长时间都没想到！！！！！！）维护这个东西，然后我抄了个板子就过了 (5,150/1)。

然后 G I 两题过的人较多，于是我们分别开这两道题。chy 想出 G 的贪心做法但不会证明，讨论一下觉得没问题就上去写了。因为特判没写 return 0 贡献一发 WA，改完就过了 (6,234/2)。

我按照套路推出 I 的 n4 期望DP，但它难以优化，于是让他们再去开个 E。E 开完的同时 chy 提出可以把状态修改一下，它变成了 n3，再用树状数组优化变成了 n2logn，虽然这个复杂度过 n <= 5000 有点离谱但时间紧张我还是直接上去写了。调过样例后直接提交，在比赛结束前 6 分钟绝杀 I 题 (7,294/1)（1965ms卡脖子过的）。

这场如果 H 不卡住应该可以过 8 题的。

个人总结

fr：差卷积这种经典套路没想到真的不应该。谢罪。

scl：又是只有签到的一天……至少还是提供了一点点I的状态思路？还是需要好好学习一下怎么分析复杂度，补题的时候发现暴搜都能打挂掉……练练练！

题解

A: 打表（fr）

B: 几何（chy）

C:

D: 签到（scl）

E:

F: 签到（fr）

G：贪心（chy）

H: 差卷积（fr & chy sol）

I：期望 DP + 树状数组优化（fr）

J:

附加文件