Codeforces 1027E
题意：给出一个正方形，要求在每个位置涂上黑/白色，要求满足：任意相邻的两行，其颜色要么完全相同，要么完全相反。任意相邻的两列，其颜色也要么相同要么完全相反。
且这个矩形中，不存在任意一个大小大于等于$k$的同色矩形。

对于”满足：任意相邻的两行，其颜色要么完全相同，要么完全相反。任意相邻的两列，其颜色也要么相同要么完全相反。”，也就是说只要确定正方形一行一列，整个正方形都被确定。
那么我们设确定的行的黑白情况是$a_i$, 列是$b_i$，对于$(i,j)$的颜色即为$a_i xor b_i$
那么我们就考虑如何满足不存在任意一个大小大于等于$k$的同色矩形。
显然就是$a_i$最大连续的一段和$b_i$最大连续的一段的乘积不能大小大于等于$k$。
那么我们用 DP 求出序列上最大连续的一段为$x$的方案数就可以用乘法原理做了。但是发现这个状态并不容易求，那么我们就求序列上最大连续的一段小于等于$x$的方方案，对于等于，就是$dp(i)-dp(i-1)$算出来。
所以设$dp(i,j)$为前$i$个数最大连续的一段为$j$的方案数。那么$dp(i,j)=dp(i-k,j), 1 \leq k \leq min(i,j)$
然后统计答案就可以了。

知识点：要善于发掘题目条件对解题的限制

Codeforces 1037E
题意：有$n$个人，$m$天，每天晚上都会有一次聚会，一个人会参加一场聚会当且仅当聚会里有至少$k$个人是他的朋友。每天早上都会有一对人成为好朋友，问每天晚上最多能有多少人参加聚会。朋友关系不满足传递性。
相当于有$n$个点，进行$m$次加边操作，每次操作后附加一个询问，问最大点集的大小，使得点集中每个点的度数均大于等于$k$

本题还是逆向思维比较容易。
我们先思考所有边加入的答案。对于一些点他的度数如果不足$k$那就肯定不能够成为点集元素，删掉他，并且删掉他所连的边。直到没有这样的点为止。剩余的点即为答案。
然后就是删边。如果该边已经被删除，那么这条边对之前的答案没有任何影响，直接输出上一个的答案即可。否则就删掉这条边并让边的两个点度数都减一，如果有度数不足$k$的就继续删并且删掉他所连的边直到没有这样的点为止。剩余的点即为答案。之后都是类推。
对于判断有度数不足$k$要用dg(u)+1==k来判断，否则可能多次记录答案导致错误

知识点：1、正难则反
2、从简单情况到复杂情况的思路

Codeforces 1017D
题意：给你$n,m,q$，表示在这一组数据中所有的$01$串长度均为$n$，然后给你一个含有$m$个元素的multiset，之后有$q$次询问。每次询问会给你一个$01$串$t$和一个给定常数$k$，让你输出串$t$和multiset里面多少个元素的$Wu$值不超过$k$。对于$Wu$值的定义：如果两个$01$串$s$和$t$在位置$i$上满足s[i]=t[i]，那么加上$w[i]$，处理完$s$和$t$的所有$n$位之后的结果即为这两个$01$串的$Wu$值。

发现本题有$n$和$k$小，那么从这两个下手。$2^n≈4000$很小，我们可以将二进制数两两求$Wu$值之后$O(1)$查询。然后因为$k=100$, 那么我们再开一个二维数组记录某个二进制数能与multiset里面的元素组成某值的个数。这个状态非常好用。

知识点：
1、这种题目数据范围小是突破点。
2、写完程序要核对自己想的复杂度和实现是否有差异。

Codeforces 1004E
题意：一棵$n$个点的树，你需要选出一条不超过$k$长度的链，使得其他所有点到链上的最短距离的最长距离最短。

这个有点像二分，但是并不好做。我们想到树的直径的性质，一棵树以直径中心为根子树深度最小。
考虑边权全是1的情况，选择的链一定在直径中间$k$长度的链。根据一棵树以直径中心为根子树深度最小性质很好证明。
现在有边权，那么就要找一个加权的直径，并且链也不在中间了。但是还在直径上。我们预处理出以下的信息：

$d1(u)$，直径上第$u$个点到左端点的距离
$d2(u)$，直径上第$u$个点的枝叶最长深度距离
$dl$，直径的带权长
$a(i)$，直径上的点从左到右的序号

求直径两遍 BFS，然后用 Dinic 分层图思想找出直径上的点。即找到一个任意点的最远点之后，找这个最远点的最远点时候顺便对于每个点分层，然后再从这个最远点往回一层一层地走必然能找到直径。对于$d1​$，顺便求出即可。$d2​$，DFS 求每个直径点往下枝叶最大深度即可，注意不要走到直径上。

