2020-team1-C006

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 10/12  dirt: 38%

rank: 1

[[Image(Rank.jpg,800px)]]

我们是冠军！


== 流水账 ==



== 总结 ==

== Statistics ==

 * TYPE: Contest
 * NAME: 2020 - ZJCPC
 * PLAT: Oms-pintia
 * MODE: Online
 * TIME: 2020.10.17 12:00-17:00
 * TEAM: Phantom Ensemble[Oscar, Grammy, Sakuya]
 * RANK: 1/404(Au)
 * SOLVE: 10/12(1240)
  * A-00:08:41(first blood)
  * B-01:04:03
  * C-02:10:28(-1)
  * E-00:53:28(-2)
  * F-03:39:04(-4)
  * G-01:34:56
  * H-03:08:28
  * I-00:32:44(-1)
  * K-00:12:37
  * L-04:40:35

== Comp ==

 * 两本吉老师板子，一本talisman板子，两本reconquista板子，一本heltion板子，一本zqq板子，一本上交板子，三个队员自己的板子各一本，零本legilimens板子，零本OEIS板子
 * 两个摄像头

== Day1 ==

Oscar开场看A，发现是个超小模拟，直接上机写了写'''A1Y8'''。写到剩最后一点的时候Sakuya开出了K，于是在过了A以后也把K过了'''K1Y12'''。

接下来榜上没题了，Oscar发现B是两部分拼起来，其中一半很好写，就利用空机位写了写，然后Grammy开出了E，Sakuya开出了I，挑了一个简单的I上机，同时Oscar把B的剩下一半丢给了数据结构带师Grammy并继续开题。

I题因为离散化挂了一发以后'''I2Y32'''，Grammy上机写E和B，'''E3Y53'''，'''B1Y64'''，这段时间里Oscar开出了G和C（但C题意是假的），Sakuya认为自己开出了F。

我们决定先上机干F，Oscar和Grammy在机下聊了聊C和H的做法，决定接下来按GCH的顺序写题。结果F wa了，Oscar上去写了G，给Sakuya开了第二个devc++看F的代码。'''G1Y94'''之后改了改F，还是没有过，于是Grammy按既定计划写C。

C写完交上去发现没有过，和F交替调了一会，然后Oscar终于发现了自己读的C题意是假的，但改几行就可以过，'''C2Y130'''。F又写了一会以后提交还是没过，决定先把手上的H过掉，Grammy在上机写H之前先把想到思路的L丢给了Oscar。

Grammy非常强力地一遍就把几何给过了，'''H1Y188'''，这期间Oscar还没有把L的做法补充完整，于是两人讨论L，让Sakuya继续上机肝F。

Sakuya终于把情况讨论清楚了，'''F4Y219'''后Oscar和Grammy也把L的做法基本完善了，由于封榜时的巨大优势以及剩下两题看起来不太可做我们决定2人或者3人一块做这个题，确保把它过掉。

Oscar尝试在Grammy上机的前几分钟把做法讲给Sakuya听，然而做法太复杂不太容易很快搞懂，于是Oscar开始死亡凝视Grammy写代码，让Sakuya去把另外两题想一想。

封榜后20分钟左右Grammy写完了，发现样例的大部分情况都是对的，Oscar也认为代码写的没啥问题，于是Grammy开始自己用gdb debug，Oscar跑去和Sakuya一起想题。

Oscar回来冷静一下后发现自己的D题意有点问题，但已经陷入之前的思路了，并且感觉最后30分钟只够写一个乱搞做法。Grammy调了一会以后发现了一个边界问题，改了改发现自造数据也能过，交上去一遍AC '''L1Y280'''。

最后Oscar上机写D的乱搞，Grammy和Sakuya在一旁观察榜单并谈笑风生，结果到最后Oscar也没有写完，比赛就结束了。

== Conclusion ==

=== Oscar ===

 * 假题意害人啊，555
 * 如果想要再提升大概需要把F快点过掉并且通过正确的题意做出D题
 * 从结果上来看D就算想出来了也不够时间写（光速逃

=== Grammy ===

 * 假题意害人，这场我得到了队友的两个假题意
 * 感觉我们队有个问题就是C这种不难但是题面长的题，开的晚，过得也不稳，时常看错题
 * 这场除了开场的E，其他我写的题好像都还挺稳的
 * 边吃东西边看队友写东西真香啊


=== Sakuya ===

 * F题要背挺大的锅的，如果早点过F就可以为他们想出D腾出挺多的时间的了
 * K题一读完题意就冲上去写了，没有看到要离散化，以后还是要仔细看题目条件

== 题解 ==

A: 枚举，前缀和

B: BF用set，FF用线段树查第一个>=x的数

C: 哈希

D: 枚举点对，直线在点对附近切开可以遍历所有答案；极角排序后统计答案

E: 主席树

F: 只考虑一维或两维

G: 每次一定是从当前风场起飞，然后一直向一个方向飞，直到落地。跑n^2^+m的dijkstra

H: 点对线段做投影得到区间（1.线段在点下方直接做；2.线段一上一下，求出向下的交点，叉积判答案是左半还是右半；3.线段在点上方平凡；4.线段经过点平凡），扫几遍求出区间并的交

I: dfs

J: dfs树上欧拉序dp并维护连通性

K: 枚举

L: key observation: 枚举质因子，再只枚举包含这个质因子的所有数，复杂度O((n+m)log(max ai))

