team2012-E2

从 Trac 迁移的文章

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

原文章内容如下：

*Group A
  *Kitty's Game
     题目大意:连通图上存在若干个点，每个点上有一个数字，到达一个点的时候，得分变为原得分与该点分数的LCM值，不允许一次移动后得分不变，求到达终点时得分恰好为K的方案数。
     符合条件上的路径的点一定是K的约数，所以可以先分离出K的约数（数量不超过2000个),之后从原点出发进行BFS即可。（判断新得分是否仍为约数并且数值出现变化）。
     注意使用BFS的话，可能存在两种符合条数的路径，中间经过的层数不同（如1-->3 与 1-->2-->3皆为合法路径，但层数不同），所以每次一个状态拓展完成后，将该点的计数清零。
  *The Review Plan
     题目大意： 有N ( N<=50 )页的书，每天只能选择一页来看，给定M(M<=25)个限制，第Di天不能看第Ci页，求方案数。若不存在限制，则方案数为N!
     所求方案数可以由总数减去所有与限制条件冲突的方案数来得到。
     因为M<=25 ，可以直接枚举这M个限制是否产生冲突，共可得到不超过2的m次方种的限制条件结合， 
     之后根据容斥原理处理即可
     似乎是因为数据中存在重复的情况，所以rejudge过..
     用map判掉重复情况
  *Decode
     题目大意：给定k个长度为n的二进制编码，接下来给出m个询问，每个询问包含一个长度为n的编码，问能否用k个编码中的若干个进行异或运算后，得到与该编码误差位不超过3位的编码。(取字典序最小的一个)。
      这是一个线性代数题，首先使用高斯消元，对k个给定编码进行处理，最后得到一组基。之后对于每个询问，O(n)扫描是否能  通过基来表示即可。注意n<=30，所以二进制编码可以用一个int值来表示。
  *Ribbon Gymnastics
     题目大意：给定4个点，以他们为圆心，求使得4个圆不相交的情况下，4圆半径之和的最大值能为多少。
     设符合条件的4个圆半径分别为R1，R2，R3，R4
     点1 2 3 4 两两间的距离分别为 L12,L13，L14, L23, L24, L34
     则R1 R2 R3 R4 满足以下不等式：
     R1+R2 <= L12  ……<1>
     R1+R3 <= L13  ……<2>
     R1+R4 <= L14  ……<3>
     R2+R3 <= L23  ……<4>
     R2+R4 <= L24  ……<5>
     R3+R4 <= L34  ……<6>
     <1>+<6>可得
     R1+R2+R3+R4 <= L12 + L34
     <2>+<5>可得
     R1+R2+R3+R4 <= L13 + L24
     <3>+<4>可得
     R1+R2+R3+R4 <= L14 + L23
     综合可得，R1+R2+R3+R4 <= Min{ L12+L34,L13+L24,L14+L23 }
     而R1+R2+R3+R4为所求答案，所以所求最大值为Min{ L12+L34,L13+L24,L14+L23 }
  *Gao the Grid
     题目大意：给定N*M的格点，求格点内包含的三角形的个数。
     答案为任取三点数量减去三点位于同一行/列，再减去三点位于同一斜线。
     其中，最后一种情况，以（0,0）为端点，枚举斜线斜率，在此基础上扣去重复部分，
     之后算出该斜线在整个格点图中共存在多少条，用答案减去即可。
     其中重复部分，可由求横纵坐标的最大公约数值得到
  *Cut the Tree 2
     题目大意： 给定一棵有N( N<=100,000 ）个节点的树，每个节点上有一个权值。Vi 表示以节点i为根时，下属所有子树间权值和的乘积。求最大的Vi
     拓扑排序后，从队尾到队头O(N)预处理出每个子树的权值和，以及下属子树权值和的乘积
     一开始默认1号点为根，之后使用DFS，依次替换下属节点为根
     转换的代价转移： 对于每个点x，转换代价：∏(sum[1]-sum[k])*multi[k] ，其中k为x的所有子节点，sum[k]表示以1为根时，以节点k为根的子树的权值和，multi[k]表示以1为根时，节点k下属所有子树的权值               
     和的乘积。总复杂度O（N） 注意涉及高精度运算。
*Group B
  *Alice's present
     题目大意：给定一个长度为N（ N<= 500,000 )的数列，接着给出M（ M<=50,000 )个询问,每个询问包含一段区间的开始和结束位置。对于每个询问，求出给定区间从右往左第一个出现重复的数字。
     首先离散给定数字。之后使用头、尾指针扫描队列，初始位置均为1。 如果头指针当前指向的数字，在之前出现过(in [a[head]]=true),则令尾指针不断加一，并且使 in[a[tail]]都变为false,
     直到in[a[head]]=false为止（这样即可保证头尾指针所框定的区间中不存在重复数字)，记录下此时tail指针的位置，该位置即为头指针当前指向的数字，在数列中上一次出现的位置，
     此时令pos[head]=tail即可。(pos[i]表示对于以第i个位置结尾的区间来说，所求答案所在的位置） 
     时间复杂度为O(n)。
  *Bounty hunter
     题目大意：给出N个城市，初始金钱X，初始攻击力Y。
      第i天能走到第i个城市，在每个城市，可以花费a[i]单位的钱来提升1单位的攻击力，攻击力可以提升小数。在离开i城市时，会获得b[i]*p的收益，其中p为你现有攻击力。求到达终点后，获利最多的情
      况。首先，一个显然的结论：对于当前城市，要么花掉所有钱提升攻击力，要么不花钱。考虑到终点的方案，若在第i天购买攻击力（之前均不买），则购买是否更优仅取决于a[i]是否小于sum(b[i]...
     b[n])。对于第i天购买攻击力，如果其之后存在购买攻击力的天j，并且：
      ①：单独第i天购买比单独第j天购买更优时，两者同时选择，会使得决策更优。
      ②：单独第i天购买劣于单独第j天购买时，第i天不选择购买，并把钱留至第j天，会使得决策更优。
      所以从尾到头扫描一遍选出需要购买攻击力的城市，之后正序模拟即可。
  *Guess a Function
     ymZYC学长的神题。完全没有头绪啊QAQ..
     最后看了好几个学长的题解，最后大概弄懂了0 0..
     题目给定了f(x)的形式，并且给出了若干组(x,f(x))，求f(x)
     注意到g(x)=x ^ (x/2) ,而(x/2)=x>>1 ，即实际上g(x)是将x与x右移一位
      得到的数进行抑或运算。假设令y=g(x),则可以得到x的最高位(等于y的最高位),
     剩余位上的数字可以从高到低推出，即可得知g(x)的反函数，记为g'(x)。
      原式f(x) = g( h2( g( h1( g( x ) ) ) ) )  可写成：
      g'( f(x) )=h2( g(h1( g(x) ) ) )
     之后枚举h1(即枚举其中的m1和s1的值)，这样可以得到g(h1(g(x)))的值，设其为t
     接下来只需要确定h2(t)就行。
      观察h2的表达式，发现当x%m2 + s2< m2时，h2(x)=x+s2,否则h2(x)=x+s2-m2。
      这样就这要找到两组大小互异的{x和h2(x)},来确定出s2和m2,再判断是否为题目的解。
      最终会得到解: s1 = 100007, m1 = 214748, s2 = 123123, m2 = 201263 （再次ym学长们)

  *Maze
     题目大意：给出一个k行n列的网格，每个格子内有三种类型：墙，直道，弯道
      列共有m组，每组中，每一列都是相同的，你可以任意设定管道旋转方向。
      求从左边缘出发，到达右边缘有几种走法
      此题做法是矩阵乘法。对于每一列我们可以使用1*K的矩阵ans=[a0,a1,...,ak-1]，ai表示到达i行的格子的方案数。初始情况ans=[1,1,...,1]。
      对于下一列，可以使用一个K*K的矩阵来表示当前列和下一列间的转移情况。
      对于同组中多列，因为每列状态相同，所以可以使用快速幂优化矩阵乘法。
  *Paint Erased

     这题好神> <..又是看了好多学长的题解后才勉强明白的...
     题目大意：在平面上，每次对若干个矩形区域进行染色和擦除操作，然后给出一条折线段,询问这条折线段在染色区域内的长度。
      一条直线可以用(x0,y0)+k*(X,Y）来表示,k为向量增量的倍数。
      折线段可以看做若干段直线段，而答案就是每一段线段上染色部分的长度。
      问题变成，对于每条线段关于每个矩形，求一个相交区间。
      使用扫描线的方法，对于每一段，询问当前最大标号的区间的情况，来判定是否计入答案。


  *Versus
     题目大意：两队人进行对决，第一队的第i个选手只能跟第二队的编号大于i且之前未对决过的
      的选手对决，给出N条信息，每条信息表示一队的X选手能赢二队的Y选手，求一队最多能赢几场。
      可以看出这是一个LIS的模型，因为N较大(N<=100,000) ,所以需要使用O(nlogn)的算法。
*Group C
  *Battle: Dojo

   题目大意： 小智要挑战道馆，道馆是一个矩形，其中有些格子上有障碍物，还有一些格子里面有训练师，每个训练师有初始面朝 向，之后每秒按顺时针方向转90°。每个训练师有不同的视野长度，但你处于他的视野内，你就必须跟他决斗，决斗不损耗时间。求从一个位置出发，前往另一个位置，经历最少的决斗次数，并且此时最短的损耗时间。
    建好图BFS即可，注意站在起点的时候（时间为0时），也可能存在被决斗的情况。  
  *Balloon

   题目大意：N组气球，每组有两个，要从每组中选取一个气球。求一个最大的半径R，使得选出的气球中任意两个之间的距离不小于R*2。
    这是一个2-SAT问题。先二分枚举半径R，
    在这个半径下，如果不同组的两个气球A、B之间的距离小于R*2，
    则建立 A到B' 及 B到A' 的有向边。其中A'是A同组的气球，B’是B同组的气球。
    建边表示，如果选了气球A，则必须选B’，如果选了B，则必须选A'。
    建好图后，判断是否存在任意的A到A'之间的双向路径，
    即选了A必须要选A’，选了A'就一定要选A，
    如果不存在，则为可行解，否则为不可行解。
    使用tarjan或gabow均可。


  *Kaguya's Game

  题目大意：给一棵树上每个结点染色，其中相邻两点不能同色。共有C种颜色可选。
  存在M个询问，每个询问表示，在X和Y之间添加一条边，则染色方案会减少多少.
  首先，对于一棵树，易知方案数为 C * (C-1)的n-1次方。
  在树上添加一条边后，原图变为一个环加外向树的形式。
  对于环来说，设F[i][0]表示长度为i的环，且末尾不与开头颜色相同，
  f[i][1]表示长度为i的环，且末尾与开头颜色相同， 
  则有f[i][0]=f[i-1][0]*(c-2)+f[i-1][1]*(c-1)，
  又f[i][1]=f[i-1][0]
  所以代入得，f[i][0]=f[i-1][0]*(c-2)+f[i-2][0]*(c-1)
  即 f[i]=f[i-1]*(c-2)+f[i-2]*(c-1)
  长度为X的环的染色方案数确定后，剩下点的方案数就是(C-1)的(N-X)次方
  接着考虑如何计算添边后产生的环的长度，
  这里可以使用倍增的LCA来处理。

  *The Toy of Flandre Scarlet

  题目大意：一个L*W*H的立方体上，每单位块上有一个数字，每次你可以另相邻两块增加或减少同样的整数，求是否存在一种方式，使得最终每个块上数字均为0。
   一个显然的结论，如果对立方体每一块进行黑白染色的话，数字同时变化的方块必定为一黑一白，即黑白两色数字和的差值不会因为操作而改变。那么判断黑白两色的数字和是否相同，即可确定答案。

  *Cipher Lock

  题目大意：n个点构成一个环，每个点上有两个属性值，相邻两点间至少有一个属性值一样。现在给定其中的8个点的属性值，求有多少种满足条件的构成环的方案。
  对于两个给定点之间，因为相邻两点之间至少有一个属性值相同，所以两给定点之间的中间点，属性值只可能有4种情况：
  [xy,xB,Ay,AB]，其中x表示第一个属性不为A的任意值，y表示第二个属性不为B的任意值
  初始矩阵T为两个给定点的状态（上述4种情况）
  转移矩阵D为
  [p+q-3,1,1,0, 
  q-1,p-1,0,1, 
  p-1,0,q-1,1,
  0,p-1,q-1,1]
  接下来用快速幂叠加计算相邻两点间的数量。 
  每转移完一段，需要重置矩阵，总共做8次
  最后乘回起点时，矩阵中代表AB的元素就是答案


  *Japanese Mahjong I

  题目大意：麻将题……麻将题……麻将题……（怨念中），总之就是给你一副手牌，再告诉你胡牌方式，让你判断“听”那些牌...按照它说的做就好了...
*Group D

  *Social Net

  题目大意：给出N个点,M条边，先求出最大生成树（保证唯一），之后对于该树，有Q个询问，每次询问一条从X到Y的路径，求C  [i]-C[j]的最大值（i,j均为X到Y路径上的点，且满足j在i之后访问）
  首先先求出最大生成树。对于每个询问，可以使用倍增的LCA来解决。
  倍增的同时，利用2的i次方来预处理维护一段路径中的最大值、最小值，
  同时对于路径中的任意两点(i,j)，记录下c[j]-c[i]的最大值（左半边上去)，c[i]-c[j]最大值（右半边下去)
  对于每次查询，最优答案可能来自于左半边或者右半边，此时答案可从上述的两个数组中找到。最优答案的两点也可能来自于左右两边，此时把左右两边通过二进制拆分得到的段分别扔入数组l和h内，l[i]表示前i个数中的最小值，h[i]表示从i至末尾的数中最大值，之后线性扫描一遍即可。


  *Diablo III

  题目大意：在大菠萝三的游戏中，你需要打N个怪物，其中有一些是精英怪，剩余的则是BOSS。满足以下规则：
  ①：打死一个精英怪后，能够获得一层BUFF，最高为5层。
  ②：当你干掉一个BOSS时，你身上带有5层BUFF，则你获得一个宝物。
  ③：每个BOSS都拥有独立的血量和攻击力，且你打死BOSS后,BUFF层数会清零。
  你拥有三个属性：血量、攻击力、喝药之后血量的回复值
  每个回合战斗按照如下顺序，直到其中一方血量小等于0为止。
  决定是否喝药--->我方攻击--->敌方攻击---->决定是否喝药（如果这回合战前没喝)
  求在获得尽可能多的宝物的前提下，所喝药水最少。
   对于每个BOSS的对战，可能出现以下几种情况：
  ①：BOSS攻击力小于或等于你喝药的回复值
  处理策略：跟BOSS对砍，直到你下次攻击打不死BOSS，而BOSS却能打死你时，此时选择在战斗阶段前喝一瓶药
  ②：BOSS攻击力大于你喝药的回复值
  处理策略：每次战斗阶段结束后，喝一瓶药水。若干回合后，会出现以下几种情况：
  2.1：BOSS阵亡 
    处理策略：计算出多喝了几瓶药，保留最低血量即可。
  2.2：我方这回合会被BOSS打死
    处理策略：战斗阶段前喝一瓶药，之后因为BOSS伤害高于回复值，每回合战斗阶段前必须喝一瓶药，直到你这回合能解决BOSS。
  2.3：换作攻击前喝药后，最终仍然会被BOSS打死
     处理策略：放弃这个BOSS吧，ALT+F4 ╮(￣▽￣")╭
  dp[i]为pair<int,int>类型，记录处理完前i个怪物后，能获得的最多宝物数，以及此时最少消耗药水数。
  如果第i个怪是精英怪，则dp[i]=dp[i-1]
  否则dp[i]=max{dp[i-1],{dp[x].first+1,dp[x].second + cal(i)} }
  即将最近的5个精英怪保留给当前BOSS，在之前位置选择最优的x来进行转移

  *Driving Helicopter I

  题目大意：问一个直升机从一点到另一点飞行的最短距离，不能直接穿过山。
   裸的凸包……真的是裸的凸包啊

  *E-Cup

  题目大意：给出几个球队间两两比赛的比分，求各队伍的名次。
  利用stl进行统计即可，注意净胜球可以为负。

  *Wagon

  题目大意：给定N个货仓，每个货仓内有a[i]货物。现在有M辆货车可以安排，货车只能被安排在货仓上，要求使得所有货仓到它最 近的货车的距离和最小。（如果存在多解，则取字典序最小解）货仓会将储存的货物转移到离他最近的货车上（如果存在2个距离相同的货车，则可以取任意一个），求在此情况下，每辆车的最小载货量为多少。
  对于后面那个问题，显然可以使用二分来得到解，问题在于如何确定货车的位置。
  正向放置货车不容易满足字典序最小的方案，所以此时应考虑反向思考，即先固定好车的位置，之后在空隙间填入货仓。对于货车从右往左扫描并选择放置货仓，那么得到的结果一定满足字典序最小。另外，为了满足距离和最小的要求，应该平均地在间隔中塞货仓，直至N-M个货仓全部塞完。注意存在所有a[i]都为0的情况。

  *Toy Block

  题目大意：给出N个木块，每个木块所在的位置为X[i]，其高度为H[i]。你可以选择将一个木块朝左或者朝右推倒，由于高度的缘故，木块在推倒过程中，有可能推倒其他的一些木块，引发连锁反应。问至少要手动推动多少块，才能让所有木块都倒下。
这题没有好的想法，参考了猛犸学长的解题报告。利用u[i]、v[i]数组维护每个木块向左或者向右推倒时，最远能碰倒的木块编号。预处理u[i]、v[i]后，利用两个数组进行dp。
  dp[i]表示弄倒前i个木块所需要的最少手动推倒次数，转移方程为：
  1、dp[i]=min(dp[i],min(dp[u[i]]-1]...dp[i-1])+1) //用连续的一段元素更新一个元素
  2、dp[i]..dp[v[i]]=min(dp[i]...dp[v[i]],dp[i-1]+1)// 用一个元素更新连续的一段元素
  利用单调队列优化转移方程。
  对于第一项，只要每次添加元素前维护一下队列即可。
  对于第二项，因为它的修改只会降低那个区间内的dp值，而对于相同的dp值，只需要保留最后一个，所以实际上只需要更新第v[i]个元素的值即可。

