2020-team0x06-C01

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team0x06 返回]

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

== Statistics ==

 * TYPE: Contest
 * NAME: 2020 - ZJCPC
 * PLAT: Oms-pintia
 * MODE: Online
 * TIME: 2020.10.17 12:00-17:00
 * TEAM: Refrain[ntwbvdbl_oe, Orange_User, functionendless]
 * RANK: 17/404(Au)
 * SOLVE: 7/12(805)
   * A-00:31:17
   * B-01:23:47
   * C-04:28:07(-2)
   * E-01:38:24(-1)
   * G-02:24:22(-1)
   * I-00:47:05(-1)
   * K-00:14:25(-1)
 * ATTEMPTED
   * H(-2)

== Comp ==

 * 一本Claris板子
 * 两个摄像头
 * 三位神志不清的参赛选手

== Day1 ==

lmh高峰期打车就是容易出问题，到218已经11:55了。

开场各自看题，fx从前往后，czyh从后往前，lmh中间。fx开出A，让czyh上机写，lmh看到K抢过键盘，喜获一发WA。czyh发现lmh看错题了，觉得他是sb，'''K2Y14'''，'''A1Y31'''。fx上机写I，犯了常见并查集错误WA了一发，'''I2Y47'''。

机下，czyh对着E的柿子推出了一个结论，lmh一看就是主席树，fx质疑了一下主席树不太可能过得这么快，lmh表示熟练如他10min就能写完，于是上机去写了。fx开出B想丢给czyh，czyh表示自己不会写线段树(fx:???)。lmh写完WA了(fx:明明写了15min)，换fx写B。

lmh左看右看，感觉自己写得很对，拉czyh过来看，也没有什么问题，决定写对拍。czyh开出H几何丢给lmh，lmh稍微感受了一下，觉得没有问题。fx顺利写完B。'''B1Y83'''。换lmh调E，lmh拍了拍发现关于重复数字上处理有问题，改完'''E2Y98'''，继续写H。

lmh越写越感觉不对劲，发现这个几何细节爆炸多，决定机下理一理思路。czyh开出G上机，lmh接过fx给的C的'''假题意'''，表示这是一个裸的AC自动机，只是他不会字符串，fx又质疑了一下AC自动机不太可能过得这么快，觉得还要再想想，lmh表示这都是基操。

[czyh调了调G]，'''G2Y144'''，lmh继续写H。fx将C的'''假题意'''给了czyh，并对题意提出质疑，但是两人并没有回归到正确路线，反而越走越远了。czyh对着假题意确认了AC自动机的做法，并给出了一些细节。机上的lmh写完了全部讨论，还差最后一步，他觉得C题应该写得很快，就把机子让给fx。

fx写写调调，获得一发WA，czyh让他写对拍，于是fx继续写，此时已经是192min。机下的lmh和czyh交流了一下H的细节，又想了想F和L，均无果，此时两人已经是半挂机状态。fx写写调调，拍出来完全没有问题，lmh和czyh表示疑惑，lmh甚至认为有可能爆longlong，测了测并不会爆。

已经封榜，fx一脸绝望，重新对题意提出质疑，并让lmh读了读题。lmh读完题才发现题意'''真的假了'''，fx表示czyh看完题也没有提出异议，显然他已经被带进去转不过弯。fx一边写一边让czyh看代码，不到20min就写完了，'''C3Y268'''。lmh上机写H，最终并没有调出来。

赛后，lmh看了看题解[[BR]]
lmh:  诶这个H所有东西都在x轴上方?不是可以任意位置的吗?[[BR]]
czyh: 真的吗......哦输入有说y>=1的[[BR]]
lmh:  ...........我题意也假了

== Conclusion ==

=== ntwbvdbl_oe ===

 * 中期不应该让fx在机上呆太久。但是对于这种题意清晰、思路清晰的题目（假题意也很清晰的），就应本着相信队友的原则。而且榜上表现出的状态也符合这道题的特征，就不会去多管，WA了就是写挂了，很难想到读错题的方面。再加上自己手上还有需要思考的题目，就不想读其他题。
 * 最重要的一点是，一定要在1-2h内读完所有题，并且三人确定题意，才能最大程度避免读错题的发生
 * 一直坚持着C>H的想法是不对的，如果早点写完H开始debug，就有时间过了这题，还可能和czyh开出另外一题。第4h内三人完全无作为
 * 其实F和L是不会写的，总结来说就是菜

=== Orange_User ===
 * 英语不好读不懂题，可能需要多一些读题训练
 * A题的日期处理还是不大熟练，应该15分钟写完的
 * F题的构造答案方法基本想出来了，但无解处理想了很久，似乎应该多和队友讨论一下（但自己想不出来就是菜）
 * G题似乎也不应该想这么久，可能是没有达到兴奋的做题状态
 * 想题能力还行但许多东西都不大会写，如果能想出来的题不用推给队友写可能会过得更快

=== functionendles ===
 * 一个想题型选手在机上那么长时间我也是醉了.
 * 中后期体会就是我人没了,除了把C题难度抬了个档次并做出来之后就什么都没干了
 * 应该抽时间(没时间)想想FL之类的,都有些基本思路但没想下去

== Solutions ==

A: 日期相关签到模拟题

B: 第一种线段树,第二种'''multi'''set+lowerbound

C: 假题意:所有子串贡献统计. -> AC自动机fail树信息pushdown后在AC自动机上走即可.
   真题意:建个trie树直接跑

D: 

E: 观察dp方程，容易将问题转化为求(l, r)区间内前k大之和，主席树即可

F:

G: 按风力大小排序后n^2^的dp

H: 假题意：点光源和遮光板可以分布在平面的任意位置
   真题意：只在x轴上方，枚举点-线段投影在x轴上，交一交并一并

