Classification.txt

简单题
#1001	-____-b  A+B。
#1105	烟雾题，其实双行线的图直接按照DFS路线肯定是一个欧拉回路。因此，只需要统计所有边长除以20km/s再除1000m/km就得到小时数。
#1110	Dick and Jane 胡乱枚举收缩一下情况就可以了。
#1115	a[i+1] = a[i] 的全部数位上的加起来，直到剩下一个，直接模拟。
#1414	太弱太弱，按照模 4 分类讨论一下即可。
#1631	星际争霸，水题，但题目极度有病，注意输入顺序是 name HP Armor Cool Amount Power
#1681	一个特殊的背包问题，求一个立方数加一个四面体数的背包。其实只需要用一个 set 保存所有的组合即可。假设最大输入是 N，则复杂度为 O(N^2/3)，完全可以胜任。
#1713	简单的字符串截取和字符计数。
#1716	简单的二维数组区间求和，作累加，然后容斥一下；预处理 O(W*H)，查询 O(1) 顶多 (W-w)*(H-h) 次查询。
#1745	简单的 hotter colder，滚动输入，判断一下远近即可。
#1847	该属于简单题，但涉及一个取整或许有所麻烦，精确解应该是求出平均值，再求偏差绝对值和除 2。这里由于精确到分，求出平均值 mean，按分求出 ceil 和 floor 的值。然后对于每个人，若钱 < mean，求与 floor 偏差绝对值加到总和中，否则与 ceil 求。另外，记录偏差(不取绝对值总和)，如果最后总偏差不为 0，要将总偏差绝对值加到总和中。最后输出总和一半即可。
#2104	-____-b 非一般水型，输入若干个字符串，统计最多的那个输出，喜欢怎么乱搞都行。
#2176	车速限制，相当的水。
#2183	水题，读清楚题目就好，输出严格大于一半人判 simple 的，没有人判 hardest 的，注意格式和没有的时候，太水了。
#2186	-____-b 只输入三个数，找出第一个 <= 168 的数。
#2201	-____-b 太他妈水了：while(cin >> a >> b) puts(a >= b ? "MMM BRAINS" : "NO BRAINS");
#2207	字符的重排，直接把字符矩阵还原再变一下枚举次序即可。
#2220	天花板和狗，很水的问题，直接蛮力枚举钉子坐标。注意他是不管绳子长度最优的，只管 x 最优，y 次优，合法即可。
#2321	足球队球员选择，很简单，就是 if-else 一下即可。
#2358	求一个整数是否能表示成某些阶乘数的和，简单枚举即可，注意题目描述比较阴险，一个负数作为结束(不是-1)，不然会 WA 死的。
#2388	知道 x-y 和 x+y 求 x 和 y，(x>y)，相当弱啦。
#2405	求一个范围内满足某些性质的数的列表，枚举+判定即可。
#2417	-____-b  求一个整数的最低非 0 二进制位。
#2476	带点格式输入输出的 a+b，怎么说也还是 a+b。
#2478	数手指的玩意。
#2480	矩形覆盖问题，由于规模很小，蛮力即可。注意，点击一个窗口不会使它置顶。
#2481	将该序列排序，去重之后输出。
#2482	二进制 IP 转 10 进制，没啥意思。
#2514	简单的字符替换。
#2548	相当简单，课程编号不超过 10000 直接寻址就可以。
#2554	简单，直接枚举一下所有的点判分即可。
#2659	求六个矩形是否能拼成一个正六面体。
#2679	很弱的虫食算，直接蛮力穷举也就是 O(90)。
#2722	说白了就是求二对数，也就是最高位为 1 的位数。
#2736	-____-b  完全没有难度。
#2744	求一个串有多少个子串是回文，数据比较弱，直接枚举各个字母(一个或相邻两个)作为回文中心向外扩展计数。
#2773	简单的一个公式求和，也可以选择根据递推求出通项：(X^4+6*X^3+11*X^2+6*X)/8 。
#2781	按最高位取整。没啥说的。
#2795	判断一个序列的置换是否跟它本身相等。
#2807	求插座总共能提供的接口数，可见，原来墙上有一个主插口，加上所有插板的孔数，减去插板数，也就是说，结果为 1+Sum(S[i]-1)，S[i] 为第 i 个插板的孔数。
#2812	-____-b  小学生都会做的求和。
#2830	很明显一场淘汰掉两个，因此一共有 N/2 场。
#2850	如题，直接扫描一下是否一个也没有或者有两个相邻的即可，但本题有变态版。
#2857	弱智，对每个格子求三个数的平均数。
#2886	他叫干啥就干啥吧，没啥好说的。
#2932	简单的字符替换，也就甭提了。
#2947	考察一组串的开头字母拼起来是否一样，弱智题。
#2965	太简单了，怎么搞都过，直接枚举模拟到 800 即可，因为明显 700~799 都是 CocaCola，已经可以满足输入范围了。
#2970	一个序列求最大/最小值，太弱，奥运专栏。
#2987	-____-b  不说啥了，一个字符串删掉中间一个再输出来。
#2988	也没啥好说了，公制转换，一乘一除收工。
#3100	-____-b  超水肉题，求和剔除最大最小值求平均。
#3023	换一张牌使得总和相等，先求出差值，然后枚举一下就行，n 只有 100，很水。
#3121	简单模拟，字母重排。
#3124	*____*?  绝对有病的题！！！我题目都没读懂他想怎么样，然后输出 = 输入 AC!! 你说有病不有病？！
#3163	苹果题，x 和 y 不用管输出 n-1，如果是 0 输出 0。
#3174	简单题，求给定年份之间存在多少个月，使得月份的平方等于年份的后两位或者后三位，直接枚举年月然后判定，计数即可。
#3191	根据时针的角度判断时钟所指的时间段，简单的角度转换即可解决。
#3202	-____-b  水题，求数组的最大值所在位置，以及第二大的值是什么。
#3210	判断序列经过栈的处理还是经过队列的处理。如果系列相同，则为队列，如互为回文，则为栈。
#3295	简单题，问一个 2^N 个选手的全淘汰赛，一个人最多和最少能赢多少局，算法不说自明。
#3311	ZOJ串检验，逻辑等价变换，命题等价于：有且仅有一个 Z，有且仅有一个 J，J 在 Z 后面且不能紧跟在后面，另外，中间夹杂的三段 O 分别有 a, b, c 的长度，必须满足 a + b = c。
#3313	输出每天时针与分针角度 < 给定角度的秒数。用相对运动的角度分析，由于是循环对称的，因此夹角为某一度的时间都是均等的，因此，直接 x/180*86400 即乘以 480 可得到结果。

模拟
#1071	恶心模拟题，到了什么程度了捏？一个晚上，一道题交出了所有的错误。。算法：从 ? 开始，跟着路径往前走，碰到 o 记录一次反转；碰到 ) 和 > 插入一个节点，然后构造二叉树；构造完之后再读入字符串后序求值就行了，中间处理细节做得想吐。
#1072	模拟指令机器，纯粹模拟，把我调戏得好痛苦啊~~
#1111	有点小麻烦的模拟题，梭哈，同花顺，两手牌比大小。以不变应万变是上策。
#1122	时钟指针追赶问题，把相对位移，相对速度想清楚，再用时间求出结束位移模一下圈的格数即可。
#1189	简单题，字串演变循环，直接模拟迭代即可。
#1404	油管最优布局，中级模拟题，对算法要求不高，直接蛮力即可。注意一下布局框的计算、坐标的位置等即可，注意题目说最北的坐标必须顶格，也就是说如果左侧坐标最大值 < 10 的话左侧坐标只需要留一个位置。
#1493	音频压缩，直接模拟，注意输入输出可以用格式化 %x 的方式实现省代码。
#1575	普通的分形模拟，怎么搞都行。
#1717	DP，每个格子存放一个最优字符串，确定一个字符串"更优"的比较函数，即可不断更新到当前字符位置的最长字符串。
#1720	简单模拟，多项式的格式输出，先把各阶的基数用字符串存好，然后直接拼接，另外特殊情况稍加处理即可。
#1764	简单模拟，编程竞赛记分，只要求输出最后胜出者的题数和 penalty。
#1804	推箱子，推土机，并不繁琐的模拟。注意读题，如果出现位置不够，推土机会被顶停。
#1916	时区转换，就是字符串形式的时间和分钟数之间的转换。实际时间表示上，如果对 am-pm 的时间表示方式不是太熟悉的话，搞起来有点恶心。时区的输入处理稍要技巧，手工打一个表然后 map 就差不多了。
#1975	画分形图。类似于 2423 的做法即可。
#2108	模拟电梯的运行，策略是给定的，因此直接模拟即可。
#2161	蜂巢状直接最短路，先按照序号求出坐标，这可以参照 1954 Bee Maja，然后根据两个坐标求出最短的两段折线构成的路径。假设两段路径长度为 a 和 b，那么结果是 C(a, b)。
#2164	洗牌，简单模拟题，不用多想，直接硬搞。
#2173	流布局，很水的模拟题。
#2183	比较水的模拟，读清楚题目就好。
#2187	图像缩放，超简单模拟题，几层 for 就可以搞定的事。
#2235	策略已经给出，那么直接模拟就可以了。
#2240	字符串压缩：恶心英语阅读题，比较水，具体翻译的规则见标程注释。
#2311	同 2971，英文句子转阿拉伯数字。
#2312	蘑菇题，画板的模拟，关键在于字符的组合规则，先把字符的组合规则包成函数，然后画一个字符上去就只须与原来的字符组合就行了。
#2409	纸牌的蘑菇题，创建比较准则，生成所有排列并检验即可。
#2420	给出某一天是几年几月几日星期几，然后问它后面的第 n 天是几年几月几日星期几，模拟硬搞就是。
#2423	画一个分形图，一个便宜的做法是，先把字符矩阵全部生成出来，放在内存里，然后再输出左上角的子阵。
#2495	五子棋局势判定，枚举起始点，然后对于每个点检测是否(右/下/坐下/右上)具有连续的棋子即可。
#2508	小蘑菇一道，Windows 的窗口点击。枚举即可，需要注意的是连击的逻辑关系。
#2529	特殊进制加法，直接用 vector 运算进位，每位的进位权注意就行。
#2521	模拟足球联赛积分，只是操作上有一点麻烦，也比较简单。
#2571	字符串解压缩，可以用递归来解开，然后直接输出。
#2572	中文字，连通块搜索，注意各个字符表示的传递方向做个方向表 DFS 就好了。
#2593	英语阅读+超级蘑菇，编程竞赛排名的模拟，读清楚那些麻烦的规则，然后一点一点写就是。
#2613	竞标，如果一个价格有多个人竞标，该价格无效，选取竞标价唯一的竞标胜出，否则，冲突数最少的价格胜出，胜出者为第一个竞标该价格的人。
#2635	矩阵索引加密，把矩阵生成出来转置读取就行了。
#2680	角度的转化，比较明显，要考虑到时针非整格的情况，但千万不要用浮点就是了，宁可整倍扩大，否则会引入精度误差。
#2731	Josephu 问题变种，先模拟，模拟到当前要杀掉 Josephus 的时候停止，然后，假设剩下 x 个，那么用 J 函数求出 x-1 剩下最后一个的编号是多少。详见代码注释。
#2732	典型英语阅读 + 模拟，规则很繁琐，但是没什么算法的。具体规则翻译见代码注释。
#2741	关于足球越位规则的判定，注意如下几点：1. 用浮点；2. 输入之间可能有相当多的多余空格；3. 在自己的半场，理解为 x<=0 。
#2743	泡泡龙，不是很难的，搜索一下连通块即可。
#2772	剩下的钱里面，优先先提取最大面值的硬币，容易证明这样贪心的最优性。
#2782	直接模拟各个操作即可。
#2814	简单模拟，读懂题就好，给一个字符串，按照不同的间隔 D 为等级抽取所有字符对，假如在所有等级中这样的对没有重复的，就是 surprising，反之不是。
#2831	蘑菇版 A+B，除了硬搞还是硬搞了。
#2835	幻方验证，没什么好说的。
#2840	模拟搜索，枚举一遍所有文件检查是否符合即可。
#2851	文本扫描，删除不必要的空白字符，看题吧，很水。
#2892	小波变换，相当于加密，给出规则和暗文求明文。
#2902	十滴水小游戏，用个任务队列乱搞即可。注意空格中或者玩家水箱中没水时，操作要忽略。 
#2910	足球计分，格式上处理也有一定麻烦，总体来说也不难搞。
#2934	因为总是会循环的，因此把所有情况都走一遍就好，最坏不过 2^16。
#2954	给出一组汉诺塔操作序列，输出结果状态，简单。
#2958	纯蘑菇题，求可能的数码组表示，反正用巧妙点的方法就可以避免复杂的代码。其中一个技巧就是用 9 个二进制位表示一个数码。于是就可以通过位与求知一个数码是否能由另一个数码识别错误而来的。
#2971	英文单词数字转阿拉伯数字，比较好搞啦，不过有个变态版本，2698。
#2989	螺旋加密，注意找个好的枚举方法就行。
#2990	螺旋解密，同上，这两题都不难搞。
#2992	猴子天平，结论很简单，最大深度为 h，结果就是 2^(h-1)
#3009	Excel，记忆化搜索，记录每个格子的串或值进行递归，比较烦琐。
#3048	模拟消除方块的游戏，记得以前那个快译通的机子上玩过，直接 DFS 最大的连通块消掉然后方块下落，如果有空行右边向左平移，跟 3055 有点像，稍为简单一点。
#3050	七段码识别数字，用 set 记录所有线段，根据线段的数目和查找某些特定位置的线段是否存在进行判别。
#3052	机器人与垃圾堆：1.分象限处理，2.对于垃圾堆，删除它能影响到的机器人，3.碰撞事件队列判断。详见解题报告。
#3055	对对碰，考虑方块的下落，模拟整个过程，难度一般。
#3106	成绩预测，注意输入输出，读明题意之后蛮力即可，没什么难度，新预测过的成绩并不需要追加到历史档案中。
#3109	解密，螺旋重排。
#3151	模拟题，判断两个骰子是相同的或者镜像关系还是完全不同的。第一步就是读入，将骰子类构造旋转的函数，然后用 DFS 每次将骰子按指定方向旋转之后将数字填在顶面。将骰子读入之后，通过旋转枚举所有面向上，然后在作四次旋转跟另一个骰子比较。
#3179	算盘，先按照算盘形状读出实际数字，然后再验证即可，比较简单的一道题。
#3220	DotA 称号提示，纯蘑菇题，用对象包起来好些的话优美一点。
#3240	模拟俄罗斯方块，直接暴搜，加一点剪枝条件即可。
#3290	简单题，构造最长递增序列拆分，按照 a(n+1) = a(n) * 2 + 1 构造，有剩的全部加到最后一个就是了。 
#3317	酒店订房，先把进入事件和退出事件分拆开放到一个序列里，按时间先后排序。然后直接模拟即可。

