2020-team0x06-C03

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team0x06 返回]

[[Image(Standings.png, 1000px)]][[BR]][[Image(Submissions.png, 600px)]]

== Statistics ==

 * TYPE: Contest
 * NAME: 2020 - ICPC - Nanjiang
 * PLAT: Nowcoder
 * MODE: Online
 * TIME: 2020.12.20 11:00-16:00
 * TEAM: Refrain[ntwbvdbl_oe, Orange_User, functionendless]
 * RANK: 17/543(Au)
 * SOLVE: 7/13(1562)
   * A-04:51(-19)
   * E-03:41(-2)
   * F-01:24(-1)
   * H-03:14(-2)
   * K-00:14
   * L-00:48
   * M-03:27(-1)
 * ATTEMPTING

== Comp ==

 * 从机房搬的打印机和显示器
 * 从Runespoor借来的几本板子和数列表
 * cute functionendless

== Day-1 ==

给czyh的笔记本配上环境，结果装好emacs后，包括devc++在内的各种地方出现了蜜汁乱码。czyh一脸哀怨，虽然这并不影响他发挥。lmh表示wsl才是正道，于是给wsl装上了gdb和java。

三人切掉RockyMountain，中途czyh去拿快递，结果路上和电动车相撞把自己的自行车撞坏了，czyh十分难受，希望献祭了自己的自行车能带给我们力量。

== Day0 ==

打了打bytedance网络赛，事实证明赛中进食会严重影响发挥。

三人打车把打印机和显示器搬到玉泉，并摆了个看起来就很宽的位置，将4张桌子全都利用起来，感觉电竞体验会提高不少。

== Day1 ==

开场各自看题，czyh'''K1Y14'''，然后czyh写了个滥用stl的复杂度带log的L，本地跑了3秒，于是把fx叫过去写L的two-pointer，'''L1Y48'''，czyh感到不爽，交了一下自己的程序，发现也过了，于是更不爽了。fx对着F推出了一个柿子，lmh觉得可以三分，fx验算了一遍，推出了另一个柿子。lmh自己推了推，推出了fx的第一个柿子，于是lmh上机去写三分，fx在机下求导。lmh写完没过样例，发现函数是单增的，且值域里没有样例。fx求完导也发现是单增的，同样没过样例，fx把czyh拉过来也求了遍导还是认为是单增的，三人一致认为是柿子错了。(fx和czyh现在还没发现哪里导错了)

czyh开出E，将lmh踢下机。lmh又推了一遍柿子，感觉没什么问题，让机上的czyh用python算了算，居然算出了样例的数。lmh才反应过来自己写挂了，改过了样例，提交WA。czyh测了测极限数据，发现爆longlong了，于是修改了三分的上界，'''F2Y84'''。

czyh对着E写了几种不同的随机拼在一起，但是都WA了。fx和lmh讨论M，得了一个看起来不错的做法，于是fx上机去写。lmh开出H，找czyh验了验，觉得没问题。fx写了一半，突然觉得复杂度不对，于是找lmh讨论。lmh给了一些想法，fx思考了一会儿（指在启发式合并，dsu on tree，重链剖分，长链剖分中试图分析复杂度），最后发现其实复杂度是对的，于是继续写。期间lmh见czyh在E上自闭，把A丢给他，czyh很有兴趣，上机写了一个checker并造了几组数据，没有效果。

fx写完没过样例，换lmh上机写H。fx频繁打断lmh并输出一些调试信息和更改细节，好一会才发现自己写好的dfsDP没有调用，改完依然没过样例。lmh写完获得WA，发现搜索范围小了。fx改好获得TLE，lmh改好也获得TLE，lmh打了个表，于是'''H3Y194'''。fx写了个dmk，把卡掉他的数据改对了，'''M2Y207'''。czyh捡起E上机，'''E3Y221'''。

由于罚时劣势，现在的6题一定没有Au，所以需要再搞一题，fx捡起D，拉着czyh讨论。lmh觉得他大概会做J，但由于从来没写过SegmentTreeBeats，所以一定写不出来，于是去搞A。lmh写了个退火，调czyh的checker，发现并无卵用，继续使用人类智慧。fx貌似搞出了D的做法，不久czyh把他叉掉了，czyh提出了随机化的算法，fx表示这东西怕是来不及写了，于是封榜后三人搞A。

