team2012-C3
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
陈泽闽
QQ: 545258758
邮箱用的是qq邮箱= =！
[wiki:Flandre_Scarletsplay splay]
[wiki:Flandre_Scarletsuffixarray suffixarray]
解题报告
0001
给出一个n个点，m条边的图，每个点有一个分值p[i]，走到某个点，你的当前分值=lcm（当前分值，p[i]）,一开始你在1号点，问到达n号点的时候分值为k的方案数，注意每一步你的分数都必须改变。
注意到j的约数是根号n级别的，f[i][j]表示到达i节点，得分是p的第j小个约数的方案数，直接转移即可。
0002
有n天要复习n门课，有m个限制条件，第x天不能复习第y门课，问所有可行的方案数。
这题显然是容斥原理，注意要去重。
0003
给出一些数，问能否通过异或操作得到与目标数误差不超过3的数，误差为在二进制表示下，不同的位的个数。
先预处理出基底，枚举答案，判断是否可行。
0004
给出平面上4个圆的圆心坐标，求一种方案使得所有圆不想交且所有圆的半径总和最大。
一个简单的线性规划问题，列出所有的限制的式子后，发现可以推出两两分组，答案最小的那一组是可行的最大答案。
0005
给出一个n+1行，m+1列的格点图，问在图中选取3个点，使得它们能组成三角形的方案数。
一个组合数学的问题，三角形的个数=所有点中选3个点的方案数-3个点在同一直线上的方案数。
0006
给出一棵n个节点的树，每个点上都有1个权值，一颗子树的权值定义为它的所有节点的权值的和，现在要你砍掉一个节点，使得剩下的树的权值相乘最大。
预处理遍历一次树得出以i为根的子树的权值以后就能很容易的得出答案，因为每条边会被枚举两次，所以时间复杂度是O（n）的，要用高精度。
0007
给出一列数，询问一段区间里面是否有重复的数，如果有重复的，输出从右边开始数，第一个重复的数。
预处理出相同数字下一个的出现位置，用一些数据结构搞一搞就可以了= =！
0008
有一个赏金猎人要依次通过n个城市，在第i个城市，他可以用钱按当前城市的比率换成攻击力，然后再用当前的攻击乘以一个数赚钱，给出他初始的时候的攻击力和钱以及每个城市的兑换比率，问最后他最多能获
取多少钱。
用f1[i]表示当前有1点攻击力能在i这个城市以及后面的城市赚多少钱，f2[i]表示当前有1块钱能在i这个城市以及后面的城市赚多少钱，然后倒着dp一遍就可以了。
0009
g(x) = x^(x/2)
h1(x) = x / m1 * m1 + ( x + s1) % m1
h2(x) = x / m2 * m2 + ( x + s2) % m2
f(x) = g( h2( g( h1( g( x ) ) ) ) )
给出一堆x和f（x），要你求出这个函数的四个参数s1，s2，m1，m2。
枚举两个数，算出另外两个数（喂，说得很简单的样子！）。先要找出g（x）的反函数，剩下的就可以慢慢地推出来了！
0010
你在一个k*n的迷宫的左边，你现在要跑到迷宫的右边去，问方案总数。迷宫里面有3种方格，因为迷宫里面都是按段分布的，所以对于每一段，我们可以分开处理。
对于每一段，我们可以先预处理出dp的转移方程，然后加一个矩阵优化算出方案数，最后的时候把所有段连接起来就可以了。
0011
给出一条折线段，现在要擦去和涂上某些区域，问最后被涂上的线段的总长度。
判断线段和矩形的交，一条线段与一个矩形的交可以用两个向量的长度来表示一下。处理的时候可以先求出直线与竖直的两条边相交的一段，再求出直线与水平的两条边相交的一段，第三段则是线段自己本身，然
后三段求一下交集，就能得出两个点，后面就变成了一个覆盖的问题，对于水平的线段和竖直的线段，我们可以特判一下。
0012
给出两个长度为n的序列，每个序列都是1到n，给出第一个序列的x和第二个序列的y之间能相连了，问在没有线段相交的情况下，最多能有多少条线段相连。
解法就是一个类似最长不下降序列的dp。
0013
给出一个格子图，每个点可以是空格、障碍、或者是人，人是有目光长度的，如果你走到人的目光内，那么代价+1，每个人会随着时间转变自己的朝向，问从起点到终点的最少代价。
按时间拆点，然后最短路就可以了。
0014
一个三维空间里，你必须在n组气球里面选出n个气球来，每组只能选一个，所有气球的半径是统一的，问半径最长是多少。
二分答案，然后就变成了一个2-sat。
0015
给出一个n个节点的树，每个节点能染c种颜色，相邻的节点不能染相同的颜色，问在树上添加一条边后，可行的方案数会减少多少。
lca+一个简单的dp。
0016
给出一个L*W*H的立方体，每个格子里有一个数，每次可以将相邻的格子里的数同时加上或减去一个数，问最后能否使得所有的格子都变为0，相邻是有同一个面的两个格子。
将立方体的每一个格子黑白染色，两边数字的和相同的时候就可行，否则不可行。
0017
给出一个n个节点的多边形，多边形的每个点上有一个点对（x，y），一个多边形是合法，当且仅当所有相邻的点对至少有一个值是一样的，给出多边形上8个点的点对，问合法的方案数。
一个用矩阵优化的dp。
0018
麻将题，麻将里胡牌是要凑成4个面子和一个对子，现在给出你13张牌，问最后哪些牌能胡牌。
枚举剩下的一张，然后判断是否胡牌。
0019
前面说的就是要你做一次最大生成树= =！然后得到这棵树以后，有q个询问，询问从x节点到y节点的路径上，某两个节点的差值最大是多少，注意这个差值是有方向的，只能是后面的数-前面的数。
用倍增的思想处理一下整棵树，注意有顺着和反着两个方向，要分别处理。
0020
大菠萝3，就是你要依次经过一些精英怪和boss，你可以秒杀精英怪，没杀死一个精英怪，你的buff+1，buff的上限是5，当你有5个buff的时候，你打boss就会掉落东西，且打完后buff会消失。然后给出你自
己和所有boss的攻击力，hp上限。再给出，嗑药能补的血，问最后打出最多的东西最少要用多少药。
一个dp，用单调队列弄一下，然后打boss的时候再用一下记忆化搜索。
0021
直升飞机要飞过一段山脉，问到达终点最少要飞多远。
就是一个凸包……
0022
就是给出n只球队的对战情况，再给出一堆很复杂的比较方法，问最后所有球队的名次。
一个复杂的排序，注意净胜球可以是负的，咦，好像谁被黑了！
0023
你要给n个村庄分配m辆马车，每个村庄的人回去最近的有马车的村庄，现在要求分配后使得所有村庄的人走的路程和最小，在同样能达到和最小的方案里，选择字典序最小的方案。求出方案后，每个村庄都有一定
的货物，要求所有马车能装的货物最大的最小。
这题关键是要求出每辆马车所在的位置，这个可以转换思路，用插入村庄的思想得出每辆马车的位置。
0024
有n个玩具排成一排，每个玩具有一个高度，推倒一个玩具后会引发连锁，使得一堆玩具倒下，问手动最少推倒几个玩具，能使得所有玩具都被推倒。
先按x坐标排序，f[i]表示推倒（我喜欢这个词！！）前i个玩具所用的最少时间，然后我们预处理出每一个积木向左推最远能推到哪个积木、向右推最远能推到哪个积木，就可以用线段树来优化这个dp了。陈泽闽
QQ: 545258758
邮箱用的是qq邮箱= =！
解题报告
0001
给出一个n个点，m条边的图，每个点有一个分值p[i]，走到某个点，你的当前分值=lcm（当前分值，p[i]）,一开始你在1号点，问到达n号点的时候分值为k的方案数，注意每一步你的分数都必须改变。
注意到j的约数是根号n级别的，f[i][j]表示到达i节点，得分是p的第j小个约数的方案数，直接转移即可。
0002
有n天要复习n门课，有m个限制条件，第x天不能复习第y门课，问所有可行的方案数。
这题显然是容斥原理，注意要去重。
0003
给出一些数，问能否通过异或操作得到与目标数误差不超过3的数，误差为在二进制表示下，不同的位的个数。
先预处理出基底，枚举答案，判断是否可行。
0004
给出平面上4个圆的圆心坐标，求一种方案使得所有圆不想交且所有圆的半径总和最大。
一个简单的线性规划问题，列出所有的限制的式子后，发现可以推出两两分组，答案最小的那一组是可行的最大答案。
0005
给出一个n+1行，m+1列的格点图，问在图中选取3个点，使得它们能组成三角形的方案数。
一个组合数学的问题，三角形的个数=所有点中选3个点的方案数-3个点在同一直线上的方案数。
0006
给出一棵n个节点的树，每个点上都有1个权值，一颗子树的权值定义为它的所有节点的权值的和，现在要你砍掉一个节点，使得剩下的树的权值相乘最大。
预处理遍历一次树得出以i为根的子树的权值以后就能很容易的得出答案，因为每条边会被枚举两次，所以时间复杂度是O（n）的，要用高精度。
0007
给出一列数，询问一段区间里面是否有重复的数，如果有重复的，输出从右边开始数，第一个重复的数。
预处理出相同数字下一个的出现位置，用一些数据结构搞一搞就可以了= =！
0008
有一个赏金猎人要依次通过n个城市，在第i个城市，他可以用钱按当前城市的比率换成攻击力，然后再用当前的攻击乘以一个数赚钱，给出他初始的时候的攻击力和钱以及每个城市的兑换比率，问最后他最多能获
取多少钱。
用f1[i]表示当前有1点攻击力能在i这个城市以及后面的城市赚多少钱，f2[i]表示当前有1块钱能在i这个城市以及后面的城市赚多少钱，然后倒着dp一遍就可以了。
0009
g(x) = x^(x/2)
h1(x) = x / m1 * m1 + ( x + s1) % m1
h2(x) = x / m2 * m2 + ( x + s2) % m2
f(x) = g( h2( g( h1( g( x ) ) ) ) )
给出一堆x和f（x），要你求出这个函数的四个参数s1，s2，m1，m2。
枚举两个数，算出另外两个数（喂，说得很简单的样子！）。先要找出g（x）的反函数，剩下的就可以慢慢地推出来了！
0010
你在一个k*n的迷宫的左边，你现在要跑到迷宫的右边去，问方案总数。迷宫里面有3种方格，因为迷宫里面都是按段分布的，所以对于每一段，我们可以分开处理。
对于每一段，我们可以先预处理出dp的转移方程，然后加一个矩阵优化算出方案数，最后的时候把所有段连接起来就可以了。
0011
给出一条折线段，现在要擦去和涂上某些区域，问最后被涂上的线段的总长度。
判断线段和矩形的交，一条线段与一个矩形的交可以用两个向量的长度来表示一下。处理的时候可以先求出直线与竖直的两条边相交的一段，再求出直线与水平的两条边相交的一段，第三段则是线段自己本身，然
后三段求一下交集，就能得出两个点，后面就变成了一个覆盖的问题，对于水平的线段和竖直的线段，我们可以特判一下。
0012
给出两个长度为n的序列，每个序列都是1到n，给出第一个序列的x和第二个序列的y之间能相连了，问在没有线段相交的情况下，最多能有多少条线段相连。
解法就是一个类似最长不下降序列的dp。
0013
给出一个格子图，每个点可以是空格、障碍、或者是人，人是有目光长度的，如果你走到人的目光内，那么代价+1，每个人会随着时间转变自己的朝向，问从起点到终点的最少代价。
按时间拆点，然后最短路就可以了。
0014
一个三维空间里，你必须在n组气球里面选出n个气球来，每组只能选一个，所有气球的半径是统一的，问半径最长是多少。
二分答案，然后就变成了一个2-sat。
0015
给出一个n个节点的树，每个节点能染c种颜色，相邻的节点不能染相同的颜色，问在树上添加一条边后，可行的方案数会减少多少。
lca+一个简单的dp。
0016
给出一个L*W*H的立方体，每个格子里有一个数，每次可以将相邻的格子里的数同时加上或减去一个数，问最后能否使得所有的格子都变为0，相邻是有同一个面的两个格子。
将立方体的每一个格子黑白染色，两边数字的和相同的时候就可行，否则不可行。
0017
给出一个n个节点的多边形，多边形的每个点上有一个点对（x，y），一个多边形是合法，当且仅当所有相邻的点对至少有一个值是一样的，给出多边形上8个点的点对，问合法的方案数。
一个用矩阵优化的dp。
0018
麻将题，麻将里胡牌是要凑成4个面子和一个对子，现在给出你13张牌，问最后哪些牌能胡牌。
枚举剩下的一张，然后判断是否胡牌。
0019
前面说的就是要你做一次最大生成树= =！然后得到这棵树以后，有q个询问，询问从x节点到y节点的路径上，某两个节点的差值最大是多少，注意这个差值是有方向的，只能是后面的数-前面的数。
用倍增的思想处理一下整棵树，注意有顺着和反着两个方向，要分别处理。
0020
大菠萝3，就是你要依次经过一些精英怪和boss，你可以秒杀精英怪，没杀死一个精英怪，你的buff+1，buff的上限是5，当你有5个buff的时候，你打boss就会掉落东西，且打完后buff会消失。然后给出你自
己和所有boss的攻击力，hp上限。再给出，嗑药能补的血，问最后打出最多的东西最少要用多少药。
一个dp，用单调队列弄一下，然后打boss的时候再用一下记忆化搜索。
0021
直升飞机要飞过一段山脉，问到达终点最少要飞多远。
就是一个凸包……
0022
就是给出n只球队的对战情况，再给出一堆很复杂的比较方法，问最后所有球队的名次。
一个复杂的排序，注意净胜球可以是负的，咦，好像谁被黑了！
0023
你要给n个村庄分配m辆马车，每个村庄的人回去最近的有马车的村庄，现在要求分配后使得所有村庄的人走的路程和最小，在同样能达到和最小的方案里，选择字典序最小的方案。求出方案后，每个村庄都有一定
的货物，要求所有马车能装的货物最大的最小。
这题关键是要求出每辆马车所在的位置，这个可以转换思路，用插入村庄的思想得出每辆马车的位置。
0024
有n个玩具排成一排，每个玩具有一个高度，推倒一个玩具后会引发连锁，使得一堆玩具倒下，问手动最少推倒几个玩具，能使得所有玩具都被推倒。
先按x坐标排序，f[i]表示推倒（我喜欢这个词！！）前i个玩具所用的最少时间，然后我们预处理出每一个积木向左推最远能推到哪个积木、向右推最远能推到哪个积木，就可以用线段树来优化这个dp了。