team2012-F2
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
= Personal Information =
Name: Qing REN
Email: {{{renqing@1992y.com}}}
Mobile: 18768186355/626355
QQ: 396794
= Round I =
== Group A ==
=== 0001 ===
本题目是一道在图上的DP，首先进行预处理，计算出所有能整出k的元素，
然后DP，设f[a][b]表示走到第a个节点，分数为b的方案个数，转移为f[a][b] = sum(f[k][x])。
=== 0002 ===
通过离散数学课上学习的容斥原理可以解决这道题目，不知道为什么比赛的时候一直WA = =
需要开一个hash表用来判重复
=== 0003 ===
这道题目可以通过构造一个线性空间，然后求出线性空间的一组线性解基解决题目
=== 0004 ===
给出四个点，以点为圆心画圆且限制四个圆无公共部分相交，求四个圆半径之和的最大值。
可以枚举两两分组，最小的那组是可行的最大答案。
=== 0005 ===
三角形三个顶点的方案数再减去三点共线的方案数，就是答案
三点共线的情况分为 斜率大于零、小于零、等于零和无穷大
=== 0006 ===
本题目需要通过写高精度
首先进行BFS遍历这颗树，然后在树上进行DP就可以了。
== Group B ==
=== 0007 ===
这道题目是比赛时候写的代码
题目大意是给定一个整数序列，然后偶一些查询，查询在某一区间内从右到左第一个重复出现的数字
首先根据数字大小排序，对于重复出现的数字记录它下一次出现的位置
然后将查询读入，根据右区间排序，进行离线化
开一个队列搞一搞就可以了
=== 0008 ===
这道题目用的mj学长的方法解决的
设mow[i]表示如果你在进入第i个城市之前，有1块钱，那么在之后最多能变成多少块钱
设apw[i]表示如果你在进入第i个城市之前，有1点攻击力，那么在之后最多会演化成多少块钱
然后转移什么的直接看代码吧...就像dp一样的思路
唯一需要说明的一点大概是：因为这个转换关系都是常数倍的关系，所以这些获利都可以分开考虑，最后叠加。
=== 0009 ===
这道题目暴力算出四个参数，然后直接计算据可以了...
参数没有计算，直接用题解里面的 - -
=== 0010 ===
以每一列构造一个矩阵，然后根据重复次数进行快速幂就可以了
总而言之，这道题目是矩阵乘法的
=== 0011 ===
这道题目比较难
=== 0012 ===
据说这道题目是我比赛时候写出来的
当时看到一堆人瞬秒，然后看样子像LIS，就贴了一个LIS上去
结果也AC了- -
== Group C ==
今天太没RP了，胃疼了一天TAT
=== 0013 ===
在一个n*m的矩形上，存在着一些守卫，他们按照顺时针方向巡视，每次巡视只能看到一个方向，需要求从起点到终点，最少需要被守卫看到几次
这道题目可以用最短路搞定，用SPFA搞一下就可以了
=== 0014 ===
这道题目鄙人出的，比赛的时候因为精度，给大家造成困扰，表示歉意
题目大意就是，在一个立体空间里面，存在着一堆成对的圆心，你要从每组里面选取一个圆心，构成n个半径相同且没有公共部分的圆，求最大r
这道题目是一道赤裸裸的2-SAT，只要二分然后2SAT一下判断是否可行就好
=== 0015 ===
给定一棵树，然后进行染色，总共有c种颜色，要求相邻两点颜色不能相同，然后有一堆询问，问如果某两点之间增加一条边，方案数会减少多少
对于n节点的书，方案数是C * (C - 1) ^ (N - 1)， 然后这道题目可以变为章鱼图模型，求染色方案数可以用DP解决掉
=== 0016 ===
有一个立方体，每个格子上面都有数字，我们可以对相邻的两个格子增加或者减去同一个数，求是否可以全部变成0
进行黑白染色，然后分别将黑格子与白格子的数之和相加，判断是否相等即可
=== 0017 ===
给定一个n边型，每个顶点上有两个属性u,v，要求相邻两顶点至少有一个属性相同，给你8个点的数值，求方案数
先推出dp公式，f[i][1,2,3,4]表示从起点到i的方案数，总共有四种转移，然后再通过矩阵乘法快速求解即可
=== 0018 ===
一开始给你13张牌，问再有什么牌就可以win
首先枚举一下牌，然后在搜索就可以
== Group D ==
=== 0019 ===
先求最小生成树，进行一次Kruskal，然后用LCA倍增法，维护四个数组就可以了
=== 0020 ===
就是有一堆怪物，一些是普通怪一些是老boss，打普通怪可以得到buff，老boss如果集齐5个buff可以获得宝物一个，打boss的时候可以嗑药
求在掉最多宝物的情况下要嗑多少药。难道被EOF给卡TLE了- -
对于每一个老boss通过dp进行预处理，可以通过dp进行预处理，计算pk所需要的嗑药量，共三种转移，然后在进行主dp即可，单调队列维护一下
=== 0021 ===
裸的凸包
=== 0022 ===
这道题目规则好多- -英文看起来好乱
按照规则进行模拟，用递归处理就可以了。
=== 0023 ===
比赛的时候就卡在这道题目上了 - -
构造可以通过贪心的方法，从右到左进行贪心。之后，二分答案，再通过贪心的方法，这次从左到右把货物放入货仓中
=== 0024 ===
这道题目不会做，看了一下出题的KT学姐的解题方法
首先用栈处理出每个木块向左或者向右能够推倒的最远距离lefti和righti。然后再动态规划求解。f[i]表示1-i个骨牌全被推倒并且第i个向左倒最少推几个，
g[i]表示1-i个骨牌全被推倒并且第i个向右倒最少推几个。转移时，平方级的枚举很好想，但是复杂度太高，所以我们需要用到数据结构来维护。用线段树来维护最小值。最后的ans=min(f[n],g[n])。 Personal Information
Name: Qing REN
Email: renqing@1992y.com
Mobile: 18768186355/626355
QQ: 396794
Round I
Group A
0001
本题目是一道在图上的DP，首先进行预处理，计算出所有能整出k的元素，
然后DP，设f[a][b]表示走到第a个节点，分数为b的方案个数，转移为f[a][b] = sum(f[k][x])。
0002
通过离散数学课上学习的容斥原理可以解决这道题目，不知道为什么比赛的时候一直WA = =
需要开一个hash表用来判重复
0003
这道题目可以通过构造一个线性空间，然后求出线性空间的一组线性解基解决题目
0004
给出四个点，以点为圆心画圆且限制四个圆无公共部分相交，求四个圆半径之和的最大值。
可以枚举两两分组，最小的那组是可行的最大答案。
0005
三角形三个顶点的方案数再减去三点共线的方案数，就是答案
三点共线的情况分为 斜率大于零、小于零、等于零和无穷大
0006
本题目需要通过写高精度
首先进行BFS遍历这颗树，然后在树上进行DP就可以了。
Group B
0007
这道题目是比赛时候写的代码
题目大意是给定一个整数序列，然后偶一些查询，查询在某一区间内从右到左第一个重复出现的数字
首先根据数字大小排序，对于重复出现的数字记录它下一次出现的位置
然后将查询读入，根据右区间排序，进行离线化
开一个队列搞一搞就可以了
0008
这道题目用的mj学长的方法解决的
设mow[i]表示如果你在进入第i个城市之前，有1块钱，那么在之后最多能变成多少块钱
设apw[i]表示如果你在进入第i个城市之前，有1点攻击力，那么在之后最多会演化成多少块钱
然后转移什么的直接看代码吧...就像dp一样的思路
唯一需要说明的一点大概是：因为这个转换关系都是常数倍的关系，所以这些获利都可以分开考虑，最后叠加。
0009
这道题目暴力算出四个参数，然后直接计算据可以了...
参数没有计算，直接用题解里面的 - -
0010
以每一列构造一个矩阵，然后根据重复次数进行快速幂就可以了
总而言之，这道题目是矩阵乘法的
0011
这道题目比较难
0012
据说这道题目是我比赛时候写出来的
当时看到一堆人瞬秒，然后看样子像LIS，就贴了一个LIS上去
结果也AC了- -
Group C
今天太没RP了，胃疼了一天TAT
0013
在一个n*m的矩形上，存在着一些守卫，他们按照顺时针方向巡视，每次巡视只能看到一个方向，需要求从起点到终点，最少需要被守卫看到几次
这道题目可以用最短路搞定，用SPFA搞一下就可以了
0014
这道题目鄙人出的，比赛的时候因为精度，给大家造成困扰，表示歉意
题目大意就是，在一个立体空间里面，存在着一堆成对的圆心，你要从每组里面选取一个圆心，构成n个半径相同且没有公共部分的圆，求最大r
这道题目是一道赤裸裸的2-SAT，只要二分然后2SAT一下判断是否可行就好
0015
给定一棵树，然后进行染色，总共有c种颜色，要求相邻两点颜色不能相同，然后有一堆询问，问如果某两点之间增加一条边，方案数会减少多少
对于n节点的书，方案数是C * (C - 1) ^ (N - 1)， 然后这道题目可以变为章鱼图模型，求染色方案数可以用DP解决掉
0016
有一个立方体，每个格子上面都有数字，我们可以对相邻的两个格子增加或者减去同一个数，求是否可以全部变成0
进行黑白染色，然后分别将黑格子与白格子的数之和相加，判断是否相等即可
0017
给定一个n边型，每个顶点上有两个属性u,v，要求相邻两顶点至少有一个属性相同，给你8个点的数值，求方案数
先推出dp公式，f[i][1,2,3,4]表示从起点到i的方案数，总共有四种转移，然后再通过矩阵乘法快速求解即可
0018
一开始给你13张牌，问再有什么牌就可以win
首先枚举一下牌，然后在搜索就可以
Group D
0019
先求最小生成树，进行一次Kruskal，然后用LCA倍增法，维护四个数组就可以了
0020
就是有一堆怪物，一些是普通怪一些是老boss，打普通怪可以得到buff，老boss如果集齐5个buff可以获得宝物一个，打boss的时候可以嗑药
求在掉最多宝物的情况下要嗑多少药。难道被EOF给卡TLE了- -
对于每一个老boss通过dp进行预处理，可以通过dp进行预处理，计算pk所需要的嗑药量，共三种转移，然后在进行主dp即可，单调队列维护一下
0021
裸的凸包
0022
这道题目规则好多- -英文看起来好乱
按照规则进行模拟，用递归处理就可以了。
0023
比赛的时候就卡在这道题目上了 - -
构造可以通过贪心的方法，从右到左进行贪心。之后，二分答案，再通过贪心的方法，这次从左到右把货物放入货仓中
0024
这道题目不会做，看了一下出题的KT学姐的解题方法
首先用栈处理出每个木块向左或者向右能够推倒的最远距离lefti和righti。然后再动态规划求解。f[i]表示1-i个骨牌全被推倒并且第i个向左倒最少推几个，
g[i]表示1-i个骨牌全被推倒并且第i个向右倒最少推几个。转移时，平方级的枚举很好想，但是复杂度太高，所以我们需要用到数据结构来维护。用线段树来维护最小值。最后的ans=min(f[n],g[n])。