搜索
#1008	经典搜索，压缩数值完全相同的方块即可 AC。
#1118	多维空间搜索，其实也就是一般的图 dfs，只要做一个映射。这里我是硬搞的。
#1505	跳棋，状态压缩广搜，时间差不多，应该刚刚好的。
#1598	国际象棋，单后杀王，把可达格子枚举一下状态就行，8X8 很好对付。
#1832	字符串搜索，把一组字符串配对，使得合并之后相同。先对所有串 V[N] 字典序排好序，枚举前缀V[i]，那么必须 V[i] 是 V[i+N/2-1] 的前缀，否则剪掉，然后找到长度能与 V[i] 配对的后缀 V[j]，得到 Pattern，然后 DFS 回溯验证。
#2100	播种，本质是一个哈密顿路的问题，范围还比较小，直接 DFS 一下可以过。
#2103	周游路线，NP 的搜索，注意搜索的起点和回溯的条件，如果有奇度点，则必从奇度点开始搜索。
#2165	地图连通块搜索，BFS 或者并查集都行。
#2203	搜索 + 剪枝：求一个 1..n 的排列，使得任意相邻 2..d 个数之和均为素数。
#2207	中位排列，给 5 个字母的排列，求某个排列使得它到所有给出的排列距离最短，直接枚举所有排列即可，这用 STL 的 next_permutation 硬来最好了。
#2243	笛卡尔树的构造，有线性的方法，详细方法参见 TopCoder 算法教程里面 RMQ & LCA 那篇文章有介绍。
#2274	好变态，一直都是在优化一个常数因子：构造一个图邻接矩阵 X[1..N][1..N]，X[i][j] 表示 A[i] A[j] 是否互质；同时构造一个邻接表存 X[i][j]==true 的部分 和 X[i][j]==false 的部分。然后枚举顶点 i，从邻接表中枚举另外两个 j,k，看邻接矩阵 j,k 是否相邻 
#2406	求一个图从源到汇的所有长度不超过限制的路径，并按长度排序输出，直接蛮力回溯所有路径即可，然后存储路径之后排序输出。
#2412	地图 DFS 变种，决定一个点是否能通向另一个点的充要条件取决于这两个相邻的点。
#2416	开密码盘最少需要多少步，BFS 一下就完了。
#2418	要枚举所有行的不同移位方案的组合，最多 n^n 种，但是要剪枝：1. 第一行可以不动，总是移位 0；2. 再求值的时候增加分支限界，当某一列总和大于现有结果，直接 break。
#2512	对称的项链，枚举中心位置向两边检查就是了。
#2520	格雷码的生成，简单 dfs 一下就可以了。
#2576	问题可以转化为求 2 * k 的所有切分，使最大的小于等于 k，用 DFS 可以生成出所有的组合。
#2580	9*9 数独求解，回溯，注意搜索的时候注意次序，总是填不同的选择数最少的，这样才能比较快。
#2730	DFS 回溯所有状态，把相邻两个珠子的颜色配对作为状态标记进行回溯。
#2734	规模极小，直接 DFS 回溯一下就过了。
#2891	bt++ 的搜索，基本是 DFS，然后先枚举长度（从大到小），然后判别，标记上用排列，n! 可以，标记禁止的长度。注意题意：1. 必须由两根以上拼接；2. 不可以有开断相同的地方。
#2922	炸弹，记忆化搜索，比较简单。
#2925	多米诺骨牌，只能用 BFS，DFS 是错的。
#2936	访问权限，英语阅读题，动态维护：大写字母代表文件，小写字母代表用户，问最后权限的分布，其实很简单。
#2938	打水漂，没啥难的，枚举一下参数就好。
#2951	环形物资传递：求最小的传递代价。反正在最优的策略下，必定有一条路径没有传递。枚举这条路径都计算一次就行了，O(n^2) 的复杂度。还可以归约成最小费用最大流来做。
#2977	蛮力枚举第一行的情况，然后剩下的就唯一确定了，需要加位运算优化。
#3010	开灯关灯游戏，硬枚举所有组合状态，2^N。
#3059	广搜，关键在于骰子状态的表示，用 top 和 north 的排列作为状态即可。可以预处理出各个状态向四面滚能够到达的状态，然后 BFS 即可。
#3094	敢死队，很经典的一道题，二分 + BFS。首先需要做一个预处理，处理出每一个格子离最近的敌营的距离：这可以通过对所有敌营入队列 BFS 得出。然后二分一个最近距离，这个结果应该处于 0 到 X + Y 之间。对于二分的每一个值 bound，从起点 BFS 到终点。可走的点为所有到敌营距离 >= bound 的格子。这样就可以二分了。
#3110	入门级 dfs，三维的地图，种子填充法。
#3158	切蛋糕，dfs 枚举出所有状态，注意，每一行两边都必须有蛋糕(不能一边没有)。
#3196	算是一道比较水的搜索题，关键在于用 dfs 暴力找出所有可能的符号排列。

