team2012-F1

从 Trac 迁移的文章

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

原文章内容如下：

开坑

= 个人资料 =
王夏君

Email: {{{ sliver_kimi@126.com }}}

qq:309376287

= 解题报告 =

== Round 1 ==

=== 0001 Kitty's Game ===
题意我觉得我说不清，还是不说了。

显然如果一条路径上走到同一个点两次是非法的，因为lcm不会发生变化。于是这道题就没环了，可以用DP去做。

记f[i][j]为走到第i个点，当前lcm是j的方案数。注意到j当且仅当为k的约数时才会有意义，我们可以干脆剪掉不是k的约数的点。这样j就只有sqrt(200000)的级别了，就不会爆内存，可以直接做了。

另外土问学长们都是用什么写的，我用hash wa，用set也wa，暴力找要更新的点才能ac。。。（基本什么都没改啊喂）

=== 0004 Ribbon Gymnastics ===
就是给四个点，每个点为圆心作一个圆，要求圆与圆之间不能相交，求半径之和最大值。

{{{
A + B ≤ X[1]
A + C ≤ X[2]
A + D ≤ X[3]
B + C ≤ X[4]
B + D ≤ X[5]
C + D ≤ X[6]
}}}

于是就成了两个个if解决的事了。

=== 0002 The Review Plan ===

用n天复习n个章节，并给定m个限制：在某天不能复习某章节。问安排的方案数。

看上去就觉得是容斥题，但是范围好大不敢做。没想到就是直接暴力容斥 = =|||颠覆了我的三观啊！！！

注意(0)! = 1………………………………………………………………………………………………………………………………………………

=== 0003 Decode ===
给出k个n位的编码，每次询问一个编码，问它能否由给定的编码异或出来。异或的结果最多允许有三位与询问的编码不同。若能组成则输出相异数最小的且字典序最小的异或结果。

注意到C(30,0)+C(30,1)+C(30,2)+C(30,3)不是很大，我们可以枚举编码，再判断编码是否能由原来的编码组成。

这其实就是异或方程求解。首先我们把原来编码的一组基求出来（高斯消元），然后用这组基搞一下询问的编码。

对于询问的编码，从最高位开始往低位做。每次从基中找一个异或后能让当前最高位变零，且不会令最高位变大的向量异或当前的编码，逐步让编码变成0，若不能消成0则当前枚举的编码不合法。

=== 0005 Gao the Grid ===
在最大为1000*1000的网格中数三角形……

注意到任选三个点，只要不是三点共线，就可以构成一个三角形。于是只需要先算出任选三个点的方案数，减去三点共线的方案数即可。

算三点共线方案数其实挺简单。我们先讨论共线构成的线段斜率为正的情况。先默认(0,0)为线段的一端，枚举另一端(x,y)，那以当前两个点为端点的三点共线方案数为gcd(x,y)-1。然后将这条线段在合理的范围内平移一下就可以得出类似的线段的方案数了。对于斜率为负数的情况类似。而斜率为0和斜率不存在的情况就非常容易算出结果了。

=== 0006 Cut the Tree II ===
题意是说，给一棵有点权的树，现删掉一个点以及与之相关的所有边，这样树会被拆分成若干棵树。现在问删掉哪一个点，形成的价值最大。价值的定义是，每棵树的点权之和之积。

这题还算是挺简单的，就是一个类似树dp，每个节点记录以这个节点为根的子树的权值和，在dfs过程中更新一下答案即可。但是要注意题目中要用到高精度，而且时限卡得紧要压缩高精度位数。另外在dfs的时候也要注意不要乱开内存导致爆栈。

=== 0007 Alice's Present ===
摸你傻生日了，威震天要送礼物。威震天有N个人偶，每个人偶有一个编号，现在威震天每次选择一个区间，如果区间内有数字相同，则输出从右数起第一个出现相同的；如果没有数字相同，则输出"OK"

这题O(n)的解法还是听好想到的。但是我傻逼，看到这题第一眼就想一道叫做“数颜色”（这题我挺推荐做的……在八中上可以找到）的题目，就想到每个节点记录一下下一个相同编号的人偶的位置（没有下一个则记录为∞），插入线段树中，线段树维护区间中最大值（题目中没有修改操作可以这么干 = =|||）。每次询问一个区间[l,r]中比r大的且最靠右的节点。由于数据范围太仁慈，我线段树卡过去了……

