2020-team1-C008

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 9/12  dirt: 57%

rank: 3

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



== 流水账 ==



== 总结 ==
== Statistics ==

 * TYPE: Contest
 * NAME: CCPC2020 - Mianyang
 * PLAT: Oms-pintia
 * MODE: Online
 * TIME: 2020.11.1 9:00-14:00
 * TEAM: Phantom Ensemble[Oscar, Grammy, Sakuya]
 * RANK: 3/309(Au)
 * SOLVE: 9/12(1410)
  * A-
  * B-3:20
  * C-4:29
  * D-0:20(-1)
  * E-1:15(-3)(first blood)
  * F-
  * G-2:19(-3)
  * H-3:39(-1)
  * I-
  * J-1:25(-3)
  * K-0:43(-1)
  * L-2:00

== Comp ==

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

== Day0 ==

翻了翻参赛手册，发现上交的不朽之夜和西交的渡渡鸟幼儿园都没来。Oscar:“那我们岂不是很强？”cjb:“你们能踩wxh？”

感觉立下了天大的flag

== Day1 ==

开场Grammy看完D，觉得这是个签到，但他不想想也不想写，就告诉Oscar这是签到，他自己跑了。 Oscar上机写了写，交上去没过。Grammy看到E，觉得他会做，于是他上机了，然后wa了。Oscar把D题的二分上界改了一下过了，'''D2Y20'''。这时Sakuya想出了K题，上去写结果WA了，打印代码下机调。Grammy他查了查代码感觉没问题，又看了眼题，发现漏看了没有出边可以原地休息的条件，改完又wa一发，想了想发现自己只改了一半，把他彻底改干净了又wa了一发。他表示这不可能，然后被彻底想清楚K题所有分类的Sakuya拖下了机，'''K2Y43'''。接下来Oscar用特别麻烦的写法上机去写J，交上去又没过。过了一会Grammy又看了看题，发现自己又看漏了，每次是走不超过K条边，改完后抢到了E的一血，'''E4Y75'''。

Oscar让Grammy去做L，然后自己上机去调J，Grammy感觉不太会，看了看榜好像很多人过了，猜测他很简单，然后他突然就会做了。Oscar又用了一点时间和罚时过了J，'''J4Y85'''，然后提出了两个G题的结论准备上去打表，大家都觉得结论很对。机子空了后Grammy上去1A了L，'''L1Y120'''，看榜上除了队友正在做的题，有个B题，就跑去开。看了一会，没看懂题，对着图和输出格式在那里脑补。Oscar把G题按照结论和规律写完后交上去没过，此时手上没什么别的题了，Oscar问Sakuya I题有没有希望，Sakuya说I题要等机时来找规律，于是就把I题暂时抛弃去开H。Sakuya一看三个读入，一个输出，然后感觉式子应该是这三个数相加或者相乘的一个线性表达式，这不是应该很简单吗？第一次上机以为自己已经想好了，把正在写G的新打表代码的Oscar赶了下来，写完了其他的corner case之后才发现最主要的case没想好，下机。Oscar打出了完整的表，看了一下和之前结论的差异，发现之前结论的一半是错的，按照新的结论改完后过了G，'''G4Y139'''。

Sakuya终于想好了H题的主要case，上去写结果WA了。等机子空了，Grammy上去写B，写了一会他发现这个dp很恶心，有很多很多讨论，其他部分写完后他下来想了一会转移。Grammy想了一会后悟了B的题意，感觉是个简单dp。等机子再次空出来后他上去1A了B，'''B1Y200'''。Sakuya终于查出了H题的SB错误，上去改了之后过了，'''H2Y219'''。Oscar跟Grammy讲了一下大致的局势，Grammy觉得去写F不如去开C，他不想写F，而C应当不难，于是他就跑去开C。这时Oscar以为自己想清楚了A上去写。一开始Grammy不知道C有无解情况，很快出了一个解法，告诉Oscar后Oscar问他无解怎么判，他想了想，觉得直接假设有解把树建出来最后过一遍询问就行了。 Oscar写到一半发现有两种情况比想象的更复杂，于是下机让Grammy上去过了C，'''C1Y269'''，同时Oscar和Sakuya讨论清楚了除了一种情况的其它情况。接下来Oscar看了看手上的A和F，感觉都不太能写完，挑了一个比较能写完的A上去写，让Grammy帮忙想一下最后一种情况的细节，写到结束确实没写完（）。Sakuya一直在等待机时打表找I题的规律，然而一直没等到，只能试图手推limit范围，结果最后也没有推出来（仿佛在摸鱼）。

