team2012-E3
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
姓名：唐雅洁
ID： Kacey_T
邮箱：tyj_11@163.com
电话: 15267036179
**Contest 1**
0001 Kitty's Game
有n 个点，m 条有向边，每个点的权值为pi。求从1到n，路径上各点权值的最小公倍数为k的方案数。并且在路径上每走一步，最小公倍数的值都必须增加。
用动态规划求解，F[i][j]表示到第i个点时，最小公倍数的值为j的方案数，转移为F[i][j] = sum(F[k][x])，满足从k到i有边且lcm(x , pi) = j。因为最小公倍数最多可达到10^6，所以需要将可能达到的值
先预处理出来，降低动归的复杂度。
0002 Review Plan
有n本书，要求每天读完一本书，但是有m个限制条件：在第Di天时不能读完Ci这本书。求合法读书顺序的方案总数。
比较裸的容斥原理，要注意限制条件可能重复的trick。
0003 Decode
给出k个n位的编码，m次询问判断能否选取一些编码异或产生所要求的编码，并且最多可有3个错误位。若有则输出字典序最小的编码。
线性空间的基可以表示出空间内任意元素。所以对k个编码消元，最多剩下n个的编码，每一位都有一个代表元。对每一次询问，先枚举错误位数和位置，即确定可能解的编码，再DFS一位一位判断是否可行。
0004 Ribbon Gymnastics
给出四个点，以四个点为圆心构造四个两两不相交的圆，求四个圆半径之和的最大值。
画图可推出只有三种情况。
0005 Gao the Grid
n*m的网格，求三个格点构成三角形的总方案数。
直接计算太复杂，所以可以用总方案数-不合法方案数来求解。不合法的情况就是三点共线。枚举三点共线的线段所占格子的长x和宽y，然后在这个区域内共线的情况总共有gcd(x,y)-1种，所以可以平方级枚举
统计不合法方案数。
0006 Cut the Tree 2
给一棵树，树的权值为子树所有权值之和。现在可以选一个点，所得价值为以它为根的情况下，它的所有子树权值之积。问选哪个点得到的价值最大。
DFS遍历求子树权值之和，再枚举所选的点计算价值。要注意高精度处理大数。
**Contest 2**
0007 Alice's present
一行上有的n个数，m次查询，每次询问[Li,Ri]区间内最靠右的第二次出现了的数字是什么。
首先从左往右扫一遍，记录下每个数字上一次出现的位置。然后离线处理查询，按照右端点Ri排序，不断更新最优值即可。
0008 Bounty hunter
有n个城市，每个城市提升1攻击力需花费ai金钱,提升量可以为小数。离开城市时可获得当前攻击力*bi的收益。初始时有x0的金钱及y0的攻击力。
很有趣的贪心题，ym猛犸学长。倒着推，首先显然如果要在某个城市购买攻击力，一定是将钱全部花完。列出表达式可以发现，在第i天是否购买攻击力，取决于ai与sum(bi~bn)的大小。假设已经觉得在第j天
购买攻击力，则在第i天时(i<j)，若购买攻击力的的收益+后面的收益>不在第i天购买+后面的收益，则在第i天购买攻击力。
0009 Guess a Function
格雷码的反函数。
原式可以改写成g'(f(x))=h2(g(h1(g(x))))，然后我枚举m1和s1，可以得到g(h1(g(x)))的值p，然后h2(p)可由两种情况确定，现当p%m2+s2<m2时，h2(p)=p+s2,否则h2(p)=p+s2-m2。求出m1,s1,m2,s2后
问题也就解决了。
0010 Maze
k*n的网格，三种类型的格子，旋转方向任意。m组格子，每一组中的格子类型是相同的。求从左边缘到达右边缘的总方案数。
显然用动态规划求解，枚举不同的情况即可，转移方程很容易推。另外每一组组内可以用矩阵进行加速。总是WA的原因是矩阵写错了一个变量。
0011 Paint Erased
给出一些矩形进行插入和删除，最后求一条折线段在插入区域内的长度。
看了prowindy学长的报告。首先求出每一个矩形和每一个线段的交（用0~1表示），然后把线段离散化，用set维护。
0012 Versus
给出n对数，求满足(xj>xi,yj>yi)(j>i)的个数是否大于n的一半。
比较裸的最长上升子序列。nlogn级的算法。
**Contest 3**
0013 Battle: Dojo
题意比较长，偷个懒不再描述一遍。这道题是典型的格子题求最优解。
BFS求解。先预处理出mod4的不同情况下每个defender的朝向和不能够到的点。注意在时刻0也是会遭受攻击的。这种题目主要是考验人的细心程度。
0014 Balloon
n对圆心坐标，每一组恰好选出一个圆，确定半径，使得它们互不相交。求最大半径为多少。
比较裸的2-SAT问题。将每个圆拆成两个点，分别表示取与不取，在有条件i则必有条件j时，从i到j建立一条有向边。
0015 Kaguya's Game
给出一棵树，c种颜色，要求给每个结点染色，并且相邻两结点不能同色。m次询问若在结点x和结点y之间加一条边，染色方案会减少多少。
单棵树的染色方案数为(c-1)^n，从上往下染色即可推出。而加上一条边之后，原本的一棵树变成了一个环+环上某个结点生出的一颗树。统计环上的方案数可推出公式Fi=Fi-1*(c-2)+Fi-2*(c-1)。最后环与树
的方案数相乘即可。求解过程中需要用到LCA算法。
0016 The Toy of Flandre Scarlet
l*w*h的立方格子，每个格子有一个值。每次操作可以任选相邻两个格子同时加上或减去一个数，不限操作次数。问是否能够将所有格子上的数都变为0。
比较典型的黑白染色问题。每一次选定一黑一白同时加减，可以套用网络流模型求解，从黑格子往白格子建边。若满流则有解，否则无解。
PS：貌似就是判断奇偶性的问题，弄复杂了。。。
0017 Cipher Lock
给出一个n个点构成的环，每个点有两个值，要求保证相邻两个点至少有一个值是一样的。给8个点的属性值，求剩下的点有多少种合法方案。
比较明显的矩阵递推题，加上限制条件之后，对被分成八段的环，顺序扫一遍。对于每个点有4种状态，值1与右端点相同\值1与右端点相同\值1与值2都与右端点相同\都不相同。于是可以推出4*4的转移矩阵，
每一段的初始状态是确定的。
0018 Japanese Mahjong I
给出13张牌，问加上哪些牌可以按照规则胡。
枚举将，然后DFS判断即可。
**Contest 4**
0019 Social Net
n个点，m条边，每个点有一个权值ci。先求最大生成树，然后在这棵树上，有q次查询，每次查询从结点x到结点y的路径上cj-ci的最大值(j出现在i之后）。
kruskal求最大生成树，然后LCA查询。倍增维护从结点x，向根走2^i步这段路径中的最大值、最小值、从下至上与从下至上的cy-cx的最大值。最后分两种情况，在同一段/在不同段考虑最优值。同一段的随着
DFS倍增维护已处理出，在不同段的线性扫一遍即可。
0020 Diablo III
题目规则不一一描述。大意是打死一定量的小兵就可以打boss，问在满足规则下最多能打死几个boss，在此基础上所喝药水最少。
打单个boss的过程可以先用动归枚举出来所有情况，F[i][j][k]表示当前人血量为i，boss血量为j，boss攻击力为k的情况下所喝最少要水量。外层的动归则是以第x个地图作为状态量，转移是在该地图打或者
不打boss，用最近的满足条件的地图转移即可(队列维护）。
0021 Driving Helicopter I
裸凸包。。。。。
0022 E - Cup
n个队进行单循环赛，给出每场比赛的比分和世界排名。按照给定规则求小组最终排名。
按照题目进行递归的模拟即可。
0023 Wagon
在水平轴上1~n的整点中取m个点放仓库，使得左右点到仓库距离之和最小。并且要求字典序最小的解。然后每个点有一个货物量pi，需要送到离它最近的仓库，如果有两个则任选一个。求最小仓库容量。
题意不太好懂，它要求的是首先固定住仓库的位置。第一步用贪心模拟，确定仓库的位置。然后再二分答案+贪心判定。
0024 Toy Blocks
给出n个木块，每个木块有个坐标xi，高度hi。可以讲木块向左或向右推倒，产生类似多米诺骨牌的效果。问至少推倒几块可以全部推倒。
首先用栈处理出每个木块向左或者向右能够推倒的最远距离lefti和righti。然后再动态规划求解。f[i]表示1-i个骨牌全被推倒并且第i个向左倒最少推几个，g[i]表示1-i个骨牌全被推倒并且第i个向右倒最少
推几个。转移时，平方级的枚举很好想，但是复杂度太高，所以我们需要用到数据结构来维护。用线段树来维护最小值。最后的ans=min(f[n],g[n])。姓名：唐雅洁
ID： Kacey_T
邮箱：tyj_11@163.com
电话: 15267036179
**Contest 1**
0001 Kitty's Game
有n 个点，m 条有向边，每个点的权值为pi。求从1到n，路径上各点权值的最小公倍数为k的方案数。并且在路径上每走一步，最小公倍数的值都必须增加。
用动态规划求解，F[i][j]表示到第i个点时，最小公倍数的值为j的方案数，转移为F[i][j] = sum(F[k][x])，满足从k到i有边且lcm(x , pi) = j。因为最小公倍数最多可达到10^6，所以需要将可能达到的值
先预处理出来，降低动归的复杂度。
0002 Review Plan
有n本书，要求每天读完一本书，但是有m个限制条件：在第Di天时不能读完Ci这本书。求合法读书顺序的方案总数。
比较裸的容斥原理，要注意限制条件可能重复的trick。
0003 Decode
给出k个n位的编码，m次询问判断能否选取一些编码异或产生所要求的编码，并且最多可有3个错误位。若有则输出字典序最小的编码。
线性空间的基可以表示出空间内任意元素。所以对k个编码消元，最多剩下n个的编码，每一位都有一个代表元。对每一次询问，先枚举错误位数和位置，即确定可能解的编码，再DFS一位一位判断是否可行。
0004 Ribbon Gymnastics
给出四个点，以四个点为圆心构造四个两两不相交的圆，求四个圆半径之和的最大值。
画图可推出只有三种情况。
0005 Gao the Grid
n*m的网格，求三个格点构成三角形的总方案数。
直接计算太复杂，所以可以用总方案数-不合法方案数来求解。不合法的情况就是三点共线。枚举三点共线的线段所占格子的长x和宽y，然后在这个区域内共线的情况总共有gcd(x,y)-1种，所以可以平方级枚举
统计不合法方案数。
0006 Cut the Tree 2
给一棵树，树的权值为子树所有权值之和。现在可以选一个点，所得价值为以它为根的情况下，它的所有子树权值之积。问选哪个点得到的价值最大。
DFS遍历求子树权值之和，再枚举所选的点计算价值。要注意高精度处理大数。
**Contest 2**
0007 Alice's present
一行上有的n个数，m次查询，每次询问[Li,Ri]区间内最靠右的第二次出现了的数字是什么。
首先从左往右扫一遍，记录下每个数字上一次出现的位置。然后离线处理查询，按照右端点Ri排序，不断更新最优值即可。
0008 Bounty hunter
有n个城市，每个城市提升1攻击力需花费ai金钱,提升量可以为小数。离开城市时可获得当前攻击力*bi的收益。初始时有x0的金钱及y0的攻击力。
很有趣的贪心题，ym猛犸学长。倒着推，首先显然如果要在某个城市购买攻击力，一定是将钱全部花完。列出表达式可以发现，在第i天是否购买攻击力，取决于ai与sum(bi~bn)的大小。假设已经觉得在第j天
购买攻击力，则在第i天时(i
0009 Guess a Function
格雷码的反函数。
原式可以改写成g'(f(x))=h2(g(h1(g(x))))，然后我枚举m1和s1，可以得到g(h1(g(x)))的值p，然后h2(p)可由两种情况确定，现当p%m2+s2 问题也就解决了。 0010 Maze k*n的网格，三种类型的格子，旋转方向任意。m组格子，每一组中的格子类型是相同的。求从左边缘到达右边缘的总方案数。 显然用动态规划求解，枚举不同的情况即可，转移方程很容易推。另外每一组组内可以用矩阵进行加速。总是WA的原因是矩阵写错了一个变量。 0011 Paint Erased 给出一些矩形进行插入和删除，最后求一条折线段在插入区域内的长度。 看了prowindy学长的报告。首先求出每一个矩形和每一个线段的交（用0~1表示），然后把线段离散化，用set维护。 0012 Versus 给出n对数，求满足(xj>xi,yj>yi)(j>i)的个数是否大于n的一半。 比较裸的最长上升子序列。nlogn级的算法。 **Contest 3** 0013 Battle: Dojo 题意比较长，偷个懒不再描述一遍。这道题是典型的格子题求最优解。 BFS求解。先预处理出mod4的不同情况下每个defender的朝向和不能够到的点。注意在时刻0也是会遭受攻击的。这种题目主要是考验人的细心程度。 0014 Balloon n对圆心坐标，每一组恰好选出一个圆，确定半径，使得它们互不相交。求最大半径为多少。 比较裸的2-SAT问题。将每个圆拆成两个点，分别表示取与不取，在有条件i则必有条件j时，从i到j建立一条有向边。 0015 Kaguya's Game 给出一棵树，c种颜色，要求给每个结点染色，并且相邻两结点不能同色。m次询问若在结点x和结点y之间加一条边，染色方案会减少多少。 单棵树的染色方案数为(c-1)^n，从上往下染色即可推出。而加上一条边之后，原本的一棵树变成了一个环+环上某个结点生出的一颗树。统计环上的方案数可推出公式Fi=Fi-1*(c-2)+Fi-2*(c-1)。最后环与树 的方案数相乘即可。求解过程中需要用到LCA算法。 0016 The Toy of Flandre Scarlet l*w*h的立方格子，每个格子有一个值。每次操作可以任选相邻两个格子同时加上或减去一个数，不限操作次数。问是否能够将所有格子上的数都变为0。 比较典型的黑白染色问题。每一次选定一黑一白同时加减，可以套用网络流模型求解，从黑格子往白格子建边。若满流则有解，否则无解。 PS：貌似就是判断奇偶性的问题，弄复杂了。。。 0017 Cipher Lock 给出一个n个点构成的环，每个点有两个值，要求保证相邻两个点至少有一个值是一样的。给8个点的属性值，求剩下的点有多少种合法方案。 比较明显的矩阵递推题，加上限制条件之后，对被分成八段的环，顺序扫一遍。对于每个点有4种状态，值1与右端点相同\值1与右端点相同\值1与值2都与右端点相同\都不相同。于是可以推出4*4的转移矩阵， 每一段的初始状态是确定的。 0018 Japanese Mahjong I 给出13张牌，问加上哪些牌可以按照规则胡。 枚举将，然后DFS判断即可。 **Contest 4** 0019 Social Net n个点，m条边，每个点有一个权值ci。先求最大生成树，然后在这棵树上，有q次查询，每次查询从结点x到结点y的路径上cj-ci的最大值(j出现在i之后）。 kruskal求最大生成树，然后LCA查询。倍增维护从结点x，向根走2^i步这段路径中的最大值、最小值、从下至上与从下至上的cy-cx的最大值。最后分两种情况，在同一段/在不同段考虑最优值。同一段的随着 DFS倍增维护已处理出，在不同段的线性扫一遍即可。 0020 Diablo III 题目规则不一一描述。大意是打死一定量的小兵就可以打boss，问在满足规则下最多能打死几个boss，在此基础上所喝药水最少。 打单个boss的过程可以先用动归枚举出来所有情况，F[i][j][k]表示当前人血量为i，boss血量为j，boss攻击力为k的情况下所喝最少要水量。外层的动归则是以第x个地图作为状态量，转移是在该地图打或者 不打boss，用最近的满足条件的地图转移即可(队列维护）。 0021 Driving Helicopter I 裸凸包。。。。。 0022 E - Cup n个队进行单循环赛，给出每场比赛的比分和世界排名。按照给定规则求小组最终排名。 按照题目进行递归的模拟即可。 0023 Wagon 在水平轴上1~n的整点中取m个点放仓库，使得左右点到仓库距离之和最小。并且要求字典序最小的解。然后每个点有一个货物量pi，需要送到离它最近的仓库，如果有两个则任选一个。求最小仓库容量。 题意不太好懂，它要求的是首先固定住仓库的位置。第一步用贪心模拟，确定仓库的位置。然后再二分答案+贪心判定。 0024 Toy Blocks 给出n个木块，每个木块有个坐标xi，高度hi。可以讲木块向左或向右推倒，产生类似多米诺骨牌的效果。问至少推倒几块可以全部推倒。 首先用栈处理出每个木块向左或者向右能够推倒的最远距离lefti和righti。然后再动态规划求解。f[i]表示1-i个骨牌全被推倒并且第i个向左倒最少推几个，g[i]表示1-i个骨牌全被推倒并且第i个向右倒最少 推几个。转移时，平方级的枚举很好想，但是复杂度太高，所以我们需要用到数据结构来维护。用线段树来维护最小值。最后的ans=min(f[n],g[n])。