2021-team7-025

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team7 返回]

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

Solved: 8/11

rank：12/257 (现场), 32/992 (vp)

== 流水账 ==

by fr

开场签到 A(1,6/0)，K(2,8/0)，D(3,10/0)，G(4,12/0)。

然后开了 C，先写了个爆搜，TLE on 64。然后改了改继续 T。于是想了个（伪的）O(n^3^) 做法，从 20min 卡到 70min。

看到 I 过了很多于是先去过了 I(5,101/0)，回去继续搞 C。再 WA 了几发后冷静下来证明了做法是错的，回去继续爆搜继续 T。想了个状压但是状态是 2^36^ 的，然后优化了一下变成 2^18^ 惊喜地发现它可以过，写写就过了 (6,160/11)。

此时榜上有 B E F，B 过的最多。但是我开了 E 而且把它秒了 (7,184/13)。

然后看 B 但是不会，看 F，发现是原题加强版，想了 30min 优化就会了，上去写一发过了 (8,255/13)。

剩下时间继续卡 B 但是还是不会。看了 J 但这种看上去就很不好做的树形 DP 也没啥思路。最终 8 题罚时垫底收场。

== 个人总结 ==

fr: 我永远不会 DP/zj

== 题解 ==

A: 签到，模拟

B: 

C: 状压 DP。只有一个景点的公司不要压到状态里。

D: 签到，sum{max{a[i-1],a[i]}}

E: 首先 k=max{f[i]}/max{a[i]}，然后 k 确定之后用 倍增+背包 即可求出 k 个物品的答案，跟 f 比较一下即可。

F: 哈希把 一行/一列 看成一个字符，然后 KMP 求循环节。

G：签到，1/n

H: 

I：签到，模拟

J: 

K: 签到，模拟

[/wiki/2021-team7 返回]

Rank和提交情况

Solved: 8/11

rank：12/257 (现场), 32/992 (vp)

流水账

by fr

开场签到 A(1,6/0)，K(2,8/0)，D(3,10/0)，G(4,12/0)。

然后开了 C，先写了个爆搜，TLE on 64。然后改了改继续 T。于是想了个（伪的）O(n³) 做法，从 20min 卡到 70min。

看到 I 过了很多于是先去过了 I(5,101/0)，回去继续搞 C。再 WA 了几发后冷静下来证明了做法是错的，回去继续爆搜继续 T。想了个状压但是状态是 2³⁶ 的，然后优化了一下变成 2¹⁸ 惊喜地发现它可以过，写写就过了 (6,160/11)。

此时榜上有 B E F，B 过的最多。但是我开了 E 而且把它秒了 (7,184/13)。

然后看 B 但是不会，看 F，发现是原题加强版，想了 30min 优化就会了，上去写一发过了 (8,255/13)。

剩下时间继续卡 B 但是还是不会。看了 J 但这种看上去就很不好做的树形 DP 也没啥思路。最终 8 题罚时垫底收场。

个人总结

fr: 我永远不会 DP/zj

题解

A: 签到，模拟

B:

C: 状压 DP。只有一个景点的公司不要压到状态里。

D: 签到，sum{max{a[i-1],a[i]}}

E: 首先 k=max{f[i]}/max{a[i]}，然后 k 确定之后用倍增+背包即可求出 k 个物品的答案，跟 f 比较一下即可。

F: 哈希把一行/一列看成一个字符，然后 KMP 求循环节。

G：签到，1/n

H:

I：签到，模拟

J:

K: 签到，模拟

附加文件

0.jpg by fr200110217102