== Conclusion ==

=== Oscar ===

这场写了写签到，找了找规律（结果漏一堆细节dirt爆炸,555我是罚时担当），最后的A题写到最后一种最麻烦的情况就结束了。总体来说这场细节很多，大概我们在大家都卡题的时候很强吧（

=== Grammy ===

这场抢到了E的一血，然后带歪了全场的榜，太棒了。（E看漏了两个题意导致wa了3发）  然后就跟榜把L，B，C做了，一发过非常干净，今天我不是罚时担当力。 仔细想想今天我除了C，其他写的三个都是dp，不怪得做的这么开心（）  这场前面签到签的太慢了，中后期才渐渐找到节奏。另外就是这场的罚时炸裂了（

=== Sakuya ===

这场机时已经挺满的了，打到最好也等不来I的机时去打个表找一下规律。这场if-else挺多的，不过H题浪费的机时很少（真不知道sub为什么搞了90分钟（笑））。

Grammy哥哥太强啦！

赛后发现I题PTA上无论怎么调参都会T或者WA，被出题人拿到CF上测用时2.5s过了

== 咕咕咕 ==


Sakuya:这场机时已经挺满的了，打到最好也等不来I的机时去打个表找一下规律。这场if-else挺多的，不过H题浪费的机时很少（真不知道sub为什么搞了90分钟（笑））。

Grammy哥哥太强啦！

(upd:GTMD PTA，还有GTMD毒瘤卡常出题人，I题PTA上无论怎么调参都会T或者WA，被出题人拿到CF上测用时2.5s过了)

Grammy: 这场抢到了E的一血，然后带歪了全场的榜，太棒了。（E看漏了两个题意导致wa了3发）  然后就跟榜把L，B，C做了，一发过非常干净，今天我不是罚时担当力。 仔细想想今天我除了C，其他写的三个都是dp，不怪得做的这么开心（）  这场前面签到签的太慢了，中后期才渐渐找到节奏。另外就是这场的罚时炸裂了（


Oscar: 这场写了写签到，找了找规律（结果漏一堆细节dirt爆炸），最后的A题写到最后一种最麻烦的情况就结束了，还是比较快乐的。总体来说这场细节很多，大概我们在大家都卡题的时候很强吧（

== 题解 ==

A:

B: 一条一条对角线去dp，f[i][0/1]表示上一条对角线的方块有没有顶到这一条的顶格。

C: 假设一定有解，我们去把值相同的搞个lca，然后当一个点没有值，他存在某个孩子，这个孩子的子树里只有一个值，这个孩子就可以并到这个点身上。我们dfs做一次这个合并，得到答案树，然后再跑一边所有输入串看看是不是和输入的值相符，不相符就无解，否则就找到了最优解。

D: 二分，注意上界>2e9

E: f[i][j]表示在i号节点，还打算走j步，最后的答案。看清楚题就是个经典的bfs转移。

F: 对坐标系仿射变换然后树套树（

G: 对c0=c3=0打表看出c1%3=0或(c1%3=1且c2=0)时后手胜，加入c0后发现c0%2=1且c1%3=2且c2>=2时先手胜，其余根据c0%2交换先后手，再判掉c1=c2=c3=0（c0=0和c0=1是一样的，因为没有可行操作）

H: 最后推出来的式子还是很漂亮的，判掉d0=0，d2=d1-d0，d2=d1+d0以及一些非法的情况后答案为(d0+d1+d2)*4。

I:原始式子dp[i]=min(dp[i],dp[j]+dp[i-j])，打表找规律发现后面delta(dp)有循环节B（B为sqrt(C)或者sqrt(C)+1），怎么暴力怎么来即可。

J: big small然后线段树（好像去重后直接调和级数+线段树就好）

K: 一堆if-else，如果n是奇数答案为1，4的倍数答案为2，6的倍数答案为2，n%6==2或者4都看一下答案是3还是4