贪心
#1117	经典贪心，哈夫曼编码。
#1184	硬币称重，经典，1.若被判平，左右所有球必正常；2.若判轻或判重，对应球被判轻、重记数+1；3.只有球只被判轻或判重，且次数跟天平不平衡次数相等，该球才能是坏的，否则必然是好的。
#1409	求最佳带宽价格比，其中带宽为所有组件的带宽最小值，价格为各个组件价格总和，用贪心即可：记录所有可能的带宽，然后枚举带宽求最优价格值，直接贪心得到当时的比例更新最大值。
#1543	将原式稍微展开，发现各个数字分别被开方了 N 次，N-1 次...剩下因子是不变常数。因此贪心让大的数先结合，预排序即可。 
#2067	数矩形，保存每个格子同以行往右最多的白格子数(包括自身)，然后作 O(n^3) 的枚举。
#2109	肥老鼠系列：简单的贪心即可，从最大比例的入手。
#2229	骑车上学，贪心，O(n)，枚举所有车子，如果：1. 开始时间 < 0 的，不予考虑，太快的赶不上，太慢的赶上也没用。2. 开始时间 > 0 的，Charley 和最早到达的车子一起到达。
#2256	计程车计费的策略，怎么坐最便宜：当有整 8 公里以上，换成 18 块钱。有剩下的，如果剩下 5 块以下，按 2.4 块每公里算。当然，这里必须是在输入为 8 公里以上才能这样算。否则的话，按照先跑 10 公里，再跑 2 元每公里算。
#2376	所有蚁碰头后不改方向互换身份，因此等价于只会直走互相穿透。
#2397	田忌赛马，经典的贪心，具体见解题报告。
#2422	1985 的升级版，现将本题形象化，就是一组并排矩形包含的最大矩形面积，用两个栈，来回扫一遍即可。
#2433	如果 N <= 3 无法达到，否则，修的高速公路肯定是 1..i 和 i-1..n，这样，只需恰当选取 i 令 i-1..i 这段路最短即为最优。
#2488	排序之后贪心，假设前 i-1 根都断了，那么剩下重量取决于第 i 根，并且，加入剩下的 n-i 根，那么当前的承重为 A[i]*(n-i)，扫描一遍求出这个最大值即可。
#2511	很水很直白，直接加起来，然后贪心取最大就行了。
#2536	背包，先将现有的砝码全部背包一次，然后每增加一个砝码，就取最小的不符值作为新的砝码加入再背包，所有砝码加完之后剩下的不符值就是结果。不过这样做很慢的，也是刚刚够时间和内存。
#2581	找出一条欧几里德图的最短周游回路，满足：先只往右走到最右点，再走回最左点，要覆盖所有点，求最短回路长度。具体贪心方法见程序注释。
#2585	回文距离，简单的统计各个字母出现次数，统计差别数的绝对值求和即可。
#2592	把从头累加的数组 FD[] 和从尾累加的数组 BK[] 求出，并且求出某个位置往前 FD[] 的最小值，往后 BK[] 的最大值，然后枚举 j 判别即可，详见程序注释。
#2642	堆栈贪心法，给一个数组 A[N]，对于区间 i, j 之间，函数 f(i, j) = SUM(A[i..j]) * MIN(A[i..j])，求 MAX(f(i, j)), 0 <= i <= j < N。首先，对数组求和预处理，于是可以 O(1) 得到区间的求和。然后，用堆栈贪心法：求出第 i 个元素左边第一个比它小的下标 L[i]，和右边第一个逼它大的下标 R[i]。预处理 O(N)，现在可以求出最小值是 A[i] 时的最宽区间即为 L[i]+1..R[i]-1，然后枚举 i，求最大的 A[i] * SUM(A[L[i]+1..R[i]-1])，O(N) 可以处理完毕。 
#2656	要从某个站开始直到结束，油量保持为正即可。可以用堆栈做到线性的处理，具体解释见程序注释。
#2658	可以证明，假设所有 A~Z 的字母统计数序列为 C[k]，对 C[k] 排序，两个序列是 YES 的充要条件是已排序 C[k] 和 C'[k] 完全相同。
#2670	构造一个贪心算法的反例，其实不难想出，看程序注释有一种构造方法。
#2688	很巧妙的一道最优化题，大概可以列入贪心的范畴。题目要求一个 5 维空间的 Manhattan 距离 N 点最远点对距离，可以用 O(2 ^ 5 * N) 的方法解决。详见解题报告。
#2878	明显，找到最大的铺号 max，最小的铺号 min，Michael 将车停在这区间内任一个地方，最少刚好走 2*(max-min) 的距离。
#2883	明显全部要买，并且折扣的个数有且仅有 N/3 个，于是先排序，然后贪心从大往小取，每次取 3 个。
#2921	股票买卖：经典的贪心，先记录所有档案，然后从尾到头遍历；遍历之前创建一个优先队列，存放当天之后剩余的价格 p 和剩余可卖出数为优先级的所有档案。每遍历一天，加入当天价格和可卖出数到优先队列，然后将当天买入的股票卖完：一直从优先队列中取档案，先取出来的肯定是最贵的，一直卖，直到队列为空或者当天买入的股票已经卖完。
#2956	把各个坐标重叠的厚度累加一下，最后取最大值即可。
#2975	福娃，奥运专栏，对每种福娃算一次，枚举两行，如果两行有 k 个公共的，结果加 C(k,2)，复杂度 O(n^3) 还可以加位运算优化。
#3019	就是求两个集合交集元素个数，即已序序列的 LCS，先排序，然后 STL 交集就好了。
#3116	经典贪心，先按分值大的优先，然后按尽可能大的事间来分配。
#3143	贪心，生成一个序列，后一个各位乘积等于前一个数，直接分解前一个，注意要从 9 到 2 分解，然后串接起来就得到下一个。
#3197	给出若干个线段，求把整个 [0,N] 的区间覆盖需要最少多少条线段。比较特殊的贪心方法，先对所有区间排序。然后，顺序枚举，记录到当前区间左界止最少的次数 K，初始化 K 为 1。和 K-1 次时能到达最右位置 A，以及新一段往后接能到最右的位置 B。对于当前枚举到的线段，如果左界 > A+1，那么 A = B，并 K++。然后用其右区间更新到 B。
#3212	矩阵构造，使得恰好有 K 个内部单元的值等于其四周的值之和。随便找 K 个内部单元格，将其本身及四周的单元格都涂成 0，其他的全涂成 1 即可。
#3258	新型的背包变种，固体物品加流体物品。采用 背包DP + 贪心 的办法来求得最优解。先对固体物品做背包，然后枚举所有重量为 w 时的最大价值 p。然后还有 W-w 的容量，求取 W-w 的容量用最优的流体组合(直接贪心)能有的价值 q。最后用 p + q 来更新最优值。

栈处理
#1246	计算循环程序的多项式时间复杂度，递归一下即可。
#2483	中缀表达式，二值逻辑与或非的运算。
#2492	中缀表达式，解一元一次方程。
#2704	最长括号配对子串，要求 O(n) 复杂度，用栈来搞，从串开头往后面扫描，动态维护每个位置的最前合法匹配位置，并且注意 ()[] 这种连接情况，如果一段匹配了而前一段恰好也能匹配，长度应该串接。比较繁琐，注意正确性。
#3025	三值逻辑，中缀表达式的处理，用个栈搞搞搞就是了，也不是很烦。

动态规划
#1100	经典，状态压缩 DP，DP[i][j][k] 表示 i 层，j 末状态，本层还能在 k 位之后加的方案数，注意枚举的次序，从 1 位少的到多的。
#1425	交叉线匹配，经典 DP，n^3。
#1503	估价游戏，一个决策为背景的 DP，当前剩下 i 次机会和 j 条命，最优的策略可以覆盖 DP[i][j] 范围内的所有情况，那么DP[0][j] = 0, DP[i][0] = i, DP[i][j] = DP[i-1][j-1] + 1 + DP[i-1][j]。
#1520	经典背包，记录路径，放得下就行。
#1524	在线刷新，维护一个序列 V[M]，表示当前可以买到菜单上某一个物件的最便宜值。
#1558	欧元面值组合，DP，其实本质是 BFS，对于每一个目标价格，做一次 BFS，每次增加一个币。由于是 BFS，得到的最短次数即为所求。值得注意的是，可以先让钱加到一个很大的数，然后再减回来，因此 DP 数组要开大一点。
#1563	珠宝采购，类似背包，n^3 的 DP，DP[k] 为买完第 k 种珠宝之后的最小花费。然后，对于每个 k，可以考虑用它代替前面的 j..k 种珠宝，然后选择不同的 j 以更新最小值，即可完成 DP。 
#1883	简单 DP，明显长度为 n，最大数字是 k 的串有 (k+1)^n 个。那么只需求出 tight 的有多少个就行，这样的话就可以 DP 了。
#1738	比较简单的 DP, DP[k][x] 表示 x 在累加 k 次之后有多少种选择，然后类似背包加入即可。
#1792	类似 LCS 的经典 DP，O(n^3)，基因串匹配，1027 的升级版。
#1986	信号线连接，经典 LIS，必须用 O(nlogn) 的算法，否则超时。
#1991	先作图处理，dfs 求二分图连通块，然后可以 DP，具体细节见解题报告。
#2059	双塔，超经典 DP，每加入一个高度，更新双塔高度差为 i 时较低塔高度的最大值 DP[i]。
#2061	买票，经典组合数学 DP，先用类似于求组合数的手法 DP 出不区分的种类数。然后将结果乘以 M! * N! 即可得到全排列数，记得用大数。
#2068	DP，关键在于，排序之后最优的解匹配中必定不存在交叉。
#2136	经典，O(n^2) 的 LIS。
#2156	非常经典的多重背包问题，具体算法可见背包九讲。注意物品拆分，路径保存和最优性判断。
#2189	多重背包问题，与 2156 基本一样。但规模较少，直接用最原始的拆分即可。
#2202	不难的 1 维 DP，O(n)但是下面的一种情况绝对不能忽略！因为 0 是没有编码的！
#2224	典型可重复选取背包，数值较大，用 map 不失为好的实现。10 个物品也顶多是出来 2<<10 大约 1000 个价格组合。
#2250	简单题，水题，求出现次数第二多的数字们是多少。不要想当然，题目没错。。
#2254	经典，LCS 转 LIS，前提是 LCS 的双方都是一个等长的置换。将 LCS 混合置换之后，对于这个 置换之后的序列求 LIS 即可。问题的做法就是按照优先级求出各自的顺序，然后做 LCS 即可。
#2271	碰到女孩的概率，入门级概率 DP，每过一天更新一下 girl 在各个格子的概率，然后将遇上的格子的概率累加并清空，最后累加结果就是最终结果。
#2297	拳皇，状态压缩 DP，将 n! 的状态压缩到 2^n，假设用二进制位 bit 表示哪些人已经打过 DP[bit] 表示打过这些人之后剩下的最大血量，即可进行 DP，从打了 k 个人推到打了 k+1 个人，因此只需 DP 2^n * n 的效率，对于 n <= 20，小菜一碟。
#2401	经典 DP，字符串合并，跟 LCS 差不多，类似混合水果名字那个题。
#2402	求 1..m 的数字里面取 n 个构成子序列，每一个必须至少是前一个的两倍，求有多少种。DP 选取第 i 个数字的时候，最后一个数字是 j 有多少种情况。
#2414	求一个素数是否可分拆成几个其他素数的和，最少能分拆成几个，输入 <= 10000，类似0/1背包地处理一下即可，另外，其实根据哥德巴赫猜想，顶多也只有 3 个。
#2501	简单 DP，最优化取到第 i 个车厢，使用了 j 个机头时最多的乘客数。
#2527	寻找最长的等差子串，先预排序，然后用类似 LCS 的 DP，DP[i][j] (i<j)表示数列最后一段是 A[i], A[j] 的往前有几个，这样往前可以二分查找。
#2771	在线刷新，DP[i][j] 为第 i 次反射，正处于第 j 个状态的路径数，状态 j 由反射层位置及上下方向决定。
#2811	圆弧拼接，等价于求一组边(可以只取部分)能不能组成多边形，用 DP，一组边里面组合能形成等价为长度在区间 [low, high] 的边，加进去新的边，对区间只能扩大，不能缩小，直到 low <= 0 即可。
#2822	类似背包的 DP，DP[i][j][k] 表示共 i 个数编号小于 j 总和为 k 的方案数。
#2949	求期望的决策次数，非常短小的 DP，DP[M][N] 是两种面剩余碗数时的期望。初值是 DP[0][j] = DP[i][0] = 0。递推条件是 DP[i][j] = 1 + DP[i-1][j] + DP[i][j-1]。
#2972	刘翔，奥运专栏，在线刷新，跨到当前栏，处于各种状态的时候，最优的结果。
#3013	经典 DP，保持某个 text 前缀往前最小的划分花费，注意，每个 passage 都要输出一个值和划分串，另外，字典的存储容易超时，可选用 Trie 或 Hash。
#3017	魔法城堡游戏，BFS 状态，状态由所在城堡、所在楼层以及剩余魔法构成。
#3034	n^2 的 DP，类似于最长公共子串(LCS)。
#3049	先贪心再 DP，对于非魔法物品和鉴定反而价值减少的，直接卖掉，如果卖掉这些之后的钱购买卷轴直接将其它的全部鉴定卖掉，否则要选择一些不鉴定就先卖掉，这样就成了一个 DP，假设每个剩下的物品都有一个基础价和增值，求一个子集，基础价之和能凑够钱买卷轴并且增值损失最少，是个类似背包的 DP。
#3060	O(n^3) 的 DP，先预处理出每个位置往左和往右回到原位的最大值，然后按层 DP 到达 (i,j) 位置能够达到的最大值。
#3141	掰巧克力，经典，问掰多少下能把 M * N 的巧克力掰成全部是正方型的。用 DP，DP[M][N] 表示 M * N 需要的次数。那么初始条件就是 DP[i][i] = 0。递推条件就是 DP[M][N] = min(DP[i][N] + DP[M-i][N] + 1, DP[M][j] + DP[M][N-j] + 1)。其中 0<i<M，0<j<N。用递归做这个 DP 比较方便。 
#3160	给一个序列，某些编号之间如果相邻可以消去，问最多可以消掉多少个。经典 DP，先预处理出从 i 到 j 可以连块消掉的邻接矩阵，然后将这些块串接起来。
#3171	给一个字符串，问里边不同的子序列是 'seven' 的有多少个。很经典很巧妙的 DP 题，O(n) 的时间空间就可以解决。
#3211	砍树，经典DP，由于最后按天排序的砍树序列必有 b[i] <= b[j]，当 i < j。因此，先对 b[1..N] 排序，然后再用 DP 解决，复杂度 O(N*K)。 
#3305	经典的二进制背包 DP，但是直接硬搞的话物品太多。可以做一个预处理，把可能包含其他物品的物品先剔除掉，再处理就不会超时了。
#3310	环形相邻互斥0-1背包问题，只需分第一个是否选定来DP即可。