*Group A

*Kitty's Game

题目大意:连通图上存在若干个点，每个点上有一个数字，到达一个点的时候，得分变为原得分与该点分数的LCM值，不允许一次移动后得分不变，求到达终点时得分恰好为K的方案数。

符合条件上的路径的点一定是K的约数，所以可以先分离出K的约数（数量不超过2000个),之后从原点出发进行BFS即可。（判断新得分是否仍为约数并且数值出现变化）。

注意使用BFS的话，可能存在两种符合条数的路径，中间经过的层数不同（如1-->3 与 1-->2-->3皆为合法路径，但层数不同），所以每次一个状态拓展完成后，将该点的计数清零。

*The Review Plan

题目大意： 有N ( N<=50 )页的书，每天只能选择一页来看，给定M(M<=25)个限制，第Di天不能看第Ci页，求方案数。若不存在限制，则方案数为N!

所求方案数可以由总数减去所有与限制条件冲突的方案数来得到。

因为M<=25 ，可以直接枚举这M个限制是否产生冲突，共可得到不超过2的m次方种的限制条件结合，

之后根据容斥原理处理即可

似乎是因为数据中存在重复的情况，所以rejudge过..

用map判掉重复情况

*Decode

题目大意：给定k个长度为n的二进制编码，接下来给出m个询问，每个询问包含一个长度为n的编码，问能否用k个编码中的若干个进行异或运算后，得到与该编码误差位不超过3位的编码。(取字典序最小的一个)。

