2016-E31-team1

从 Trac 迁移的文章

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

原文章内容如下：

||Time||Problem||Result||
||04:20:54||F||Accepted||
||04:16:50||F||Wrong Answer !#6||
||02:18:26||K||Accepted||
||01:48:38||K||Wrong Answer !#2||
||01:01:47||E||Accepted||

比赛链接: http://10.71.10.90/sfiction/ranklist/ICPCCamp2017/ICPCCamp2017-Day1.htm

start at 12:30

== 流水账 ==

== 总结 ==

== 题解 ==


=== A. Even Three if Odd [sfiction] ===

dp(i,j,l)表示x_1..x_{i+l}已经确定，并且max(x_i,x_{i+1})=j的序列贡献和。考虑dp(i,j,l)到dp(i,k,l')的转移即可，固定k和k'，l和l'的取值共四种，每种情况各不相同。注意如果x_i==x_{i+1}可能会重复计算，要规定相等时l=0。O(n^2)。

00，要求j>=k，x_{i+1}被唯一确定，*w[j]。01，x_{i+1}可以取[1,min(j,k-1)]，*max(j,k)。10，要求j=k，x_{i+1}被唯一确定，*w[j]。11，要求j<k，x_{i+1}被唯一确定，*w[k]。

=== B. Walk of Length 6 [JTJL] ===

分成9类分别进行计数：链长=1、链长=2、链长=3、三元环、Y型、四元环、四元环对角线、四元环加边、相交三元环。s1=|E|。s2=\sum{C(deg(u),2)}。s3=\sum{(deg(u)-1)*(deg(v)-1)}。s4枚举边，bitset与。s5=\sum{C(deg(u),3)}。s6枚举所有点对，bitset与后choose 2。s7枚举E，bitset后choose 2。s8在s6基础上选一个点枚举其他边。s9计算u在多少个三角形上choose 2，减去s7。注意计算每种形状对应的方案数。

=== C. City United [JTJL] ===

考虑对\sum_S{2!^{C(S)}}计数，其中C(S)是点集S的诱导子图中的连通块。那么连通的诱导子图贡献2，不连通的诱导子图贡献4的倍数，对这个和mod 4再除以2就能得到答案。

将2!^{C(S)}视为对连通块中的点黑白染色，S外的点染为灰色。那么和式的意义就相当于对整个图黑白灰染色，并且黑点和白点不能有边相连（相连边应该位于诱导子图，从而两点同色）。O(3!^13*n)状压DP即可。

=== D. Coins 2 [sfiction] ===

设m=lcm(1..n)，对于任意s>=nm的方案，都必然存在至少一种货币i总价值>=m，不断减去(m/i)个货币i即得到s<nm的方案。因此所有方案可以分解为公差为m，首项小于nm，尾项>sum-nm的等差数列。计算总量为nm的多重背包问题即可求出每种等差数列的上下界。O(n!^2lcm)。

=== E. Lowest Common Ancestor [sfiction] ===

考虑计算f(i)，LCA只可能是i到1路径上的点。将>=i的点的权重设为0，g()表示子树总权重。则f(i)=\sum{g(u)*(w[u]-w[fa[u]])}。从i对应的f()转移到i+1对应的f()也是处理i+1到1的路径，因此可以用树链剖分+线段树维护。O(nlog!^2n)。

=== F. Multi-stage Marathon [JTJL, sfiction] ===

异或和乘法/加法没有交换律，很难统一计算，只能考虑计算出所有的E(t,n)。而T又太大，必须将单次计算限制在O(n)。考虑用递推计算f(i,j)，表示E(t,j)对E(t+i,n)的贡献，单次转移为O(n!^2)，考虑到n的大小可以计算前n!^2项，这一部分复杂度为O(n!^4)。有人进入的位置必须计算出向量，考虑到m的大小，单次复杂度必须限制在O(n!^2)，因此只能用向量乘矩阵。由上一步的估计确定最大段长为n!^2（过长的段手动插入关键点进行分割）。设转移矩阵为T，则可以在O(n!^4)时间内预处理出T!^i{i=1..n}和T!^(ni){i=1..n}，这样每次关键点之间的向量乘矩阵都可以用两次乘法解决。段数最多为m+T/n!^2，因此总的复杂度为O(n!^4+nT+n!^2m)。

标程：关键点单次转移只需要O(n!^2)，因此最多可以有m+T/n段，最大段长n。预处理部分暴力即可做到O(n!^4)。

=== G. Matrix Recurrence [sfiction] ===

假设当前有p<=ci<q，并且对所有p<=j<q，维护了\prod{f(p..j)}。那么显然只要维护q..i的乘积即可快速计算f(i)。当ci>=q时，取p=q，q=i，重新计算以q-1结尾的后缀和即可。这样每个i对应一个后缀和，复杂度为O(n)。

=== H. Permutation and noitatumreP [JTJL] ===

是个线性递推。详细证明：http://www.valpo.edu/mathematics-statistics/files/2014/09/Pudwell2015.pdf

=== I. Compressed LCS ===

TBA

=== J. Circle Sectors ===

TBA

=== K. Welcome to ICPCCamp 2017 [sfiction] ===

对于每种让r(n+1,1)在区域赛出线的方案，都可以令X->X-1，Y->1从而使其在final出线而不影响其他学校。因此令r(n+1,1)出现与否的方案数分别是Y=0且其不出线和Y>0的方案数。后者在去除r(n+1,1)之后即为一个子问题。设rk[i]为i在区域赛中最好成绩，b[i]为最好成绩为i的队伍数。则前者相当于1+(2^b[1]-1)+...+(2^b[rk[r(n+1,1)]-1]-1)。用树状数组维护2!^b[i]即可。O(nlogn)。
TimeProblemResult
04:20:54FAccepted
04:16:50FWrong Answer !#6
02:18:26KAccepted
01:48:38KWrong Answer !#2
01:01:47EAccepted

比赛链接: http://10.71.10.90/sfiction/ranklist/ICPCCamp2017/ICPCCamp2017-Day1.htm

start at 12:30

流水账

总结

题解

A. Even Three if Odd [sfiction]

dp(i,j,l)表示x_1..x_{i+l}已经确定，并且max(x_i,x_{i+1})=j的序列贡献和。考虑dp(i,j,l)到dp(i,k,l')的转移即可，固定k和k'，l和l'的取值共四种，每种情况各不相同。注意如果x_i==x_{i+1}可能会重复计算，要规定相等时l=0。O(n^2)。

00，要求j>=k，x_{i+1}被唯一确定，*w[j]。01，x_{i+1}可以取[1,min(j,k-1)]，*max(j,k)。10，要求j=k，x_{i+1}被唯一确定，*w[j]。11，要求j

B. Walk of Length 6 [JTJL]

分成9类分别进行计数：链长=1、链长=2、链长=3、三元环、Y型、四元环、四元环对角线、四元环加边、相交三元环。s1=|E|。s2=\sum{C(deg(u),2)}。s3=\sum{(deg(u)-1)*(deg(v)-1)}。s4枚举边，bitset与。s5=\sum{C(deg(u),3)}。s6枚举所有点对，bitset与后choose 2。s7枚举E，bitset后choose 2。s8在s6基础上选一个点枚举其他边。s9计算u在多少个三角形上choose 2，减去s7。注意计算每种形状对应的方案数。

C. City United [JTJL]

考虑对\sum_S{2!^{C(S)}}计数，其中C(S)是点集S的诱导子图中的连通块。那么连通的诱导子图贡献2，不连通的诱导子图贡献4的倍数，对这个和mod 4再除以2就能得到答案。

将2!{C(S)}视为对连通块中的点黑白染色，S外的点染为灰色。那么和式的意义就相当于对整个图黑白灰染色，并且黑点和白点不能有边相连（相连边应该位于诱导子图，从而两点同色）。O(3!13*n)状压DP即可。

D. Coins 2 [sfiction]

设m=lcm(1..n)，对于任意s>=nm的方案，都必然存在至少一种货币i总价值>=m，不断减去(m/i)个货币i即得到ssum-nm的等差数列。计算总量为nm的多重背包问题即可求出每种等差数列的上下界。O(n!^2lcm)。

E. Lowest Common Ancestor [sfiction]

考虑计算f(i)，LCA只可能是i到1路径上的点。将>=i的点的权重设为0，g()表示子树总权重。则f(i)=\sum{g(u)*(w[u]-w[fa[u]])}。从i对应的f()转移到i+1对应的f()也是处理i+1到1的路径，因此可以用树链剖分+线段树维护。O(nlog!^2n)。

F. Multi-stage Marathon [JTJL, sfiction]

异或和乘法/加法没有交换律，很难统一计算，只能考虑计算出所有的E(t,n)。而T又太大，必须将单次计算限制在O(n)。考虑用递推计算f(i,j)，表示E(t,j)对E(t+i,n)的贡献，单次转移为O(n!2)，考虑到n的大小可以计算前n!2项，这一部分复杂度为O(n!4)。有人进入的位置必须计算出向量，考虑到m的大小，单次复杂度必须限制在O(n!2)，因此只能用向量乘矩阵。由上一步的估计确定最大段长为n!2（过长的段手动插入关键点进行分割）。设转移矩阵为T，则可以在O(n!4)时间内预处理出T!i{i=1..n}和T!(ni){i=1..n}，这样每次关键点之间的向量乘矩阵都可以用两次乘法解决。段数最多为m+T/n!2，因此总的复杂度为O(n!4+nT+n!^2m)。

标程：关键点单次转移只需要O(n!2)，因此最多可以有m+T/n段，最大段长n。预处理部分暴力即可做到O(n!4)。

G. Matrix Recurrence [sfiction]

假设当前有p<=ci=q时，取p=q，q=i，重新计算以q-1结尾的后缀和即可。这样每个i对应一个后缀和，复杂度为O(n)。

H. Permutation and noitatumreP [JTJL]

是个线性递推。详细证明：http://www.valpo.edu/mathematics-statistics/files/2014/09/Pudwell2015.pdf

I. Compressed LCS

TBA

J. Circle Sectors

TBA

K. Welcome to ICPCCamp 2017 [sfiction]

对于每种让r(n+1,1)在区域赛出线的方案，都可以令X->X-1，Y->1从而使其在final出线而不影响其他学校。因此令r(n+1,1)出现与否的方案数分别是Y=0且其不出线和Y>0的方案数。后者在去除r(n+1,1)之后即为一个子问题。设rk[i]为i在区域赛中最好成绩，b[i]为最好成绩为i的队伍数。则前者相当于1+(2b[1]-1)+...+(2b[rk[r(n+1,1)]-1]-1)。用树状数组维护2!^b[i]即可。O(nlogn)。