几何
#1114	蜂窝距离，坐标转换。将坐标作出变换，以六边形中心为网格，宽为 1.5s，高为 sqrt(3)/2s，s为边长。然后找到离起点和终点最近的六边形中心，求出第一步距离。然后根据选定的两个中心可以将坐标转化为整数。由于坐标的对称性，相减取绝对值即为坐标距离(tx和ty)。两个六边形中心相距 sqrt(3)s，实际的间隔应该为max(tx, ty)*sqrt(3)s。另外注意 tx = ty = 0 的情况下，距离为直接的两点间距离。
#1377	祖父的遗产，求凸包，保留所有边上的点，每边必须>=3个点，且不能所有点共线。
#1453	凸包，数据不是很强，围树，求凸包周长。
#1465	凸包，数据比较强，城墙，求凸包周长加一个圆周。
#1550	判别一个长方形能否放到另一个长方形中。如果能正放，直接 YES，如果完全不可能，直接 NO。否则，斜放，用一条边距离的平行线卡住长方形，求两端的宽是否小于另一边长。这些直接用三角函数即可达到。
#1560	知道点 p1 p2 的坐标以及相对于 p 的角度，求 p 的坐标。用点斜式得到两直线方程，再求交点即可。
#1597	求两个圆形相交的面积，可以选择几何计算出公式，也可以化成积分公式，使用符号积分，得到直接的闭合公式。
#1648	线段集是否有相交，电路板，算法导论的扫除法。
#1806	很简单很弱的几何题，把多边形(连带中点)找出来，然后枚举一下局部多边形即可。
#1821	可以证明，问题等价于求三角形垂心，不知道为什么。求垂心的话，直接几何模板套就行了。
#1868	蛮力枚举解决，剩下要做的就仅仅是球面距的计算了。
#1892	给出一个正多边形的任意三个顶点，求一个最小的边平行 x, y 轴的矩形型，使得它能包围这个多边形，输出其面积。根据三个点求外心即可求出多边形中心，然后旋转可以得到所有顶点坐标。最后的面积就是顶点坐标的 x 落差乘以 y 落差。 
#1917	给一个多边形中的任意三个顶点坐标，问这至少是个几边形？先求出三角形外心，则也必定为多边形的中心。然后任意选出两对顶点与外心求出两个圆心角 a1, a2。假设是 n 边形，那么圆心角肯定等于 2*PI*k/n，k是整数。然后从小到大枚举 n，检查是否两个圆心角 (a/2*PI)*n 都是整数，第一个满足条件的 n 即为所求。
#2102	把棍子等比分成若干段，然后在每个分段点看看是否落在任一个圆上，看落在圆上的点中，第一个和最后一个之间是否包含了棍子中点。
#2107	求最近点对距离一半。
#2347	求一个整点集中有多少个正方形，用 pair<int, int> 存点，然后枚举前两个，从后面的地方二分搜索另外两个。
#2352	凸包，先求凸包，然后按次序输出。
#2157	一个篱笆，所有边都是水平或者竖直的。给出所有的拐弯点的坐标，问篱笆的长度。很明显，对于同一 x 坐标的点有 2k 个，它们的 y 坐标排序后是 y[1..2k]。那么很明显 y2-y1 肯定有篱笆， y4-y3 肯定有篱笆，依次类推，可以求出所有平行 x 轴的篱笆长度。如法炮制即可求得平行 y 轴那一部分的。
#2167	平面上有若干点，求固定大小的圆在能包含最多几个点。用 O(n^3) 的算法可以通过，枚举两个点，得到边界落在这两个点上的圆，然后看一下所有的点落在这个圆中的有几个，用此更新最大值。
#2370	一根直棒的桥，受热伸长导致弯曲成圆弧，其宽度不变，求拱起的高度，简单的演算即可得到结果。
#2403	堆圆柱，一层一层往上算，每次相邻两个生成一个，因此每处理一层少一个，最后剩一个输出坐标。至于两个生成一个的方法，找出中点，加上一个垂直于圆心连线，长度为 sqrt(4 - (dist/2)^2) 的向量即可。
#2419	求点集中的最大三角形面积，O(n) 的旋转卡壳，先凸包，然后选取开头三个点 p,q,r 开始旋转，注意 r 不超过第一个点，q 不超过 r，p 不超过 q 。每次做三次推进，先推进 r，使 pq 不动面积最大，然后推进 q，再推进 p，如果三次都没有推进过，r 推进一格。每次推进完一个点都更新一下面积最大值。
#2540	给四个(x,y)坐标点，问是否为正方形，坐标优先排序一下再判就好判了。
#2681	把网格展开，求就由反弹转换成在平面直角坐标直行，找到线段，考虑跟跟网格的哪些边相交即可。
#2748	足球人墙，很无聊的几何题，注意墙一定是直线，不能是弧线就是了。 
#2819	天文望远镜，立体几何，只需判定一下两个三维向量的夹角即可。
#2855	Google 地图，坐标转换。结构本来是个四叉树，但这里任务相对简单，只求叶子定位的轨迹，关键是先将球坐标转换成平面坐标，然后向下扫描即可。
#2967	彩虹，堆栈贪心法。先按斜率排序，然后用一个堆栈保存一系列 "半直线" 。半直线保存直线和最后一个交点 x 值。然后按照排序向堆栈插入直线，如果新加入的直线与栈顶直线交点小于栈顶 x，退栈。直到堆栈只剩一个或者满足条件，插入新的 x 和直线。最后堆栈的大小即为所求。
#2976	蛮力枚举所有灯泡包围住的网格!!! 注意是求所有网格点的最大光强而不仅仅是原点的。
#3015	弹球游戏，反射定律，先求出 a 或 b 的镜像，然后求两直线交。
#3027	滚球，贪心，线段运算，枚举各个方块所容许的最大半径取最大值。
#3058	求圆形和圆环的面积交，容斥原理即可，圆跟环外圆交 - 圆跟环内圆交。
#3099	等高线，很巧妙的几何题，用一种特殊的贪心方法可以达到，详见解题报告。
#3107	简单的多边形面积计算，不用预存，不用浮点，直接搞。
#3139	火塔，漂亮的几何题，经典问题的扩展！类似 2967 的彩虹那道题。先找出所有斜坡确定的直线，然后按照 2967 的彩虹法求出一系列的上边界折线。然后就是要求上边界折线与下边界折线之间的最短的 y 距离。
#3194	给出一组坐标点 (所有坐标值为正)，X 坐标固定，Y 坐标可以随意调动。问将此系列坐标点用折线连接后与 x 轴围成面积最大是多少。此题应用贪心思想，通过面积公式的变形得到每个 Y[i] 分配的一组系数，然后对应排序后相乘即可，具体算法见程序注释。
#3203	影子长度最大值，稍加转化就是一个单峰函数最大值问题，直接二分可得解。
#3234	给一个点集，求不相交的多边形最多的层数。实际就是求凸包的层数，一直凸包，剔除，直到点数小于三。
#3280	Choose The Best 题目大意：给定N维空间的一些点，求加权曼哈顿距离最近的两个点的距离。分析： 权值可以乘到点坐标上去，就是说可以把每个点每一维都乘上对应的w[t]。考虑2维的情况 |x1-x2|+|y1-y2| 最大值只有4种情况：(x1+y1)-(x2+y2) , (-x1+y1)-(-x2+y2), (-x1-y1)-(-x2-y2), (x1-y1)-(x2-y2)，最大值是4种之一，这里面取最大就可以了。尽一步看到4种形式，每种自身第一个点和第二个点坐标间加正负号的方法是一样的。推广到N维，我们枚举加符号的方式，一共（1<<M）种，然后对每种方式，每个点的坐标按枚举的加括号的方式N维运算求出一个值来，取最大和最小值的差，作为可能结果，最后取所有差值中最大的即可。（注意M很小，只有8）复杂度O(2M*n)

