2020-team1-C009

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 10/13  dirt: 63%
rank: 2
[[Image(Rank.2.png,800px)]]
== 总结 ==

== 题解 ==
A: 
B:  Oscar扫雷，把雷和空位互换，不影响数字总和，答案要么是原图要么是原图反。
C:  数位dp，log^2^草过去了，log的不难想，会难写一些。
D:  三分加分类讨论
E: 推式子，考虑1放在第i个位置(1<=i<=k)，然后前i-1个随便放，剩下的重编号后就是f(n-i)的情况
F: 右端点扫过去，对每个左端点存当前选择的最大区间的长度，按照把选的区间个数放到最外面那一维滚动掉（其实甚至可以原地转移）dp，瓶颈上转移的时候状态的翻译常数很大，但这部分事实上可以预处理掉，实现的不够优美，常数萎了就没过
G: 签到，考虑一下0出现在哪些位置即可
H: 对应一定是按顺时针一一对应过去的，所以枚举第1个人对应哪一个菜，需要左移和右移一些步，找个移动总路径的最小值
I:  讨论一下，n=1 corner case：这时原点不是交点。
J: 
K:  一定是high low high low的序列，结论1：路上没有偶环；结论2：把两端点不同色的边连上，一定是图上某一棵dfs树加上一条同色的返祖边，结论3：对同一个点双，任取3点ABC，一定存在A到B到C的点不重复的路径，结论4：以0为根建圆方树，存在同色边(u,v)，u在的点双是v点双的祖先。
L: 先把gcd(n,m)=1情况排除掉。然后猜想只会中转一次，发现最优的点与起点、终点组成的三角形内部不应该包含任何一个点。所以只需枚举对角线周围一小块的点即可。
M: 树上贪心

[/wiki/2020-team1 返回]

概述

solved: 10/13 dirt: 63%

rank: 2

总结

题解

A:

B: Oscar扫雷，把雷和空位互换，不影响数字总和，答案要么是原图要么是原图反。

C: 数位dp，log2草过去了，log的不难想，会难写一些。

D: 三分加分类讨论

E: 推式子，考虑1放在第i个位置(1<=i<=k)，然后前i-1个随便放，剩下的重编号后就是f(n-i)的情况

F: 右端点扫过去，对每个左端点存当前选择的最大区间的长度，按照把选的区间个数放到最外面那一维滚动掉（其实甚至可以原地转移）dp，瓶颈上转移的时候状态的翻译常数很大，但这部分事实上可以预处理掉，实现的不够优美，常数萎了就没过

G: 签到，考虑一下0出现在哪些位置即可

H: 对应一定是按顺时针一一对应过去的，所以枚举第1个人对应哪一个菜，需要左移和右移一些步，找个移动总路径的最小值

I: 讨论一下，n=1 corner case：这时原点不是交点。

J:

K: 一定是high low high low的序列，结论1：路上没有偶环；结论2：把两端点不同色的边连上，一定是图上某一棵dfs树加上一条同色的返祖边，结论3：对同一个点双，任取3点ABC，一定存在A到B到C的点不重复的路径，结论4：以0为根建圆方树，存在同色边(u,v)，u在的点双是v点双的祖先。

L: 先把gcd(n,m)=1情况排除掉。然后猜想只会中转一次，发现最优的点与起点、终点组成的三角形内部不应该包含任何一个点。所以只需枚举对角线周围一小块的点即可。

M: 树上贪心

附加文件