2021-team7-004

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team7 返回]

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

Solved: 3/11

rank（校内）：7/13

== 流水账 ==

by fr

由于 scl 临时有事，所以这场（约等于）双打。

开场我签 H (1,25/1)，然后发现榜上没人过题于是判断这场应该是毒瘤场。看 F 有人过于是和 chy 一起看 F 。9:50 chy 想出做法并跟我交流后上去写，过了(2,77/1)。

我开 G，想过容斥、组合意义和多项式代数推导等多种方法然而复杂度均不对。

期间我们读了剩下所有的题，感觉 A E J 比较可做，而且榜上 A E J 都有人提交，于是决定开这几道。

10:58 chy 说他会 A ，但是不确定自己能写出来，11:38 提交后 MLE 了，我提醒他去 CF 上测试极限数据，11:52 交第二发 TLE 了，同时公告空间放宽了（？？？），很快交了第三发，过了(3,178/3)。

G 仍然没有能过的思路，于是战略性弃掉，一起开 E。我们在开场就发现 E 是七月集训原题加修改，但想了很久都想不到 Queen 的操作如何支持修改。

12:45 我提出用可以维护前缀和的某些数据结构优化，但仍然没有思路。12:55 E被弃掉，我们又开了 J。

我之前已经看出 J 是凸包切线板子题。然而手头并没有板子，硬想也想不出来。chy 提出分 12 种情况分类讨论然而根本写不完了。结果就是 3 题结束。

== 个人总结 ==

fr：J 板子没备好我谢罪。另外感觉 G 是一个很常见的套路（甚至我自己还出过？），没想出来不太应该。。。

chy：
A的第一发MLE是过于相信STL（觉得string erase后会自动清干净），第二发是没有意识到100长度的字符串要101个空间（还有末尾结束符），导致有长度为100的字符串时strlen爆炸。这两发其实都是对字符串不熟悉造成的，跟时限放不放宽没有关系……（最后311ms,27M）。

E题因为以前做过类似的，被绕进去了。线段树维护区间累乘不应该想不到。一直在考虑把贡献相同的k压缩成一个状态……然后队长似乎也挺相信我的DS的……背锅

最后一个半小时我节奏完全乱掉了，变成了EJK三开，然后一个都想不出来，还跟队长交流带节奏……背锅

要抓紧时间提升自己了。现在来不及把自己变得全方面的强，那不如先把某些技能点满……QwQ

== 题解 ==

A: 压缩trie树（chy）

B: 

C: 

D: 

E：（chy待补）

F：贪心（chy）

G：容斥 + NTT（fr 赛后）

H: 签到（fr）

I：

J: （fr待补）

K:

[/wiki/2021-team7 返回]

Rank和提交情况

Solved: 3/11

rank（校内）：7/13

流水账

by fr

由于 scl 临时有事，所以这场（约等于）双打。

开场我签 H (1,25/1)，然后发现榜上没人过题于是判断这场应该是毒瘤场。看 F 有人过于是和 chy 一起看 F 。9:50 chy 想出做法并跟我交流后上去写，过了(2,77/1)。

我开 G，想过容斥、组合意义和多项式代数推导等多种方法然而复杂度均不对。

期间我们读了剩下所有的题，感觉 A E J 比较可做，而且榜上 A E J 都有人提交，于是决定开这几道。

10:58 chy 说他会 A ，但是不确定自己能写出来，11:38 提交后 MLE 了，我提醒他去 CF 上测试极限数据，11:52 交第二发 TLE 了，同时公告空间放宽了（？？？），很快交了第三发，过了(3,178/3)。

G 仍然没有能过的思路，于是战略性弃掉，一起开 E。我们在开场就发现 E 是七月集训原题加修改，但想了很久都想不到 Queen 的操作如何支持修改。

12:45 我提出用可以维护前缀和的某些数据结构优化，但仍然没有思路。12:55 E被弃掉，我们又开了 J。

我之前已经看出 J 是凸包切线板子题。然而手头并没有板子，硬想也想不出来。chy 提出分 12 种情况分类讨论然而根本写不完了。结果就是 3 题结束。

个人总结

fr：J 板子没备好我谢罪。另外感觉 G 是一个很常见的套路（甚至我自己还出过？），没想出来不太应该。。。

chy：

A的第一发MLE是过于相信STL（觉得string erase后会自动清干净），第二发是没有意识到100长度的字符串要101个空间（还有末尾结束符），导致有长度为100的字符串时strlen爆炸。这两发其实都是对字符串不熟悉造成的，跟时限放不放宽没有关系……（最后311ms,27M）。

E题因为以前做过类似的，被绕进去了。线段树维护区间累乘不应该想不到。一直在考虑把贡献相同的k压缩成一个状态……然后队长似乎也挺相信我的DS的……背锅

最后一个半小时我节奏完全乱掉了，变成了EJK三开，然后一个都想不出来，还跟队长交流带节奏……背锅

要抓紧时间提升自己了。现在来不及把自己变得全方面的强，那不如先把某些技能点满……QwQ

题解

A: 压缩trie树（chy）

B:

C:

D:

E：（chy待补）

F：贪心（chy）

G：容斥 + NTT（fr 赛后）

H: 签到（fr）

I：

J: （fr待补）

K:

附加文件