L: 从低到高位，考虑这一位取0还是1，会带着剩下能用的数字到下一位，然后能用的个数至多只有两种，于是每一位只需要2个状态。

[/wiki/2020-team1 返回]

概述

solved: 9/12 dirt: 57%

rank: 3

流水账

总结

Statistics

  • TYPE: Contest
  • NAME: CCPC2020 - Mianyang
  • PLAT: Oms-pintia
  • MODE: Online
  • TIME: 2020.11.1 9:00-14:00
  • TEAM: Phantom Ensemble[Oscar, Grammy, Sakuya]
  • RANK: 3/309(Au)
  • SOLVE: 9/12(1410)
    • A-
    • B-3:20
    • C-4:29
    • D-0:20(-1)
    • E-1:15(-3)(first blood)
    • F-
    • G-2:19(-3)
    • H-3:39(-1)
    • I-
    • J-1:25(-3)
    • K-0:43(-1)
    • L-2:00

Comp

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

Day0

翻了翻参赛手册，发现上交的不朽之夜和西交的渡渡鸟幼儿园都没来。Oscar:“那我们岂不是很强？”cjb:“你们能踩wxh？”

感觉立下了天大的flag

Day1

开场Grammy看完D，觉得这是个签到，但他不想想也不想写，就告诉Oscar这是签到，他自己跑了。 Oscar上机写了写，交上去没过。Grammy看到E，觉得他会做，于是他上机了，然后wa了。Oscar把D题的二分上界改了一下过了，D2Y20。这时Sakuya想出了K题，上去写结果WA了，打印代码下机调。Grammy他查了查代码感觉没问题，又看了眼题，发现漏看了没有出边可以原地休息的条件，改完又wa一发，想了想发现自己只改了一半，把他彻底改干净了又wa了一发。他表示这不可能，然后被彻底想清楚K题所有分类的Sakuya拖下了机，K2Y43。接下来Oscar用特别麻烦的写法上机去写J，交上去又没过。过了一会Grammy又看了看题，发现自己又看漏了，每次是走不超过K条边，改完后抢到了E的一血，E4Y75。

Oscar让Grammy去做L，然后自己上机去调J，Grammy感觉不太会，看了看榜好像很多人过了，猜测他很简单，然后他突然就会做了。Oscar又用了一点时间和罚时过了J，J4Y85，然后提出了两个G题的结论准备上去打表，大家都觉得结论很对。机子空了后Grammy上去1A了L，L1Y120，看榜上除了队友正在做的题，有个B题，就跑去开。看了一会，没看懂题，对着图和输出格式在那里脑补。Oscar把G题按照结论和规律写完后交上去没过，此时手上没什么别的题了，Oscar问Sakuya I题有没有希望，Sakuya说I题要等机时来找规律，于是就把I题暂时抛弃去开H。Sakuya一看三个读入，一个输出，然后感觉式子应该是这三个数相加或者相乘的一个线性表达式，这不是应该很简单吗？第一次上机以为自己已经想好了，把正在写G的新打表代码的Oscar赶了下来，写完了其他的corner case之后才发现最主要的case没想好，下机。Oscar打出了完整的表，看了一下和之前结论的差异，发现之前结论的一半是错的，按照新的结论改完后过了G，G4Y139。

Sakuya终于想好了H题的主要case，上去写结果WA了。等机子空了，Grammy上去写B，写了一会他发现这个dp很恶心，有很多很多讨论，其他部分写完后他下来想了一会转移。Grammy想了一会后悟了B的题意，感觉是个简单dp。等机子再次空出来后他上去1A了B，B1Y200。Sakuya终于查出了H题的SB错误，上去改了之后过了，H2Y219。Oscar跟Grammy讲了一下大致的局势，Grammy觉得去写F不如去开C，他不想写F，而C应当不难，于是他就跑去开C。这时Oscar以为自己想清楚了A上去写。一开始Grammy不知道C有无解情况，很快出了一个解法，告诉Oscar后Oscar问他无解怎么判，他想了想，觉得直接假设有解把树建出来最后过一遍询问就行了。 Oscar写到一半发现有两种情况比想象的更复杂，于是下机让Grammy上去过了C，C1Y269，同时Oscar和Sakuya讨论清楚了除了一种情况的其它情况。接下来Oscar看了看手上的A和F，感觉都不太能写完，挑了一个比较能写完的A上去写，让Grammy帮忙想一下最后一种情况的细节，写到结束确实没写完（）。Sakuya一直在等待机时打表找I题的规律，然而一直没等到，只能试图手推limit范围，结果最后也没有推出来（仿佛在摸鱼）。