这是一个线性代数题，首先使用高斯消元，对k个给定编码进行处理，最后得到一组基。之后对于每个询问，O(n)扫描是否能 通过基来表示即可。注意n<=30，所以二进制编码可以用一个int值来表示。

*Ribbon Gymnastics

题目大意：给定4个点，以他们为圆心，求使得4个圆不相交的情况下，4圆半径之和的最大值能为多少。

设符合条件的4个圆半径分别为R1，R2，R3，R4

点1 2 3 4 两两间的距离分别为 L12,L13，L14, L23, L24, L34

则R1 R2 R3 R4 满足以下不等式：

R1+R2 <= L12 ……<1>

R1+R3 <= L13 ……<2>

R1+R4 <= L14 ……<3>

R2+R3 <= L23 ……<4>

R2+R4 <= L24 ……<5>

R3+R4 <= L34 ……<6>

<1>+<6>可得

R1+R2+R3+R4 <= L12 + L34

<2>+<5>可得

R1+R2+R3+R4 <= L13 + L24

<3>+<4>可得

R1+R2+R3+R4 <= L14 + L23

综合可得，R1+R2+R3+R4 <= Min{ L12+L34,L13+L24,L14+L23 }

而R1+R2+R3+R4为所求答案，所以所求最大值为Min{ L12+L34,L13+L24,L14+L23 }