然后对于最后的答案就化作：
$ans=min(max(d1(max(i - k + 1, 0)), dl - d1(i), d2(i), d2(i-1),……,d2(i-k+1)))$
对于后面的$d2$，就是一个滑动窗口最大值，用单调队列维护即可。

知识点：1 树上的这些最优化问题和直径、重心、二分、DP有关。
2 单调队列很容易写错，是检查重点
3 从简单到复杂，从极端到一般的思维方法很重要

Codeforces 1037D
题意：给出一棵树以及一个序列，问这个序列是否可能是原树的 BFS 序。
考虑 BFS 分层，然后每次读进来数判断一下是否能接上。看代码即可。
注意 BFS 序要按顺序，比如上一层在前面入队的是1，那么遍历这一层时一定是1的所有孩子在前面

本题结合了 BFS 序，对于 BFS 不一定要用队列，可以边处理边 BFS 一层。

Bzoj 1057
题意：在一个大矩阵中找出一个黑白相间最大的正方形和最大的矩形。
DP悬线法解：
求最大正方形可以用DP，而矩形就要悬线法(正方形也可以这样求)。
预处理$l,r$数组为当前行左右最远能到达的合法格。然后每次查询看能否合并上一行的状态，处理$up$数组为往上最远能到达的合法格。转移方法和DP差不多。正方形取两个最小值的平方，长方形直接乘即可。
单调栈解：
先来考虑 Poj 2559 的做法：
将所有高度依次加入单调栈，若出现破坏单增情况，则弹出栈直到满足为止。弹出过程中顺便记录以当前弹出高度为高，累加弹出宽度为宽求答案。最后将新的宽度+高度加入单调栈。注意最后剩余情况，直接在后面加一个高度为 0 的即可。(具体看算法竞赛进阶指南)

然后本题矩形考虑行列分开处理，对每个位置的数求出列上最高可达点，然后对于每行来说就是做 Poj 2559 的事情。所以直接每行做一次。

BZOJ 1899
题意：见上。
本题无法直接 DP，所以我们想到贪心方案，吃饭慢的排前面打饭，按照这个方法来进行排序后就可以DP了。
可以设$dp(i,j)$为前$i$个人在1号打饭花了$j$时间的最小吃饭时间。
转移：
$i$安排到1号：$dp(i,j)=max(dp(i-1,j-a_i),j+b_i)$
$i$安排到2号：$dp(i,j)=max(dp(i-1,j),sum_i-j+b_i)$
其中$sum_i=\sum_{j=1}^ia_j$
初值$dp(0,0)=0$，其他为$INF$
知识点：这种无法直接DP也无法直接贪心的题目可以贪心后DP做，并且如果DP的维度太大需要根据性质尝试合并维度或者删除维度。

BZOJ 1217
给你一棵树，上面可以放置一些点可以使距离其2的点染色，求最少放置点染色方案。

贪心做法：对于一个点，如果他的爷爷没有放置点，就放在爷爷上。因为这样可以最优，爷爷放点之后兼顾本节点、父亲节点、兄弟节点。

DP做法：

Codeforces 998D
题意：有$1,5,10,50$四种数字，问用$n$个数字，能构成多少个不同的数字?

打表，发现11项后面的数成等差数列，那么直接前面11项打表，后面用等差数列公式算即可。
附打表程序

Codeforces 1011D
题意：
有一个数字要猜，假设为$x$；给计算机的数假设为$y$，会得到以下三种回答：
若 $x<y$，回答 $−1$；
若 $x=y$，回答$0$；
若 $x>y$，回答 $1$；
但是，现在计算机坏了，对于某些询问会“说谎”；所谓“说谎”就是该回答 $−1$ 的回答了$1$ ；反之，该回答 $1$ 的回答了 $−1$。
抽象为 $01$ 字符串，$0101$ 表示第 $1$ 、$3$ 次询问计算机会“说谎”；若询问的次数大于了 $4$，就会循环；即第 $5、7$ 次会“说谎”。 (hack点)
现在，给这个 $01$ 串的长度 $n$，以及 $x$ 的最大范围 $m$(即 $x≤mx≤m$)。
还要求询问次数最多不超过 $60$ 次。

考虑到$n$只有$30$，所以前$n$次询问$1$骗取 $01$字符串，即询问$1$若回答不是$0$，则都应该是$1$，但是如果是$-1$，则说明当前说谎，记录一下。然后之后二分询问就好，注意若询问的次数大于了$n$，就会循环，Hack点