=== 0008 Bounty Hunter ===
贪心神题什么的我最不会了。

题意就是有n个城市，以及初始金钱x和初始战斗力y。在每个城市可以用金钱提升战斗力，然后按当前战斗力获得金钱（提升战斗力发生在获得奖励前）。问按顺序走完n个城市后获得的最大收益。

（不会在这里插入数学符号压力好大T_T，记sigma(1,k,s)为s[1]+s[2]+....+s[k]……变量先用i后用j）

记p[i]为第i个点中战斗力的提升数值，则离开第s个点时，状态会是（先钱后战斗力）：

x - sigma(1,s,p[i]*a[i]) + sigma(1,s,b[i]) * y + sigma(1,s,p[i] * sigma(i,s,b[j])) , y + sigma(1,s,p[i])

然后金钱项就可以写成

x + sigma(1,s,p[i] * (sigma(i,s,b[j]) - a[i])) + sigma(1,s,b[i]) * y

于是对于一个城市，要么把钱全花掉用来提升战斗力，要么就不要提升战斗力。一个城市要提高战斗力的必要条件是(sigma(i,s,b[j]) - a[i]) > 0。

然后对于满足上述条件的城市，显然不一定会全部进行买进战斗力操作（会影响后面的点的p[i]的取值范围的囧）。于是下面我们来讨论该选择哪些点买战斗力。

首先由于我们一次必然用光钱，所以一个点的决策指挥影响到相邻的、下一个点，所以我们可以倒着做。

对于一个已确定的决策点j，以及一个待决策点i(i<j)  ，对于他们的金钱表达式相减一下，发现当中剩下的那坨变量是由sigma(i,n,b[l])-a[i]和sigma(j,n,b[l])-a[j]决定的，维护一下单调性找出决策点最后模拟一下即可。。。

=== 0009 Guess a Function ===
~~看题解，抄标程~~

这题神死了，不看题解我这辈子估计都捉不出来（我只会345678的四次方枚举我会乱说？）

设原式为y = g( h2( g( h1( g( x ) ) ) ) )

首先对于g(x)求它的反函数。设y = g(x)。x/2实质上是x >> 1。于是若已知y，我们可以确定x的最高位，从高位到低位逐步解开每一位的数字，并最终得到x，于是我们就找到了g(x)的反函数。原式则可写为

g^-1^(y) = h2(g(h1(g(x))))

对于h1，我们可以枚举s1,m1。设b[i] = g^-1^（y) , a[i] = g(h1(g(x)))

那么b[i] = h2(a[i])

最后找两组大小关系不同的a[i],b[i]确定s2,m2的值，并加以验证。


=== 0010 Maze ===
题意是给一个K*N的网格，其中相邻的很多列是相同的（可以被划分为M块），每个点分为只能转弯，只能直走，不能走，问从最右走到最左的方案数。

K比较小，这显然就是一个矩阵乘法。根据每一列的状态dfs一下构建递推矩阵，分块进行矩阵乘法即可。时限卡得比较紧（其实是标程太WS了），要注意mod运算不能太多否则慢到要死。

=== 0011 Paint Erased ===
T_T I can not solve the problem.

~~看题解，抄标程之二~~

计算一条线段上被矩形覆盖的长度有多少。

对于一条线段，先把它写成向量形式，然后计算一下它与各矩形之间的相交点。把初始区间[0,1]裂解成许多小区间（最多不过2000+1）个，用类似扫描线的方法做一遍即可。

=== 0012 Versus ===
我不知道题意是啥……好像是给定一些胜负关系然后出人要递增问能不能有超过一半的比赛胜利？反正看样例猜题意 = =|||||||

我是智障嘛，就按照第一个关键字优先第二关键字其次的顺序快排一下，然后用线段树去维护第二关键字……写完了才发现是lis。

=== 0013 Dojo ===
著名神题道馆之战（大雾 = =||||）。

就是给定一个网格图，上面有一些守卫，守卫每秒都会转动，一旦处于守卫的视野内就会开展战斗。问从起点出发到终点，在战斗次数最少的前提下最小步数是多少。

由于每个守卫的周期都是4，直接把图拆成四层，再求双属性最短路。验题时失误了坑了作者了T_T