图论
#1030	求给一个平面图定长闭合环区域个数，先用搜索遍历所有给定长度的环(从所有顶点开始，任意方向的回溯搜索)，然后蛮力判断是否有别的顶点在此环内(几何判点是否在多边形内)，以及这个环是否存在弦边。这两个条件缺一不可。数据并不苛刻，逻辑对基本就能过。
#1060	偏序关系，传递闭包，用 Floyd-Warshall 算法的局部实现。
#1082	股市小道消息，对任意源点求图的最小直径，用一次 Floyd。
#1092	简单套汇，是否存在套汇，Floyd 或是 Bellman-Ford 均可。
#1119	求割顶以及其隔开了几个连通分量，用一遍 DFS 即可。
#1285	普通的全源最短路，映射一下名称之后 Floyd 即可。
#1501	擂台赛，传递闭包。首先转化为一个无权有向图：读取树，如果 i 赢了 j，增加一条边 G[i][j]；然后求传递闭包，那么顶点 i 的出度表示它必赢几个人；他的入度表示他必输几个人。然后最高排名为入度 +1，最低排名为总人数减出度。
#1518	转化成一个图二着色问题，每句话是一个顶点：如果第 i 句话说第 j 句话是真的，增加一条同色边（双向边）；如果第 i 句话说第 j 句话是假的，增加一条反色边（双向边）。然后 dfs 染色，如果有染色矛盾，也就是矛盾；否则，对于同一个连通分量，两种颜色的顶点数分别为 X 和 Y。则最终结果增加 max(X, Y)。
#1542	赤裸的最小生成树。
#1586	最小生成树。
#1589	偏序关系，传递闭包，用 Floyd-Warshall 算法的局部实现，比 1060 稍为简单。
#1695	图的二染色，直接 dfs 即可，最后判定组合的地方要用 DP。
#1802	平面图着色，贪心就可以过，连回溯都没，可是算法正确性无法证明。
#1903	中国邮路问题，Floyd + 一般图匹配(状态压缩DP解决)。详见解题报告。
#2134	求最大割，本来就是 NP 问题，直接蛮力之后还有仔细优化一下常数才行。
#2158	最小生成树 Prim 算法，注意邻接矩阵权要临时生成 
#2193	模拟题，检查窗口覆盖是否有不合法的情况。通过各个窗口的位置，构有向图 G[i][j] 如果 i 块在 j 块下面 G[i][j] 为真。然后如果 G[i][j] 无环则合法，否则不合法。
#2195	族谱，实际上这是一个 DAG。递归搞搞搞...用 map 就行。
#2281	最小生成树变种，用类似 Kruscal 的方法即可解决：边排序加并查集。
#2316	图矩阵相乘。仔细分析一下就行，是个组合问题，用各个顶点的度可以压缩。结果是各顶点度的平方和。
#2326	最小生成树，用 Kruscal 即可解决。要很注意精度。
#2475	给一个有向图，问一个顶点可达的位置中是否会存在环。先做 Floyd，然后枚举给定的顶点可达的顶点，如果存在另一个顶点使得 G[v][w] == G[w][v]，那么条件成立。注意问题背景，自环是不算的，因此在初始化图的时候要忽略所有自环。
#2588	割边，注意平行边的处理和一个很阴的 PE，看程序注释。
#2612	一道图论与数学综合的题目，比较繁琐，详见解题报告。
#2699	求强连通分量，然后组建核心 DAG，然后转化成组合的问题，要用大数。
#2740	判断一个无向图是否树，充要条件是连通且 E=V-1，用并查集就行。
#2794	先构图，每个清洁点和起点是一个图的顶点，构造完全图，边权为两个点之间的距离(可用单次 BFS 得到)，然后求 TSP(N<=10) 即可，记住回溯的时候一定要加分支限界。
#2832	对一个 DAG 求所有源点。
#2913	图论题，求一个图的中心点，使得它到某些特定点的最远距最近。从这些特定点分别 BFS 出一个最短距。然后枚举中心点，中心点到这些最短距的最大值就是这个中心点可以达到的值，取最小解即可。
#2966	最小生成树。
#2997	经典的拓扑排序，构造一个长度为 N 的序列，使得序列所有连续 P 个元素之和为正，且所有连续 Q 个元素之和为负。将问题转化，构造这个序列的累加序列，相当于构造一个长度为 N + 1 的序列 S[0..N]，满足 S[i+P] - S[i] > 0 且 S[i+Q] - S[i] < 0。这样的话，可以构造 N+1 顶点的图，将所有 S[i] > S[j] 的关系创建有向边 (i, j) 。那么，将这个图拓扑排序，然后如果有环，则不可构造，否则，其深搜弹出序号本身即可作为 S[i] 的值。
#3036	最小生成树，顶点编号需要字典处理。
#3166	求一个顶点，经过它最小的最小环最短，直接 Floy 即可。
#3172	求一个森林的最长路径，直接蛮 DFS 即可。
#3204	稍微加强的最小生成树了，用 Kruscal，在预排序的时候也把字典序先后考虑进去就行了。
#3321	简单的图论题，检查一个给定的图是否是一个单纯的环。充要条件是，图连通，且每个顶点被恰好提及两次。

最大流
#1734	经典可行流问题，增加一个源点一个汇点引入发电机和耗散地即可。
#1992	混合图的欧拉回路，将所有无向边定向，保留所有无向边，变成容量为 1 的双向边，有向边转化为出入度表，对于所有度 deg[i]>0 的顶点，增加边(s->i):in[i]，对于所有度 deg[i]<0 的顶点，增加边 (i->t):-in[i]，有欧拉回路的充要条件是最大流充满了 s 引出的所有边。
#1994	有上下界的最大流，由于是二分图，原来 s->i 的边容量减去其导出边的下界， i->t 的边容量减去其导入边的下界，其余边容量变为 cmax-cmin，再求最大流，如果有满流则可。
#2314	有上下界的环流，对于边 (v->w):l/c 增加 (s->w):l 和 (v->t):l，并原边改为 (v->w):c-l，求最大流，如果最大流是 sigma(l)，则 YES，否则 NO。
#2399	最大流 + 参数二分，构造网络，然后二分到汇点的边容量。
#2567	给一个二分图 <U, V>，选取最小的边集，使得每个顶点的度大于等于 2。构造网络，增加源点 s 汇点 t，s->U 的容量为 deg[U]-2，V->t 的容量为 deg[V]-2，求最大流，那么没有流的边集即为所选。
#2587	求最小割是否唯一，先 bfs，然后分别从源点和汇点 bfs 余流网，看是否 bfs 到所有的顶点，如果是则唯一，否则不是。
#2616	最小割，理想情况下，所有标价可以全获，实际上某些不能共存，因此新增源点汇点，源向各个 A 公司的投标连容量为标价的边，B 公司的标价连向汇点，如果 A 中某标和 B 中某标互斥，连容量无穷的边，求最小割(最大流)。结果就是 总和-最小割。

树形问题
#1113	一个完全二叉字串树，节点是等长L(L<=1000)字串，边权为字符串对应位置不同的字符数。只给出数的所有叶子，构造一个树使得边权和最小并输出树根和最小边权和。归并法，具有最优子结构的贪心方法。可以看出这个问题具有字符独立性，也就是可以对字符串每个位置的字符单独做一次操作。做法如下，对字符串的每个字符位置做一次：用一个队列，存放一个树节点，节点保存如果这个节点取某个字符，那么这个节点为根的子树边权和的最小值。维持这个最优子结构，每次从队列中取出两个节点，归并后放回队列，直到队列只有一个节点。归并方法如下：求出要归并的两个节点(兄弟)取所有字母时的最小值，然后枚举可以使用的20个字母，如果，分别对两个节点，该字母位置取值恰好等于最小值，那么对这个字母，新的值取这个最小值，否则，取所有字母最小值加1作为新的最小值。复杂度为 O(L*N*20)
#1141	最近公共祖先，用 ST 法(log2(k)祖先)，或者时间戳转 RMQ 解决，经典。
#1150	逻辑树函数，直接模拟即可。
#1427	树状 DP，直接 dfs 这棵树，后序到达某个节点时返回填满这个数需要多少棵石子。对于没有儿子(叶子)节点，返回值是 1。否则，依次 dfs 其所有叶子节点，得到结果数组 vec，降序排列， 然后按照第一个 i = 0，往后遍历这个 vec，用 i + vec[i] 去更新结果的最大值，然后返回结果即可。
#1700	给出二叉搜索树的层次删叶序列，求其先序遍历。按照后删的先插入方式构造二叉搜索树，然后遍历输出即可。
#2315	树状 DP，求最大树节点集，使得: 1. 根节点不在其内; 2. 父子节点不能同时选中;  3. 兄弟节点不能同时选中;  注意 Bill Hates 一定不能拿奖，不然就错了...
#2353	原子实验，能级作为顶点，如果两个能级之间存在对应的光子，增加一条边。树状 DP，DFS 一次就行，注意，题目保证构造的图是一个森林。 
#2615	查询一棵有根树某个顶点是否另一个顶点的祖先。DFS 得到时间戳根据包含关系即可确定。但有两个问题，第一个是构图方法；第二个是 DFS 要用堆栈手动进行，这几点见程序注释。
#2684	给出一个二叉树，节点要么是叶子，要么有两个儿子。从左到右给出所有相邻儿子之间的路径长度，然后做一次查询，求给定两个儿子之间的路径有多长。根据给定关系即可构造出整个二叉树，然后 O(N) 求最近公共祖先即可。
#2912	树状 DP，一遍 dfs 搞定，求出所有路径的总长度。其中某条边应该被计算了 P * Q 次，P 和 Q 分别是他两边的子树大小。
#2999	时间戳，考查一个有根树的两个顶点的继承关系，字典的处理上时间有点紧。
#3195	经典的 LCA 应用。快速求树的最短路，给出一个加权无向树，对于每次查询，给出三个顶点，求连接此三个顶点的路径总和。用有根树表示该树，然后拆分为 LCA 求解，整个复杂度为 O(NlogN + QlogN)，具体解法见程序注释。
#3201	超经典的一道树状 DP，求一个点权树最大的顶点数为 K 的子树。注意这里子树应理解为树中的任一个连通块。运用巧妙的树状 DP 手段才可以解决这个问题，最优子结构为 dfs 到某个节点起，其往下取 0~? 个节点子树时可达的最大值。

最短路
#1148	无负权最短路，思路与 3026 相仿，纸牌，地图，全状态节点 Dijkstra。
#1298	求多米诺骨牌系统最后倒的牌：点到达的时间一定是最短路所达到的，而边上的时间可以由它两端到达时间确定。因此，先做一次 Dijkstra，然后检查个顶点及各边的时间 。
#1333	很猥琐的，直接求 Floyd 单元路径长度，然后判断从每个点到地球剩下的价值(每个单位长度路径乘0.95)，确定最优值。但数据很 WS，直接输出最大初始价值的就可以 AC。
#1430	最短路，地图，先 BFS 求出各个交点的冒险值，然后 Dijkstra，注意判别两个交点之间是否连通。
#1456	带路径存储的最短路，用 Floyd 即可。
#1536	带状态最短路，用一个变相的广搜累加即可，注意结果很大，记得用大数！ 
#1544	套汇问题，负环及连通性检测，Bellman-Ford。
#1655	最长路，用 Dijkstra，注意特殊数据，图不保证为简单图，可能有平行边或者 s-t 不连通的情况。
#1675	推箱子模拟，只有一个箱子，求最小推的次数。因此可以直接用广搜，但是状态点应该是推箱前坐标和推箱后坐标组合而成。这样就可以用一个简洁的状态记录人的位置了。
#1857	消防局，最短路，先求出原始最短路长度，然后枚举所有顶点作 Dijkstra。注意数据有只有一个顶点的情况。
#1942	青蛙，在一个欧几里德图上，求一条路径使得路径上的边最大值最小，用类似 Dijkstra 的 PFS 即可，用 Kruscal 亦可。
#1952	求 s-t 最大流量扩充路径(路径的边最大值最小)，用类似 Dijkstra 的 PFS 即可，用 Kruscal 亦可。
#2027	很经典的最短路题，一个加权有向图，从源点到汇点，找一条最短路，其中最长的边免费，问最少需要多少时间。由于规模较小，可以枚举存在的所有边，假设该边被免费了。然后再做最短路，不过，枚举到的边长度变为 0，并且只有长度小于等于这条边的其他边是通的。
#2210	典型地图最短路 Dijkstra 搜索，注意 Nemo 的位置 X, Y 可能大于 200。
#2276	古墓丽影，很简单的环形线性广搜。只需要单独搜出两个方块到某个位置的最短路即可。
#2411	连连看，有限步数连通，BFS 即可。
#2504	上学，基础的无负权最短路，Dijkstra，先按路径求出他妈给的路径的长度 len，然后从第二个路径上的节点开始做 Dijkstra，到达学校的长度为 d，结果是 len-d，当且仅当他妈的路径不对时是 N。
#2750	成语接龙，每个成语是一个顶点，两个成语 A->B 有一条边当且仅当 A 的后 4 个字母与 B 的前 4 个字母相同。因此可用单源最短路，Dijkstra 搞定。
#2849	典型的最短路 PFS，每个节点进一次优先队列，优先级别为：时间标记短的优先，其次变种号小的优先。
#2923	给一个图，某些顶点有标记。问从 0 到 N 的最短路中，标记小于 K 的有多少条。注意问题的提法，必须是最短路，而不是小于 K 时的最短路。这个用整个状态的 广搜 DP 即可解决。DP[v][k] 记录到达 v 处并且已经经历 k 次标记点的路径长度，以及在这个长度上的路径数。这样的方式由于所有边长为 1，只需要直接广搜即可。
#2935	地图最短路，直接归约成一般图 Dijkstra。
#3026	无负权最短路，Dijkstra，机器人，地图，坐标加方向构成30*30*4个状态节点。开始方向向右，走到 Halt 可手动移动。
#3033	最短路，Bellman-Ford 就行，很无耻的，路径长度居然要用 long long。
#3080	赤壁，找出连通分量，每个连通分量求一个最短路，然后取所有分量最短路的最大值。
#3088	全源最短 / 最长路，不能够 Floyd 的，只能作为 N 个单源来做。这里就可以选 dijkstra 或者 SPFA 来实现，我这里用 SPFA 之后蛮搞就过了。
#3103	最短路，用了 SPFA，状态由一个格的坐标加上左脚或者右脚构成，直接转移即可。
#3146	常规的最短路，SPFA 很容易写，注意有一点，如果走路的范围要越出外框，那么该方向依然可以走，不过走到地图的边缘就不能继续前进了，但是距离仍然按照那个数字算。

