Codeforces

ACM专题笔记

1. 967A: 水题，把 时/分 转换成分钟存起来然后按题目要求判断即可。
2. 967B: 水题，先求和然后排序一遍从大向小贪心。
3. 967C: 考虑四种方案：从起点向左侧和右侧最近的电梯/楼梯，从终点向左侧和右侧最近的电梯/楼梯，注意特判在同一层的情况（同一层不需要上楼）。
4. 967D: 所选服务器每个服务器能承载的上限是由服务器的下限决定的，因此需要从大向小贪心而不是从小到大贪心。注意需要分别判一遍先贪心A和先贪心B，而不能粗暴地从大的开始贪心。

1. 976A: 水题，易证所有的1只能保留开头的一个，0不会减少。
2. 976B: 水题，分两类讨论，第一类是步数小于N-1的情况下在左边那列，第二类是超过的情况下在后面，除一下就好了。
3. 976C: 先按左端点大小从小到大排序，这样后面的区间的左端点必然包括在前面的区间内，然后如果左端点相同，则按右端点的大的在先。最后在查询时用优先队列维护之前出现过的最大右端点即可。
4. 976D: 首先我们考虑增加一个点并让这个点与现有的N个点连接会发生什么：该点的度将为N，其余的点的度都+1。由此我们分别维护左侧和右侧的度，一旦左侧满足，根据右侧需要减小多少个度来挪动左侧的点，并继续建图直至左侧和右侧的维护点相等。
5. 976E: 贪心，首先对每个点讨论用一个反转的最大值然后排序，先取掉前B-1个大的，然后讨论对谁使用hp2倍，从高到低贪心一遍，复杂度是$O(NlongN)$。

1. 975A: 水题，去重并计算集合大小。
2. 975B: 水题，简单模拟一遍即可。
3. 975C: 暴力模拟会超时，可以写一个树状数组二分查询。

1. 977A: 模拟题。非常水。
2. 977B: 仍然是模拟题，非常水。
3. 977C: 注意+1和-1的越界情况。当然题很简单。
4. 977D: 考虑到只有两种操作：要么乘以3，要么除以2，因此后面的数字的3的因数个数必然大于等于前面，2的因数个数必然小于等于前面，因此按照3和2的因数个数排序即可。
5. 977E: DFS拓扑找环。
6. 977F: 最长上升子序列的简化版 题目数据范围比较大用Map离散化即可。

1. 979A: 注意n=0的时候应该是0而不是1即可。除此之外讨论奇数偶数即可。
2. 979B: 太坑了……有三个边界情况需要分别讨论，还要特别注意全为同一个字母且N=1的特例。被fst了QAQ
3. 979C: 从A点DFS找有B的那条路并返回路长，然后从B点DFS找A，即可求得答案。（本质上就是不允许从B的后面走到A的后面）

1. 984A: 水题，一个人从后拿一个人从前拿，剩下的就是中位数。排序即可
2. 984B: 扫雷，字符串模拟问题。共有四种非法情况，先遇到雷以后检查周围的数字并减去1，然后从头遍历一遍检查有没有除了0和.以外的其他字符。
3. 984C: 数学题，先约分，约分完了检查分母有没有base没有的因数即可。
4. 984D: 区间DP问题。画画图就能画出来。

1. 982A: 水题，两种做法，一种是首尾和中间分开单独讨论，一种是两端补0检测序列000和11。
2. 982B: 排序，内向者是从小到大贪心取，外向是现在内向所占据的排数放进stack后的栈顶的那排。
3. 982C: 可以发现如果子树的节点个数是偶数那就可以去掉节点与子树之间的边。并且去掉这个边是不影响该节点上方的点的，因此可以放心大胆跑一遍。
4. 982D: 并查集可做，条件本质上就是所有并查集都拥有相同的元素个数，只需倒序建图即可做。

1. 985A: 水题，只需要分别检测两种方案的需要的步数然后取较小的即可。
2. 985B: 读错题了…以为是开关奇数次才行，DEBUG半个小时才发现只要开了就不会关MMP.
3. 985C: 先排序，然后判断能不能做到，能做到后再贪心。
4. 985E: 动态规划，先判断能由哪部分转移，求解到目前这个铅笔为止能不能有方案解决，最后检测最后一根铅笔有没有解决方案。

1. 981A: 最长非回文子串长度，因为数据范围太小啦，直接暴力就可以。
2. 981B: B题就是贪心，两个公司都有一种元素时候取价值较大的那个，如果只有一个公司有那显然用该公司的。
3. 981C: 询问是否能把一棵树剖成很多条链，并且这些链两两之间共用一个交点。显然只有两种可行情况：要么是一条单纯的链，这时只有两个点的度是1，其余点度是2，链数是1，要么是从一个节点开始向四周辐射，这时中央的节点度数大于2（仅能有一个节点这样），其余节点为2或者1，链为从中央节点向度数为1的节点走。
4. 981D: 数位DP，从高位往低位考虑。DFS会TLE（使劲剪枝剪到了test 30 ，本机测试跑了2s GG 剪不动了）。

1. 987A: 水题。Map+Set搞定。
2. 987B: 浮点数不能判等于！！！WA四次的血泪教训......
3. 987C: dp转移，dp[i][j]表示从包含第i个数字，并（带上这个数字）挑选了j个。复杂度N方。
4. 987D: 设置超级源点跑最短路。复杂度O(NK+NKlogK)。惊心动魄地跑了1700ms。
5. 987E: 结论题，从现在移动一定次数使之归位，然后判断移动次数与原序列的奇偶性是否相同。