=== 0014 Balloon ===
题意是给定一个三维立方体，以及若干组球（一组两个）。每组球只能选一个，球的中心必须要在立方体内，别的随意，但两球之间不能重叠（略废话）。现在每个球的半径都一样，问最大半径。
对于半径进行二分，然后2Sat判定。这题卡精度卡得相当奇葩。

=== 0015 Kaguya's Game ===
题意是说，给一棵树，然后用C种颜色给这棵树的节点上色，要求相邻节点的颜色不能一样。现在做若干次询问，每次在树上加一条边，问这么做方案数会减少多少。

首先注意到树的形态不影响染色方案数，都是C*（c-1) ^ (n-1)

然后不难发现加了一条边后，树就变成一个环伸出若干条树枝（貌似这玩意叫做环形外向树？好像ZJOI2008的骑士就是这个模型）这玩意的染色方案数就是环上染色数再乘上树枝染色数。。。设f[n,c]为点数为n的环染c种颜色的方案数，那么f[n,c] = c * (c-1)^(n-1)^ - f[n-1,c] (n>=3)。推导思路是先找出不考虑首尾是否相同时的方案数c * (c-1)^(n-1)^， 然后减去首尾相同的方案（f[n-1,c]，首尾相同合并一下，就变成了少一个点时的方案数。。。）
然后做一下lca就可以了。。

ps:土问192的机器跟我多大仇……我dfs序列+线段树维护的程序本机测比闽爷慢三倍不到，192上直接tle到飞起……

=== 0016 The Toy of Flandre Scarlet ===
给一个l*w*h的立方体，将他划分成好多个1*1*1的小立方体。每个小立方体上有一个数字。现在每次操作可以让相邻两个立方体同时加上或减去一个数。问能否经过若干次操作后让所有小立方体上的数字都变成0？

据说放到二维上是一个经典题。。。其实摆到三维上据说也差不多。。。

首先注意到，假设小立方体a与b相邻，b与c相邻。我们先让a,b同时减去x，再让b,c同时加上x。于是b数值没变，a的数值被“转移”到c上面了。于是可以得出算法：

对立方体的格子进行黑白染色，若黑立方体的数字之和等于白立方体的数字之和，则可以全变为0，否则不可以。

=== 0017 Cipher Lock ===
题意是说，给一个多边形，上面有n个点，每个点有两个属性值[1,P]，[1,Q]，相邻节点至少一个属性相同。现在要求在一些点属性值给定的前提下，求节点属性设置方案数。

利用“相邻节点属性有一个相同”这一条件，我们可以把问题变成，在一个K*S的棋盘上，从某点出发，每次走到同行同列的任意一个点上。求从一个点出发走N步后回到原点的方案数，当中8步一定要走到某些给定的点（有冲突的可以预处理掉，当然算法够健壮也可以直接处理掉）。不难发现（也可以人肉做几组观察）到棋盘上的点可以分成四种：起点，与起点同行不同列，与起点同列不同行，与起点不同列不同行。记走N步后走到点(x,y)的方案数为f(N,x,y)，不难发现，若(x1,y1)与(x2,y2)是同类点，则 f(N,x1,y1) == f(N,x2,y2)。这个性质可以用数学归纳法证明。

问题就变成了一个数列递推，按题目中给定的点将矩阵乘法分成八段去做即可。

=== 0018 Japanese Mahjoon I ===
就是给13张麻将牌，问再来哪张牌就能吃胡。

看上去挺吓人，不过还是很好做的……首先不难发现杠是坑人的，不用管。然后不难发现做对的花色的牌数量必定除3余2，别的都能整除3。

做法就是枚举最后一张牌，然后在适当的花色中枚举哪一张牌做眼，最后把剩下的12张牌判一下能否组成四组刻子或对子就可以了。有了上面那个剪枝这么做还是挺快的。

=== 0019 Social Net ===
题意是，先让你求一个最小生成树，然后再在最小生成树上进行操作：每个点有点权，每次询问给定两个点，问从第一个点走到第二个点的路径序列上，满足i<j中ai-aj的最大值。

其实就是POJ3728套个生成树。由于这题没有修改操作，倍增法做lca就可以解决了。记录一下一个点到它各祖先的路径上，点权的最小值、最大值、从下往上的最大差值、从上往下的最大差值（可以转化为从下往上的最小负差值……）