差分约束
#1508	区间，经典差分约束，变量 x[i] 代表从 0 到 i 的区间内总值，注意约束关系不要遗漏。
#2770	火烧连营，经典差分约束，变量 x[i] 代表从最左到 i 个营的兵数。

匹配问题
#1002	可以归约成二分匹配，某一条连续的横线对应 U 中顶点，竖线对应 V 中顶点，每个格点对应一条边。
#1023	高校录取，按照志愿和分数匹配，思路类似于最优婚配的延迟认可算法。
#1516	二分匹配，每个可能方块(相连的两格)为一条边，用国际象棋棋盘涂色法，黑的格在 U，白的格在 V。
#1525	经典最小覆盖路径，看相关的资料，容易归约为二分匹配。
#1576	最优婚配，男士求婚，如果不存在稳定匹配要判出来。
#2192	T-shirt，很容易规约成一个二分匹配问题。
#2221	可以归约成一个最小路径覆盖，然后用二分匹配搞。
#2223	打牌，大牌吃小牌，问作弊的情况下最多能赢几张，直接构造二分图求最大匹配。
#2404	指派问题，加权二分匹配，直接贴的浙大模板，权值直接可通过两点坐标得到。
#2521	可归约成最小覆盖路径，再用二分匹配匈牙利算法解决，注意二分图的构建。
#3037	最优婚配，这个要女士求婚，数据可以保证匹配成功。
#3111	求多米诺骨牌能否铺成二维网格内的某个图案，可归约成二分匹配，类似 1516。匹配的两个顶点集为要填的奇数格和偶数格，如果两个格子相邻，那么存在条边。如果两个集合等大且匹配是满的，那么结果就是可能的，反之亦然。
#3120	最优婚配，男士求婚，标程带有一个可重用的算法类。经典题。
#3156	参数二分 + 普通匹配。经典题。

字符串
#1423	表达式多余括号消除，完整的逻辑应该消除如下三种情况：1、开头的括号，例如 (A+B)+C ；2、前导是 '(' 或者 '+' 的括号，例如 ((A+B)-C) 和(A+(B-C)) ；3、在括号的一级范围内没有出现符号的括号，例如 ((A+B))。
#1477	字符串加解密，主要难在解密逻辑。加密的话蛮力解决，但注意排序法则是只看首字符，并且是稳定排序。解密的话贪心处理，详见程序注释。
#1481	类似于 T9 输入法自动辨认单词的题目。用 Trie 加广搜可以高效解决，本题我用了一个极为复杂的链节点 trie + 广搜解决，时效和空间效率均较高。
#1582	直接的贪心模拟，没什么技术含量，注意字符串是按行的，可能有空格。
#1707	简单的字符串替换，蛮力即可，注意读题：Continue until the find string no longer occurs within the text.
#1766	简单的字符串计数，注意审题：Words consist of the characters {a-z,A-Z,0-9}. Words are separated by whitespace, end-of-line, and punctuation.
#1838	简单的字符串替换，没什么可说的，注意下输入输出。
#2021	多余括号消除，1423 的加强版，具体判断细则见代码注释。
#2130	二维模式搜索，枚举已经可以过了，但是作为同一个问题，采用一些串的数据结构可以得到更好的效果。
#2645	IP 子网的最大掩码，实际上就是求 0-1 串的最长公共前缀。
#2737	本质是求一个 pattern 在 text 中出现了多少次(枚举所有 rotation)，数据很弱，硬搞可以过，要快的话可以用后缀数组 KMP 等速判。
#2876	求一个字典里面是否有其中一个串是其他串的前缀，限制较少，解法可以比较自由，想快可以用 Trie。
#2939	实现若干个罗马数字相加并输出。这样的话只需要做好罗马数字与十进制整数的转换即可。
#3056	核心就是给一个字典，给一个 key 要找出字典中的正确单词，头尾正确，其他打乱，直接 map 就行，当然最好用 Trie，头尾不变，中间排序作为 key，正确字符串作为 value。

递推关系
#1401	一个很经典的分治法解决的题目，对于每次切割，都可以分治为四个子切割中某部分的和，然后还需要加上重叠子状态记忆，这样才能满足效率要求。因此本题是分治和 DP 的混合解法。
#1579	经典过桥，同 1877，但不需要输出路径，注意数据类型要用 long long，否则会挂。
#1633	递归，因为前缀是一致的。可想而知，串的增长是指数级的，正如 Fibonacci 数一样。因此我们可以用 log(N) 的时间知道给出的 N 是在第几次迭代中加入的。也就是说，如果用 f(k) 来表示第 k 次迭代时总串的长度，那么 f(0) = 4, f(1) = 3, f(2) = 7, f(k+1) = f(k) + f(k-1)。如果求得 a = f(k-1) < N < f(k) = b，那么也可以得到递归式：f(N) = f(N - a)，然后锚例是 f(1~7) = "T.T^__^"。
#1652	有一个重要的规律，在平面中画一条两头伸展到无限远的曲线，它与现有的线有 k 个交点，那么他将原来的平面块多割出来 k + 1 块。因此每增加一条 z 形线，将于原来的每条 z 形线产生最多 9 个交点，由此即可递推。
#1877	过桥，超经典削减递推，先按时间排序，然后最优策略只有两种模式，实现方面用 DP 或者贪心都是 O(n)，详见解题报告。
#2185	就是一个有规律的三角形，按照 S 型往下扫描，问第几个是啥，规律应该不难找，注意行的奇偶性。
#2239	k = 2 时的约瑟夫问题：n 二进制表示循环左移的结果就是的解。经典结论。
#2345	本质就是对一个数列：1 2 2 3 3 3 4 4 4 4 的前 n 项和，输入太小了，直接打个表查都没事。
#2424	枚举顶点 1 连向哪些点，然后这根线将原来的多边形分割成两个多边形，这样就可以进行 DP，这里还需要用大数。
#2502	状态序列转移，转化成逻辑矩阵连乘即可。
#2547	三行的多米诺骨牌拼凑，可以找到分治递推公式和削减递推公式，详见解题报告。
#2604	小括号组合计数，大数的 DP 递推，DP[n][k] 是 n 个取 k 深度的话：左边留空 left 个，中间取一段 len 的长度满足深度，右边剩 right = n-left-len 个。而且为免重复左边填的括号满足深度 < k，右边填的括号满足深度 <= k。于是根据乘法原理，DP[n][k] = DP[len-1][k-1] * Sigma(DP[left][0..min(left,k-1)]) * Sigma(DP[right][0..min(right,k)])
#2625	递推公式：F[i] = (i-1) * F[i-1] + (i-2) * F[i-2]，具体推导见代码注释。
#2711	经典 DP + 滚动数组，DP[K][A][B][C] 表示现有 K 个字符时 A,B,C 的个数。
#2777	先把表全部打出来，C[i] 为 N=i 的时候上三角或者下三角的线段数，每增加一行，可以枚举出新增的线数，这样就可以达到 O(N^N) 的预处理时间和 O(1) 的查询时间。
#2872	给一个 10 进制数，求它可以分成多少种不同的由 2 的指数幂组成的和拆分。递推式为 F(N) = F(N-2) + F(N/2)，推导见该题报告。
#2893	括号配对与编号之间互转，先把所有编号的括号生成出来，然后就可以随便查了。
#2994	四行的多米诺骨牌拼凑，分成 3 种基本形状，削减法递推，A: ---- , B: -||- , C: --||，分别求出末端形状是 ABC 有几种，初值 + 递推即可解决。
#3180	对于这里，除非一个状态的前驱状态是初始状态，否则一个状态的前驱状态是确定的，因此可以不断倒推状态，每次检查。
#3182	其实这道题的递推关系与汉诺塔非常相似，非常经典：要求将所有圆盘串起来，第一个圆盘可以随意取放。/ 如果第 i 个在串上，且 1..i-1 都不在串上，那么第 i + 1 个可随意取放。用递推关系求得单独放第 i 个圆盘的代价是 f(i)=2^i-1，然后每次放最后两个盘，每次需要 2^(n-1)，最后如果还剩下 1 个，那么再加一，否则不加。具体递推的说明见代码注释。

