2021-team5-012

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team5 返回]

[[Image(Standings.png)]][[BR]]
[[Image(Submission.png)]][[BR]]

== 概述 ==

Andrew Stankevich Contest 39, Karelia Cup 2011, The First Day Petrozavodsk, February 2, 2011

== 流水账 ==

ckr去专业确认面试了，所以这场是双打。开场5min有人过了E，czyh想出一个dp但是不会去重，fx指出根本不用去重，因为不会算重，czyh觉得有理，把题丢给fx，自己去想D。过了一会fx发现自己不会处理旋转的情况，可能会算少，czyh指出可以指定顺序dp。fx'''E1Y57'''。D题很像CCPC网络赛出锅的题，由于赛后讨论过特殊的情况，czyh猜了一个结论，'''D2Y87'''。fx接下来去写J，看起来是个大模拟，czyh觉得自己帮不上忙，于是去想A。在思考了很久网络流做法后，czyh认为这应该暴力dfs找环就能过。fx'''J2Y103'''后胡出了C的做法，由于A做法看起来不大靠谱，于是C先写。'''C4Y157'''czyh开始写A，由于判负环初始化问题T了几发'''A4Y191'''。接下来czyh去想H，fx打表G，打完oeis一发发现通项公式，'''G1Y225'''。czyh开始乱搞H试图过题，然后wa了一片，fx指出你应该可以倒着做，从整个点集一个个删，于是'''H11Y285'''。
== 总结 ==



=== Orange_User ===

白给有点多，判负环应该记住初始化，乱搞能力有待提升，板子的见识有待拓展（todolist+=最大密度子图）。


=== functionendles ===


=== _Chenkerui ===

这场没有我


== 题解 ==

A: DFS找正环即可。

B: 

C: 从左到右扫描线，每次维护一列的有效圆，这些圆没有交。当加入一个圆时，如果和已有的圆相交那就直接不用，否则直接加入答案，加入set。

D: 排序，然后f[i]表示第i大及以后的环的先后手之差的最大值，对于一个大于等于4的环，后手可以让4个钻石给先手然后交换先后手（详情可见样例解释）。

E: 签到，不可能有凹进去的情况，因此枚举大矩形的长，算出宽，然后求出一个角删去x个的方案，再对四个角分配dp一下。

F: 

G: 打表oeis

H: 每次找一个度数最小的点删掉，多个相同随机删一个，每删一个点判断一下是否符合条件，多随几遍就过了（正解应该是枚举每个点加上k个自环然后跑最大密度子图）

I: 

J: sb模拟题

[/wiki/2021-team5 返回]



概述

Andrew Stankevich Contest 39, Karelia Cup 2011, The First Day Petrozavodsk, February 2, 2011

流水账

ckr去专业确认面试了，所以这场是双打。开场5min有人过了E，czyh想出一个dp但是不会去重，fx指出根本不用去重，因为不会算重，czyh觉得有理，把题丢给fx，自己去想D。过了一会fx发现自己不会处理旋转的情况，可能会算少，czyh指出可以指定顺序dp。fxE1Y57。D题很像CCPC网络赛出锅的题，由于赛后讨论过特殊的情况，czyh猜了一个结论，D2Y87。fx接下来去写J，看起来是个大模拟，czyh觉得自己帮不上忙，于是去想A。在思考了很久网络流做法后，czyh认为这应该暴力dfs找环就能过。fxJ2Y103后胡出了C的做法，由于A做法看起来不大靠谱，于是C先写。C4Y157czyh开始写A，由于判负环初始化问题T了几发A4Y191。接下来czyh去想H，fx打表G，打完oeis一发发现通项公式，G1Y225。czyh开始乱搞H试图过题，然后wa了一片，fx指出你应该可以倒着做，从整个点集一个个删，于是H11Y285。

总结

Orange_User

白给有点多，判负环应该记住初始化，乱搞能力有待提升，板子的见识有待拓展（todolist+=最大密度子图）。

functionendles

_Chenkerui

这场没有我

题解

A: DFS找正环即可。

B:

C: 从左到右扫描线，每次维护一列的有效圆，这些圆没有交。当加入一个圆时，如果和已有的圆相交那就直接不用，否则直接加入答案，加入set。

D: 排序，然后f[i]表示第i大及以后的环的先后手之差的最大值，对于一个大于等于4的环，后手可以让4个钻石给先手然后交换先后手（详情可见样例解释）。

E: 签到，不可能有凹进去的情况，因此枚举大矩形的长，算出宽，然后求出一个角删去x个的方案，再对四个角分配dp一下。

F:

G: 打表oeis

H: 每次找一个度数最小的点删掉，多个相同随机删一个，每删一个点判断一下是否符合条件，多随几遍就过了（正解应该是枚举每个点加上k个自环然后跑最大密度子图）

I:

J: sb模拟题

附加文件