竞赛刷题记录
2019.10.01
p1098 字符串的展开 模拟
p1023 税收与补贴问题 模拟
p1068 分数线划定 排序
2019.10.02
p1309 瑞士轮 排序 ————> 归并思想，分胜负两组进行合并
p1093 奖学金 排序 ————> 快排，熟悉cmp用法
p1012 拼数 排序 ————> 快排，字符数组排序
p1090 合并果子 贪心 ————> 堆排，可以用标准模板库STL
2019.10.03
p1080 国王游戏 贪心 ————> 数学推理，结合高精度（高精*单精，高精/单精）
p1019 单词接龙 DFS
p1040 加分二叉树 区间dp ————> [https://www.luogu.org/problemnew/solution/P1040](https://www.luogu.org/problemnew/solution/P1040)
- [ ] 另解：树形dp，以后再学，，
p1092 虫食算 DFS ————> 疯狂剪枝，太难了，心痛
2019.10.04
p1443 马的遍历 BFS ————> 模板题，注意输出格式和数组大小
p1126 机器人搬重物 BFS ————> 考虑bfs每一步应该是相同花费，平等的往外扩展
p1118 数字三角形 DFS ————> 比较简单的剪枝
p1141 01迷宫 BFS ————> 求连通块，bfs队列不需要memset
p1434 滑雪 DFS ————> 求最大长度，dp思想
2019.10.05
p1226 快速幂（模板）分治
p1908 逆序对 分治 ————> 归并排序
2019.10.06
p1316 丢瓶盖 二分 ————> 最小值最大
p1182 数列分段 二分 ————> 最大值最小
p1020 导弹拦截 dp ————> 线性dp，最长不上升子序列，n^2 (还有nlogn的超强做法，以后再说）
p1091 合唱队列 dp ————> 线性dp，左右分别球最长上升子序列
p1280 尼克的任务 dp ————> 线性dp，从后往前搜
2019.10.08
P1880 石子合并 dp ————> 区间dp，f[i][j] = max(f[i][k] + f[k+1][j] + d(i,j))
在考虑如何递推时，通常考虑如下几个方面：
是否能覆盖全部状态？
求解后面状态时是否保证前面状态已经确定？
是否修改了已经确定的状态？
2019.10.11
p1462 通往奥格瑞玛的道路 最短路 ————> spfa+二分
p3366 最小生成树（模板）kruskal
p3367 并查集（模板）
2019.10.21
Codeforces Round #587 (Div. 3)
A Prefixes 水题
B Shooting 水题
C White Sheet 水题
D Swords 水题
E Numerical Sequence (easy version) ————> 数学方法（分段，等差数列）+二分
F
2019.10.22
Codeforces Round #590 (Div. 3)
A Equalize Prices Again 水题
B Social Network ————> 双向队列，离散化
C Pipes ——> 水题
D Distinct Characters Queries
题意：给你一个字符串，然后有两个操作
1 a b 把字符串中a 位置的字符 替换成b
2 a b 查询字符串中 a - b区间中不同字符的种类数
思路：方法一：（树状数组）可建立26个树状数组，对应着26个字符所代表个数的前缀和，进行2操作时只需要进行26次循环查询对应区间有无这个字符即可，若有sum++
方法二：（set）set存储字符所对应的字符的下标。然后2操作时，进行26次循环，看每个字符set中，有没有一个数在 区间内即可。
方法三：（线段树，位运算）每一位都取往左移当前对应的数字（b：1<<1, d:1<<3），从叶子结点往上结点为子节点的或运算。
2019.10.22
Codeforces Round #595 (Div. 3)
A Yet Another Dividing into Teams 水题
B Books Exchange ————>并查集求连通块大小，或 dfs
C Good Numbers (hard version)
题意：求大于n的m，m有不同的3的次幂。
思路：先把 n 内所以3的不同次幂减去，保存在一个ans里面，然后从小到大找一个找出没使用过的3的次幂，使它大于n，加入答案。
D Too Many Segments (hard version)
题意：给定n个线段，线段可以相交，第i个线段覆盖的区间为[li,ri]，问最少删除多少个线段让覆盖每个点的线段数量小于等于k。
方法一（贪心+树状数组）：从左往右扫每个点x，若覆盖点x的线段数cnt大于k，则贪心的删去覆盖点x的线段中ri前cnt?k大的线段，因为点x左边的点的被覆盖数一定已经小于等于k了，删去ri越大的线段越优。可以用个堆来维护覆盖点x的线段，用树状数组维护覆盖每个点的线段数量。
[https://www.cnblogs.com/xyq0220/p/11731632.html](https://www.cnblogs.com/xyq0220/p/11731632.html)
方法二（set+vector）：将所有线段用set维护，然后从小到大枚举端点，将左端点覆盖到这个点的线段加入set中，当线段的数量大于k，移出r最大的线段，最后将右端点等于这个点的线段全部移出；
[https://www.cnblogs.com/Carered/p/11730926.html](https://www.cnblogs.com/Carered/p/11730926.html)
E. By Elevator or Stairs?
题意：n层楼，a[i] (02019.10.24
Codeforces Round #596 (Div. 2)
A Broken Keyboard 水题
B Binary Palindromes 水题
题意：给n个01序列，可任意交换，求可构成回文序列的最大数量
思路：若一个序列的0或1为偶数，则自身可以构成回文序列，只需处理0和1均为奇数的情况；若0和1均为奇数的串为偶数，则答案为n，若为奇数，则答案为n-1
C Minimize The Integer 水题
题意：一个数字序列，相邻的奇数偶数可以交换，求交换后的最小值0709->0079
思路：奇数偶数相对顺序不变，故将奇数偶数分成两个序列，依次输出较小值
D Salary Changing 水题
题意：有N名员工和S元钱，然后我们想知道在每一名员工有薪资要求在[li, ri]的情况下，我们如何在总共就S元钱的情况下做到员工薪资的中位数最高？
思路：我们可以去二分答案这个中位数，那么，如果说右区间小于这个中位数的，我们直接加他的左区间，同样的，当右区间大于这个中位数且左区间小于这个中位数（这里提到的中位数都指的是二分答案的答案）那么就直接判断，如果现在小的还不够，就直接用小的，如果小的够多了，就让他取中位数的钱，再最后就是，左区间也大于中位数的，那么直接使用左区间即可。