1.打表看dp规律。 2.用excel求回归方程。

rope头文件与命名空间： #include<ext/rope> using namespace __gnu_cxx; 大概可以称作可持久化平衡树，因为rope适用于大量、冗长的串操作，而不适合单个字符操作。rope类似块状链表。复杂度为O\sqrt n。 基本操作： 1）运算符：rope支持operator += -= + - < ==。 2）输入输出：可以用<<运

题意： 给出一个全是数字的字符串S，求其中所有回文串的总和（长得一样的算一个）。S的长度小于等于2000000。 思路： 法一：马拉车+哈希 字符串的各种算法是去年学的现在都忘光了… 所以先复习了一下马拉车（以前好像没有搞得很明白）。 参考博客：https://www.jianshu.com/p/799bc53d4e3d 这篇写得很好。 理解马拉车的原理以后可以知道扩展之前就已经把当前已知的部分回

有一个N*M的矩形，矩形中有K块涂黑了，给出涂黑的坐标，问完全白色的矩形有几个。 根据数据范围的不同，有多种做法。 Gym101350G 容斥1 ≤ N, M≤ 10^4，1 ≤K≤20。 思路： 因为K比较小，N，M又比较大，所以可以考虑容斥。 对于一个N*M的矩形，它的子矩形有C_{n+1}^2\times C_{m+1}^2=\frac{n(n+1)}{2}\times \frac{m(m+

题意： 有N个结点，由M条双向边连接，每条边有权值。可以把最多k条边的权值改为0。问从1到N的最短路为多少。其中1

题意： 有n道题，有a_i和b_i两个值，每道题得在m道题做完之后才能做，给出了这m道题。如果第t个做出这道题目的话，得到的价值为a_i*t+b_i。问最大价值为多少。其中0

bzoj2002题意： 一条直线上有n个装置，每个装置设定初始弹力系数k_i，当达到第i个装置时，它会往后弹k_i步，达到第i+k_i个装置，若不存在第i+k_i个装置，则绵羊被弹飞。 有两种操作： 1 x：当它从第i个装置起步时，被弹几次后会被弹飞。 2 x y：修改第x个弹力装置的弹力系数为y。 思路： 因为直接暴力的话一步一步弹太慢了，是O(n)的，可以考虑分块提前把弹几步处理出来，这样就可

1.__builtin_popcount(unsigned int n)：返回x的二进制下1的个数。 2.__builtin_parity(unsigned int n)：返回x二进制下1的个数的奇偶性（偶数个输出0，奇数个输出1）。 3.__builtin_ffs(unsigned int n)：返回x的最后一位1的是从后向前第几位 （从1开始）。 int n = 1;//1 int m = 8

题意： 给出一个价格n和一些零钱的数量c_1,c_5,c_{10},c_{20},c_{50},c_{100},c_{200},c_{500},c_{1000},c_{2000}。求最多用多少零钱凑出这个n。 思路： 用最少的零钱凑会比用最多的零钱凑好考虑。 如果零钱是1,5,10,50,100,200,1000,2000的话，就可以从大到小直接贪心取，就是每个零钱都是后面一个的约数的时候就可以直

题意： 有n个数形成一个环，问走最多走m次，每次k步，可以从任意位置开始，问得到的最大价值为多少。 思路： 对于一个环，固定步数下是有循环节的。不同循环节内的节点各不相同，根据裴蜀定理可得每个循环节的长度为n/gcd(n, k)。 所以暴力求出所有循环节。对于每个循环节，可以走k步，可知圈数num和圈数外的c，所以有两种情况： 走num圈，并且对于不够整个循环节的c，求这个循环节的长度不超过c的