*Gao the Grid

题目大意：给定N*M的格点，求格点内包含的三角形的个数。

答案为任取三点数量减去三点位于同一行/列，再减去三点位于同一斜线。

其中，最后一种情况，以（0,0）为端点，枚举斜线斜率，在此基础上扣去重复部分，

之后算出该斜线在整个格点图中共存在多少条，用答案减去即可。

其中重复部分，可由求横纵坐标的最大公约数值得到

*Cut the Tree 2

题目大意： 给定一棵有N( N<=100,000 ）个节点的树，每个节点上有一个权值。Vi 表示以节点i为根时，下属所有子树间权值和的乘积。求最大的Vi

拓扑排序后，从队尾到队头O(N)预处理出每个子树的权值和，以及下属子树权值和的乘积

一开始默认1号点为根，之后使用DFS，依次替换下属节点为根

转换的代价转移： 对于每个点x，转换代价：∏(sum[1]-sum[k])*multi[k] ，其中k为x的所有子节点，sum[k]表示以1为根时，以节点k为根的子树的权值和，multi[k]表示以1为根时，节点k下属所有子树的权值

和的乘积。总复杂度O（N） 注意涉及高精度运算。

*Group B

*Alice's present

题目大意：给定一个长度为N（ N<= 500,000 )的数列，接着给出M（ M<=50,000 )个询问,每个询问包含一段区间的开始和结束位置。对于每个询问，求出给定区间从右往左第一个出现重复的数字。