Conclusion

Oscar

这场写了写签到，找了找规律（结果漏一堆细节dirt爆炸,555我是罚时担当），最后的A题写到最后一种最麻烦的情况就结束了。总体来说这场细节很多，大概我们在大家都卡题的时候很强吧（

Grammy

这场抢到了E的一血，然后带歪了全场的榜，太棒了。（E看漏了两个题意导致wa了3发） 然后就跟榜把L，B，C做了，一发过非常干净，今天我不是罚时担当力。 仔细想想今天我除了C，其他写的三个都是dp，不怪得做的这么开心（） 这场前面签到签的太慢了，中后期才渐渐找到节奏。另外就是这场的罚时炸裂了（

Sakuya

这场机时已经挺满的了，打到最好也等不来I的机时去打个表找一下规律。这场if-else挺多的，不过H题浪费的机时很少（真不知道sub为什么搞了90分钟（笑））。

Grammy哥哥太强啦！

赛后发现I题PTA上无论怎么调参都会T或者WA，被出题人拿到CF上测用时2.5s过了

咕咕咕

Sakuya:这场机时已经挺满的了，打到最好也等不来I的机时去打个表找一下规律。这场if-else挺多的，不过H题浪费的机时很少（真不知道sub为什么搞了90分钟（笑））。

Grammy哥哥太强啦！

(upd:GTMD PTA，还有GTMD毒瘤卡常出题人，I题PTA上无论怎么调参都会T或者WA，被出题人拿到CF上测用时2.5s过了)

Grammy: 这场抢到了E的一血，然后带歪了全场的榜，太棒了。（E看漏了两个题意导致wa了3发） 然后就跟榜把L，B，C做了，一发过非常干净，今天我不是罚时担当力。 仔细想想今天我除了C，其他写的三个都是dp，不怪得做的这么开心（） 这场前面签到签的太慢了，中后期才渐渐找到节奏。另外就是这场的罚时炸裂了（

Oscar: 这场写了写签到，找了找规律（结果漏一堆细节dirt爆炸），最后的A题写到最后一种最麻烦的情况就结束了，还是比较快乐的。总体来说这场细节很多，大概我们在大家都卡题的时候很强吧（

题解

A:

B: 一条一条对角线去dp，f[i][0/1]表示上一条对角线的方块有没有顶到这一条的顶格。

C: 假设一定有解，我们去把值相同的搞个lca，然后当一个点没有值，他存在某个孩子，这个孩子的子树里只有一个值，这个孩子就可以并到这个点身上。我们dfs做一次这个合并，得到答案树，然后再跑一边所有输入串看看是不是和输入的值相符，不相符就无解，否则就找到了最优解。

D: 二分，注意上界>2e9

E: f[i][j]表示在i号节点，还打算走j步，最后的答案。看清楚题就是个经典的bfs转移。

F: 对坐标系仿射变换然后树套树（

G: 对c0=c3=0打表看出c1%3=0或(c1%3=1且c2=0)时后手胜，加入c0后发现c0%2=1且c1%3=2且c2>=2时先手胜，其余根据c0%2交换先后手，再判掉c1=c2=c3=0（c0=0和c0=1是一样的，因为没有可行操作）

H: 最后推出来的式子还是很漂亮的，判掉d0=0，d2=d1-d0，d2=d1+d0以及一些非法的情况后答案为(d0+d1+d2)*4。

I:原始式子dp[i]=min(dp[i],dp[j]+dp[i-j])，打表找规律发现后面delta(dp)有循环节B（B为sqrt(C)或者sqrt(C)+1），怎么暴力怎么来即可。

J: big small然后线段树（好像去重后直接调和级数+线段树就好）

K: 一堆if-else，如果n是奇数答案为1，4的倍数答案为2，6的倍数答案为2，n%6==2或者4都看一下答案是3还是4

L: 从低到高位，考虑这一位取0还是1，会带着剩下能用的数字到下一位，然后能用的个数至多只有两种，于是每一位只需要2个状态。

附加文件