=== 0020 大菠萝3 ===
题意是，有n个关卡需要挑战，每个关卡中有精英怪或者boss。

对于精英怪，在打倒一个精英怪后会获得一个buff，buff最多叠加五层。与精英怪的战斗不需要作任何结算，直接推倒。

对于boss，在获得五层buff后可以挑战boss，也可以跳过它。boss战需要进行回合制模拟。

求打完n个关卡后能打倒的boss的最大值，同时求在这条件下需要消耗血瓶的最小值。


记f[i]为走到第i个关卡，打倒boss的最大值以及在这前提下消耗血瓶的最小值。

若i为精英怪关卡，直接f[i] = f[i-1]

若i为boss关卡，我们从中做另一个dp：

记录g[i][j][k]为当前玩家血量为i，boss血量为j，boss输出为k时打倒该boss的最少血瓶消耗。我们可以直接用记忆化搜索去搞它，注意喝血瓶的限制即可。维护一个队列找一下挑战当前boss需要从哪里开始划分buff。

=== 0021 Driving Helicopter I ===
就是一个凸包模板题……五十字啊五十字。

=== 0022 E-cup ===
就是给出一个足球小组赛中的比赛规则以及赛况，求本次小组赛结束后的最终排名。

递归搞排名，对着规则慢慢敲代码……看上去总觉得很容易超时。

=== 0023 Wagon ===
Wagon I和Wagon II都把我搞死了都……

贪心构造货车的最小字典序摆放方案，对于第二部分二分货车容量再进行验证。

=== 0024 Toy Block ===
数轴上有若干个木块，每个木块有一个高度。现在每次我们选择一个木块向左或向右把它推倒，推倒同时会产生骨牌效应使另一些骨牌倒下，问最少需要推多少次能让所有块都倒下。

看这个骨牌效应还是有点像图的模型的……不过扯不到图上。

基本做法是一个O(n*n)的dp。记l[i]，r[i]为木块i向左或者向右推倒的最远距离，记f[i]为将i以及i之前所有木块推倒的最少步数，那么我们有

f[i] = min (f[i] , f[l[i]-1] + 1)

更新完f[i]后我们再用f[i]+1更新f[l]，其中l∈[i+1,r[i+1]]

不难发现上述操作均可用线段树维护，我们只需要用线段树求区间最大值\最小值即可。

对于数据中横坐标相同的情况，我们可以贪心地只保留当中最高的那个木块。

开坑

个人资料

王夏君

Email: sliver_kimi@126.com

qq:309376287

解题报告

Round 1

0001 Kitty's Game

题意我觉得我说不清，还是不说了。

显然如果一条路径上走到同一个点两次是非法的，因为lcm不会发生变化。于是这道题就没环了，可以用DP去做。

记f[i][j]为走到第i个点，当前lcm是j的方案数。注意到j当且仅当为k的约数时才会有意义，我们可以干脆剪掉不是k的约数的点。这样j就只有sqrt(200000)的级别了，就不会爆内存，可以直接做了。

另外土问学长们都是用什么写的，我用hash wa，用set也wa，暴力找要更新的点才能ac。。。（基本什么都没改啊喂）

0004 Ribbon Gymnastics

就是给四个点，每个点为圆心作一个圆，要求圆与圆之间不能相交，求半径之和最大值。

A + B ≤ X[1]
A + C ≤ X[2]
A + D ≤ X[3]
B + C ≤ X[4]
B + D ≤ X[5]
C + D ≤ X[6]

于是就成了两个个if解决的事了。

0002 The Review Plan

用n天复习n个章节，并给定m个限制：在某天不能复习某章节。问安排的方案数。

看上去就觉得是容斥题，但是范围好大不敢做。没想到就是直接暴力容斥 = =|||颠覆了我的三观啊！！！

注意(0)! = 1………………………………………………………………………………………………………………………………………………

0003 Decode

给出k个n位的编码，每次询问一个编码，问它能否由给定的编码异或出来。异或的结果最多允许有三位与询问的编码不同。若能组成则输出相异数最小的且字典序最小的异或结果。

注意到C(30,0)+C(30,1)+C(30,2)+C(30,3)不是很大，我们可以枚举编码，再判断编码是否能由原来的编码组成。