首先离散给定数字。之后使用头、尾指针扫描队列，初始位置均为1。 如果头指针当前指向的数字，在之前出现过(in [a[head]]=true),则令尾指针不断加一，并且使 in[a[tail]]都变为false,

直到in[a[head]]=false为止（这样即可保证头尾指针所框定的区间中不存在重复数字)，记录下此时tail指针的位置，该位置即为头指针当前指向的数字，在数列中上一次出现的位置，

此时令pos[head]=tail即可。(pos[i]表示对于以第i个位置结尾的区间来说，所求答案所在的位置）

时间复杂度为O(n)。

*Bounty hunter

题目大意：给出N个城市，初始金钱X，初始攻击力Y。

第i天能走到第i个城市，在每个城市，可以花费a[i]单位的钱来提升1单位的攻击力，攻击力可以提升小数。在离开i城市时，会获得b[i]*p的收益，其中p为你现有攻击力。求到达终点后，获利最多的情

况。首先，一个显然的结论：对于当前城市，要么花掉所有钱提升攻击力，要么不花钱。考虑到终点的方案，若在第i天购买攻击力（之前均不买），则购买是否更优仅取决于a[i]是否小于sum(b[i]...

b[n])。对于第i天购买攻击力，如果其之后存在购买攻击力的天j，并且：

①：单独第i天购买比单独第j天购买更优时，两者同时选择，会使得决策更优。

②：单独第i天购买劣于单独第j天购买时，第i天不选择购买，并把钱留至第j天，会使得决策更优。

所以从尾到头扫描一遍选出需要购买攻击力的城市，之后正序模拟即可。

*Guess a Function

ymZYC学长的神题。完全没有头绪啊QAQ..

最后看了好几个学长的题解，最后大概弄懂了0 0..

题目给定了f(x)的形式，并且给出了若干组(x,f(x))，求f(x)

注意到g(x)=x ^ (x/2) ,而(x/2)=x>>1 ，即实际上g(x)是将x与x右移一位

得到的数进行抑或运算。假设令y=g(x),则可以得到x的最高位(等于y的最高位),

剩余位上的数字可以从高到低推出，即可得知g(x)的反函数，记为g'(x)。

原式f(x) = g( h2( g( h1( g( x ) ) ) ) ) 可写成：

g'( f(x) )=h2( g(h1( g(x) ) ) )

之后枚举h1(即枚举其中的m1和s1的值)，这样可以得到g(h1(g(x)))的值，设其为t

接下来只需要确定h2(t)就行。

观察h2的表达式，发现当x%m2 + s2< m2时，h2(x)=x+s2,否则h2(x)=x+s2-m2。

这样就这要找到两组大小互异的{x和h2(x)},来确定出s2和m2,再判断是否为题目的解。

最终会得到解: s1 = 100007, m1 = 214748, s2 = 123123, m2 = 201263 （再次ym学长们)