数值方法
#1007	求级数和，为保证精度及提高效率，需要通过积分公式求出余项 R(n)，然后求和结果 S(n) 加上余项 R(n) 得到结果。
#1026	二进制多项式乘和模，用卷积与反卷积即可。
#1113	赤裸求和，没什么疑问吧。
#1601	求一个小数的分数逼近，枚举分子或分母，然后可以直接找到另一个，不断更新最优值即可。
#1640	多项式求根，模板蛮干型，巧解的话，可以通过对常数项的因数分解，然后枚举猜测的整数根反卷积验证。
#1803	多项式求值的模拟，用(...((x+c[N])*x+c[N-1])*x+...)+c[0] 的方法模拟即可。
#1981	简单的分段函数，高中的知识。先把所有冰和水都化成 -30 度的冰，得到一定的能量在分段讨论。
#2105	求数组的二阶递推公式第 N 项模 7，一种解法是找循环节(<49个状态)，更好的方法就是求转移矩阵用矩阵连乘。
#2124	求最大的 K，使得给定的 N 是某个整数的 K 次方，开方即可，注意很变态，输入的数可以是负数！！
#2150	带模求幂求和，用 log(N) 的求幂即可。
#2191	简单解方程。
#2277	求 N^N 最高位的数字，用 double 整过的。
#2330	求 a^b = b^a，即 log(b)/b = log(a)/a，给出 a，求 b，容易发现，f(x) = log(x) / x 在 (0, e]上单增，在 [e, +inf) 上单减，用二分求根即可。
#2351	化学题，H+ 离子浓度的计算，题意很难读懂，最后化成一个二次方程求根，具体题意和演算见标程注释。
#2369	求两，圆柱相交部分的体积。数值积分，假设两个圆柱的轴为 x 和 y，交点为 o，然后用平行 xoy 的平面切他们相交的部分，必定为一个矩形，因此得到积分公式：8∫sqrt(r1^2-x^2)*sqrt(r2^2-x^2)dx，用龙贝格积分即可。
#2408	求等效净利率，明显到目标月的结余按照净利率是单增的，则二分利率即可。
#2410	数值算法，有理分式分解：求三次方程根，然后分母多项式除 (x-r[i])，再求有理函数值。
#2431	求多项式是否可因式分解。多项式分解因式，因式只可能是一阶或者二阶的。分别对应与单个实根和一对共轭复根。因此，用多项式求根技术，求出实根的个数为 re, 复根个数为 im。im 必为偶数，因此若 re + im/2 > 2 则必可分解，否则不然。
#2503	求多边形顶点追赶路线长度，结果是 1/(1-cos(2*PI/N))，可以用微积分推导一个常微分方程解得。详见解题报告。
#2557	蹦极跳，物理题，用能量守恒定理即可。计算詹姆斯邦德到达桥底时的 动能 = 初始重力势能 - 末尾时弹性势能。然后通过动能即可求出末速度。注意当 s < l 时弹性势能为 0。
#2584	用一个向量 w{c0, c1, c00, c01, c10, c11} 表示一个串的当前状态，包括串中 0 的个数，1 的个数，00 的个数...可以做出转移矩阵，然后矩阵连乘，先把结果打出来，再直接查表，注意要用大数。
#2614	电线杆，用到很多微积分的运算，最后推导出来一个方程二分求根，详解见解题报告。
#2707	高等代数的内容，二进制多项式的运算。可以抽象出多项式的 乘、除、模、减 运算，然后就变成解模线性方程组。可以应用数论的扩展欧几里德算法实现。
#2818	求一个整数 B 的最接近整 N 次方根 A，直接用浮点求根然后在 +-1 验证即可。
#2896	求两个多项式是否有公因式：多项式除和求余用解卷积，用辗转相除法求最大公因式，判断其阶是否大于一即可。
#2928	典型的模拟退火算法迭代，跟 Google Code Jam 2008 Round 2 C题的解法是一样的，当时居然不会。这里的模拟退火只产生令结果减少的解，接受概率为 1。
#2969	多项式求导的系数，直接模拟即可，相当简单。
#2874	倒水，矩阵乘：生成转移矩阵，然后 logN 求幂。注意 k=0 的含义是只倒回自己，不知道的话会 WA。
#3001	数值方法，拉格朗日插值，C++数值算法(第二版)3.1节有讲，要用大数乘，除可以不用。
#3219	经典的高斯消元，根据概率转移建立线性方程组，再消元求解。

数论
#1095	丑数，这个是特殊的，一般的算法见 1596。
#1133	Smith Number，其实就是质因数分解，直接蛮力就可以，用 sqrt(n) 的因数分解就够了。
#1136	保存余数和字符串广搜，注意细节，N 可以为 0，也有可能结果是一位数。方法类似 1530。
#1143	千年虫，模线性方程组。但是数据很小，可以维护集合不断求交。
#1160	生理周期，中国余数定理。
#1222	无比经典的经典+BT题，光输入 n 可以到 100 位，处理的手段绝对是数论的精粹。详见对应目录下所引用的大牛解题报告。
#1278	求伪随机数的线性同余法模拟，求循环圈的长度，数据很小，可以直接模拟出来。
#1284	求一个数是否 大于?小于?等于? 它的所有因子之和，蛮力即可。
#1312	把素数表序列打出来，然后将中间的一段输出，没啥意思。
#1314	求伪随机数的线性同余法参数选择，只需判定 STEP 和 MOD 是否互质即可。
#1385	求 Stirling 数模 2 : 可以推得公式 S(n,m) == C(n-1-[m/2], [(m-1)/2]) % 2，然后用快速求阶乘 2 因子数可以求得结果。
#1408	数论搜索 + 剪枝，任意符号二进制数的表示还原。要留意数字的极限和输入是负数的情况。
#1489	2^x mod n = 1，对于给出的 n 求 x。明显，有解的充要条件是 2 与 n 互质，那么如果 n = 1 或者 n 是偶数，无解；否则，蛮力模拟。
#1526	求阶乘的位数，对阶乘取 log10，可以变成 log10 的和，然后就显而易见了。
#1530	求一个数的任一个倍数，能被输入的 k 整除，dfs 一个串，dfs 到某一个数的时候，判断 mod k 的余数是否为 0 。加分支限界法保证算法正确。 
#1569	求一个数串有多少个子串和能被 m 整除，先累加，再求每个位置 mod m 的余数 r[i]，如果 r[i] == r[j]，那么 a[i..j] 即为一个，统计 r[i] 中出现不同的值对应的个数 p[k]，对这些数求 C(p[k], 2) 求和即为总数。
#1577	知道 p，q 的最大公倍数和最小公约数，求 p 和 q 可能有多少种取值。问题可转化：x = lcm/gcd，再求 x = m * n，m, n 互质的取值有多少种，假设 x 有 k 个不同的质因子，结果就是 2^k，注意，有可能 lcm 不能被 gcd 整除。
#1596	三个因子的丑数，用一种特殊的 DP，假设当前生成的丑数序列为 H[1..k]，因子为 F[1..3]，那么找 H[k+1]，就是从 H[j..k] 里面选一个数乘以 F[1..3] 得到一个最小的大于 H[k] 的数。j 的位置可以二分找到，或者动态推进。注意要用 unsigned long long。
#1657	哥德巴赫猜想，给一个偶数 x，求有多少个分拆 a+b=x，a<=b，a,b 为素数。范围只有 2^15，把素数表打出来枚举就行。
#1712	斜二进制，简单的进制转换，没什么好说的。
#1797	超简单，求多个数的最小公倍数，直接传递过去就行，注意 lcm(m,n) = m/gcd(m,n)*n，一定要先除后乘，否则容易溢出。
#1842	区间打素数表，筛法的扩展，由于区间不长，但是区间的基数很大，因此打素数表要直接在该区间上打，很有意思的一道题。
#1850	问 x! 能否被 y 整除：对 y 因式分解，对于任一个质因子 i，如果 y 有 t 个因子 i。而 x! 的 i 因子 < t 则不能整除，处理到最后都没有的话就是能整除。注意处理输入有 0 的情况。 
#1889	枚举 1 的个数，考虑当前的余数 r，每增加一位，余数变成 (r*10+1)%n，如果余数为 0 就成功，如果出现了重复，那就是一个都没。
#1906	经典，求比 n 小与 n 互质的数有几个。转换思路，求不互质的几个，因式分解，得到各个质因子，对于每个质因子 k，它的任意倍数都与 n 不互质，共有 n/k 个，然后容斥一下就可以得到结果。
#1951	哥德巴赫猜想，求一个偶数，分解为两个素数相加，先把素数表打出来，然后枚举素数，看另一个是不是素数。
#2022	求阶乘数末位有几个 0，log5 快速求有 F(N) 几个 5 因子即可。
#2095	求一个整数 n 所有因子(只要能整除 n 且小于 n 的数)的和。由于查询非常密集，因此要用一次打表生成所有的答案，然后直接查表，
#2286	效率很严格的数论 + DP，查询很多，要用很巧妙的方法先把整个结果表打出来。
#2305	求最小的 N，使得 A + C * N == B (mod 2^k)。也就是求模线性方程 C * N == B - A (mod 2^k) 的最小解。
#2313	接球游戏。本质是最大公约数问题：每隔 k 就一个人，那么数总和为 m = n * k, 则要求 m 是 n 与 k 的最小公倍数,即 n 与 k 的最大公约数必须为 1，求满足上述条件的最大的k。具体解法见该题报告。
#2421	求一个递推数列的第 K 项，用蛮力把整个表先打出来，用个 set 存已经存在的数，这样即可迅速查询，然后模拟的复杂度就很低了。
#2520	定义一种数对(A, B)，其中 A 的因子(包括 1, 不包括它本身)之和等于 B，B 的因子之和等于 A。给出 K，求第 K 对这样的数对是什么。他 K 没给范围，其实很小，直接蛮力即可。
#2545	求不比 2^D 内最大的 N!，输出 N，转化，即求 log(N!) < log(2^D)，即 log2(N!) < D，sum{log2(1..N)} < D，因此生成对数表累加一下，然后二分即可。
#2723	求一个整数是否刚好能分解成两个素数的乘积，先打素数表然后枚举即可。
#2806	密钥判定，枚举一个小数再用，大数模小数运算判别。
#2945	加密，容易转换为一个求模线性方程组的解。
#2952	乱搞，直接枚举所有情况得到结果排一下序就收工，很简单。
#2955	飞镖游戏，先把 10000 以内的情况 DP 出来(DP方法略)，然后当 N > 10000 的时候，将 N 表示成 N=k*x+y (k=N/x, y=N%x)，然后枚举一下即可，难度中等，详细见标程注释。
#2964	很好的数论题，三角形，用到欧拉函数及费马小定理，详细做法见标程注释。
#3008	先把 n^m 分解成素数的因子，然后 DFS 这些素数的组合，得到所有可能的分拆。
#3014	质数判别，进制转换，用暴搜打表过的。
#3024	星期一星期六素数，用筛法，筛的过程中保存所有因子。
#3175	算是有点小巧妙的题吧，求 SUM(N div i - 1), i = 1..N。枚举 i，p = N div i，可以得到当前 i 的结果是 p + 1。然后求有同样结果的有多少个，取 t = N / i + 1。那么同样的结果有 (p - 1) * (t - i)，累加起来。然后步进条件改为 i = t 替换掉就行了效率约 O(sqrt(N))。 

组合数学
#1577	容斥原理，知道 p*q，求 pq 的可能组合，分解出所有质因子，然后搜索组合，根据组合元素个数的奇偶确定加还是减。
#2000	求第 n 个回文数，劈开两半，可以找到规律(每一位有几个回文数，第几个是谁)，然后反过来可以根据序号求出该回文数。
#2060	求一个递推数列某一项是否能被三整除，显然有很短的循环节，因此结论很简。
#2098	很简单的组合概率计算，结果 = Prod(C(M[i], P[i])) / C(M, K)。
#2759	将问题转化成一个三进制数制的问题，看解题报告。
#2836	容斥原理，求出被其中一个可除的有 +M/A[i] 个，被两个都能除的有 -M/lcd(A[i],A[j]) 个，如此类推。
#2859	求静态二维 RMQ，与一维 SparseTable 算法类似，应该不难写出来二维的 ST 算法。总空间时间复杂度为 O(nlogn)^2。
#2996	大的组合数模 2，经典方法，while(n>>=1) tot += n; 就可以计算出阶乘数 n 有几个 2 因子，剩下的就好想了。