这其实就是异或方程求解。首先我们把原来编码的一组基求出来（高斯消元），然后用这组基搞一下询问的编码。

对于询问的编码，从最高位开始往低位做。每次从基中找一个异或后能让当前最高位变零，且不会令最高位变大的向量异或当前的编码，逐步让编码变成0，若不能消成0则当前枚举的编码不合法。

0005 Gao the Grid

在最大为1000*1000的网格中数三角形……

注意到任选三个点，只要不是三点共线，就可以构成一个三角形。于是只需要先算出任选三个点的方案数，减去三点共线的方案数即可。

算三点共线方案数其实挺简单。我们先讨论共线构成的线段斜率为正的情况。先默认(0,0)为线段的一端，枚举另一端(x,y)，那以当前两个点为端点的三点共线方案数为gcd(x,y)-1。然后将这条线段在合理的范围内平移一下就可以得出类似的线段的方案数了。对于斜率为负数的情况类似。而斜率为0和斜率不存在的情况就非常容易算出结果了。

0006 Cut the Tree II

题意是说，给一棵有点权的树，现删掉一个点以及与之相关的所有边，这样树会被拆分成若干棵树。现在问删掉哪一个点，形成的价值最大。价值的定义是，每棵树的点权之和之积。

这题还算是挺简单的，就是一个类似树dp，每个节点记录以这个节点为根的子树的权值和，在dfs过程中更新一下答案即可。但是要注意题目中要用到高精度，而且时限卡得紧要压缩高精度位数。另外在dfs的时候也要注意不要乱开内存导致爆栈。

0007 Alice's Present

摸你傻生日了，威震天要送礼物。威震天有N个人偶，每个人偶有一个编号，现在威震天每次选择一个区间，如果区间内有数字相同，则输出从右数起第一个出现相同的；如果没有数字相同，则输出"OK"

这题O(n)的解法还是听好想到的。但是我傻逼，看到这题第一眼就想一道叫做“数颜色”（这题我挺推荐做的……在八中上可以找到）的题目，就想到每个节点记录一下下一个相同编号的人偶的位置（没有下一个则记录为∞），插入线段树中，线段树维护区间中最大值（题目中没有修改操作可以这么干 = =|||）。每次询问一个区间[l,r]中比r大的且最靠右的节点。由于数据范围太仁慈，我线段树卡过去了……

0008 Bounty Hunter

贪心神题什么的我最不会了。

题意就是有n个城市，以及初始金钱x和初始战斗力y。在每个城市可以用金钱提升战斗力，然后按当前战斗力获得金钱（提升战斗力发生在获得奖励前）。问按顺序走完n个城市后获得的最大收益。

（不会在这里插入数学符号压力好大T_T，记sigma(1,k,s)为s[1]+s[2]+....+s[k]……变量先用i后用j）

记p[i]为第i个点中战斗力的提升数值，则离开第s个点时，状态会是（先钱后战斗力）：

x - sigma(1,s,p[i]*a[i]) + sigma(1,s,b[i]) * y + sigma(1,s,p[i] * sigma(i,s,b[j])) , y + sigma(1,s,p[i])

然后金钱项就可以写成

x + sigma(1,s,p[i] * (sigma(i,s,b[j]) - a[i])) + sigma(1,s,b[i]) * y

于是对于一个城市，要么把钱全花掉用来提升战斗力，要么就不要提升战斗力。一个城市要提高战斗力的必要条件是(sigma(i,s,b[j]) - a[i]) > 0。

然后对于满足上述条件的城市，显然不一定会全部进行买进战斗力操作（会影响后面的点的p[i]的取值范围的囧）。于是下面我们来讨论该选择哪些点买战斗力。

首先由于我们一次必然用光钱，所以一个点的决策指挥影响到相邻的、下一个点，所以我们可以倒着做。

对于一个已确定的决策点j，以及一个待决策点i(i

0009 Guess a Function

看题解，抄标程

这题神死了，不看题解我这辈子估计都捉不出来（我只会345678的四次方枚举我会乱说？）

设原式为y = g( h2( g( h1( g( x ) ) ) ) )

首先对于g(x)求它的反函数。设y = g(x)。x/2实质上是x >> 1。于是若已知y，我们可以确定x的最高位，从高位到低位逐步解开每一位的数字，并最终得到x，于是我们就找到了g(x)的反函数。原式则可写为

g^-1(y) = h2(g(h1(g(x))))

对于h1，我们可以枚举s1,m1。设b[i] = g^-1（y) , a[i] = g(h1(g(x)))