*Maze

题目大意：给出一个k行n列的网格，每个格子内有三种类型：墙，直道，弯道

列共有m组，每组中，每一列都是相同的，你可以任意设定管道旋转方向。

求从左边缘出发，到达右边缘有几种走法

此题做法是矩阵乘法。对于每一列我们可以使用1*K的矩阵ans=[a0,a1,...,ak-1]，ai表示到达i行的格子的方案数。初始情况ans=[1,1,...,1]。

对于下一列，可以使用一个K*K的矩阵来表示当前列和下一列间的转移情况。

对于同组中多列，因为每列状态相同，所以可以使用快速幂优化矩阵乘法。

*Paint Erased

这题好神> <..又是看了好多学长的题解后才勉强明白的...

题目大意：在平面上，每次对若干个矩形区域进行染色和擦除操作，然后给出一条折线段,询问这条折线段在染色区域内的长度。

一条直线可以用(x0,y0)+k*(X,Y）来表示,k为向量增量的倍数。

折线段可以看做若干段直线段，而答案就是每一段线段上染色部分的长度。

问题变成，对于每条线段关于每个矩形，求一个相交区间。

使用扫描线的方法，对于每一段，询问当前最大标号的区间的情况，来判定是否计入答案。

*Versus

题目大意：两队人进行对决，第一队的第i个选手只能跟第二队的编号大于i且之前未对决过的

的选手对决，给出N条信息，每条信息表示一队的X选手能赢二队的Y选手，求一队最多能赢几场。

可以看出这是一个LIS的模型，因为N较大(N<=100,000) ,所以需要使用O(nlogn)的算法。

*Group C

*Battle: Dojo

题目大意： 小智要挑战道馆，道馆是一个矩形，其中有些格子上有障碍物，还有一些格子里面有训练师，每个训练师有初始面朝 向，之后每秒按顺时针方向转90°。每个训练师有不同的视野长度，但你处于他的视野内，你就必须跟他决斗，决斗不损耗时间。求从一个位置出发，前往另一个位置，经历最少的决斗次数，并且此时最短的损耗时间。

建好图BFS即可，注意站在起点的时候（时间为0时），也可能存在被决斗的情况。

*Balloon

题目大意：N组气球，每组有两个，要从每组中选取一个气球。求一个最大的半径R，使得选出的气球中任意两个之间的距离不小于R*2。

这是一个2-SAT问题。先二分枚举半径R，

在这个半径下，如果不同组的两个气球A、B之间的距离小于R*2，

则建立 A到B' 及 B到A' 的有向边。其中A'是A同组的气球，B’是B同组的气球。

建边表示，如果选了气球A，则必须选B’，如果选了B，则必须选A'。

建好图后，判断是否存在任意的A到A'之间的双向路径，

即选了A必须要选A’，选了A'就一定要选A，

如果不存在，则为可行解，否则为不可行解。

使用tarjan或gabow均可。

*Kaguya's Game

题目大意：给一棵树上每个结点染色，其中相邻两点不能同色。共有C种颜色可选。

存在M个询问，每个询问表示，在X和Y之间添加一条边，则染色方案会减少多少.

首先，对于一棵树，易知方案数为 C * (C-1)的n-1次方。

在树上添加一条边后，原图变为一个环加外向树的形式。

对于环来说，设F[i][0]表示长度为i的环，且末尾不与开头颜色相同，

f[i][1]表示长度为i的环，且末尾与开头颜色相同，

则有f[i][0]=f[i-1][0]*(c-2)+f[i-1][1]*(c-1)，

又f[i][1]=f[i-1][0]

所以代入得，f[i][0]=f[i-1][0]*(c-2)+f[i-2][0]*(c-1)

即 f[i]=f[i-1]*(c-2)+f[i-2]*(c-1)

长度为X的环的染色方案数确定后，剩下点的方案数就是(C-1)的(N-X)次方

接着考虑如何计算添边后产生的环的长度，

这里可以使用倍增的LCA来处理。

*The Toy of Flandre Scarlet

题目大意：一个L*W*H的立方体上，每单位块上有一个数字，每次你可以另相邻两块增加或减少同样的整数，求是否存在一种方式，使得最终每个块上数字均为0。

一个显然的结论，如果对立方体每一块进行黑白染色的话，数字同时变化的方块必定为一黑一白，即黑白两色数字和的差值不会因为操作而改变。那么判断黑白两色的数字和是否相同，即可确定答案。

*Cipher Lock

题目大意：n个点构成一个环，每个点上有两个属性值，相邻两点间至少有一个属性值一样。现在给定其中的8个点的属性值，求有多少种满足条件的构成环的方案。

对于两个给定点之间，因为相邻两点之间至少有一个属性值相同，所以两给定点之间的中间点，属性值只可能有4种情况：

[xy,xB,Ay,AB]，其中x表示第一个属性不为A的任意值，y表示第二个属性不为B的任意值

初始矩阵T为两个给定点的状态（上述4种情况）

转移矩阵D为

[p+q-3,1,1,0,

q-1,p-1,0,1,

p-1,0,q-1,1,

0,p-1,q-1,1]

接下来用快速幂叠加计算相邻两点间的数量。

每转移完一段，需要重置矩阵，总共做8次

最后乘回起点时，矩阵中代表AB的元素就是答案

*Japanese Mahjong I

题目大意：麻将题……麻将题……麻将题……（怨念中），总之就是给你一副手牌，再告诉你胡牌方式，让你判断“听”那些牌...按照它说的做就好了...

*Group D

*Social Net

题目大意：给出N个点,M条边，先求出最大生成树（保证唯一），之后对于该树，有Q个询问，每次询问一条从X到Y的路径，求C [i]-C[j]的最大值（i,j均为X到Y路径上的点，且满足j在i之后访问）

首先先求出最大生成树。对于每个询问，可以使用倍增的LCA来解决。

倍增的同时，利用2的i次方来预处理维护一段路径中的最大值、最小值，

同时对于路径中的任意两点(i,j)，记录下c[j]-c[i]的最大值（左半边上去)，c[i]-c[j]最大值（右半边下去)

