2021-team8-008

从 Trac 迁移的文章

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

原文章内容如下：

= 流水账 =
没有签到题？签E题rtx就花了1h，太慢了。随后xqj找到C题很对的做法，但是WA，改了几个错，还是WA，于是让给yys写G，但是也WA了。rtx思考D没有完备的做法，与xqj交流，xqj提出从小到大取，上机写，直接过。然后G顺利发现问题，过了，是首A，然后C也过了，自此士气大增（在这之前已经虚死了）。随后过了模拟题J。然后A口胡了一个不知道对不对的网络流，I有一个分块，最后去写I了，时间太少没调出来。（场后发现A也不用真的写网络流，暴力找环加流就行）

= 总结 =
不大懂，开场太吓人了。

= 题解 =
A: 可以把题意转化为一个有上界最小费用可行流模型（有负环），但是数据范围很小，所以可以直接dfs找环，然后把相应边的流量加上去

B: 有一个性质：三条边扩展出的圆弧半径是相同的。所以可以二分这个半径。证明不会。

C: 将每个圆的左右端点扔进去排序，然后扫描线，按圆心y坐标加入set里面找前一个和后一个，多画几个图会发现这样是对的。

D: 结论：先手割开一个环后只可能发生两种情况：1.后手把这一堆全拿走，然后先后手交换 2.后手取到盛4个，然后割成2+2，先后手不变。还有一个大胆猜想：一定是从小到大取。所以倒着推过来即可。证明，意会一下。

E: dp，可能比较繁

F: 

G: dp套dp，好像要优化一下转移的复杂度

H: 听说可以转化成最大权闭合子图

I: 场后分块好像做出来了？不是我写的不大会（--rtx）

J: 直接模拟

流水账

没有签到题？签E题rtx就花了1h，太慢了。随后xqj找到C题很对的做法，但是WA，改了几个错，还是WA，于是让给yys写G，但是也WA了。rtx思考D没有完备的做法，与xqj交流，xqj提出从小到大取，上机写，直接过。然后G顺利发现问题，过了，是首A，然后C也过了，自此士气大增（在这之前已经虚死了）。随后过了模拟题J。然后A口胡了一个不知道对不对的网络流，I有一个分块，最后去写I了，时间太少没调出来。（场后发现A也不用真的写网络流，暴力找环加流就行）

总结

不大懂，开场太吓人了。

题解

A: 可以把题意转化为一个有上界最小费用可行流模型（有负环），但是数据范围很小，所以可以直接dfs找环，然后把相应边的流量加上去

B: 有一个性质：三条边扩展出的圆弧半径是相同的。所以可以二分这个半径。证明不会。

C: 将每个圆的左右端点扔进去排序，然后扫描线，按圆心y坐标加入set里面找前一个和后一个，多画几个图会发现这样是对的。

D: 结论：先手割开一个环后只可能发生两种情况：1.后手把这一堆全拿走，然后先后手交换 2.后手取到盛4个，然后割成2+2，先后手不变。还有一个大胆猜想：一定是从小到大取。所以倒着推过来即可。证明，意会一下。

E: dp，可能比较繁

F:

G: dp套dp，好像要优化一下转移的复杂度

H: 听说可以转化成最大权闭合子图

I: 场后分块好像做出来了？不是我写的不大会（--rtx）

J: 直接模拟