team2012-B1

从 Trac 迁移的文章

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

原文章内容如下：

dd_engi 崔添翼
13958103659 / 658659
tianyicui@gmail.com
== Round 1 ==
=== Group A ===
==== 0001 Kitty's Game ====
显然途中的数肯定是K的约数，若将在场景i、分数j（j是K的约数）的情况抽象成一个点(i,j)，那么题目就是在有向无环图中求路径数。
==== 0002 The Review Plan ====
容斥原理。2^M^ 地枚举出需满足的条件组合（有些条件组合可能存在冲突无法满足），根据条件数的奇偶性决定是加或减一个全排列数。
==== 0003 Decode ====
给出的是一个异或运算的线性空间，先用高斯消元求出空间的基，然后即可求出任意元素是否在空间内。枚举改动了0、1、2、3位的情况，找到在空间内的字典序最小的解。
==== 0004 Ribbon Gymnastics ====
设d[i][j]表示第i、第j两点的距离。r[i]表示第i点圆的半径。则要求满足形如r[i]+r[j]<=d[i][j]的六个方程的前提下最大化r[0]+r[1]+r[2]+r[3]。将方程分成三组两两相加可知最优解是min(d[0][1]+d[2][3],d[0][2]+d[1][3],d[0][3]+d[1][2])。
==== 0005 Gao the Grid ====
若三角形的边界在一个(x,y)的矩形上，三角形的数量是有四种情况： a) 4 * (x - 2) * (y - 2) （一个点在角上，两个点在边上；b) 2 * (x * y - gcd(x-1,y-1) - 3) （两个点在对角上，另一个点不在边上或矩形内）；c) 2 * (x - 2) + 2 * (y - 2)（两个点在相邻角上，一个点在对边上）；d) 4 （三个点都在角上）。(n,m)的矩形中共有(n-x+1)*(n-y+1)个这样的矩形。枚举(x,y)从(1,1)到(n,m)并相加。
==== 0006 Cut the Tree 2 ====
枚举选哪个点，分割成的权值和就是它的儿子上的子树的权值和以及总权值和减去它自身子树的权值和，算出权值和的积，取最大的即可。需要用大数。
=== Group B ===
==== 0007 Alice's present ====
给一个数列a[1..n]，每次询问一个区间a[i..j]内的数是否全部unique，如果不是，输出a[max(k | i<=k<=l<=j, a[k]==a[l]]。预处理p[1..n]，p[i]表示a[1..i]区间的答案。p[i]=max(p[i-1], max(j | j < i, a[j]==a[i]))。则a[i..j]的答案只需看p[j]是否小于i，如果不是输出a[p[j]]，否则满足unique条件。
==== 0008 Bounty hunter ====
标准算法是贪心，但不好想，这个dp比较好想。f[i]表示在第i个城市时有有1金钱时最终最多能有多少金钱，g[i]表示在第i个城市时有1经验时最终最多能有多少金钱。转移是f[i] = max(f[i+1], 1 / A[i] * B[i] * f[i+1] + 1 / A[i] * g[i+1]); （也即不花钱和花钱两种情况）；g[i] = g[i+1] + B[i] * f[i+1]; 最终答案就是 f[0] * X + g[0] * Y。
==== 0009 Guess a Function ====
可以按位求出g的反函数。故只需求h2(g(h1(x)))这样一个函数。若枚举h1的参数m1、s1，则可以通过数据求出m2、s2。因为h2(x) = x + s2（当h2(x)>x时）或 h2(x) = x + s2 - m2（当h2(x)<x时）。当验证两组数据求出的h2满足所有数据时则解出了h1。
==== 0010 Maze ====
对于每次给出的一列，先预处理出一个矩阵m[i][j]表示从第i行进能否从第j行出。这个矩阵的t次方就是整段从第i行进第j行出的方案数。将所有这些矩阵相乘，最后的结果就是矩阵的元素和。
==== 0011 Paint Erased ====
对于每一个线段，算出与每一个矩形的交集，将交出的这些交集（线段）按照paint、erase的规则进行模拟，则可得到这个线段最后留下的长度。将所有线段留下的长度加起来即可。写起来有些麻烦。
==== 0012 Versus ====
对于输入的(x,y)，储存在数组a[x]=y中。最多能胜的场次就是a[1..n]的最长递增子序列的长度。
=== Group C ===
==== 0013 Battle: Dojo ====
建一个图，节点(x,y,k)表示在格子(x,y)中且时间模4余k。每个节点有最多四条边（上下左右）出去。边的权值为二元组(t,1)，t是走出去后需打的敌人数量，1是需耗费的时间，比较权值大小时敌人数量优先。则在这个图上求(xs,ys,0)到(xt,yt,0..3)的最短路即可。
==== 0014 Balloon ====
先二分答案。对于一个R，若两个气球：第i组的第a个和第j组的第b个之间的距离小于2*R，则说明它们俩不能同时选。也就是说，若选(i,a)，必须选(j,!b)；若选(j,b)，必须选(i,!a)。这就是一个2-SAT问题。按照若选x则必选y就连边的方式建有向图，求图的强连通分支，原答案能满足仅当所有的(i,0)和(i,1)都不在同一个分支里。
==== 0015 Kaguya's Game ====
只需求x与y同色时的树的染色数。从x到y的路径的染色数可用dp求。设路径长为i，则f[i]=g[i-1]; g[i]=f[i-1]*(C-1)+g[i-1]*(C-2)。最后的答案是f[i]*q[N-i]*C。
==== 0016 The Toy of Flandre Scarlet ====
设坐标和为奇数的点为奇点，反之为偶点。有解当且仅当奇点上数之和等于偶点上数之和。
==== 0017 Cipher Lock ====
可以分为单独的8段来求。对于每一段，要求的就是固定了首尾后的方案数。将每一位分为等于尾上的数和不等于尾上的数两种情况，两位就有四种情况。转移就是一个4x4的矩阵。最终的方案数就是矩阵的幂中对应于首到尾的一个元素。
==== 0018 Japanese Mahjong I ====
枚举需要的是什么牌。然后再枚举哪两个牌做Eyes，再递归地选三张牌做Meld这样判断是否是赢牌。
=== Group D ===
==== 0019 Social Net ====
首先求最大生成树。然后对于询问(x,y)，设m=lca(x,y)，则答案就是(x,m)段上的答案、(m,y)段上的答案、以及(m,y)段上的最大值减去(x,m)段上的最小值这三者中的最大值。这三者都是用倍增算法求的。需预处理的是pa[x][i]表示x向上走1<<i步是谁，mi[x][i]表示[x,pa[x][i])这一段中的最小值，ma[x][i]相应的最小值，up[x][i]表示[x,pa[x][i])这一段中从下往上的答案，dn[x][i]表示相应的从上往下的答案。
==== 0020 Diablo III ====
相当于两道题目。首先是求打每个boss需要多少血瓶，然后是求怎样在掉宝最多的前提下血瓶最少。设g[h][d][m]表示boss具有生命h、伤害d、自身的生命m时需耗费的血瓶，则dp一次就可求出所有boss的需要多少血瓶。（这里是由于boss的伤害<=10，故本质只有10种boss，减少了计算。）然后f[i][j]（是一个pair）表示打到第i个section有j个buff时的最优解，转移只需在每个boss处枚举打或不打即可。
==== 0021 Driving Helicopter I ====
只需求凸包，并沿着凸包的上沿走即可。
==== 0022 E - Cup ====
看懂麻烦的规则，然后按照规则模拟，没什么好说的。我觉得规则还是说的比较清晰的。
==== 0023 Wagon ====
相当于两道题。首先求字典序最小的最优摆放方案。然后求怎么运最优。对于第一问，可以先摆好一列wagon，然后从右往左依次插入storages，先插距离为1的，再插距离为2的⋯⋯用完为止。得到的就是字典序最小的最优方案。这样摆以后，实际上和两边距离相等的storage最多只有一个，枚举以下它运到哪边就好了。
==== 0024 Toy Blocks ====
首先用简单的单调队列预处理出l[i],r[i]，即一块block向左或向右推最远能倒到哪里。然后动态规划求f[i]，即前i块全推倒且第i块在最后一批倒最少用几次。求的时候f[i]=min(f[l[i]-1..f[i-1]])+1（即枚举在把i向左推倒前推哪些）。这一步用单调队列或sparse table都可做。然后用f[i-1]+1更新f[r[i]]。

dd_engi 崔添翼

13958103659 / 658659

tianyicui@gmail.com

Round 1

Group A

0001 Kitty's Game

显然途中的数肯定是K的约数，若将在场景i、分数j（j是K的约数）的情况抽象成一个点(i,j)，那么题目就是在有向无环图中求路径数。

0002 The Review Plan

容斥原理。2^M 地枚举出需满足的条件组合（有些条件组合可能存在冲突无法满足），根据条件数的奇偶性决定是加或减一个全排列数。

0003 Decode

给出的是一个异或运算的线性空间，先用高斯消元求出空间的基，然后即可求出任意元素是否在空间内。枚举改动了0、1、2、3位的情况，找到在空间内的字典序最小的解。

0004 Ribbon Gymnastics

设d[i][j]表示第i、第j两点的距离。r[i]表示第i点圆的半径。则要求满足形如r[i]+r[j]<=d[i][j]的六个方程的前提下最大化r[0]+r[1]+r[2]+r[3]。将方程分成三组两两相加可知最优解是min(d[0][1]+d[2][3],d[0][2]+d[1][3],d[0][3]+d[1][2])。

0005 Gao the Grid

若三角形的边界在一个(x,y)的矩形上，三角形的数量是有四种情况： a) 4 * (x - 2) * (y - 2) （一个点在角上，两个点在边上；b) 2 * (x * y - gcd(x-1,y-1) - 3) （两个点在对角上，另一个点不在边上或矩形内）；c) 2 * (x - 2) + 2 * (y - 2)（两个点在相邻角上，一个点在对边上）；d) 4 （三个点都在角上）。(n,m)的矩形中共有(n-x+1)*(n-y+1)个这样的矩形。枚举(x,y)从(1,1)到(n,m)并相加。