对于每次查询，最优答案可能来自于左半边或者右半边，此时答案可从上述的两个数组中找到。最优答案的两点也可能来自于左右两边，此时把左右两边通过二进制拆分得到的段分别扔入数组l和h内，l[i]表示前i个数中的最小值，h[i]表示从i至末尾的数中最大值，之后线性扫描一遍即可。

*Diablo III

题目大意：在大菠萝三的游戏中，你需要打N个怪物，其中有一些是精英怪，剩余的则是BOSS。满足以下规则：

①：打死一个精英怪后，能够获得一层BUFF，最高为5层。

②：当你干掉一个BOSS时，你身上带有5层BUFF，则你获得一个宝物。

③：每个BOSS都拥有独立的血量和攻击力，且你打死BOSS后,BUFF层数会清零。

你拥有三个属性：血量、攻击力、喝药之后血量的回复值

每个回合战斗按照如下顺序，直到其中一方血量小等于0为止。

决定是否喝药--->我方攻击--->敌方攻击

---

>决定是否喝药（如果这回合战前没喝)

求在获得尽可能多的宝物的前提下，所喝药水最少。

对于每个BOSS的对战，可能出现以下几种情况：

①：BOSS攻击力小于或等于你喝药的回复值

处理策略：跟BOSS对砍，直到你下次攻击打不死BOSS，而BOSS却能打死你时，此时选择在战斗阶段前喝一瓶药

