2020-team1-040

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 8/10  dirt: 47%
rank: 15
[[Image(Rank.png,800px)]]

== 流水账 ==

== 总结 ==
Sakuya:对A题的判断出现了比较大的失误，以为这种半提交答案题是用罚时莽过去的，而且应该把它交给擅长模拟的oscar（斜眼笑）。
Grammy:虽然好像很用力了，但是队伍节奏确实慢一拍，感觉可能个人实力不够是原因之一。A题作为一个原本的签到题，差点出事了，占了两人一机，把队伍节奏拖住了。
== 题解 ==
A: 暴力
B: 类似字典序
C: 随机染色，不断调整，每次把相邻颜色相同最多的点变成相邻颜色中最少的
D: fwt
E: 先O(nsqrtn)找出所有三角形（Appollonian network 的结论说明至多O(n)个），找到每条边两侧对应的面积最小的三角形连一条边；新图度数至多3，每次如果有旁边已取节点数为2的节点优先取，否则找到一个'''三角形三个顶点不全在已取边界上的'''节点取，拿个队列维护这个过程即可。不判粗体字部分会WA107~108，so sad..
F: 暴力枚举+判是否为对角线，先判顶点连线是否与边界相交，再取中点射线法判是否在多边形内
G: 
H: 从根开始的dfs中所有返祖边一定都直接返回根，因此把根去掉后形成森林，定义与根相连的点为关键点，最终答案需要满足任意两个关键点形成的路径上至少被去掉一个点。树形dp。
I: dp[i][j][0/1]代表第一条路径走到i，第二条路径走到j，i~j这条边是否被任意一条路径用过的答案；卡内存，要么重新跑一遍输出方案，要么开short和bitset记录
J: 一定是一个矩形特别小，一个矩形特别大，且大的矩形比较接近正方形，预处理1e6以内小矩形，爆搜大矩形

[/wiki/2020-team1 返回]

概述

solved: 8/10 dirt: 47%

rank: 15

流水账

总结

Sakuya:对A题的判断出现了比较大的失误，以为这种半提交答案题是用罚时莽过去的，而且应该把它交给擅长模拟的oscar（斜眼笑）。

Grammy:虽然好像很用力了，但是队伍节奏确实慢一拍，感觉可能个人实力不够是原因之一。A题作为一个原本的签到题，差点出事了，占了两人一机，把队伍节奏拖住了。

题解

A: 暴力

B: 类似字典序

C: 随机染色，不断调整，每次把相邻颜色相同最多的点变成相邻颜色中最少的

D: fwt

E: 先O(nsqrtn)找出所有三角形（Appollonian network 的结论说明至多O(n)个），找到每条边两侧对应的面积最小的三角形连一条边；新图度数至多3，每次如果有旁边已取节点数为2的节点优先取，否则找到一个三角形三个顶点不全在已取边界上的节点取，拿个队列维护这个过程即可。不判粗体字部分会WA107~108，so sad..

F: 暴力枚举+判是否为对角线，先判顶点连线是否与边界相交，再取中点射线法判是否在多边形内

G:

H: 从根开始的dfs中所有返祖边一定都直接返回根，因此把根去掉后形成森林，定义与根相连的点为关键点，最终答案需要满足任意两个关键点形成的路径上至少被去掉一个点。树形dp。

I: dp[i][j][0/1]代表第一条路径走到i，第二条路径走到j，i~j这条边是否被任意一条路径用过的答案；卡内存，要么重新跑一遍输出方案，要么开short和bitset记录

J: 一定是一个矩形特别小，一个矩形特别大，且大的矩形比较接近正方形，预处理1e6以内小矩形，爆搜大矩形

附加文件