NAQC2017D
题意：
有一只猫去捉n(n<=15)只老鼠，猫的初始位置在(0,0)，给出n只老鼠的x,y,s，分别表示所在位置和s秒后会钻入地下，猫每捉到一只老鼠速度会*m(m<1)，问猫的初速度至少为多少才能捉到所有老鼠。
思路：
看数据范围很容易想到要状压dp，可是发现每个状态要记录的有两个量，时间和初速度，如果把其中一个加一维，就开不下了。
其实对于类似记录的有两个量的题目，还可以用二分+dp的思路。
这里二分初速度，然后dp记录下到该状态的最小时间就可以了。
这里我状压的两重循环写反了…结果debug了好久啊（甚至下了数据…
NAQC2016D
题意：
给出一个括号序列，可以选择翻转一个区间，问能否匹配。其中len<=5000。
思路：
如果把’(‘记为1，把’)’记为-1。匹配的条件为每个前缀和都>=0而且总的前缀和为0。
根据数据范围可以看出可以dp。
没想到要怎么dp…其实可以先考虑一下这如果要搜索要怎么写，然后记忆化一下。
这里可以设计状态，其中sta表示没有翻转，翻转过且连续，翻转过且没有连续。
然后转移一下就可以了。
Codeforces1073C
题意：
给出一个包含’L’,’R’,’U’,’D’的序列，要到达(x,y)，而且可以改变一些字符，把改变的长度定义为改的最后一个字符和改的第一个字符的距离。问这个改变的长度最小为多少。如果无论怎么改都不能到达(x,y)，则输出-1。
思路：
可以对答案进行二分。
确定好改变的长度后，枚举改变的区间，这个区间里面的值都是可以改的，所以统计一下除了这个区间以外的走得到的所在的位置，因为区间里面的都是可以改的，所以只要当前位置到最终位置的曼哈顿距离小于等于区间长度就说明是可行的，否则就不可行。
Codeforces1073D
题意：
有n个店家形成一个环，初始有T元钱，每个店家可以买元的东西，当前的钱可以买的时候就一定要买，问最终能买多少东西。
思路：
可以模拟。
对于n个店家，按顺序看能买哪些店家。
然后对这些可以买的店家计算可以买几次，钱也相应更新就可以了。
Codeforces1076D
题意：
给出n个点m条边，把从1到i的最短路记为，问在最多剩下k条边的情况下，使不变的个数最多。求这些剩下的边。
思路：
要剩下的肯定是在所有最短路中经过最多次数的边。
这里怎么处理呢。可以在求最短路的过程中记录下每个顶点的前驱，然后就形成一棵最短路径树。因为要的是经过最多次数的边，所以bfs就可以了。
Codeforces1076E
题意：
给出一棵有n个结点的树，每个结点的权值初始都为0。给出m组操作，在v的子树中与它的距离小于等于d的结点的权值都增加x。问在这些操作之后，结点的权值分别为多少。
思路：
这里是区间修改单点查询。
因为每个结点的权值变化只与祖先的操作有关系，所以就可以直接把每个深度当成区间。在dfs的过程中进入一个有操作的结点，对深度的区间进行修改，这样它的子树就会受到影响。然后单点查询就可以。出这个结点要把区间修改回来，因为从该结点出来之后访问的就不是它的子树了，它的操作对那些结点不会有影响。
Codeforces1077F2
题意：
给出n个数，在每k个数里至少选一个，总共选x个，问最大值为多少。
思路：
可以想到是dp+单调队列。
刚开始想的是这么设计状态：到第i个总共选了j个的最大值，然后分选和不选来转移，这样子是不行的，因为你得确定知道转移过来的这个到底有没有被选。
所以要这么设计状态：选了第i个总共选了j个的最大值。
Codeforces1054D
题意：
给出n个数，每个数都可以，在所有区间中，让区间异或为0的区间最少。问在这种情况下，异或不为0的区间有多少个。
思路：
首先异或是可以前缀和的，xor[l,r]=pre[r]-pre[l-1]。
所以要使异或和相同的最少。因为在一个区间中如果两个数都取反就相当于没变，所以每个异或只有两种情况。
所以就贪心取不同的前缀和然后计算一下就可以了。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！