czyh造了好几个数据，用checker测了测，只有一个正确率有8/100，其他都是0/100。lmh换了个思路构造，czyh在他的基础上改了改，居然跑到了25/100，三人欣喜地提交。

没过。

怀疑是rand的锅，多交几发还是一样，lmh把czyh的改动扩展了一下，居然变成了12/100。czyh又小改了一下，跑到了33/100!

还是没过。

三人很难受，觉得本地的checker和评测的checker大不一样，但又不知道应该怎么写checker。czyh开始变魔术，把数据旋转90度，镜像翻转……完全没用。

比赛还有10min结束，czyh决定把之前的所有构造都交一遍，1个，2个，3个，诶第二个怎么过了???

三人一脸懵，这明明是0/100的数据，居然恰好直击checker的灵魂。czyh数了数，我们交了20发，'''A20Y291'''，不过好歹有7题。

赛后发现其他过A的队伍都不是爆OJ过的，说明我们可不是乱搞的啊，我们只是提交数多了点。

听cjb说我们交的第一个构造跑了123/500，第二个跑了124/500，然鹅只要125/500就能过了。

== Conclusion ==

=== ntwbvdbl_oe ===

 * 首先是签到慢了，当rank17过了3道题，rank18已经过了6道。我开场看EF，但都没有想法就先放一边，经过队友提示才有思路。是因为做过这类题太少，没有感觉，归根结底是个人实力不足。
 * 其次是中期十分迷茫，czyh乱搞E无果，fx和lmh开M也很慢，M是一道经典的DP，套路十分固定，专业的DP选手应该在至多40min内独立解决。
 * 在fx写M时(甚至是之前)我开出了H，在12:50-13:00之间，可以说M和H是同时出的，但是我先让fx写M了，因为H做法还没验过。但大量经验表明，fx上机的优先级很低，且M题的代码难度是远高于H的（来自fx的吐槽：我发现我上机优先级低的原因了，难想的题我传达不出我的思想所以只能我自己写然后调，难写的题被czyh reject掉然后还是只能自己写。 czyh的吐槽：不是我不想写难写的题，而是我真的听不懂你的做法是啥啊。）
 * 关于后期的决策，在E过了之后，由于榜上形式，BCGI自动忽略。对于J，我知道大概要怎么写，去问fx关于博弈的部分，结论是对于集合的异或值x，求y>x的y的数量，这个结论假了，我想的线段树套set的做法也不对
 * 对于A，其实只要checker是对的，czyh很早就能把A过了，但我们并没有意识到rand()的问题，而牛客的clarification也基本看不到，所以浪费了很多时间
 * UPD1: 补了J，发现SegmentTreeBeats也不是很难写，虽然比赛时的思路假了，但如果专攻这题是有可能写出来的
 * UPD2: 补了I，几何题细节茫茫多，如果没有队友帮助，赛场上根本想不清楚所有的cornercase，不过代码挺好写

=== Orange_User ===

 * 对stl依赖过大，对卡常没有信仰导致L题晚过了28分钟还浪费了队友的时间。
 * A的checker的代码没有问题，问题在于windows的rand（）函数，如果在wsl下跑checker做A题应该就不会如此绝望了。（总结：辣鸡windows）
 * 乱搞能力有待提升（主要是对乱搞方案正确性的估计能力）

=== functionendless ===

 * 全程负责卡题的导数求不对的复杂度推不对的天天给假结论的函数都能忘调用的D题又想歪的菜鸡选手

== Solutions ==

A: 尽可能长的，格子数尽可能多的链

B:

C:

D:

E: 尽可能把一个方向的操作做完，然后再做另一个方向的，考虑到终点是固定的，把终点有炸弹特判一下可以少许多讨论。

F: 每次点燃的烟花数量固定，设c为烟花数量，有f(c)=(n*c+m)/(1-(1-p)^c^)，三分

G:

H: 手推一下可以发现只有nm很小时才会有不合法方案，爆搜

I: 最优策略一定只经过线段端点，预处理任意两端点间的连通性，二分vx后接dfs判断连通，注意若线段一端在边界上则该端不可达，两端均在同一边界上却都可达，直接将其删去

J: 设集合xor值为x，则先手能够调整y当且仅当{{{y>x^y}}}，等价于x最高位的1的位置上y也为1，线段树维护每一位为1的数量，用SegmentTreeBeats的技巧，复杂度O(nlognlogm)

K: 对差分数组求gcd即可O（1）回答询问。

L: 