I: 并查集找最大的那个集合,输出其size

J: 

K: 签到

L:

[/wiki/2020-team0x06 返回]


Statistics

  • TYPE: Contest
  • NAME: 2020 - ZJCPC
  • PLAT: Oms-pintia
  • MODE: Online
  • TIME: 2020.10.17 12:00-17:00
  • TEAM: Refrain[ntwbvdbl_oe, Orange_User, functionendless]
  • RANK: 17/404(Au)
  • SOLVE: 7/12(805)
    • A-00:31:17
    • B-01:23:47
    • C-04:28:07(-2)
    • E-01:38:24(-1)
    • G-02:24:22(-1)
    • I-00:47:05(-1)
    • K-00:14:25(-1)
  • ATTEMPTED
    • H(-2)

Comp

  • 一本Claris板子
  • 两个摄像头
  • 三位神志不清的参赛选手

Day1

lmh高峰期打车就是容易出问题，到218已经11:55了。

开场各自看题，fx从前往后，czyh从后往前，lmh中间。fx开出A，让czyh上机写，lmh看到K抢过键盘，喜获一发WA。czyh发现lmh看错题了，觉得他是sb，K2Y14，A1Y31。fx上机写I，犯了常见并查集错误WA了一发，I2Y47。

机下，czyh对着E的柿子推出了一个结论，lmh一看就是主席树，fx质疑了一下主席树不太可能过得这么快，lmh表示熟练如他10min就能写完，于是上机去写了。fx开出B想丢给czyh，czyh表示自己不会写线段树(fx:???)。lmh写完WA了(fx:明明写了15min)，换fx写B。

lmh左看右看，感觉自己写得很对，拉czyh过来看，也没有什么问题，决定写对拍。czyh开出H几何丢给lmh，lmh稍微感受了一下，觉得没有问题。fx顺利写完B。B1Y83。换lmh调E，lmh拍了拍发现关于重复数字上处理有问题，改完E2Y98，继续写H。

lmh越写越感觉不对劲，发现这个几何细节爆炸多，决定机下理一理思路。czyh开出G上机，lmh接过fx给的C的假题意，表示这是一个裸的AC自动机，只是他不会字符串，fx又质疑了一下AC自动机不太可能过得这么快，觉得还要再想想，lmh表示这都是基操。

[czyh调了调G]，G2Y144，lmh继续写H。fx将C的假题意给了czyh，并对题意提出质疑，但是两人并没有回归到正确路线，反而越走越远了。czyh对着假题意确认了AC自动机的做法，并给出了一些细节。机上的lmh写完了全部讨论，还差最后一步，他觉得C题应该写得很快，就把机子让给fx。

fx写写调调，获得一发WA，czyh让他写对拍，于是fx继续写，此时已经是192min。机下的lmh和czyh交流了一下H的细节，又想了想F和L，均无果，此时两人已经是半挂机状态。fx写写调调，拍出来完全没有问题，lmh和czyh表示疑惑，lmh甚至认为有可能爆longlong，测了测并不会爆。

已经封榜，fx一脸绝望，重新对题意提出质疑，并让lmh读了读题。lmh读完题才发现题意真的假了，fx表示czyh看完题也没有提出异议，显然他已经被带进去转不过弯。fx一边写一边让czyh看代码，不到20min就写完了，C3Y268。lmh上机写H，最终并没有调出来。

赛后，lmh看了看题解

lmh: 诶这个H所有东西都在x轴上方?不是可以任意位置的吗?

czyh: 真的吗......哦输入有说y>=1的

lmh: ...........我题意也假了

Conclusion

ntwbvdbl_oe

  • 中期不应该让fx在机上呆太久。但是对于这种题意清晰、思路清晰的题目（假题意也很清晰的），就应本着相信队友的原则。而且榜上表现出的状态也符合这道题的特征，就不会去多管，WA了就是写挂了，很难想到读错题的方面。再加上自己手上还有需要思考的题目，就不想读其他题。
  • 最重要的一点是，一定要在1-2h内读完所有题，并且三人确定题意，才能最大程度避免读错题的发生
  • 一直坚持着C>H的想法是不对的，如果早点写完H开始debug，就有时间过了这题，还可能和czyh开出另外一题。第4h内三人完全无作为
  • 其实F和L是不会写的，总结来说就是菜

Orange_User

  • 英语不好读不懂题，可能需要多一些读题训练
  • A题的日期处理还是不大熟练，应该15分钟写完的
  • F题的构造答案方法基本想出来了，但无解处理想了很久，似乎应该多和队友讨论一下（但自己想不出来就是菜）
  • G题似乎也不应该想这么久，可能是没有达到兴奋的做题状态
  • 想题能力还行但许多东西都不大会写，如果能想出来的题不用推给队友写可能会过得更快

functionendles

  • 一个想题型选手在机上那么长时间我也是醉了.
  • 中后期体会就是我人没了,除了把C题难度抬了个档次并做出来之后就什么都没干了
  • 应该抽时间(没时间)想想FL之类的,都有些基本思路但没想下去

Solutions

A: 日期相关签到模拟题

B: 第一种线段树,第二种multiset+lowerbound

C: 假题意:所有子串贡献统计. -> AC自动机fail树信息pushdown后在AC自动机上走即可.

真题意:建个trie树直接跑

D:

E: 观察dp方程，容易将问题转化为求(l, r)区间内前k大之和，主席树即可

F:

G: 按风力大小排序后n2的dp

H: 假题意：点光源和遮光板可以分布在平面的任意位置

真题意：只在x轴上方，枚举点-线段投影在x轴上，交一交并一并

I: 并查集找最大的那个集合,输出其size

J:

K: 签到

L:

附加文件