那么b[i] = h2(a[i])

最后找两组大小关系不同的a[i],b[i]确定s2,m2的值，并加以验证。

0010 Maze

题意是给一个K*N的网格，其中相邻的很多列是相同的（可以被划分为M块），每个点分为只能转弯，只能直走，不能走，问从最右走到最左的方案数。

K比较小，这显然就是一个矩阵乘法。根据每一列的状态dfs一下构建递推矩阵，分块进行矩阵乘法即可。时限卡得比较紧（其实是标程太WS了），要注意mod运算不能太多否则慢到要死。

0011 Paint Erased

T_T I can not solve the problem.

看题解，抄标程之二

计算一条线段上被矩形覆盖的长度有多少。

对于一条线段，先把它写成向量形式，然后计算一下它与各矩形之间的相交点。把初始区间[0,1]裂解成许多小区间（最多不过2000+1）个，用类似扫描线的方法做一遍即可。

0012 Versus

我不知道题意是啥……好像是给定一些胜负关系然后出人要递增问能不能有超过一半的比赛胜利？反正看样例猜题意 = =|||||||

我是智障嘛，就按照第一个关键字优先第二关键字其次的顺序快排一下，然后用线段树去维护第二关键字……写完了才发现是lis。

0013 Dojo

著名神题道馆之战（大雾 = =||||）。

就是给定一个网格图，上面有一些守卫，守卫每秒都会转动，一旦处于守卫的视野内就会开展战斗。问从起点出发到终点，在战斗次数最少的前提下最小步数是多少。

由于每个守卫的周期都是4，直接把图拆成四层，再求双属性最短路。验题时失误了坑了作者了T_T

0014 Balloon

题意是给定一个三维立方体，以及若干组球（一组两个）。每组球只能选一个，球的中心必须要在立方体内，别的随意，但两球之间不能重叠（略废话）。现在每个球的半径都一样，问最大半径。

对于半径进行二分，然后2Sat判定。这题卡精度卡得相当奇葩。

0015 Kaguya's Game

题意是说，给一棵树，然后用C种颜色给这棵树的节点上色，要求相邻节点的颜色不能一样。现在做若干次询问，每次在树上加一条边，问这么做方案数会减少多少。

首先注意到树的形态不影响染色方案数，都是C*（c-1) ^ (n-1)

然后不难发现加了一条边后，树就变成一个环伸出若干条树枝（貌似这玩意叫做环形外向树？好像ZJOI2008的骑士就是这个模型）这玩意的染色方案数就是环上染色数再乘上树枝染色数。。。设f[n,c]为点数为n的环染c种颜色的方案数，那么f[n,c] = c * (c-1)^(n-1) - f[n-1,c] (n>=3)。推导思路是先找出不考虑首尾是否相同时的方案数c * (c-1)^(n-1)， 然后减去首尾相同的方案（f[n-1,c]，首尾相同合并一下，就变成了少一个点时的方案数。。。）

然后做一下lca就可以了。。

ps:土问192的机器跟我多大仇……我dfs序列+线段树维护的程序本机测比闽爷慢三倍不到，192上直接tle到飞起……

0016 The Toy of Flandre Scarlet

给一个l*w*h的立方体，将他划分成好多个1*1*1的小立方体。每个小立方体上有一个数字。现在每次操作可以让相邻两个立方体同时加上或减去一个数。问能否经过若干次操作后让所有小立方体上的数字都变成0？

据说放到二维上是一个经典题。。。其实摆到三维上据说也差不多。。。

首先注意到，假设小立方体a与b相邻，b与c相邻。我们先让a,b同时减去x，再让b,c同时加上x。于是b数值没变，a的数值被“转移”到c上面了。于是可以得出算法：

对立方体的格子进行黑白染色，若黑立方体的数字之和等于白立方体的数字之和，则可以全变为0，否则不可以。

0017 Cipher Lock

题意是说，给一个多边形，上面有n个点，每个点有两个属性值[1,P]，[1,Q]，相邻节点至少一个属性相同。现在要求在一些点属性值给定的前提下，求节点属性设置方案数。