M: f[i][j][0/1]表示i为根的子树,用j次咒,根节点是否使用的最大优惠,合并两子树的复杂度为size之积,复杂度证明相当于每个点对被算一次.

[/wiki/2020-team0x06 返回]

Statistics

TYPE: Contest
NAME: 2020 - ICPC - Nanjiang
PLAT: Nowcoder
MODE: Online
TIME: 2020.12.20 11:00-16:00
TEAM: Refrain[ntwbvdbl_oe, Orange_User, functionendless]
RANK: 17/543(Au)
SOLVE: 7/13(1562)
- A-04:51(-19)
- E-03:41(-2)
- F-01:24(-1)
- H-03:14(-2)
- K-00:14
- L-00:48
- M-03:27(-1)
ATTEMPTING

Comp

从机房搬的打印机和显示器
从Runespoor借来的几本板子和数列表
cute functionendless

Day-1

给czyh的笔记本配上环境，结果装好emacs后，包括devc++在内的各种地方出现了蜜汁乱码。czyh一脸哀怨，虽然这并不影响他发挥。lmh表示wsl才是正道，于是给wsl装上了gdb和java。

三人切掉RockyMountain，中途czyh去拿快递，结果路上和电动车相撞把自己的自行车撞坏了，czyh十分难受，希望献祭了自己的自行车能带给我们力量。

Day0

打了打bytedance网络赛，事实证明赛中进食会严重影响发挥。

三人打车把打印机和显示器搬到玉泉，并摆了个看起来就很宽的位置，将4张桌子全都利用起来，感觉电竞体验会提高不少。

Day1

开场各自看题，czyhK1Y14，然后czyh写了个滥用stl的复杂度带log的L，本地跑了3秒，于是把fx叫过去写L的two-pointer，L1Y48，czyh感到不爽，交了一下自己的程序，发现也过了，于是更不爽了。fx对着F推出了一个柿子，lmh觉得可以三分，fx验算了一遍，推出了另一个柿子。lmh自己推了推，推出了fx的第一个柿子，于是lmh上机去写三分，fx在机下求导。lmh写完没过样例，发现函数是单增的，且值域里没有样例。fx求完导也发现是单增的，同样没过样例，fx把czyh拉过来也求了遍导还是认为是单增的，三人一致认为是柿子错了。(fx和czyh现在还没发现哪里导错了)

czyh开出E，将lmh踢下机。lmh又推了一遍柿子，感觉没什么问题，让机上的czyh用python算了算，居然算出了样例的数。lmh才反应过来自己写挂了，改过了样例，提交WA。czyh测了测极限数据，发现爆longlong了，于是修改了三分的上界，F2Y84。

czyh对着E写了几种不同的随机拼在一起，但是都WA了。fx和lmh讨论M，得了一个看起来不错的做法，于是fx上机去写。lmh开出H，找czyh验了验，觉得没问题。fx写了一半，突然觉得复杂度不对，于是找lmh讨论。lmh给了一些想法，fx思考了一会儿（指在启发式合并，dsu on tree，重链剖分，长链剖分中试图分析复杂度），最后发现其实复杂度是对的，于是继续写。期间lmh见czyh在E上自闭，把A丢给他，czyh很有兴趣，上机写了一个checker并造了几组数据，没有效果。

fx写完没过样例，换lmh上机写H。fx频繁打断lmh并输出一些调试信息和更改细节，好一会才发现自己写好的dfsDP没有调用，改完依然没过样例。lmh写完获得WA，发现搜索范围小了。fx改好获得TLE，lmh改好也获得TLE，lmh打了个表，于是H3Y194。fx写了个dmk，把卡掉他的数据改对了，M2Y207。czyh捡起E上机，E3Y221。

由于罚时劣势，现在的6题一定没有Au，所以需要再搞一题，fx捡起D，拉着czyh讨论。lmh觉得他大概会做J，但由于从来没写过SegmentTreeBeats，所以一定写不出来，于是去搞A。lmh写了个退火，调czyh的checker，发现并无卵用，继续使用人类智慧。fx貌似搞出了D的做法，不久czyh把他叉掉了，czyh提出了随机化的算法，fx表示这东西怕是来不及写了，于是封榜后三人搞A。

czyh造了好几个数据，用checker测了测，只有一个正确率有8/100，其他都是0/100。lmh换了个思路构造，czyh在他的基础上改了改，居然跑到了25/100，三人欣喜地提交。

