2021-team8-0328

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Standings.png,1000px)]]
[[Image(Submissions.png,1000px)]]

== 流水账 ==
昨天因为输出格式clarification的问题自闭了徐州，今天一开始大家都感到非常累，Szy先签了G，然鹅第二个签到题E大家就不会做了，cy上机开始漫长的写A，期间KanaD开出了D，过了A和D后三个人一起想E，szy终于突然回了，过了E(晚上ljm愤愤不平地说这是假做法)，之后KanaD先找出了F的n3 DP，szy表示这肯定是决策单调性优化，但是想了一会发现不对，最后发现漏了一个题目条件，szy证明了一下让cy上机去写，cy调了好一会调出来了，但是KanaD和szy都不会J和K，于是五题结束
== 个人总结 ==

Szy:连续两场训练好像太累了，其他打的还可以

cy:

zhw:

== 题解 ==

A:

B:

C:

D:先手取中间某个点，后手则必定取两边某个点，考虑两边的贡献随着中间点右移一个单调递减一个单调递增，所以二分中间点使得两边贡献的Min最大

E:如果能一步取完则结束，若不能考虑若有中心点可以先走中心，然后每步走对称点，先手必胜，否则后手每步走对称点，后手必胜，据ljm说是假做法

F:dp[i][j]表示前i个取J个miss的最优答案，有决策单调性，但是注意，因为P的存在，dp[i][j]从dp[i-1][j-1]转移时没有决策单调性，要特殊处理

G:Nim游戏

H:

I:

J:网络流，考虑每个点拆成K层，每一层向出边同层节点连边，层与层之间连inf，这样删掉一条边只能让它层数-1，这样可以让它割K条不同的边，非常妙，orz l1ll5.

K:板子题，大概是用PAP^(-1)于A特征多项式一样得结论搞出A的特征多项式

流水账

昨天因为输出格式clarification的问题自闭了徐州，今天一开始大家都感到非常累，Szy先签了G，然鹅第二个签到题E大家就不会做了，cy上机开始漫长的写A，期间KanaD开出了D，过了A和D后三个人一起想E，szy终于突然回了，过了E(晚上ljm愤愤不平地说这是假做法)，之后KanaD先找出了F的n3 DP，szy表示这肯定是决策单调性优化，但是想了一会发现不对，最后发现漏了一个题目条件，szy证明了一下让cy上机去写，cy调了好一会调出来了，但是KanaD和szy都不会J和K，于是五题结束

个人总结

Szy:连续两场训练好像太累了，其他打的还可以

cy:

zhw:

题解

A:

B:

C:

D:先手取中间某个点，后手则必定取两边某个点，考虑两边的贡献随着中间点右移一个单调递减一个单调递增，所以二分中间点使得两边贡献的Min最大

E:如果能一步取完则结束，若不能考虑若有中心点可以先走中心，然后每步走对称点，先手必胜，否则后手每步走对称点，后手必胜，据ljm说是假做法

F:dp[i][j]表示前i个取J个miss的最优答案，有决策单调性，但是注意，因为P的存在，dp[i][j]从dp[i-1][j-1]转移时没有决策单调性，要特殊处理

G:Nim游戏

H:

I:

J:网络流，考虑每个点拆成K层，每一层向出边同层节点连边，层与层之间连inf，这样删掉一条边只能让它层数-1，这样可以让它割K条不同的边，非常妙，orz l1ll5.

K:板子题，大概是用PAP^(-1)于A特征多项式一样得结论搞出A的特征多项式

附加文件