2020-team1-005

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 10/11  dirt: 47%

rank: 5 (现场榜<1)

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



== 流水账 ==

开场Oscar J2Y8,I1Y12，Grammy写完了A一跑发现样例二过不去，手玩了一下发现自己玩不出样例二的结果，他非常困惑，重新读了一下题还是不懂为什么，于是他尝试着换了一种方式理解题意，自己脑补出一个可以通过所有样例的题意理解，写完后wa3。他再次困惑，百思不得其解，直到他看到output不是让他输出最优解而是输出最优节省后。A2Y19

Oscar发现E是个二分图匹配，写了个网络流就过了 E1Y28。 Grammy表示这个D很眼熟，虽然他不记得当时怎么做了。他想了一个复杂度不对的dp，脑补了一下好像可以用长得很分块的东西优化，复杂度他不会算，O（跑得过），写完在cf  CUSTOM INVOCATION上测了测极限数据还挺快，顺便测出了数组开小的问题，一交，re on test 5，一拍脑袋他发现他交的是改之前的代码（   D2Y45。

Oscar读了两遍K题意（才读懂），发现暴力枚举完了统计就可以，为了防止炸精度把lim设成了1.1e18，结果最后忘把1e18~1.1e18之间的答案判掉了，改了一下才过， K2Y58。 

Grammy发现G是个cdq模板题，他没找到板子，写了一个cdq（虽然赛后发现标解不是cdq），G1Y67.

Oscar觉得C是个2SAT，打算写前部分，2SAT扔给Grammy写，后来他想了想发现直接二分图染色就行了。C2Y117. 

（2小时8题了就离谱）

B题Grammy提出了一个区间不包含情况下的一个结论和dp解法，想拓展到区间包含的情况下，后面Oscar想到了区间包含下直接把外层区间去掉做dp，处理后再贪心把外面的区间单独加进来，虽然都不会证明，但是两人都觉得很对，B1Y186.

剩下两道令人难受的几何，F题两个人都不会算球面上两点间的距离，当做这场比赛没有这题（

H题两人讨论了一下后，Grammy写，Oscar负责提供板子，写完调过样例后wa了，两人各造了些数据，改完后还是wa，此时只剩不到30min，两人一起对着代码瞪眼，瞪了十几分钟看不出什么东西，Grammy改了改long double，精度改小了点又交了一发竟然wa在了更前面的点，于是他把精度调大就过了。
（这题怎么还卡精度啊）

和前面某场比赛一样的最后两小时肝几何题，还好这次Grammy没有演Oscar，H4Y295

== 总结 ==

提升了几何知识（×）

扩充了几何板子（√）

== 题解 ==

A:

B:

C:

D:

E:

F: 

G:

H:

I:

J:

K:

[/wiki/2020-team1 返回]

概述

solved: 10/11 dirt: 47%

rank: 5 (现场榜<1)

流水账

开场Oscar J2Y8,I1Y12，Grammy写完了A一跑发现样例二过不去，手玩了一下发现自己玩不出样例二的结果，他非常困惑，重新读了一下题还是不懂为什么，于是他尝试着换了一种方式理解题意，自己脑补出一个可以通过所有样例的题意理解，写完后wa3。他再次困惑，百思不得其解，直到他看到output不是让他输出最优解而是输出最优节省后。A2Y19

Oscar发现E是个二分图匹配，写了个网络流就过了 E1Y28。 Grammy表示这个D很眼熟，虽然他不记得当时怎么做了。他想了一个复杂度不对的dp，脑补了一下好像可以用长得很分块的东西优化，复杂度他不会算，O（跑得过），写完在cf CUSTOM INVOCATION上测了测极限数据还挺快，顺便测出了数组开小的问题，一交，re on test 5，一拍脑袋他发现他交的是改之前的代码（ D2Y45。

Oscar读了两遍K题意（才读懂），发现暴力枚举完了统计就可以，为了防止炸精度把lim设成了1.1e18，结果最后忘把1e18~1.1e18之间的答案判掉了，改了一下才过， K2Y58。

Grammy发现G是个cdq模板题，他没找到板子，写了一个cdq（虽然赛后发现标解不是cdq），G1Y67.

Oscar觉得C是个2SAT，打算写前部分，2SAT扔给Grammy写，后来他想了想发现直接二分图染色就行了。C2Y117.

（2小时8题了就离谱）

B题Grammy提出了一个区间不包含情况下的一个结论和dp解法，想拓展到区间包含的情况下，后面Oscar想到了区间包含下直接把外层区间去掉做dp，处理后再贪心把外面的区间单独加进来，虽然都不会证明，但是两人都觉得很对，B1Y186.

剩下两道令人难受的几何，F题两个人都不会算球面上两点间的距离，当做这场比赛没有这题（

H题两人讨论了一下后，Grammy写，Oscar负责提供板子，写完调过样例后wa了，两人各造了些数据，改完后还是wa，此时只剩不到30min，两人一起对着代码瞪眼，瞪了十几分钟看不出什么东西，Grammy改了改long double，精度改小了点又交了一发竟然wa在了更前面的点，于是他把精度调大就过了。

（这题怎么还卡精度啊）

和前面某场比赛一样的最后两小时肝几何题，还好这次Grammy没有演Oscar，H4Y295

总结

提升了几何知识（×）

扩充了几何板子（√）

题解

A:

B:

C:

D:

E:

F:

G:

H:

I:

J:

K:

附加文件