没过。

怀疑是rand的锅，多交几发还是一样，lmh把czyh的改动扩展了一下，居然变成了12/100。czyh又小改了一下，跑到了33/100!

还是没过。

三人很难受，觉得本地的checker和评测的checker大不一样，但又不知道应该怎么写checker。czyh开始变魔术，把数据旋转90度，镜像翻转……完全没用。

比赛还有10min结束，czyh决定把之前的所有构造都交一遍，1个，2个，3个，诶第二个怎么过了???

三人一脸懵，这明明是0/100的数据，居然恰好直击checker的灵魂。czyh数了数，我们交了20发，A20Y291，不过好歹有7题。

赛后发现其他过A的队伍都不是爆OJ过的，说明我们可不是乱搞的啊，我们只是提交数多了点。

听cjb说我们交的第一个构造跑了123/500，第二个跑了124/500，然鹅只要125/500就能过了。

Conclusion

ntwbvdbl_oe

首先是签到慢了，当rank17过了3道题，rank18已经过了6道。我开场看EF，但都没有想法就先放一边，经过队友提示才有思路。是因为做过这类题太少，没有感觉，归根结底是个人实力不足。
其次是中期十分迷茫，czyh乱搞E无果，fx和lmh开M也很慢，M是一道经典的DP，套路十分固定，专业的DP选手应该在至多40min内独立解决。
在fx写M时(甚至是之前)我开出了H，在12:50-13:00之间，可以说M和H是同时出的，但是我先让fx写M了，因为H做法还没验过。但大量经验表明，fx上机的优先级很低，且M题的代码难度是远高于H的（来自fx的吐槽：我发现我上机优先级低的原因了，难想的题我传达不出我的思想所以只能我自己写然后调，难写的题被czyh reject掉然后还是只能自己写。 czyh的吐槽：不是我不想写难写的题，而是我真的听不懂你的做法是啥啊。）
关于后期的决策，在E过了之后，由于榜上形式，BCGI自动忽略。对于J，我知道大概要怎么写，去问fx关于博弈的部分，结论是对于集合的异或值x，求y>x的y的数量，这个结论假了，我想的线段树套set的做法也不对
对于A，其实只要checker是对的，czyh很早就能把A过了，但我们并没有意识到rand()的问题，而牛客的clarification也基本看不到，所以浪费了很多时间
UPD1: 补了J，发现SegmentTreeBeats也不是很难写，虽然比赛时的思路假了，但如果专攻这题是有可能写出来的
UPD2: 补了I，几何题细节茫茫多，如果没有队友帮助，赛场上根本想不清楚所有的cornercase，不过代码挺好写

Orange_User

对stl依赖过大，对卡常没有信仰导致L题晚过了28分钟还浪费了队友的时间。
A的checker的代码没有问题，问题在于windows的rand（）函数，如果在wsl下跑checker做A题应该就不会如此绝望了。（总结：辣鸡windows）
乱搞能力有待提升（主要是对乱搞方案正确性的估计能力）

functionendless

全程负责卡题的导数求不对的复杂度推不对的天天给假结论的函数都能忘调用的D题又想歪的菜鸡选手

Solutions

A: 尽可能长的，格子数尽可能多的链

B:

C:

D:

E: 尽可能把一个方向的操作做完，然后再做另一个方向的，考虑到终点是固定的，把终点有炸弹特判一下可以少许多讨论。

F: 每次点燃的烟花数量固定，设c为烟花数量，有f(c)=(n*c+m)/(1-(1-p)^c)，三分

G:

H: 手推一下可以发现只有nm很小时才会有不合法方案，爆搜

I: 最优策略一定只经过线段端点，预处理任意两端点间的连通性，二分vx后接dfs判断连通，注意若线段一端在边界上则该端不可达，两端均在同一边界上却都可达，直接将其删去

J: 设集合xor值为x，则先手能够调整y当且仅当y>x^y，等价于x最高位的1的位置上y也为1，线段树维护每一位为1的数量，用SegmentTreeBeats的技巧，复杂度O(nlognlogm)

K: 对差分数组求gcd即可O（1）回答询问。

L:

M: f[i][j][0/1]表示i为根的子树,用j次咒,根节点是否使用的最大优惠,合并两子树的复杂度为size之积,复杂度证明相当于每个点对被算一次.

附加文件

Standings.png by ntwbvdbl_oe
Submissions.png by ntwbvdbl_oe