0006 Cut the Tree 2

枚举选哪个点，分割成的权值和就是它的儿子上的子树的权值和以及总权值和减去它自身子树的权值和，算出权值和的积，取最大的即可。需要用大数。

Group B

0007 Alice's present

给一个数列a[1..n]，每次询问一个区间a[i..j]内的数是否全部unique，如果不是，输出a[max(k | i<=k<=l<=j, a[k]==a[l]]。预处理p[1..n]，p[i]表示a[1..i]区间的答案。p[i]=max(p[i-1], max(j | j < i, a[j]==a[i]))。则a[i..j]的答案只需看p[j]是否小于i，如果不是输出a[p[j]]，否则满足unique条件。

0008 Bounty hunter

标准算法是贪心，但不好想，这个dp比较好想。f[i]表示在第i个城市时有有1金钱时最终最多能有多少金钱，g[i]表示在第i个城市时有1经验时最终最多能有多少金钱。转移是f[i] = max(f[i+1], 1 / A[i] * B[i] * f[i+1] + 1 / A[i] * g[i+1]); （也即不花钱和花钱两种情况）；g[i] = g[i+1] + B[i] * f[i+1]; 最终答案就是 f[0] * X + g[0] * Y。

0009 Guess a Function

可以按位求出g的反函数。故只需求h2(g(h1(x)))这样一个函数。若枚举h1的参数m1、s1，则可以通过数据求出m2、s2。因为h2(x) = x + s2（当h2(x)>x时）或 h2(x) = x + s2 - m2（当h2(x)

0010 Maze

对于每次给出的一列，先预处理出一个矩阵m[i][j]表示从第i行进能否从第j行出。这个矩阵的t次方就是整段从第i行进第j行出的方案数。将所有这些矩阵相乘，最后的结果就是矩阵的元素和。

0011 Paint Erased

对于每一个线段，算出与每一个矩形的交集，将交出的这些交集（线段）按照paint、erase的规则进行模拟，则可得到这个线段最后留下的长度。将所有线段留下的长度加起来即可。写起来有些麻烦。

0012 Versus

对于输入的(x,y)，储存在数组a[x]=y中。最多能胜的场次就是a[1..n]的最长递增子序列的长度。

Group C

0013 Battle: Dojo

建一个图，节点(x,y,k)表示在格子(x,y)中且时间模4余k。每个节点有最多四条边（上下左右）出去。边的权值为二元组(t,1)，t是走出去后需打的敌人数量，1是需耗费的时间，比较权值大小时敌人数量优先。则在这个图上求(xs,ys,0)到(xt,yt,0..3)的最短路即可。

0014 Balloon

先二分答案。对于一个R，若两个气球：第i组的第a个和第j组的第b个之间的距离小于2*R，则说明它们俩不能同时选。也就是说，若选(i,a)，必须选(j,!b)；若选(j,b)，必须选(i,!a)。这就是一个2-SAT问题。按照若选x则必选y就连边的方式建有向图，求图的强连通分支，原答案能满足仅当所有的(i,0)和(i,1)都不在同一个分支里。

0015 Kaguya's Game

只需求x与y同色时的树的染色数。从x到y的路径的染色数可用dp求。设路径长为i，则f[i]=g[i-1]; g[i]=f[i-1]*(C-1)+g[i-1]*(C-2)。最后的答案是f[i]*q[N-i]*C。

0016 The Toy of Flandre Scarlet

设坐标和为奇数的点为奇点，反之为偶点。有解当且仅当奇点上数之和等于偶点上数之和。

0017 Cipher Lock

可以分为单独的8段来求。对于每一段，要求的就是固定了首尾后的方案数。将每一位分为等于尾上的数和不等于尾上的数两种情况，两位就有四种情况。转移就是一个4x4的矩阵。最终的方案数就是矩阵的幂中对应于首到尾的一个元素。

0018 Japanese Mahjong I

枚举需要的是什么牌。然后再枚举哪两个牌做Eyes，再递归地选三张牌做Meld这样判断是否是赢牌。

Group D

0019 Social Net

首先求最大生成树。然后对于询问(x,y)，设m=lca(x,y)，则答案就是(x,m)段上的答案、(m,y)段上的答案、以及(m,y)段上的最大值减去(x,m)段上的最小值这三者中的最大值。这三者都是用倍增算法求的。需预处理的是pa[x][i]表示x向上走1<

0020 Diablo III

相当于两道题目。首先是求打每个boss需要多少血瓶，然后是求怎样在掉宝最多的前提下血瓶最少。设g[h][d][m]表示boss具有生命h、伤害d、自身的生命m时需耗费的血瓶，则dp一次就可求出所有boss的需要多少血瓶。（这里是由于boss的伤害<=10，故本质只有10种boss，减少了计算。）然后f[i][j]（是一个pair）表示打到第i个section有j个buff时的最优解，转移只需在每个boss处枚举打或不打即可。

0021 Driving Helicopter I

只需求凸包，并沿着凸包的上沿走即可。

0022 E - Cup

看懂麻烦的规则，然后按照规则模拟，没什么好说的。我觉得规则还是说的比较清晰的。

0023 Wagon

相当于两道题。首先求字典序最小的最优摆放方案。然后求怎么运最优。对于第一问，可以先摆好一列wagon，然后从右往左依次插入storages，先插距离为1的，再插距离为2的⋯⋯用完为止。得到的就是字典序最小的最优方案。这样摆以后，实际上和两边距离相等的storage最多只有一个，枚举以下它运到哪边就好了。

0024 Toy Blocks

首先用简单的单调队列预处理出l[i],r[i]，即一块block向左或向右推最远能倒到哪里。然后动态规划求f[i]，即前i块全推倒且第i块在最后一批倒最少用几次。求的时候f[i]=min(f[l[i]-1..f[i-1]])+1（即枚举在把i向左推倒前推哪些）。这一步用单调队列或sparse table都可做。然后用f[i-1]+1更新f[r[i]]。