利用“相邻节点属性有一个相同”这一条件，我们可以把问题变成，在一个K*S的棋盘上，从某点出发，每次走到同行同列的任意一个点上。求从一个点出发走N步后回到原点的方案数，当中8步一定要走到某些给定的点（有冲突的可以预处理掉，当然算法够健壮也可以直接处理掉）。不难发现（也可以人肉做几组观察）到棋盘上的点可以分成四种：起点，与起点同行不同列，与起点同列不同行，与起点不同列不同行。记走N步后走到点(x,y)的方案数为f(N,x,y)，不难发现，若(x1,y1)与(x2,y2)是同类点，则 f(N,x1,y1) == f(N,x2,y2)。这个性质可以用数学归纳法证明。

问题就变成了一个数列递推，按题目中给定的点将矩阵乘法分成八段去做即可。

0018 Japanese Mahjoon I

就是给13张麻将牌，问再来哪张牌就能吃胡。

看上去挺吓人，不过还是很好做的……首先不难发现杠是坑人的，不用管。然后不难发现做对的花色的牌数量必定除3余2，别的都能整除3。

做法就是枚举最后一张牌，然后在适当的花色中枚举哪一张牌做眼，最后把剩下的12张牌判一下能否组成四组刻子或对子就可以了。有了上面那个剪枝这么做还是挺快的。

0019 Social Net

题意是，先让你求一个最小生成树，然后再在最小生成树上进行操作：每个点有点权，每次询问给定两个点，问从第一个点走到第二个点的路径序列上，满足i

其实就是POJ3728套个生成树。由于这题没有修改操作，倍增法做lca就可以解决了。记录一下一个点到它各祖先的路径上，点权的最小值、最大值、从下往上的最大差值、从上往下的最大差值（可以转化为从下往上的最小负差值……）

0020 大菠萝3

题意是，有n个关卡需要挑战，每个关卡中有精英怪或者boss。

对于精英怪，在打倒一个精英怪后会获得一个buff，buff最多叠加五层。与精英怪的战斗不需要作任何结算，直接推倒。

对于boss，在获得五层buff后可以挑战boss，也可以跳过它。boss战需要进行回合制模拟。

求打完n个关卡后能打倒的boss的最大值，同时求在这条件下需要消耗血瓶的最小值。

记f[i]为走到第i个关卡，打倒boss的最大值以及在这前提下消耗血瓶的最小值。

若i为精英怪关卡，直接f[i] = f[i-1]

若i为boss关卡，我们从中做另一个dp：

记录g[i][j][k]为当前玩家血量为i，boss血量为j，boss输出为k时打倒该boss的最少血瓶消耗。我们可以直接用记忆化搜索去搞它，注意喝血瓶的限制即可。维护一个队列找一下挑战当前boss需要从哪里开始划分buff。

0021 Driving Helicopter I

就是一个凸包模板题……五十字啊五十字。

0022 E-cup

就是给出一个足球小组赛中的比赛规则以及赛况，求本次小组赛结束后的最终排名。

递归搞排名，对着规则慢慢敲代码……看上去总觉得很容易超时。

0023 Wagon

Wagon I和Wagon II都把我搞死了都……

贪心构造货车的最小字典序摆放方案，对于第二部分二分货车容量再进行验证。

0024 Toy Block

数轴上有若干个木块，每个木块有一个高度。现在每次我们选择一个木块向左或向右把它推倒，推倒同时会产生骨牌效应使另一些骨牌倒下，问最少需要推多少次能让所有块都倒下。

看这个骨牌效应还是有点像图的模型的……不过扯不到图上。

基本做法是一个O(n*n)的dp。记l[i]，r[i]为木块i向左或者向右推倒的最远距离，记f[i]为将i以及i之前所有木块推倒的最少步数，那么我们有

f[i] = min (f[i] , f[l[i]-1] + 1)

更新完f[i]后我们再用f[i]+1更新f[l]，其中l∈[i+1,r[i+1]]

不难发现上述操作均可用线段树维护，我们只需要用线段树求区间最大值\最小值即可。

对于数据中横坐标相同的情况，我们可以贪心地只保留当中最高的那个木块。

附加文件

• module_9.18.rar by akalm