数据结构
#1128	常规矩形切割。
#1449	求最大的子立方阵和，直接用求和预处理之后容斥原理，再用 n^6 的枚举即可解决。
#1565	铺地板砖，用矩形切割即可解决所有问题：如果最后的面积并 < 所有面积和，说明有重叠；如果有任何 x<0 || x>W || y<0 || y>H，说明没有包含；如果最后面积并不等于 W*H 说明没有完全覆盖；否则 OK。
#1752	类似刷墙问题，典型的矩形切割，反向染色亦可。
#1789	实际是个连通分量问题，用并查集就是最高效的解决。
#1899	字典，简单的映射一下即可，用 STL map 足够了。当然，用 Trie 是最快的。
#2113	父链树动态合并、查询节点距离，用蛮力搞的，结果擦边球 WS 无限次刚好在时限边缘通过了。正解是用倍增 LCA 算法解决的。
#2132	寻找一堆数(很多)里面出现最多的那个，本题卡内存，只有 1024K，用个 map BST 即可。
#2212	任务优先处理，直接用个优先队列搞啊搞啊。
#2273	暴力的艺术，本题查询超多！先用一次暴力处理把表打出来，然后让每次查询的代价降到最低。用一个链表(这里用数组模拟)，存放从 1 串到 99999 的所有字符，以及该个字符是属于哪一个数字的。然后一次一次删，删之前检查链表第一个和第二个是否属于同一个数字。如果不是，那么假设第一个节点属于数字 k，字符是 c，那么查询 k 的结果就是 c，保存 ans[k] = c，这样预处理了之后，对于每次查询 k：如果 k 已经出来过结果，那么记过就是 ans[k]，否则就一直往前找，直到找出第一个计算出来过的 ans[k']。
#2301	经典题型，离散化 + 线段树。
#2334	猴子打架，可合并堆：用左偏堆是最简单的实现，当然，二项堆与 Fibonacci 堆也是可以的。
#2339	求 huffman 编码的最短编码后文本长度。思路是模拟 huffman 树的构造，但是并不需要完全构造。用一个优先队列，放进去个字符频数。每次取出最小的两个，总结果累加它们的长度之和。然后将它们之和放入优先队列，直到队列中只剩一个。总复杂度 O(NlogN)。 
#2505	并查区间，动态维护连续区间，每一个节点只向他的低位并查，在此还要保存区间长度，详见解题报告。
#2706	蛮搞模拟即可，注意序列里面的数是有负数的，根据正负注意取整方向。效率方面，动态维护当前序列的总和，每次判取整方向的时候就不用另外算了。 
#2724	Windows 线程管理，用 STL 优先队列即可解决。
#2747	多种解法：1. 离散化+二维线段树；2. 离散化，一维枚举另一维线段树；3. 离散化 + 逆向涂色 + 并查 skip；4. 矩形切割。3 是最快的。
#2828	维护字符串字典，先生成字典，对于每个单词，先查本身是否在字典中，否则 O(n) 枚举相邻交换的可能情况再查字典，用 map 已经够了，想快可以用 Trie。
#2833	经典并查集，数据规模比较够分量，用来测试模板很不错。
#2868	分组背包，超超经典的题，先转化问题，求一堆数里面总和最接近 half 的值，将集合分成两部分，分别用两个 set 各自做背包，于是最后可以枚举一个背包里的和，再二分查找另一个背包里面的和。
#3005	矩形切割，切割的过程中记录拓扑关系。
#3018	矩形区域查询，动态四叉树，最高的顶点代表整个平面，然后向下分四份切割，子平面是该节点的子女，然后动态维护节点区域内的值总合即可。
#3101	先保存所有登入登出记录，然后对每一条查询，遍历一次这些记录，得到，所有有效区间存起来，然后再求静态区间并，这样就不用线段树了。
#3114	双端的堆，用一个 STL map 作 BST 就可以了。
#3149	面包树，经典题，用稍为巧妙的暴力变相模拟，设数组A[i]表示当前有i个儿子的节点数，然后直接用这个模拟，刚开始的时候A[]={1,0,....}数组不长于K，根据转移的性质，用一个双端队列来维护这个数组可以达到一个很好的效率。
#3170	注意题意说是 BST，因此先读取数字，排序。然后用队列法生成二叉树的结构。然后中序遍历把数字填进去，再后序读出来。
#3185	特殊的列表并集差集运算，并集的话直接串接，差集的话将所有右操作列表放到 map 中，然后枚举左操作列表，如果存在于 map 中，删除该 map 中的一个计数，否则，添加到新的列表中，最后将原来的列表替换成新的列表。
#3198	比较水的有序集合求交集，O(n) 的解法应当是相当基础。
#3207	简单的字符串字典问题，直接用 set 就行了。
#2320	做题，每道题要求能力 ai，做完后能力增长 bi。共 n 道题，原始能力 p，问做 m 道题之后能够达到最大的能力是多少？先按题目的 <ai, bi> 从小到大排序，然后进入循环：维护一个堆，里面存放一个整数，也就是还没做的，可做的题目的 b 值。每次循环，从剩余题目中抽取所有能做的题目，删掉，并将其 b 值入堆，直到剩余的最容易做的题也不够能力做了。然后从堆中取出最大的 b 值(如果有)，叠加到 p 上，并令 m 减一。直到 m 为 0 或者堆已经为空。最后的 p 值即为所求。
#3279	蚂蚁，经典数据结构题，区间树。类似线段树，节点保存区间内的统计量。支持的操作：更新某一个位置的值(需要从叶子到根的值都更新到)，和查询某一个累积统计量的位置值。总体复杂度 O(nlog(n))。

高精度
#1177	很妙很强大的一道高精数论题，给 K，求最小的整数 X 使得十进制循环左移之后，得到的 Y = X / K。方法是枚举 Y 的个位，逐位(第k位)乘以 K 后得到 X 的第k位，于是得到Y 的第 k+1 位，以此类推可得整个数，枚举一次个位即可。 
#1352	终极数值转换，用大数硬做的话，几乎囊括了所有运算，最适合用来测试大数模板。最好还是用直接数制转换的方式，不需要中间转换成十进制，复杂度为长度的平方。
#1962	查找两个数之间有几个 Fibonacci 数，先生成所有 Fibonacci 序列，然后二分，需要大数加和比较。
#2306	Fibonacci 进制数，主要是要做 string(Fib) <-> BigNum(Dec) 的互转，string -> BigNum 只需模拟加一下就行，而 BigNum -> string 的话，只需要从最大的开始减贪心下来就行，然后转一下字符串处理一下就 OK 了。
#2371	将 N-1 做成二进制表示，如果二进制表示中某个位 k 为 1，则集合中包含 3^k。
#2486	k^n=p，知 n, p 求 k，用大数二分即可，下界取 0 上界取 INT_MAX。或者直接用浮点 WS。
#3167	求最小的 n，使得 M^n 的第 K 位是 7，M, K 1000 以内结果保证在 100 以内，直接大数乘法模拟，不过要加入一个操作，就是求大数第 K 位是什么。

排序
#2172	按照字符串的长度排序之后交叉输出即可。
#2386	求序列的逆序对数，用分治法排序达到 O(nlogn) 的复杂度。经典。
#2727	给出一列书目，有名字、价格与日期，按要求以不同的优先级进行排序。可以重载不同的 sort 函数然后按要求 sort。
#3157	可以用类似1986的模型归约成逆序对问题进行求解。
#3168	把 ZOJ7 这四个字符计数提出来，其余的保留，然后拼接即可，这种属于计数排序法，线性复杂度，水题。

位运算
#2729	很纯粹的位运算题，先把位翻译成串，然后再解释。可以考虑用 bitset，代码会稍为简单。

博弈论
#1827	博弈，状态不大，用记忆化搜索解决的，前推 DP 的话次序和初始状态稍为麻烦。
#3057	博弈 DP，直接前推，DP[i][j][k]，保证 i<=j<=k，然后枚举 i,j,k 前推。开始全部默认必输，然后枚举，从必输点发展出来的重新标记为必赢。否则略过。

二分
#3123	求和，枚举+二分。
#3131	数字钟，数字钟的时间 hhmmss 串接而成的整数叫时钟数。给一个闭时间区间，问当中时钟数能被 3 整除的有几个。蛮力的话单次复杂度不高，但查询个数很多。因此蛮力做一次判定，按序将合法的能被 3 整除的所有时钟数存到顺序表中。然后每给一个区间，用二分查找找到位置，然后一减即可得到结果。这样可以在单次处理的效率上打一个对数。
#3187	最优化问题，二分答案(能供给多少人)，然后判定每项配方供给这么多人的时候最少用多少钱，根据最少的钱是否多于现有的钱就可以实现完整的二分了。
#3278	求两个数组的交叉积里面的第 K 大数。双重二分，先做一个二分函数，给定一个值，知道 <= 它的有多少个。然后做外层的二分，二分结果，从小到大找到第一个值 val，使得 <= val 的值有 M*N-K+1 个。整体复杂度为 O(M*log(N)*log(MAXVAL))。

未解决：

1289	好像很有意思的多边形...
1450	最小覆盖圆

1621	javaman 说唯一的一道排序网络
2676	分数规划，图论，最小割，最大流，参数搜索，最优比率割

1829	后缀数组的应用





2241
1697
2161
1361
2110
1700
1957
1818
1675
2984
1023
2945
2980
2837
2884
1886
1303

2698 (变态模拟，英文单词数字转阿拉伯数字)
1450 (最小外接圆)
2982 (负进制，应该很好玩)
2838 (通过率超低图论题)
1252 (敌对并查集)
2398 (变态哈密顿，据说要 DP状态压缩)
1393 (变态魔方大转盘)
2200 (地球仪飞机路线加强版)
2895 (月赛 DP，不会很难)
1428 (骤看之下ms差分约束)
2634 (该不会是记忆化吧)
1217 (八码难题，状态压缩，hash+BFS)
2539 (最优化，最大流)

2526 2583 2761 2864 2881 2887 1721(最短路)

1829(后缀数组)
1507后缀数组

火鸡：2985 2984 2978 2167 2993 2839 1827 1824 3028 2382 1636 3029 1851 1850 3030
04最短路 06排序 07几何 12几何

2620 几何，找三角形

1827 博弈
1868 模拟退火
1729 后缀排序
1792 DP，类似1027
2477 魔方搜索解
1517 魔方
2265 魔方
2821 魔方
1554 字符串压缩
1505 吃跳棋
1990 判别树的同构

1380
17？？

多项式专题：
2700	二进制多项式二次方程求根。
1478	多项式求和。
2434	二元多项式
1736	二进制多项式
2019	貌似长除法
2516

1283
3130	应该是费用流

3139	有点嚼头的几何题，感觉可以类似2967地搞。
2626	怪怪的 DP

2074	最远点对