2016-C05-team5

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== jcq1234 ===
感觉欧洲人好强。。。开场读了F, G都没思路，然后大概看了下H是个几何题，准备甩锅给学长，然后就一直在想F和G怎么做。之后发现学长们都过了D，就开始想D，开始以为是动规，想了很久写不出转移方程，后来感觉应该挺简单的，就猜了一种方案，过了。后面看到其他队的学长过了F，就和triomino学长一起推F的递推公式，结果整场都没推出来。。。
=== wtthhh === 
今天出了4题，仍然是有两题卡全场。。H和F，H的计算几何迷之错误？不知道为什么。。F的数学姿势还是要学习一波
== 总结 ==

=== jcq1234 ===
 * 如果不能转换成矩阵的幂，递推公式中加的常数要想法去掉
 * 数论这块还是不太熟练，还是要多练点题

=== wtthhh ===
 * H题是我的锅，没有什么特殊的地方但就是不知道为什么被卡。。一会学习一波
 * 今天图论题比较多，感觉E维护并查集的做法还是可写的，求全局流量的题也还要学习一波姿势。。
 * 发现了H题的问题。。。复数sort用的默认比较器，比较的时候因为精度问题，出现了-0.5  1  <  -0.5  0的情况。。。-0.5 < -0.5 这在单个比较的时候并不影响。。但因为是复数就出现bug了。。
=== triomino === 
 * K题数组开小RE了一次，交之前应该检查一下。
 * F题浪费时间太多。~~其实别的题肯定也想不出来~~

 == 题解 ==

=== E ===
用并查集维护连通块中点的数量，连通块中度为2的点的数量

=== F ===

=== G ===

=== J ===
求一个图的全局点对流量和，有一个性质就是点度最大为3。
先处理点对流量为1的点对，找出图中的桥，断开即可，剩下的都是点双联通分量，块之间流量均为1
然后再在块内处理流量为2或3的情况，删掉某条边以后如果变成两个点双连通分量则两个块之间~~流量均为2~~
实际上复杂的多，要试着删除每条边，第i条边删掉之后如果分成了两个块则给两个块内的点各打上一个标记i1 或 i2
所有边处理完之后对于每一对点，看他们的标记序列是否完全相同，完全相同的流量才为3，否则为2

=== L ===

 == 补题 ==

=== jcq1234 ===
 * E, ~~F~~, H

=== wtthhh ===
 * E, ~~H~~, J

=== triomino ===
 * ~~F~~, ~~I~~

流水账

jcq1234

感觉欧洲人好强。。。开场读了F, G都没思路，然后大概看了下H是个几何题，准备甩锅给学长，然后就一直在想F和G怎么做。之后发现学长们都过了D，就开始想D，开始以为是动规，想了很久写不出转移方程，后来感觉应该挺简单的，就猜了一种方案，过了。后面看到其他队的学长过了F，就和triomino学长一起推F的递推公式，结果整场都没推出来。。。

wtthhh

今天出了4题，仍然是有两题卡全场。。H和F，H的计算几何迷之错误？不知道为什么。。F的数学姿势还是要学习一波

总结

jcq1234

如果不能转换成矩阵的幂，递推公式中加的常数要想法去掉
数论这块还是不太熟练，还是要多练点题

wtthhh

H题是我的锅，没有什么特殊的地方但就是不知道为什么被卡。。一会学习一波
今天图论题比较多，感觉E维护并查集的做法还是可写的，求全局流量的题也还要学习一波姿势。。
发现了H题的问题。。。复数sort用的默认比较器，比较的时候因为精度问题，出现了-0.5 1 < -0.5 0的情况。。。-0.5 < -0.5 这在单个比较的时候并不影响。。但因为是复数就出现bug了。。

triomino

K题数组开小RE了一次，交之前应该检查一下。
F题浪费时间太多。~~其实别的题肯定也想不出来~~

题解

E

用并查集维护连通块中点的数量，连通块中度为2的点的数量

F

G

J

求一个图的全局点对流量和，有一个性质就是点度最大为3。

先处理点对流量为1的点对，找出图中的桥，断开即可，剩下的都是点双联通分量，块之间流量均为1

然后再在块内处理流量为2或3的情况，删掉某条边以后如果变成两个点双连通分量则两个块之间~~流量均为2~~

实际上复杂的多，要试着删除每条边，第i条边删掉之后如果分成了两个块则给两个块内的点各打上一个标记i1 或 i2

所有边处理完之后对于每一对点，看他们的标记序列是否完全相同，完全相同的流量才为3，否则为2