2016-E25-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||Siunaus||D||AC||0||180||C++||1471||2016-12-03 19:10:29||
||Siunaus||A||AC||0||80||C++||2470||2016-12-03 18:51:49||
||Siunaus||C||WA|| || ||C++||4887||2016-12-03 18:45:03||
||Siunaus||E||AC||0||90||C++||4868||2016-12-03 18:40:51||
||Siunaus||A||WA|| || ||C++||2117||2016-12-03 18:36:34||
||Siunaus||A||TLE|| || ||C++||2182||2016-12-03 18:25:57||
||Siunaus||E||MLE|| || ||C++||4691||2016-12-03 18:18:56||
||Siunaus||A||WA|| || ||C++||2073||2016-12-03 17:58:38||
||Siunaus||E||WA|| || ||C++||4273||2016-12-03 17:57:32||
||Siunaus||A||WA|| || ||C++||2388||2016-12-03 17:52:47||
||Siunaus||C||RE|| || ||C++||4213||2016-12-03 17:47:45||
||Siunaus||C||WA|| || ||C++||2394||2016-12-03 17:29:12||
||Siunaus||B||AC||0||20||C++||877||2016-12-03 16:27:18||
||Siunaus||J||AC||0||30||C++||2113||2016-12-03 16:05:07||
||Siunaus||B||WA|| || ||C++||644||2016-12-03 15:42:28||
||Siunaus||K||AC||0||380||C++||1912||2016-12-03 15:30:19||
||Siunaus||C||CE|| || ||C++||1284||2016-12-03 15:07:48||
||Siunaus||C||AC||0||40||C++||1715||2016-12-03 14:49:05||
start at 14:21
比赛链接: http://vjudge.net/contest/143921
== 流水账 ==
== 总结 ==
== 题解 ==
=== A. Colourful Graph [Akalm && sfiction] ===
分两阶段去做。第一阶段先让每种颜色都取一个点，交换（交换可以不破坏其它点的性质）到其最终位置上，并将它们记为关键点，步数上限为K * 200；第二阶段对于剩余的点，把同色关键点移动到其旁边，给它染色，再原路返回，步数上限为(N-K)*200。
=== B. Doors [JTJL] ===
分类讨论即可，注意AB都小于90度时有两条垂线会影响答案。
=== C. Playing with Numbers [sfiction] ===
'''比赛时的做法有误！！'''
gcd和lcm可以视为对多维分别取min或max，两者对称，因此只讨论求最小值的情况。
- k=0. 只能全lcm。
- k=1. gcd(x3,lcm(x1,x2))=lcm(gcd(x1,x3),gcd(x2,x3))。因此lcm在最后一步做。两侧可以分别令某一维达到极值，枚举其中一维的大小，将不符的数放入另一维。对枚举产生的结果取对数比较大小。
- k>=2. 分别保留两维(2,3)最大的数，对其他所有数做gcd，之后再做两次lcm。
O(nlogn)。
=== D. Peak Tram [sfiction] ===
考虑高度改变的几种目标：增高以超过之前的建筑h；降低以低于之后的建筑h。两者都与其他建筑的高度有关，容易发现两者分别只需h+1和h-1，最多出现连续n-1次，因此一定存在最优方案，所有高度都满足与某一初始高度的差绝对值<=n-1。因此最多只有n(2n-1)个不同高度。（可能存在更小的界）根据这个分析过程取了更小的范围[qi-i+1,qi+n-i]，也能过，状态少了一半，只有n^2^个。
用dp(i,k,h)表示前i个建筑，k个可见，最高高度为h。有两种转移：
- i不可见，dp(i,k,h)->dp(i-1,k,h)
- i可见，dp(i,k,h)->min(dp(i-1,k-1,l))+change(i,p,h)， l<h
前者O(1)，后者可以通过前缀和优化到O(1)。O(n^4^)。
=== E. Peak Tower [JTJL] ===
预处理出所有关键时间点，相邻时间点之间面积是关于时间的二次函数，分段插值求最小值即可。
sfiction: 考虑矩形相交所得一个极小矩形，在变化过程中它的四条边都可以用关于t的一个一次函数来表示，因此它的两维长度可以分别用一个一次函数表示，面积可以用一个二次函数表示。直到构成这个极小矩形的边发生改变，这个函数才会发生变动。总面积也是如此。因此可以以两个方向上线段的重合为事件点，插值求得两个相邻事件点面积的表达式再求最值。采样可以用矩形并完成。O(n^2^logn+n^4^logn)。
仔细考虑的话，似乎可以让矩形的运动变得更复杂点，使得t'为关于t的一个有反函数的函数，而矩形速度是关于t'的一次函数，强行增加题目难度。
JTJL: 你有毒吧(XD，只要是多项式都没关系啊……
=== H. Slim Cut [sfiction] ===
确定割边集中最大边权后，边权更大的边不可选，因此必须合并其连接的点，其他边则可随意断开。问题转化为背包问题，物品为连通块，目标是求出最接近n/2的总体积。暴力做n次bitset优化背包复杂度过高。考虑到一个连通块的“存活时间”是连续的，可以用线段树来优化。每个叶子对应一次询问，一个结点有物品x表示以它为根的子树中所有的背包问题都有物品x。增加完线段后再做一遍DFS。这样一个连通块被划分为logn件物品，DFS过程中每个结点的物品只会被计算一次，相当于复用了父节点的结果。
O(m+n!^2logn)。
这一技巧具有很强的通用性。如果一类问题满足以下性质：
* 一个特定问题可以表示为一个集合X（一般为可重集合），其中元素x\in A。
* s(X)表示某个问题X的状态，所有s构成集合S。S需要良好地定义，满足s(X)+x=s(X\cup {x})可计算。而且可以从s快速得到解，设为answer(s(X))。有时S本身也装备有运算，即S(X)+S(Y)=S(X\cup Y)。
大致来说就是这个问题可以“增量式”地解决，而且参与运算的元素顺序与结果无关。s并不是问题的解，它还记录了足够进行递推的信息，但应当可以从s中快速计算得到解。例如背包问题中，A为正整数集，s为阶段i的所有状态f[i][]。
本题所用的分治优化中只需要能够支持快速的S+x和answer(s)。设X_1..X_n为n个特定问题，线段树中一个结点的问题可以定义为Y_u=\bigcap_{i=l(u)}!^{r(u)}X_i，这样自顶向下DFS求解，可以尽可能减少重复运算。定义Yd_u=Y_u-Y_{father(u)}为每个结点的增量部分。总的代价为\sum_{u}|Yd_u|。
从另外一种角度考虑，假设一个元素x出现在X_l..X_r中（需要按某种顺序区分可重集中的相同元素）。线段树可以将x的出现区间划分为logn个区间，x属于这些区间所对应结点u的增量集合Yd_u（因为我们已经区别了可重集中的相同元素）。设不同元素数量为m，则代入上一段中式子，可知总代价为mlogn。
如果复杂度允许，可以生成新的s(X)，否则需要让s(x)可回溯。
=== J. Taboo [sfiction] ===
AC自动机建图，删除所有终止点。由从root出发的所有可达点和可用边构成一个新图G。如果G中有环则存在无限长的串，否则即为DAG上求字典序最小的最长链。每个点出边所带权各不相同，因此可以从后往前做，不需要判断后缀的大小关系。O(S)。
=== K. Team Up [Akalm] ===
利用题目中集合的关系，每个点往恰好为其子集（即B \subset A且不存在C使得B \subset C \subset A）的点连边，建成一棵树。然后就是树dp算答案，再从根dfs下去构造方案。| User | Problem | Result | Memory | Time | Language | Length | Submit Time |
| Siunaus | D | AC | 0 | 180 | C++ | 1471 | 2016-12-03 19:10:29 |
| Siunaus | A | AC | 0 | 80 | C++ | 2470 | 2016-12-03 18:51:49 |
| Siunaus | C | WA | C++ | 4887 | 2016-12-03 18:45:03 | ||
| Siunaus | E | AC | 0 | 90 | C++ | 4868 | 2016-12-03 18:40:51 |
| Siunaus | A | WA | C++ | 2117 | 2016-12-03 18:36:34 | ||
| Siunaus | A | TLE | C++ | 2182 | 2016-12-03 18:25:57 | ||
| Siunaus | E | MLE | C++ | 4691 | 2016-12-03 18:18:56 | ||
| Siunaus | A | WA | C++ | 2073 | 2016-12-03 17:58:38 | ||
| Siunaus | E | WA | C++ | 4273 | 2016-12-03 17:57:32 | ||
| Siunaus | A | WA | C++ | 2388 | 2016-12-03 17:52:47 | ||
| Siunaus | C | RE | C++ | 4213 | 2016-12-03 17:47:45 | ||
| Siunaus | C | WA | C++ | 2394 | 2016-12-03 17:29:12 | ||
| Siunaus | B | AC | 0 | 20 | C++ | 877 | 2016-12-03 16:27:18 |
| Siunaus | J | AC | 0 | 30 | C++ | 2113 | 2016-12-03 16:05:07 |
| Siunaus | B | WA | C++ | 644 | 2016-12-03 15:42:28 | ||
| Siunaus | K | AC | 0 | 380 | C++ | 1912 | 2016-12-03 15:30:19 |
| Siunaus | C | CE | C++ | 1284 | 2016-12-03 15:07:48 | ||
| Siunaus | C | AC | 0 | 40 | C++ | 1715 | 2016-12-03 14:49:05 |
start at 14:21
比赛链接: http://vjudge.net/contest/143921
流水账
总结
题解
A. Colourful Graph [Akalm && sfiction]
分两阶段去做。第一阶段先让每种颜色都取一个点，交换（交换可以不破坏其它点的性质）到其最终位置上，并将它们记为关键点，步数上限为K * 200；第二阶段对于剩余的点，把同色关键点移动到其旁边，给它染色，再原路返回，步数上限为(N-K)*200。
B. Doors [JTJL]
分类讨论即可，注意AB都小于90度时有两条垂线会影响答案。
C. Playing with Numbers [sfiction]
比赛时的做法有误！！
gcd和lcm可以视为对多维分别取min或max，两者对称，因此只讨论求最小值的情况。
- k=0. 只能全lcm。
- k=1. gcd(x3,lcm(x1,x2))=lcm(gcd(x1,x3),gcd(x2,x3))。因此lcm在最后一步做。两侧可以分别令某一维达到极值，枚举其中一维的大小，将不符的数放入另一维。对枚举产生的结果取对数比较大小。
- k>=2. 分别保留两维(2,3)最大的数，对其他所有数做gcd，之后再做两次lcm。
O(nlogn)。
D. Peak Tram [sfiction]
考虑高度改变的几种目标：增高以超过之前的建筑h；降低以低于之后的建筑h。两者都与其他建筑的高度有关，容易发现两者分别只需h+1和h-1，最多出现连续n-1次，因此一定存在最优方案，所有高度都满足与某一初始高度的差绝对值<=n-1。因此最多只有n(2n-1)个不同高度。（可能存在更小的界）根据这个分析过程取了更小的范围[qi-i+1,qi+n-i]，也能过，状态少了一半，只有n2个。
用dp(i,k,h)表示前i个建筑，k个可见，最高高度为h。有两种转移：
- i不可见，dp(i,k,h)->dp(i-1,k,h)
- i可见，dp(i,k,h)->min(dp(i-1,k-1,l))+change(i,p,h)， l 前者O(1)，后者可以通过前缀和优化到O(1)。O(n4)。 预处理出所有关键时间点，相邻时间点之间面积是关于时间的二次函数，分段插值求最小值即可。 sfiction: 考虑矩形相交所得一个极小矩形，在变化过程中它的四条边都可以用关于t的一个一次函数来表示，因此它的两维长度可以分别用一个一次函数表示，面积可以用一个二次函数表示。直到构成这个极小矩形的边发生改变，这个函数才会发生变动。总面积也是如此。因此可以以两个方向上线段的重合为事件点，插值求得两个相邻事件点面积的表达式再求最值。采样可以用矩形并完成。O(n2logn+n4logn)。 仔细考虑的话，似乎可以让矩形的运动变得更复杂点，使得t'为关于t的一个有反函数的函数，而矩形速度是关于t'的一次函数，强行增加题目难度。 JTJL: 你有毒吧(XD，只要是多项式都没关系啊…… 确定割边集中最大边权后，边权更大的边不可选，因此必须合并其连接的点，其他边则可随意断开。问题转化为背包问题，物品为连通块，目标是求出最接近n/2的总体积。暴力做n次bitset优化背包复杂度过高。考虑到一个连通块的“存活时间”是连续的，可以用线段树来优化。每个叶子对应一次询问，一个结点有物品x表示以它为根的子树中所有的背包问题都有物品x。增加完线段后再做一遍DFS。这样一个连通块被划分为logn件物品，DFS过程中每个结点的物品只会被计算一次，相当于复用了父节点的结果。 O(m+n!^2logn)。 这一技巧具有很强的通用性。如果一类问题满足以下性质： 大致来说就是这个问题可以“增量式”地解决，而且参与运算的元素顺序与结果无关。s并不是问题的解，它还记录了足够进行递推的信息，但应当可以从s中快速计算得到解。例如背包问题中，A为正整数集，s为阶段i的所有状态f[i][]。 本题所用的分治优化中只需要能够支持快速的S+x和answer(s)。设X_1..X_n为n个特定问题，线段树中一个结点的问题可以定义为Y_u=\bigcap_{i=l(u)}!^{r(u)}X_i，这样自顶向下DFS求解，可以尽可能减少重复运算。定义Yd_u=Y_u-Y_{father(u)}为每个结点的增量部分。总的代价为\sum_{u}|Yd_u|。 从另外一种角度考虑，假设一个元素x出现在X_l..X_r中（需要按某种顺序区分可重集中的相同元素）。线段树可以将x的出现区间划分为logn个区间，x属于这些区间所对应结点u的增量集合Yd_u（因为我们已经区别了可重集中的相同元素）。设不同元素数量为m，则代入上一段中式子，可知总代价为mlogn。 如果复杂度允许，可以生成新的s(X)，否则需要让s(x)可回溯。 AC自动机建图，删除所有终止点。由从root出发的所有可达点和可用边构成一个新图G。如果G中有环则存在无限长的串，否则即为DAG上求字典序最小的最长链。每个点出边所带权各不相同，因此可以从后往前做，不需要判断后缀的大小关系。O(S)。 利用题目中集合的关系，每个点往恰好为其子集（即B \subset A且不存在C使得B \subset C \subset A）的点连边，建成一棵树。然后就是树dp算答案，再从根dfs下去构造方案。E. Peak Tower [JTJL]
H. Slim Cut [sfiction]
J. Taboo [sfiction]
K. Team Up [Akalm]