问题描述：
给你一个$W*H$的矩形网格，两个人轮流水平或垂直地剪去一部分，如果轮到某个人只剩下1*1的网格时，则认为那个人输了。
输入：
有多组数据，每组数据两个数$W,H(2<=W,H<=200)$
输出：
每组数据一行，如果先手能赢输出”WIN”，否则”LOST”
思路：
代码：
1 |
|
BZOJ1951 古代猪文 [欧拉定理+扩展卢卡斯]
问题描述：
简单来说就是让你计算：
输入：
两个数N、G
输出：
一个数，表示答案除以999911659的余数
思路：
很好的一道题呢，涵盖了大部分数论知识点呢：欧拉定理、中国剩余定理，Lucas定理，组合数取模，逆元….
不过思路不会很复杂。首先指数那么大，肯定不难想到利用欧拉定理将指数缩小，原理可以看这篇文章。所以我们可以将指数变为$\sum_{d|n}C_n^d mod 999911658$，求这个就是求组合数取模，用lucas定理。。。
那么问题来了，我们普通的Lucas定理中模数要求是质数，但这题中模数不是质数，因此我们要用扩展Lucas。首先将模数质因数分解，分解为2，3，4679，35617四个质数。分别在模这四个质数的意义下求出我们要的结果$a_1, a_2, a_3, a_4$。这样答案就可以表示为： $ans \equiv a_1 (mod 2) $ $ans \equiv a_2 (mod 3) $ $ans \equiv a_3 (mod 4769) $ $ans \equiv a_4 (mod 35617) $ 那这样就是中国剩余定理的形式，解出$ans$并利用快速幂$G^{ans}$就好了。
代码：
1 | #include <iostream> |
BZOJ4004 装备购买 [线性基]
问题描述：
脸哥最近在玩一款神奇的游戏，这个游戏里有 $n $件装备，每件装备有$ m$ 个属性，用向量$z_i(a_j ,…..,a_m)$ 表示。每个装备需要花费 $ci$，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。
如果脸哥买了 $z_{i1},…..z_{ip}$这$ p$ 件装备，那么对于任意待决定的 $z_h$，不存在 $b_1,….,b_p$ 使得 $b_1z_{i1} + … + b_pz_{ip} = z_h$（$b$ 是实数），那么脸哥就会买 $z_h$，否则 $z_h$ 对脸哥就是无用的了，自然不必购买。脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？
输入：
第一行两个数 $n$，$m$。接下来$ n $行，每行 $m$ 个数，其中第$ i $行描述装备$ i $的各项属性值。 接下来一行$ n $个数，其中$ c_i $表示购买第 $i $件装备的花费。
输出：
一行两个数，第一个数表示能够购买的最多装备数量，第二个数表示在购买最多数量的装备的情况下的最小花费
思路：
题目说简单一点就是你要在一组向量中，要求出最大的线性无关子集，也就是线性基。
线性基的求法就是把$n$个向量看成是$n*m$的系数矩阵，然后进行高斯消元，剩下的非零向量就是线性基，那么最多的装备数量就是线性基的大小。但是我们还要维护它的最小花费，这时我们就可以使用贪心的策略了，可以将价格排一个序，消元时尽可能用价格低的消去其他的，这样就可以了。
这个的证明也很有趣，因为线性基是是线性无关的，如果有一个价格更低的能被它们表示，那么我们可以放进去一个价格低的，取出一个价格高的。这样，价格高的一定能被新的线性基表示，所以我们可以使用这种贪心策略。
代码：
1 | #include <bits/stdc++.h> |
Codeforces Round #498
7月28日 Codeforces Round #498 题目链接：http://codeforces.com/contest/1006
A - Adjacent Replacements & B - Polycarp’s Practice
比较水呢。。不说
C- Three Parts of the Array
思路： 也很水呢。。。就是一个双指针，记录两边的和就好了。其余的看代码。。
代码：
1 | #include <bits/stdc++.h> |
D - Two Strings Swaps
思路： 毒瘤，卡了超级久。。。首先思路很简单，因为$a_i$, $a_{n+1-i}$, $b_i$, $b_{n+1-i}$直间能够任意交换，所以我们可以把这4个元素看成一块，计算出要改几个字符。
关于答案的的计算方法很毒瘤，就是分类讨论！！有很多情况，也有很多细节，在讨论过程中思路一定要清晰，千万不要漏情况了。。我就漏了QWQ
代码：
1 | #include <bits/stdc++.h> |
E - Military Problem
思路： 首先一棵子树在DFS序上是连续的，我们可以利用这个性质，然后这道题就是水题了。我们只要一遍DFS处理处子树大小和整棵树的DFS序，如果$k$大于了$x$的子树大小，那么答案就是-1，否则就是DFS序在$x$后$k-1$个对应的节点。
代码：
1 | #include <bits/stdc++.h> |
F - Xor-Paths
思路： 看范围就知道是双向爆搜。。。然后就直接码就好了，然后就是中间相交处理答案时有一些细节要注意。中间的那一条是计算过两次的，所以在更新$cnt$数组是还要异或一下那个数字。
代码：
1 | #include <bits/stdc++.h> |
Educational Codeforces Round 47 解题报告
7月26日 Educational Codeforces Round 47 题目链接：http://codeforces.com/contest/1009
A - Game Shopping & B - Minimum Ternary String
简单，不讲。。。
C - Annoying Present
思路： 其实也比较水。。。首先参数$x$对答案的贡献是不会变的，根据一些小学数学知识可以知道：当$d$为正时，选取的位置越靠边贡献越大；当$d$为负时，选取的位置越靠中间贡献越大。因此分类讨论一下就好了。
代码：
1 | #include <bits/stdc++.h> |
D - Relatively Prime Graph
思路： 虽然是构造一张图，其实和图论没有什么关系。。。
看懂题意以后可以发现你就是要在$1-n$内找出$m$对互素的数，于是可以暴力枚举，知道枚举出$m$对数。因为这是实在是太暴力了，比赛时还在怀疑算法不够优秀。其实互质数对的分布是玄学的，所以一般是不好卡你暴力的，再加上CF的神机，放心的打就好了。（实测46ms) 代码：
1 | #include <bits/stdc++.h> |
E - Intercity Travelling
思路： 一看题目，哇，和JXOI的风格好像的QVQ，都是小清新的期望计数题。虽然是期望，不过同样是套了期望的说法的一些计数类问题。
首先想到$n^2$的暴力DP，先处理前缀和。设$g[i]$为有多少种方法到达$i$点，$f$就是答案所求的东西，那么DP的方法就如下面代码所示：
1 | g[0]=1; |
然后我们打表发现$g[i]$就是$2^{i-1}$，又发现$f[i]$只由$a$中的元素组成，且组成方法与$a$中元素的值无关。于是再次打表，打出$f[i]$由$a$中的元素怎么构成，于是发现其中$h[n+1-i]$为构成$f[n]$(即答案)中$a[i]$的系数。即： 代码：
1 | #include <bits/stdc++.h> |
F - Dominant Indices
思路： 一直没有学树上启发式合并。膜题解发现要用这种操作，于是学了一下。个人理解就是遍历每个节点，然后从每个节点再开始另一个搜索，处理出该节点子树的信息，这样显然最坏是$O(N^2)$的。然而我们可以从先遍历节点，回溯时保留父亲节点重儿子的信息，这样从父亲节点开始的另一个搜索就可以不用搜重儿子。于是我们保证了时间复杂度在$O(logn)$。
这道题也是类似，要求子树重节点最多的那一层，于是就按照启发式合并去做就好了。 代码：
1 | #include <bits/stdc++.h> |