2017网络赛

乌鲁木齐 finished

D 区间dp

• 对点根据距离排序后，发现先跑两端再跑中间是较优的，于是有dp[i][j][0/1]表示在区间[i, j]的左/右端点跑完这个区间的最小值。

I 构造 可以通过计算异色角的数量和同色角的数量，可以确定出同色三角形的最小值，之后贪心构造即可

Megumin的代码

沈阳

1003 dp+搜索，参考了别人的做法，但是能过貌似是因为数据很水的缘故

Megumin的代码

1006 考虑dp，dp[i][j][k]表示到第i个数，当前至少取的数的个数为j，第k个玩家进行游戏的最大/最小差值

Megumin的代码

1007

1010 lca+树状数组

1011

西安

A 通过人数: 51

D 通过人数: 1

E 找规律，套用最大流模板，观察前几项的规律

[Megumin的代码] (代码什么的，当然是不存在的呀)

F 即将(cos(nx))分解成(cos(x))，结果是切比雪夫多项式

[Megumin的代码] (代码什么的，当然是不存在的呀)

G lca+倍增

H 通过人数: 4

I hash 把询问的四个字符串hash然后暴力去判断， 需要注意前两个和后两个字符串的长度总和小于等于文本串的一半

WQF代码

J 通过人数: 6

青岛

1002 (8/21)

1004 (31/741)

1005 (0/85)

1006 (21/95)

1007 (80/644) dp

1010 用双向链表去模拟整个过程即可

[Megumin的代码] (代码什么的，当然是不存在的呀)

北京

B 68/119

C 182/353 DP

• 假设修改的数是在"最优矩阵"里，那么一定选最小的那个数修改。如果不是在"最优矩阵"里，正常做。
• 令dp[i][0/1]表示正常求解还有有修改过的。
• 需要注意的是，最后一定要修改一个数，所以选整个矩阵为"最优矩阵"，必须修改。

D 23/209

F 15/95

H 17/33

J 44/77

南宁

E 计算几何

H 模拟题 需要有计组或者操作系统的知识 具体的看代码吧~

WQF的代码

K 求两个矩形之间的的线段，难度在于大量的分类以及题目不明确

[Megumin的代码] (代码什么的，当然是不存在的呀)