2016-E32-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Time||Problem||Result||
||03:54:35 ||I ||Accepted||
||03:05:46 ||B ||Accepted||
||02:22:41 ||J ||Accepted||
||02:21:07 ||J ||Wrong Answer !#1||
||02:03:10 ||G ||Accepted||
||01:34:22 ||G ||Wrong Answer !#2||
||01:30:02 ||E ||Accepted||
||01:24:59 ||G ||Wrong Answer !#2||
||01:19:04 ||E ||Time Limit Exceeded !#13||
||01:15:06 ||E ||Wrong Answer !#3||
比赛链接: http://10.71.10.90/sfiction/ranklist/ICPCCamp2017/ICPCCamp2017-Day2.htm
start at 10:00
== 流水账 ==
== 总结 ==
== 题解 ==
=== B. Connected Spanning Subgraph [JTJL, sfiction] ===
类似Day1-C。考虑对\sum_S{2!^{C(S)}}计数，其中C(S)是边集S的生成子图中的连通块数。那么连通的生成子图贡献2，不连通的生成子图贡献4的倍数，对这个和mod 4再除以2就能得到答案。
将2!^{C(S)}视为对连通块中的点黑白染色。那么和式的意义就相当于对整个图黑白染色，然后选择一个边集S，并且不能有边的两端异色。因此每个染色方案的可选边集数即为2!^{两端同色的边数}。再考虑其反色，则只有所有边都异色的染色方案才贡献2。因此当且仅当图为二分图时，答案为1。
=== D. Line Counting [JTJL, sfiction] ===
可以证明Line_{>=p}=Seg_{p}-Seg_{p+1}。Seg_{p}的求法较为简单。有一个技巧能够简化统计。对于坐标轴格点，进行任意可逆的线性变换后，Seg_{p}的数量不发生变化。将题中三角形变换为等边三角形，明显原先从左上角向第四象限的向量仍为一个顶角，其数量的三倍即为所求结果。之后可以简单求出公式\sum_{d=1}^{(n-1)/(q-1)}{phi(d)(n-qd)(n-qd+1)/2}。展开发现只需计算phi(x)、xphi(x)、x^2phi(x)三种前缀和。用一些数论方法求解即可。
=== E. Maximum Flow [JTJL, Akalm] ===
根据特殊图形+最小割贪心。每个极小割必定由顶部一段和底部一段（可能为空，即顶部尾或底部首）和所夹的连续段组成。按照顶/底部段的位置关系分成两类贪心即可。O(n)。
或者用最短路硬怼。
=== F. Rectangles Inside Rectangle [sfiction] ===
用f[h][i]表示每个一个边界，即底部为h，顶部为b[i]，中间分割为l[i]的折线。转移包括提升底部（注意h高于b[i]时将i重设为0）、i=0时随意放置底部为h的矩形，最后是放置底部为h且不与i冲突的矩形。O(nm)。
=== G. Cute Panda [JTJL, sfiction] ===
贪心/根据特殊图形+最小割DP。贪心：考虑首先将a[1..n-1]贪心地（尽可能填到i）填到b[1..n]。如果其中有一个b[i]未满，则可以将b[1..i-1]中的内容整体向后移动数个单位，从而增加b[1]的剩余空间，优化最后的解。O(n)。
网络流建图从S到A_i连a[i]边，从B_i到T连b[i]边。A_i到B_i和B_{i+1}都为inf。中间边为inf，因此不可能是最小割的组成部分。如果保留(S,A_i)，则(B_i,T)和(B_{i+1},T)都应该加入割集，否则存在一条可行路径。可以使用动态规划解决。O(n)。
=== H. Order-Preserving Partition [JTJL, sfiction] ===
利用逆序和取反可以归为8类。1234,1243,1324,1342,1423,1432,2143,2413。利用1n的所属简化计算。
1234：求出所有合法分割点。对每个位置前后缀乘积求和。1243：用a[n]做断点求出24的唯一分割后求每侧所有合法分割点相乘。1324，枚举前两段的长度和，13的分割唯一，维护3段的参数即可（可以利用Day1 G题的技巧）。1342，用a[n]做断点求出13唯一分割，再用3的第一个元素做断点求出42唯一分割，求34合法分割点数。1423，用a[n]做断点依次求出142的唯一分割，再求23的合法分割点数。1432，用2求出14的唯一分割，再用前缀和计算432合法分割。2143，类似1243。2413，用a[1]和a[n]分别做断点求出24和13唯一分割，再用其中一个求41唯一分割。
=== I. Prime Tree [JTJL, sfiction] ===
Sol1：利用树哈希解决。首先求出所有子树的哈希值。能分解出的树的大小必定是n的约数d。对于d，我们应该只考虑size[u]>=d的结点，取其所有size[v]<d的子结点合并得到哈希值。判断部分明显可以做到O(\sum{d(n)})。合并size[v]<d的子结点可以从小到大枚举d，在size[v]第一次小于d时，用其哈希值更新父亲的哈希值，这样更新部分就只需要O(n)。
Sol2：求出所有子树的哈希值。对每个结点u，用pair(size[u],hash[u])作为标记。每个结点求一个有序序列，由其所有儿子的标记组成。这个过程用O(n)树同构可以在O(n)时间内完成，暴力O(nlogn)也可以接受。将所有序列再按照size[u]排序。如果某棵树是一个因子，它的序列应该是所有size大于等于它的序列的前缀。暴力做比较即可做到O(n)复杂度，因为如果当前猜测的因子是l，在r+1处比较失败，那么l到r的所有序列都不可能是下面序列的前缀，因此它们可以全部丢弃。如果比较成功，则前缀可以丢弃。比较次数始终不多于元素个数。
=== J. Hamiltonian k-vertex-connected Graph [JTJL, Akalm] ===
构造。首先构一个环，点连通度为2。之后j从开始每加一圈(i,i+j)的边，点连通度+=2。要令点连通度为+=1，可以对每个i=1..(n+1)/2连(i,i+n/2)。| Time | Problem | Result |
| 03:54:35 | I | Accepted |
| 03:05:46 | B | Accepted |
| 02:22:41 | J | Accepted |
| 02:21:07 | J | Wrong Answer !#1 |
| 02:03:10 | G | Accepted |
| 01:34:22 | G | Wrong Answer !#2 |
| 01:30:02 | E | Accepted |
| 01:24:59 | G | Wrong Answer !#2 |
| 01:19:04 | E | Time Limit Exceeded !#13 |
| 01:15:06 | E | Wrong Answer !#3 |
比赛链接: http://10.71.10.90/sfiction/ranklist/ICPCCamp2017/ICPCCamp2017-Day2.htm
start at 10:00
流水账
总结
题解
B. Connected Spanning Subgraph [JTJL, sfiction]
类似Day1-C。考虑对\sum_S{2!^{C(S)}}计数，其中C(S)是边集S的生成子图中的连通块数。那么连通的生成子图贡献2，不连通的生成子图贡献4的倍数，对这个和mod 4再除以2就能得到答案。
将2!{C(S)}视为对连通块中的点黑白染色。那么和式的意义就相当于对整个图黑白染色，然后选择一个边集S，并且不能有边的两端异色。因此每个染色方案的可选边集数即为2!{两端同色的边数}。再考虑其反色，则只有所有边都异色的染色方案才贡献2。因此当且仅当图为二分图时，答案为1。
D. Line Counting [JTJL, sfiction]
可以证明Line_{>=p}=Seg_{p}-Seg_{p+1}。Seg_{p}的求法较为简单。有一个技巧能够简化统计。对于坐标轴格点，进行任意可逆的线性变换后，Seg_{p}的数量不发生变化。将题中三角形变换为等边三角形，明显原先从左上角向第四象限的向量仍为一个顶角，其数量的三倍即为所求结果。之后可以简单求出公式\sum_{d=1}{(n-1)/(q-1)}{phi(d)(n-qd)(n-qd+1)/2}。展开发现只需计算phi(x)、xphi(x)、x2phi(x)三种前缀和。用一些数论方法求解即可。
E. Maximum Flow [JTJL, Akalm]
根据特殊图形+最小割贪心。每个极小割必定由顶部一段和底部一段（可能为空，即顶部尾或底部首）和所夹的连续段组成。按照顶/底部段的位置关系分成两类贪心即可。O(n)。
或者用最短路硬怼。
F. Rectangles Inside Rectangle [sfiction]
用f[h][i]表示每个一个边界，即底部为h，顶部为b[i]，中间分割为l[i]的折线。转移包括提升底部（注意h高于b[i]时将i重设为0）、i=0时随意放置底部为h的矩形，最后是放置底部为h且不与i冲突的矩形。O(nm)。
G. Cute Panda [JTJL, sfiction]
贪心/根据特殊图形+最小割DP。贪心：考虑首先将a[1..n-1]贪心地（尽可能填到i）填到b[1..n]。如果其中有一个b[i]未满，则可以将b[1..i-1]中的内容整体向后移动数个单位，从而增加b[1]的剩余空间，优化最后的解。O(n)。
网络流建图从S到A_i连a[i]边，从B_i到T连b[i]边。A_i到B_i和B_{i+1}都为inf。中间边为inf，因此不可能是最小割的组成部分。如果保留(S,A_i)，则(B_i,T)和(B_{i+1},T)都应该加入割集，否则存在一条可行路径。可以使用动态规划解决。O(n)。
H. Order-Preserving Partition [JTJL, sfiction]
利用逆序和取反可以归为8类。1234,1243,1324,1342,1423,1432,2143,2413。利用1n的所属简化计算。
1234：求出所有合法分割点。对每个位置前后缀乘积求和。1243：用a[n]做断点求出24的唯一分割后求每侧所有合法分割点相乘。1324，枚举前两段的长度和，13的分割唯一，维护3段的参数即可（可以利用Day1 G题的技巧）。1342，用a[n]做断点求出13唯一分割，再用3的第一个元素做断点求出42唯一分割，求34合法分割点数。1423，用a[n]做断点依次求出142的唯一分割，再求23的合法分割点数。1432，用2求出14的唯一分割，再用前缀和计算432合法分割。2143，类似1243。2413，用a[1]和a[n]分别做断点求出24和13唯一分割，再用其中一个求41唯一分割。
I. Prime Tree [JTJL, sfiction]
Sol1：利用树哈希解决。首先求出所有子树的哈希值。能分解出的树的大小必定是n的约数d。对于d，我们应该只考虑size[u]>=d的结点，取其所有size[v] Sol2：求出所有子树的哈希值。对每个结点u，用pair(size[u],hash[u])作为标记。每个结点求一个有序序列，由其所有儿子的标记组成。这个过程用O(n)树同构可以在O(n)时间内完成，暴力O(nlogn)也可以接受。将所有序列再按照size[u]排序。如果某棵树是一个因子，它的序列应该是所有size大于等于它的序列的前缀。暴力做比较即可做到O(n)复杂度，因为如果当前猜测的因子是l，在r+1处比较失败，那么l到r的所有序列都不可能是下面序列的前缀，因此它们可以全部丢弃。如果比较成功，则前缀可以丢弃。比较次数始终不多于元素个数。 构造。首先构一个环，点连通度为2。之后j从开始每加一圈(i,i+j)的边，点连通度+=2。要令点连通度为+=1，可以对每个i=1..(n+1)/2连(i,i+n/2)。J. Hamiltonian k-vertex-connected Graph [JTJL, Akalm]