team2012-D2

从 Trac 迁移的文章

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

原文章内容如下：

= Profile =

挫人土人一个。常用ID EZ_dla、Dai@NeverLand、dailongao及其他。吃货一枚。

目标是金牌。

Website：{{{http://www.jiong3.cn}}}

QQ：228804200

TEL：18620129908

Mail：{{{dai@jiong3.cn}}}

= Homework =
== Homework1（DONE!） ==

== 第一轮感想 ==

第一轮最难写的题绝对是Paint Erased……orz……

由于拖延症的原因拖到8/6号才完成了所有的题目，不过一天差不多能保证有一道，对状态的保持也有些好处。唉，还是偷懒了，集训要努力……

学姐好早就做完了，真是膜拜死我了。

特别感谢猛犸学长的解题报告。（……）

=== 第一轮良心程度评价表 ===

Group A：★★★★☆

Group B：★★★☆

Group C：★★★★

Group D：★★☆

=== 0001 Kitty's Game ===

题目大意：给定一个有向图，每个点上有一个值Pi，当前Kitty有一个分数X，到达某个点分数变成LCM(X, Pi），如果分数不变就不能进入这个点，求到达N号点的同时有K分数的行走方法数。

解题报告：简单注意到走一步K是单增的，于是就是一个图上的简单的DP了。猛犸学长的代码中用map进行状态的维护，但其实用priority_queue之类的东西维护也是可以的。注意对无解条件的判断和处理，还有初始条件的判断。

易错点：对于中间有可能爆long long的地方要小心处理；还有是有向图而不是无向图……

=== 0002 The Review Plan ===

题目大意：现在有N个章节要复习，一天复习一个章节，但是有M对约束关系（i, j），表示第i天不能复习第j个章节，求方案数。

解题报告：考虑如果没有约束关系，那么是N!种方案。现在我们考虑：假如计算的是符合约束条件的方案数，怎么样呢？那么我们可以“定下”某些约束关系在哪些天上，方案数就是（剩下天数）!。那么，考虑使用简单的排斥原理，Dfs处理即可算出答案，最后从n!减去即可。
排斥原理理论上还可以用2的m次方搞，但是这题会多上一个m的常数；猛犸学长的处理方法是用格雷码进行枚举，利用格雷码每次只会变化一个bit的性质把m的常数减去，比dfs慢4倍到10倍的样子，但仍然可以通过此题。真是有点厉害……
值得注意的是猛犸学长的方法应该就是本题最坏可构造数据的运行时间了。

易错点：(0)! = 1，最好中间处理都LL掉…… 还有重复情况的判断，否则容斥正负性就会发生问题。标程是错的，Rejudge过。

记录：格雷码生成公式：
{{{
r = 1 - n
i = __builtin__ctz(r);
s ^= 1 << i
}}}

=== 0003 Decode ===
题目大意：给定一些码集，定义一个合法的码必须由码集里面的若干个码异或起来，求判断给定的码在改动至多三位的情况下是否是合法的码。

解题报告：这题比赛时将操作看错了，没看出是异或，囧，但正解也挺难想到的：注意到“由若干个码异或起来所得”很类似线性空间，这题其实就是在一个异或线性空间上判断一个向量是否在空间内。改动的三个位可以简单枚举而得，剩下就是判断某个码是否在空间内了。如果有了空间的一组基，那么就可以通过直接尝试扩张这组基看能否得到这个码，那么对码集高斯消元一次就可以得到我们所要的基了。

易错点：这题数据偏弱，我的高斯消元和判断部分写的不正确，但仍然通过了绝大多数的数据（只有一个询问是错的），事实上视写法的不同，基的储存和表达方式都要不同。还有注意字典序最小的要求。

'''上面关于线性代数部分的描述可能有误（猛犸学长的解题报告是在一个模2环上，但我一直觉得是在线性空间里……），恳请各位学长指正错误。我自己也会回头看看的……'''

=== 0004 Ribbon Gymnastics ===
题目大意：给定4个圆的圆心，规定圆和圆之间不能相交，问半径和最大是多少。

解题报告：这是一个线性规划的模型，只要按照题意列出6条式子，再用单纯形模板直接解决即可。WF模板上的单纯形的init函数有误，需要自己手动初始化一些数组。

关于单纯形法，可以看2007年国家集训队论文“浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用”。

=== 0005 Gao the Grid ===
题目大意：给定n * m的网格，求用网格点构造出来的三角形个数。

解题报告：这是一道论文题，具体做法可以用论文里面的分三种类型讨论三角形个数的做法，也可以用总三角形数减去不合法（共线）三角形数的方法。

易错点：long long就可以存下了不用高精度了呜呜呜……

=== 0006 Cut the Tree 2 ===
题目大意：给一棵树，求删掉一个点和它连着的所有边后形成的若干棵树的权值和。

解题报告：题目本身应该还是很水的，怎么搞都能过；就是加了一个高精度后比较恶心。听闻马甲是Java过的，真是无限敬仰……

易错点：似乎对高精度的速度要求比较高，比赛时手写的高精度超时了，orz……

=== 0007 Alice's present ===
题目大意：爱丽丝是一个人偶使（大雾），然后有一些人偶，人偶后面贴着数字（……）。现在魔理沙生日了，于是爱丽丝决定选一个区间的人偶当礼物，她对于一个区间(i, j)会从右到左依次检查，如果有数字重复就是Unsuitable。回答询问（输出OK或者第一个重复的数字）

解题报告：一开始容易开始各种用数据结构，但是仔细想想应该是比较简单的吧？对每一个位子记录一个“当前位置最近的重复数字的位置”，然后O(n)地预处理一下（实际上还要用到map，还要多个lgn），然后直接判断来回答询问就可以了。

=== 0008 Bounty hunter ===
题目大意：给定N个城市，你要依次从1 - N访问。在每个城市，你可以先以A[i]块/点的代价提升一次攻击力（可以是小数），然后打任务获得B[i] * atk（当时的攻击力）的金钱。问你最后离开第N个城市的时候能获得多少金钱。

解题报告：这题我是看了官方解题报告和猛犸学长的解题报告后写的，实质上就是倒着考虑，定义S[i] = sum(B[j]) (i <= j <= N)，然后不断地比较当前最优的S[i] - A[i]，如果更优就在这个城市提升攻击力。具体的证明方法应该也不用再多说了，参考解题报告似乎就行了（猛犸学长的意识流证明方法似乎不够严谨，vout学长的就比较科学了）。这题真是比较猎奇，不知道以后遇到这样的题能不能想出来……

=== 0009 Guess a Function ===
题意：给定三个函数g(x), h1(x), h2(x)，其中{{{g(x) = x ^ (x / 2)}}}，h1和h2都是类似于{{{x - x % m + (x % m + s) % m}}}的形式的，但是h1和h2的s和m都不知道，现在已知x和g(h2(g(h1(g(x)))))的值（输入输出文件给定），求在1KB内解决本题。

解题报告：首先1KB的限制其实就是叫我们猜函数的s和m的值。注意到范围是345678，所以平方或立方的猜测应该都可以（立方的可能要跑几个小时……）。

比赛时我一直想搞这题，无奈搞不出来。比赛时我也想到的一点是，g(x)是可以简单地被消掉的（毕竟可以简单地看出是一个一一对应函数，看不出来的用Wolfram Alpha也该看出来了……），但是接下来就很不好搞了。

赛后听讲题和看报告才知道正确解法：首先枚举其中一个函数h1，然后可以消成类似y = h2(x)的形式，其中x和y都是已知的，那么题目就可以转变成如何判断对于给定x和y是否合法。
实际上观察函数的形式，可以得到：

'''y = x + s ( (x % m + s) < m )'''

'''y = x + s - m ( (x % m + s) >= m  )'''

当然这个东西非常难推，我比赛时推了半天没推出来，结果看着猛犸学长的解题报告又推了半天=_=

之后应该就比较显然了吧？关键看s2 m2有没有矛盾或多解。

最后就是跑了。我的机子（i5-2430M 2.4GHz）用单核跑了将近7分钟，如果分段的话大概需要2分钟左右，应该算是比较合理的范围吧。

这道题还是要赞的，就是1KB的限制有点限制做法。其实限制到10K左右会比较有意思，因为可以压缩做，又是一种不同的做法。

=== 0010 Maze ===
题目大意：给定一个K * N的矩阵，其中有很多列是相同的（只有M种矩阵），每个方格有三种状态：可以直着走、只能转弯走和不能走，求从左到右的方案数。

解题报告：这题是个比较显然的矩阵题，单独考虑每一列，将从哪一格进来作为行，哪一格出去作为列，那么对于一个给定的列的方案，可以构造出一个唯一的矩阵；那么对于一次行走，将所有矩阵乘起来，最后把所有格子的值加起来就是答案了（因为这表示“我可以出去”）。当然规模比较大，要用矩阵快速幂，然后由于标程写的比较牛逼，这题的时限也给的比较紧，在实现快速幂的时候要注意实现的方法。

=== 0011 Print Erased ===
题目大意：给定若干条折线段和若干个平行于坐标轴的矩形，以及矩形是“染色”还是“擦去”的两种操作之一，求最后染色的折线段的长度。

解题报告：这是一道很好的题目。首先不知道为什么厉害的学长们都开始矩形切割，反正我也不知道是什么……这个题正解就是对每条折线段分别枚举矩形处理操作长度，然后算出总长度，不过其实这里有很多细节很多难写的地方，我折腾了将近半个月最后还是只好看着[wiki:team2012-E1-mysol-0011 猛犸学长的解题报告]把题目写完了，罪过=_=。其实后面事件点的处理还算好写，就是前面那个求交点我搞半天还是没搞出来……

=== 0012 Versus ===
题目大意：老实说我木有看懂题目，大概就是有些人要比赛，给定了一些胜负关系，其中选人要用一个奇怪的规则来选（单调递增？），然后问能不能打败一半以上的人。

解题报告：看着像最长递增序列，于是比赛时直接翻了个代码写了交上去了……然后就过了。注意要用nlgn的（去年我的水题就不卡这个，于是觉得有点不厚道：））

=== 0013 Battle: Dojo ===
题目大意：给定一个N * M的格子，格子有可以走和不可以走的两种~~姿势~~形式，有一些不可走的格子上面有一些人，这些人在视线范围里会无视格子类型用眼神杀人（大雾），每一秒顺时针转一个方向，现在问从起始点到终点你最少要被眼神杀死几次（……），并且在前述条件下最少的时间是多少？

解题报告：比较裸的一道最短路，先将图分成4层，对每层图的每个格子处理出有多少个人的眼神能杀死站在这格子上的人，然后直接SPFA即可。SPFA的状态是(x, y, t)，其中(x, y)是坐标，t是哪一张图。看了猛犸学长的写法中有一个小技巧是用pair<int, int>直接比较，非常方便，又学会了新的姿势（……）

=== 0014 Balloon ===
题目大意：给定一个三维立方体，你要放置若干组球，球的中心要在立方体中间，每组球只能选一个，球的半径都是相同的，问最大的半径是多少。

解题报告：idea刚出来的时候被我pia到死，这个题太裸了（就是代码量有点略大）。简单的2-SAT（两个球选一个已经很明显了），剩下就是二分半径了（对于有可能碰撞的球，要加上一个约束关系）。

=== 0015 Kaguya's Game ===
题目大意：给定一棵树，树上的点可以被染成C种颜色，同时一条边两边的两个点不能是同一种颜色，每次询问一对节点（x, y），求（x, y）也要求不同色时，相比原来减少的合法方案数。

解题报告：这题就是那种“看着好像挺厉害实际水的够可以”的题目，我们首先不考虑加上的边而去考虑整棵树的染色方案数，很容易发现一个简单的性质：树的样子其实无关紧要，关键只在于树有多少个节点！对于N节点的树，方案数为{{{C * (C - 1) ^ (N - 1)}}}。这个性质下面还会用到多次。

接下来连上一条边后，实际上就是一个“章鱼型”的图：一个环，上面某些点长了一些枝丫。对于环的染色方案数其实很简单就能搞出来，需要手推一下一个公式，大概是{{{A[i - 1] * (M - 2) + A[i - 2] * (M - 1)}}}的样子，然后对于枝丫，套用上面我们对于N节点的树的结论就可以了。

总的复杂度是lgn级别的。

'''补充一下如何推公式：考虑一个环插一个点和插两个点的情况。'''

{{{
    int lca(int x, int y){
        int c=lv[x]-lv[y];
        if(c>0) for(int i=0;i<BIT;i++) if(+c&1<<i) x=fa[x][i];
        if(c<0) for(int i=0;i<BIT;i++) if(-c&1<<i) y=fa[y][i];
        if(x==y) return x;
        for(int i=BIT-1;~i;i--)
            if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
}}}

易错点：1、在Windows下会几率性爆栈，但实际上在Linux下什么也不会发生。标程用的是模拟栈的写法。

2、里面有很多可能会超long long的地方，要注意处理。

=== 0016 The Toy of Flandre Scarlet ===
题目大意：给定一个n*m*h的立方体，然后分割成若干个1*1*1的单位立方体，每个立方体上有一个数字，现在每次可以进行的操作是对某两个相邻（有一个面接触）的立方体同时加上或减去一个数，求有无可能使立方体所有数变成0.

解题报告：这题换到二维或许大部分就会做了，马甲还在用网络流真是不可思议。简单地对立方体黑白染色，就会发现每次操作必定操作的是一个黑色立方体和白色立方体，那么直接黑白的和加起来判断一下是否相等就行。另外prowindy学长用的是将所有数“推”到一个格子的做法，本质上来说是一样的，在此不再累述。

=== 0017 Cipher Lock ===
题目大意：给定一个N边形，这个N边形的顶点上都有两个属性(u, v)，规定一个合法的锁是N边形相领顶点上的属性值至少有一个是一样的，现在给定了8个点的初始值，求方案数。

解题报告：这题跟去年集训的一道题有点类似（依稀记得好像还在省赛出现过？）。这题的关键在于设计合理的dp状态，并且推出转移方程，进而通过矩阵进行加速。假如我们已经固定了两个点，那么中间点的状态只有四种，相对应的转移方程手推也能推出来（具体请参考肥羊学长的解题报告）。有了方程，就能写出转移矩阵，进而通过矩阵快速幂快速算出两个点之间的方案数，最后将方案数反复代入初值（初值也可以用一个矩阵来直接表示），算一圈就可以求出答案了。

=== 0018 Japanese Majhong I ===
题目大意：你是一个刚刚开始接触日麻的小朋友，现在你手上有13张牌，问你听的什么牌（有可能没听牌）

解题报告：这题的关键在于意识到递归的重要性。首先枚举听的牌，然后尝试分成4442的形式即可。

验题的时候我的写法非常暴力，导致用了20多秒才跑完，实际上将牌转换之类的操作是必须的，常数也要注意控制。

'''补充：我又重写了一个版本，这次跑了8秒多，然后改了一些细微写法上的问题优化进了2秒，汗……vector乱搞果然常数大……'''

=== 0019 Social Net ===
题目大意：~~~不想写了，这破题意~~~……还是得写。给定一个图，先求最大生成树，然后在最大生成树上处理若干个询问(x, y)，回答出max{c[j] - c[i]}, 其中c[]是一个点权数组，对于x -> y这条路径，j要在i的后面出现。

解题报告：首先这道是个原题我就不扯了，网上的解题报告也挺多的，建议先看完解题报告。求最大生成树就是Kruscal反着做一次（我猜数据是用边权唯一来控制生成树唯一的，但是有没有assert过呢？），然后由于被猛犸学长吐槽了我的LCA的模板，所以我学了猛犸学长的倍增写法，确实好写多了（不过目测常数好像大一点……），维护四个数组，然后对询问分段处理就可以了。具体可以看[wiki:team2012-E1-mysol-0019 猛犸学长的解题报告]。

=== 0020 Diablo III ===
题目大意：现在有N个怪物，其中有精英怪和大Boss，打一只精英怪会加一个Buff，打一只Boss假如有lv.5的Buff就掉一个宝物，你现在身上有无限个血瓶，打Boss的时候可以喝，已知Boss的血量、DPS和你的血量、DPS，求在掉最多宝物的情况下喝最少的血瓶。

解题报告：这题的两个dp应该比较明显：第一个dp是打boss时候消耗的血瓶，状态为f[i][j][k]，i为攻击力，j为怪物血量，k为自己血量，转移分三步：不喝、打之前喝、打之后喝。注意喝的时候判断一下怪物死了没有，还有自己被打死了没有。
第二个dp是关卡时候的判断，dp[i] = max(dp[i], dp[j] + 1), j <= i - 5。这里假如暴力的话是{{{O(n^2)}}}的，会超时，可以用一个单调队列维护。必须注意的是deque的操作不是线性的复杂度，有可能会被卡常数。

=== 0021 Driving Helicopter I ===
题目大意：一台直升机飞啊飞……可以在山峰上面飞。问最短距离是多少？

解题报告：裸的凸包。练习模板……

=== 0022 E - Cup ===
题目大意：给了一个小组赛的排名规则，问最后的排名。

解题报告：这题必须递归的处理，我的写法是用一个vector把队全塞进去，然后用两个函数反复处理中间的vector。如果知道净胜球可能是负数的话，这题应该不算特别难写。

=== 0023 Wagon ===
题目大意：给定N个货仓，每个货仓有A[i]的货物，现在有M部汽车停留在某些货仓上，要求所有货仓到离它最近的汽车的距离的和最小（距离相同取字典序最小的情况），货仓会搬运它自身的所有货物去离它最近的汽车上（如果有多个相同距离的汽车则任一皆可），求在前述限制下汽车的最小载货量是多少。

解题报告：这题题意不好理解，理解后可以发现这道题目实际上有两个问。对于第二问，其实二分贪心判断是可以很容易解决的。在知道汽车如何安排的情况下，只要先二分一个值，然后从左到右把货物塞进货仓中，对于相同距离的情况先塞左边再塞右边即可。问题的难度在第一问。其实假如不考虑字典序，那么我们有许多构造的方法，大概的思路都是想办法让货仓的距离相等，如果~~我们把棋盘翻转过来考虑~~我们反过来考虑，假如汽车放好了，往汽车之间平均地塞货仓应该怎么样塞呢？很简单，从右到左处理汽车，先在汽车右边放一个货仓，再在左边放一个，直至用完N - M个货仓为止就好了。很容易发现这样能够保证字典序最小。只要想到了这点，这题也就不难解决了。

=== 0024 Toy Blocks ===
题目大意：给定N个木块的位置和长度，每个木块能向左或向右推，推倒后x - l或x + l长度的方块也会被推倒，然后连锁反应，以此类推。求推的时间（1秒推1次，实际上是次数）。

解题报告：这题我完全不会做，所以是看着[wiki:team2012-E1-mysol-0024 猛犸学长的解题报告]做的。其中的核心是维护三个单调队列，其中两个处理出某个木块向左或向右最远到达的木块编号，第三个是一个dp方程的优化。dp中向右部分的转移非常科学，要用力研究。

== Homework 2 ==

=== 0025 Faster and Faster ===
据说神题不用做……

=== 0026 Kobe ===

=== 0027 Maze ===

=== 0028 E-Cup 2 ===

=== 0029 Challenge League ===

=== 0030 Sleeper's Schedule ===

=== 0031 Fairy Wars II ===

=== 0032 Harmonious Melody ===

=== 0033 Triangle Counting ===

=== 0034 Geek's Meal ===

=== 0035 Lightning Strike Array ===

=== 0036 Letty's Math Class ===
WA过这道题的都是⑨。真的。

=== 0037 Sid Meier's Civilization ===

=== 0038 Man VS Wild ===

=== 0039 GF And RP ===

=== 0040 E - Cup 3 ===

=== 0041 Wagon 2 ===

=== 0042 Electricity ===

=== 0043 Final Exam Arrangement ===

=== 0044 Starfruit ===

=== 0045 Average Score ===

=== 0046 LF2 ===

=== 0047 Gao the GridII ===

=== 0048 Aho's Problem ===

Profile

挫人土人一个。常用ID EZ_dla、Dai@NeverLand、dailongao及其他。吃货一枚。

目标是金牌。

Website：http://www.jiong3.cn

QQ：228804200

TEL：18620129908

Mail：dai@jiong3.cn

Homework

Homework1（DONE!）

第一轮感想

第一轮最难写的题绝对是Paint Erased……orz……

由于拖延症的原因拖到8/6号才完成了所有的题目，不过一天差不多能保证有一道，对状态的保持也有些好处。唉，还是偷懒了，集训要努力……

学姐好早就做完了，真是膜拜死我了。

特别感谢猛犸学长的解题报告。（……）

第一轮良心程度评价表

Group A：★★★★☆

Group B：★★★☆

Group C：★★★★

Group D：★★☆

0001 Kitty's Game

题目大意：给定一个有向图，每个点上有一个值Pi，当前Kitty有一个分数X，到达某个点分数变成LCM(X, Pi），如果分数不变就不能进入这个点，求到达N号点的同时有K分数的行走方法数。

解题报告：简单注意到走一步K是单增的，于是就是一个图上的简单的DP了。猛犸学长的代码中用map进行状态的维护，但其实用priority_queue之类的东西维护也是可以的。注意对无解条件的判断和处理，还有初始条件的判断。

易错点：对于中间有可能爆long long的地方要小心处理；还有是有向图而不是无向图……

0002 The Review Plan

题目大意：现在有N个章节要复习，一天复习一个章节，但是有M对约束关系（i, j），表示第i天不能复习第j个章节，求方案数。

解题报告：考虑如果没有约束关系，那么是N!种方案。现在我们考虑：假如计算的是符合约束条件的方案数，怎么样呢？那么我们可以“定下”某些约束关系在哪些天上，方案数就是（剩下天数）!。那么，考虑使用简单的排斥原理，Dfs处理即可算出答案，最后从n!减去即可。

排斥原理理论上还可以用2的m次方搞，但是这题会多上一个m的常数；猛犸学长的处理方法是用格雷码进行枚举，利用格雷码每次只会变化一个bit的性质把m的常数减去，比dfs慢4倍到10倍的样子，但仍然可以通过此题。真是有点厉害……

值得注意的是猛犸学长的方法应该就是本题最坏可构造数据的运行时间了。

易错点：(0)! = 1，最好中间处理都LL掉…… 还有重复情况的判断，否则容斥正负性就会发生问题。标程是错的，Rejudge过。

记录：格雷码生成公式：

r = 1 - n
i = __builtin__ctz(r);
s ^= 1 << i

0003 Decode

题目大意：给定一些码集，定义一个合法的码必须由码集里面的若干个码异或起来，求判断给定的码在改动至多三位的情况下是否是合法的码。

解题报告：这题比赛时将操作看错了，没看出是异或，囧，但正解也挺难想到的：注意到“由若干个码异或起来所得”很类似线性空间，这题其实就是在一个异或线性空间上判断一个向量是否在空间内。改动的三个位可以简单枚举而得，剩下就是判断某个码是否在空间内了。如果有了空间的一组基，那么就可以通过直接尝试扩张这组基看能否得到这个码，那么对码集高斯消元一次就可以得到我们所要的基了。

易错点：这题数据偏弱，我的高斯消元和判断部分写的不正确，但仍然通过了绝大多数的数据（只有一个询问是错的），事实上视写法的不同，基的储存和表达方式都要不同。还有注意字典序最小的要求。

上面关于线性代数部分的描述可能有误（猛犸学长的解题报告是在一个模2环上，但我一直觉得是在线性空间里……），恳请各位学长指正错误。我自己也会回头看看的……

0004 Ribbon Gymnastics

题目大意：给定4个圆的圆心，规定圆和圆之间不能相交，问半径和最大是多少。

解题报告：这是一个线性规划的模型，只要按照题意列出6条式子，再用单纯形模板直接解决即可。WF模板上的单纯形的init函数有误，需要自己手动初始化一些数组。

关于单纯形法，可以看2007年国家集训队论文“浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用”。

0005 Gao the Grid

题目大意：给定n * m的网格，求用网格点构造出来的三角形个数。

解题报告：这是一道论文题，具体做法可以用论文里面的分三种类型讨论三角形个数的做法，也可以用总三角形数减去不合法（共线）三角形数的方法。

易错点：long long就可以存下了不用高精度了呜呜呜……

0006 Cut the Tree 2

题目大意：给一棵树，求删掉一个点和它连着的所有边后形成的若干棵树的权值和。

解题报告：题目本身应该还是很水的，怎么搞都能过；就是加了一个高精度后比较恶心。听闻马甲是Java过的，真是无限敬仰……

易错点：似乎对高精度的速度要求比较高，比赛时手写的高精度超时了，orz……

0007 Alice's present

题目大意：爱丽丝是一个人偶使（大雾），然后有一些人偶，人偶后面贴着数字（……）。现在魔理沙生日了，于是爱丽丝决定选一个区间的人偶当礼物，她对于一个区间(i, j)会从右到左依次检查，如果有数字重复就是Unsuitable。回答询问（输出OK或者第一个重复的数字）

解题报告：一开始容易开始各种用数据结构，但是仔细想想应该是比较简单的吧？对每一个位子记录一个“当前位置最近的重复数字的位置”，然后O(n)地预处理一下（实际上还要用到map，还要多个lgn），然后直接判断来回答询问就可以了。

0008 Bounty hunter

题目大意：给定N个城市，你要依次从1 - N访问。在每个城市，你可以先以A[i]块/点的代价提升一次攻击力（可以是小数），然后打任务获得B[i] * atk（当时的攻击力）的金钱。问你最后离开第N个城市的时候能获得多少金钱。

解题报告：这题我是看了官方解题报告和猛犸学长的解题报告后写的，实质上就是倒着考虑，定义S[i] = sum(B[j]) (i <= j <= N)，然后不断地比较当前最优的S[i] - A[i]，如果更优就在这个城市提升攻击力。具体的证明方法应该也不用再多说了，参考解题报告似乎就行了（猛犸学长的意识流证明方法似乎不够严谨，vout学长的就比较科学了）。这题真是比较猎奇，不知道以后遇到这样的题能不能想出来……

0009 Guess a Function

题意：给定三个函数g(x), h1(x), h2(x)，其中g(x) = x ^ (x / 2)，h1和h2都是类似于x - x % m + (x % m + s) % m的形式的，但是h1和h2的s和m都不知道，现在已知x和g(h2(g(h1(g(x)))))的值（输入输出文件给定），求在1KB内解决本题。

解题报告：首先1KB的限制其实就是叫我们猜函数的s和m的值。注意到范围是345678，所以平方或立方的猜测应该都可以（立方的可能要跑几个小时……）。

比赛时我一直想搞这题，无奈搞不出来。比赛时我也想到的一点是，g(x)是可以简单地被消掉的（毕竟可以简单地看出是一个一一对应函数，看不出来的用Wolfram Alpha也该看出来了……），但是接下来就很不好搞了。

赛后听讲题和看报告才知道正确解法：首先枚举其中一个函数h1，然后可以消成类似y = h2(x)的形式，其中x和y都是已知的，那么题目就可以转变成如何判断对于给定x和y是否合法。

实际上观察函数的形式，可以得到：

y = x + s ( (x % m + s) < m )

y = x + s - m ( (x % m + s) >= m )

当然这个东西非常难推，我比赛时推了半天没推出来，结果看着猛犸学长的解题报告又推了半天=_=

之后应该就比较显然了吧？关键看s2 m2有没有矛盾或多解。

最后就是跑了。我的机子（i5-2430M 2.4GHz）用单核跑了将近7分钟，如果分段的话大概需要2分钟左右，应该算是比较合理的范围吧。

这道题还是要赞的，就是1KB的限制有点限制做法。其实限制到10K左右会比较有意思，因为可以压缩做，又是一种不同的做法。

0010 Maze

题目大意：给定一个K * N的矩阵，其中有很多列是相同的（只有M种矩阵），每个方格有三种状态：可以直着走、只能转弯走和不能走，求从左到右的方案数。

解题报告：这题是个比较显然的矩阵题，单独考虑每一列，将从哪一格进来作为行，哪一格出去作为列，那么对于一个给定的列的方案，可以构造出一个唯一的矩阵；那么对于一次行走，将所有矩阵乘起来，最后把所有格子的值加起来就是答案了（因为这表示“我可以出去”）。当然规模比较大，要用矩阵快速幂，然后由于标程写的比较牛逼，这题的时限也给的比较紧，在实现快速幂的时候要注意实现的方法。

0011 Print Erased

题目大意：给定若干条折线段和若干个平行于坐标轴的矩形，以及矩形是“染色”还是“擦去”的两种操作之一，求最后染色的折线段的长度。

解题报告：这是一道很好的题目。首先不知道为什么厉害的学长们都开始矩形切割，反正我也不知道是什么……这个题正解就是对每条折线段分别枚举矩形处理操作长度，然后算出总长度，不过其实这里有很多细节很多难写的地方，我折腾了将近半个月最后还是只好看着猛犸学长的解题报告把题目写完了，罪过=_=。其实后面事件点的处理还算好写，就是前面那个求交点我搞半天还是没搞出来……

0012 Versus

题目大意：老实说我木有看懂题目，大概就是有些人要比赛，给定了一些胜负关系，其中选人要用一个奇怪的规则来选（单调递增？），然后问能不能打败一半以上的人。

解题报告：看着像最长递增序列，于是比赛时直接翻了个代码写了交上去了……然后就过了。注意要用nlgn的（去年我的水题就不卡这个，于是觉得有点不厚道：））

0013 Battle: Dojo

题目大意：给定一个N * M的格子，格子有可以走和不可以走的两种姿势形式，有一些不可走的格子上面有一些人，这些人在视线范围里会无视格子类型用眼神杀人（大雾），每一秒顺时针转一个方向，现在问从起始点到终点你最少要被眼神杀死几次（……），并且在前述条件下最少的时间是多少？

解题报告：比较裸的一道最短路，先将图分成4层，对每层图的每个格子处理出有多少个人的眼神能杀死站在这格子上的人，然后直接SPFA即可。SPFA的状态是(x, y, t)，其中(x, y)是坐标，t是哪一张图。看了猛犸学长的写法中有一个小技巧是用pair直接比较，非常方便，又学会了新的姿势（……）

0014 Balloon

题目大意：给定一个三维立方体，你要放置若干组球，球的中心要在立方体中间，每组球只能选一个，球的半径都是相同的，问最大的半径是多少。

解题报告：idea刚出来的时候被我pia到死，这个题太裸了（就是代码量有点略大）。简单的2-SAT（两个球选一个已经很明显了），剩下就是二分半径了（对于有可能碰撞的球，要加上一个约束关系）。

0015 Kaguya's Game

题目大意：给定一棵树，树上的点可以被染成C种颜色，同时一条边两边的两个点不能是同一种颜色，每次询问一对节点（x, y），求（x, y）也要求不同色时，相比原来减少的合法方案数。

解题报告：这题就是那种“看着好像挺厉害实际水的够可以”的题目，我们首先不考虑加上的边而去考虑整棵树的染色方案数，很容易发现一个简单的性质：树的样子其实无关紧要，关键只在于树有多少个节点！对于N节点的树，方案数为C * (C - 1) ^ (N - 1)。这个性质下面还会用到多次。

接下来连上一条边后，实际上就是一个“章鱼型”的图：一个环，上面某些点长了一些枝丫。对于环的染色方案数其实很简单就能搞出来，需要手推一下一个公式，大概是A[i - 1] * (M - 2) + A[i - 2] * (M - 1)的样子，然后对于枝丫，套用上面我们对于N节点的树的结论就可以了。

总的复杂度是lgn级别的。

补充一下如何推公式：考虑一个环插一个点和插两个点的情况。

    int lca(int x, int y){
        int c=lv[x]-lv[y];
        if(c>0) for(int i=0;i<BIT;i++) if(+c&1<<i) x=fa[x][i];
        if(c<0) for(int i=0;i<BIT;i++) if(-c&1<<i) y=fa[y][i];
        if(x==y) return x;
        for(int i=BIT-1;~i;i--)
            if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
        return fa[x][0];
    }

易错点：1、在Windows下会几率性爆栈，但实际上在Linux下什么也不会发生。标程用的是模拟栈的写法。

2、里面有很多可能会超long long的地方，要注意处理。

0016 The Toy of Flandre Scarlet

题目大意：给定一个n*m*h的立方体，然后分割成若干个1*1*1的单位立方体，每个立方体上有一个数字，现在每次可以进行的操作是对某两个相邻（有一个面接触）的立方体同时加上或减去一个数，求有无可能使立方体所有数变成0.

解题报告：这题换到二维或许大部分就会做了，马甲还在用网络流真是不可思议。简单地对立方体黑白染色，就会发现每次操作必定操作的是一个黑色立方体和白色立方体，那么直接黑白的和加起来判断一下是否相等就行。另外prowindy学长用的是将所有数“推”到一个格子的做法，本质上来说是一样的，在此不再累述。

0017 Cipher Lock

题目大意：给定一个N边形，这个N边形的顶点上都有两个属性(u, v)，规定一个合法的锁是N边形相领顶点上的属性值至少有一个是一样的，现在给定了8个点的初始值，求方案数。

解题报告：这题跟去年集训的一道题有点类似（依稀记得好像还在省赛出现过？）。这题的关键在于设计合理的dp状态，并且推出转移方程，进而通过矩阵进行加速。假如我们已经固定了两个点，那么中间点的状态只有四种，相对应的转移方程手推也能推出来（具体请参考肥羊学长的解题报告）。有了方程，就能写出转移矩阵，进而通过矩阵快速幂快速算出两个点之间的方案数，最后将方案数反复代入初值（初值也可以用一个矩阵来直接表示），算一圈就可以求出答案了。

0018 Japanese Majhong I

题目大意：你是一个刚刚开始接触日麻的小朋友，现在你手上有13张牌，问你听的什么牌（有可能没听牌）

解题报告：这题的关键在于意识到递归的重要性。首先枚举听的牌，然后尝试分成4442的形式即可。

验题的时候我的写法非常暴力，导致用了20多秒才跑完，实际上将牌转换之类的操作是必须的，常数也要注意控制。

补充：我又重写了一个版本，这次跑了8秒多，然后改了一些细微写法上的问题优化进了2秒，汗……vector乱搞果然常数大……

0019 Social Net

题目大意：~不想写了，这破题意~……还是得写。给定一个图，先求最大生成树，然后在最大生成树上处理若干个询问(x, y)，回答出max{c[j] - c[i]}, 其中c[]是一个点权数组，对于x -> y这条路径，j要在i的后面出现。

解题报告：首先这道是个原题我就不扯了，网上的解题报告也挺多的，建议先看完解题报告。求最大生成树就是Kruscal反着做一次（我猜数据是用边权唯一来控制生成树唯一的，但是有没有assert过呢？），然后由于被猛犸学长吐槽了我的LCA的模板，所以我学了猛犸学长的倍增写法，确实好写多了（不过目测常数好像大一点……），维护四个数组，然后对询问分段处理就可以了。具体可以看猛犸学长的解题报告。

0020 Diablo III

题目大意：现在有N个怪物，其中有精英怪和大Boss，打一只精英怪会加一个Buff，打一只Boss假如有lv.5的Buff就掉一个宝物，你现在身上有无限个血瓶，打Boss的时候可以喝，已知Boss的血量、DPS和你的血量、DPS，求在掉最多宝物的情况下喝最少的血瓶。

解题报告：这题的两个dp应该比较明显：第一个dp是打boss时候消耗的血瓶，状态为f[i][j][k]，i为攻击力，j为怪物血量，k为自己血量，转移分三步：不喝、打之前喝、打之后喝。注意喝的时候判断一下怪物死了没有，还有自己被打死了没有。

第二个dp是关卡时候的判断，dp[i] = max(dp[i], dp[j] + 1), j <= i - 5。这里假如暴力的话是O(n^2)的，会超时，可以用一个单调队列维护。必须注意的是deque的操作不是线性的复杂度，有可能会被卡常数。

0021 Driving Helicopter I

题目大意：一台直升机飞啊飞……可以在山峰上面飞。问最短距离是多少？

解题报告：裸的凸包。练习模板……

0022 E - Cup

题目大意：给了一个小组赛的排名规则，问最后的排名。

解题报告：这题必须递归的处理，我的写法是用一个vector把队全塞进去，然后用两个函数反复处理中间的vector。如果知道净胜球可能是负数的话，这题应该不算特别难写。

0023 Wagon

题目大意：给定N个货仓，每个货仓有A[i]的货物，现在有M部汽车停留在某些货仓上，要求所有货仓到离它最近的汽车的距离的和最小（距离相同取字典序最小的情况），货仓会搬运它自身的所有货物去离它最近的汽车上（如果有多个相同距离的汽车则任一皆可），求在前述限制下汽车的最小载货量是多少。

解题报告：这题题意不好理解，理解后可以发现这道题目实际上有两个问。对于第二问，其实二分贪心判断是可以很容易解决的。在知道汽车如何安排的情况下，只要先二分一个值，然后从左到右把货物塞进货仓中，对于相同距离的情况先塞左边再塞右边即可。问题的难度在第一问。其实假如不考虑字典序，那么我们有许多构造的方法，大概的思路都是想办法让货仓的距离相等，如果我们把棋盘翻转过来考虑我们反过来考虑，假如汽车放好了，往汽车之间平均地塞货仓应该怎么样塞呢？很简单，从右到左处理汽车，先在汽车右边放一个货仓，再在左边放一个，直至用完N - M个货仓为止就好了。很容易发现这样能够保证字典序最小。只要想到了这点，这题也就不难解决了。

0024 Toy Blocks

题目大意：给定N个木块的位置和长度，每个木块能向左或向右推，推倒后x - l或x + l长度的方块也会被推倒，然后连锁反应，以此类推。求推的时间（1秒推1次，实际上是次数）。

解题报告：这题我完全不会做，所以是看着猛犸学长的解题报告做的。其中的核心是维护三个单调队列，其中两个处理出某个木块向左或向右最远到达的木块编号，第三个是一个dp方程的优化。dp中向右部分的转移非常科学，要用力研究。

Homework 2

0025 Faster and Faster

据说神题不用做……

0026 Kobe

0027 Maze

0028 E-Cup 2

0029 Challenge League

0030 Sleeper's Schedule

0031 Fairy Wars II

0032 Harmonious Melody

0033 Triangle Counting

0034 Geek's Meal

0035 Lightning Strike Array

0036 Letty's Math Class

WA过这道题的都是⑨。真的。

0037 Sid Meier's Civilization

0038 Man VS Wild

0039 GF And RP

0040 E - Cup 3

0041 Wagon 2

0042 Electricity

0043 Final Exam Arrangement

0044 Starfruit

0045 Average Score

0046 LF2

0047 Gao the GridII

0048 Aho's Problem