逐位确定，对每一位从大到小枚举直到当前位再减小剩余数就<k了；统计贡献时只枚举包含当前质因子的数，扔进map里去另一边再查一遍。

[/wiki/2020-team1 返回]

概述

solved: 10/12 dirt: 38%

rank: 1

我们是冠军！

流水账

总结

Statistics

TYPE: Contest
NAME: 2020 - ZJCPC
PLAT: Oms-pintia
MODE: Online
TIME: 2020.10.17 12:00-17:00
TEAM: Phantom Ensemble[Oscar, Grammy, Sakuya]
RANK: 1/404(Au)
SOLVE: 10/12(1240)
- A-00:08:41(first blood)
- B-01:04:03
- C-02:10:28(-1)
- E-00:53:28(-2)
- F-03:39:04(-4)
- G-01:34:56
- H-03:08:28
- I-00:32:44(-1)
- K-00:12:37
- L-04:40:35

Comp

两本吉老师板子，一本talisman板子，两本reconquista板子，一本heltion板子，一本zqq板子，一本上交板子，三个队员自己的板子各一本，零本legilimens板子，零本OEIS板子
两个摄像头

Day1

Oscar开场看A，发现是个超小模拟，直接上机写了写A1Y8。写到剩最后一点的时候Sakuya开出了K，于是在过了A以后也把K过了K1Y12。

接下来榜上没题了，Oscar发现B是两部分拼起来，其中一半很好写，就利用空机位写了写，然后Grammy开出了E，Sakuya开出了I，挑了一个简单的I上机，同时Oscar把B的剩下一半丢给了数据结构带师Grammy并继续开题。

I题因为离散化挂了一发以后I2Y32，Grammy上机写E和B，E3Y53，B1Y64，这段时间里Oscar开出了G和C（但C题意是假的），Sakuya认为自己开出了F。

我们决定先上机干F，Oscar和Grammy在机下聊了聊C和H的做法，决定接下来按GCH的顺序写题。结果F wa了，Oscar上去写了G，给Sakuya开了第二个devc++看F的代码。G1Y94之后改了改F，还是没有过，于是Grammy按既定计划写C。

C写完交上去发现没有过，和F交替调了一会，然后Oscar终于发现了自己读的C题意是假的，但改几行就可以过，C2Y130。F又写了一会以后提交还是没过，决定先把手上的H过掉，Grammy在上机写H之前先把想到思路的L丢给了Oscar。

Grammy非常强力地一遍就把几何给过了，H1Y188，这期间Oscar还没有把L的做法补充完整，于是两人讨论L，让Sakuya继续上机肝F。

Sakuya终于把情况讨论清楚了，F4Y219后Oscar和Grammy也把L的做法基本完善了，由于封榜时的巨大优势以及剩下两题看起来不太可做我们决定2人或者3人一块做这个题，确保把它过掉。

Oscar尝试在Grammy上机的前几分钟把做法讲给Sakuya听，然而做法太复杂不太容易很快搞懂，于是Oscar开始死亡凝视Grammy写代码，让Sakuya去把另外两题想一想。

封榜后20分钟左右Grammy写完了，发现样例的大部分情况都是对的，Oscar也认为代码写的没啥问题，于是Grammy开始自己用gdb debug，Oscar跑去和Sakuya一起想题。

Oscar回来冷静一下后发现自己的D题意有点问题，但已经陷入之前的思路了，并且感觉最后30分钟只够写一个乱搞做法。Grammy调了一会以后发现了一个边界问题，改了改发现自造数据也能过，交上去一遍AC L1Y280。

最后Oscar上机写D的乱搞，Grammy和Sakuya在一旁观察榜单并谈笑风生，结果到最后Oscar也没有写完，比赛就结束了。

Conclusion

Oscar

假题意害人啊，555
如果想要再提升大概需要把F快点过掉并且通过正确的题意做出D题
从结果上来看D就算想出来了也不够时间写（光速逃

Grammy

假题意害人，这场我得到了队友的两个假题意
感觉我们队有个问题就是C这种不难但是题面长的题，开的晚，过得也不稳，时常看错题
这场除了开场的E，其他我写的题好像都还挺稳的
边吃东西边看队友写东西真香啊

Sakuya

F题要背挺大的锅的，如果早点过F就可以为他们想出D腾出挺多的时间的了
K题一读完题意就冲上去写了，没有看到要离散化，以后还是要仔细看题目条件

题解

A: 枚举，前缀和

B: BF用set，FF用线段树查第一个>=x的数

C: 哈希

D: 枚举点对，直线在点对附近切开可以遍历所有答案；极角排序后统计答案

E: 主席树

F: 只考虑一维或两维

G: 每次一定是从当前风场起飞，然后一直向一个方向飞，直到落地。跑n²+m的dijkstra

H: 点对线段做投影得到区间（1.线段在点下方直接做；2.线段一上一下，求出向下的交点，叉积判答案是左半还是右半；3.线段在点上方平凡；4.线段经过点平凡），扫几遍求出区间并的交

I: dfs

J: dfs树上欧拉序dp并维护连通性

K: 枚举

L: key observation: 枚举质因子，再只枚举包含这个质因子的所有数，复杂度O((n+m)log(max ai))

逐位确定，对每一位从大到小枚举直到当前位再减小剩余数就

附加文件

Rank.jpg by suika_predator