②：BOSS攻击力大于你喝药的回复值

处理策略：每次战斗阶段结束后，喝一瓶药水。若干回合后，会出现以下几种情况：

2.1：BOSS阵亡

处理策略：计算出多喝了几瓶药，保留最低血量即可。

2.2：我方这回合会被BOSS打死

处理策略：战斗阶段前喝一瓶药，之后因为BOSS伤害高于回复值，每回合战斗阶段前必须喝一瓶药，直到你这回合能解决BOSS。

2.3：换作攻击前喝药后，最终仍然会被BOSS打死

处理策略：放弃这个BOSS吧，ALT+F4 ╮(￣▽￣")╭

dp[i]为pair类型，记录处理完前i个怪物后，能获得的最多宝物数，以及此时最少消耗药水数。

如果第i个怪是精英怪，则dp[i]=dp[i-1]

否则dp[i]=max{dp[i-1],{dp[x].first+1,dp[x].second + cal(i)} }

即将最近的5个精英怪保留给当前BOSS，在之前位置选择最优的x来进行转移

*Driving Helicopter I

题目大意：问一个直升机从一点到另一点飞行的最短距离，不能直接穿过山。

裸的凸包……真的是裸的凸包啊

*E-Cup

题目大意：给出几个球队间两两比赛的比分，求各队伍的名次。

利用stl进行统计即可，注意净胜球可以为负。

*Wagon

题目大意：给定N个货仓，每个货仓内有a[i]货物。现在有M辆货车可以安排，货车只能被安排在货仓上，要求使得所有货仓到它最 近的货车的距离和最小。（如果存在多解，则取字典序最小解）货仓会将储存的货物转移到离他最近的货车上（如果存在2个距离相同的货车，则可以取任意一个），求在此情况下，每辆车的最小载货量为多少。

对于后面那个问题，显然可以使用二分来得到解，问题在于如何确定货车的位置。

正向放置货车不容易满足字典序最小的方案，所以此时应考虑反向思考，即先固定好车的位置，之后在空隙间填入货仓。对于货车从右往左扫描并选择放置货仓，那么得到的结果一定满足字典序最小。另外，为了满足距离和最小的要求，应该平均地在间隔中塞货仓，直至N-M个货仓全部塞完。注意存在所有a[i]都为0的情况。

*Toy Block

题目大意：给出N个木块，每个木块所在的位置为X[i]，其高度为H[i]。你可以选择将一个木块朝左或者朝右推倒，由于高度的缘故，木块在推倒过程中，有可能推倒其他的一些木块，引发连锁反应。问至少要手动推动多少块，才能让所有木块都倒下。

这题没有好的想法，参考了猛犸学长的解题报告。利用u[i]、v[i]数组维护每个木块向左或者向右推倒时，最远能碰倒的木块编号。预处理u[i]、v[i]后，利用两个数组进行dp。

dp[i]表示弄倒前i个木块所需要的最少手动推倒次数，转移方程为：

1、dp[i]=min(dp[i],min(dp[u[i]]-1]...dp[i-1])+1) //用连续的一段元素更新一个元素

2、dp[i]..dp[v[i]]=min(dp[i]...dp[v[i]],dp[i-1]+1)// 用一个元素更新连续的一段元素

利用单调队列优化转移方程。

对于第一项，只要每次添加元素前维护一下队列即可。

对于第二项，因为它的修改只会降低那个区间内的dp值，而对于相同的dp值，只需要保留最后一个，所以实际上只需要更新第v[i]个元素的值即可。