# 1月
开始打```atcoder```
## abc132
### $a,b,c$ 题：
由于过于简单，直接跳过。
### $d$ 题：
插板法，把篮球分为 $i$ 块，也就是插 $i-1$ 块板子，所以可能性就有 $\dbinom{k-1}{i-1}$ 种，红球同理可得 $\dbinom{n-k-1}{i-1}$。
### $e$ 题：
把一条边拆成三条边，然后再跑一遍```dijkstra```即可。
## abc131
### $a,b,c,d$ 题：
都较为简单，就不再赘述了。
### $e$ 题：
首先，将 $1$ 和其他点之间连起来，保证两个点之间的距离保证最大为 $2$，
那么只需要将其他点向连，每连一次，相距 $2$ 的点就会减少一个，直到剩 $k$ 个为止。
## abc135
### $e$ 题：
贪心，尽量往目标点靠，知道靠到为止，需要注意的是，如果这个点横竖坐标值和为奇数且跳的步数为偶数，那么怎么跳横竖坐标都是偶数，不可能跳到奇数。
### P2329
贪心+二分+```dfs```
# 2月
## abc136
### $e$ 题：
序列无论怎么变，序列和都不会变，那么序列和一定是 $sum$ 的因数，然后从小到大把余数排序，一一配对就可以了。
### 最近公共祖先
倍增或者树链剖分。
## abc138
### $d$ 题 ：
首先先把这个点标记，再搜索一边树，将父亲节点的值加到子节点上。
### $e$ 题：
这道题的意思，主要就是想让你找到完成匹配子串的位置，那么首先可以将原数列的字母都用一个队列分别存起来，那么在每次查找中，我们可以知道这个字母在序列中出现的位置，用一个 $lower_bound$ 找到一个离他最近的点。
## abc134
### $d$ 题：
因为后面的数会将前面求得的答案影响，所以我们从后往前遍历，直接找一遍。
### $e$ 题：
很明显，和导弹拦截一样的题目，考虑贪心，当我们没有能够覆盖这个点的系统，我们可以动用一个系统，如果有，就动用能最小将他拦截住的系统。
### $f$ 题：
进行了 $1$ 次配对，那么有 $3$ 种情况：
- 第 $i$ 个球与没配对的 $j$ 个盒子配对 ，共有 $j$ 种。
- 第 $i$ 个盒子与没配对的 $j$ 个球配对 ，共有 $j$ 种。
- 第 $i$ 个球与第 $i$ 个盒子配对 ，共有 $1$ 种。
总共有 $2\times j+1$ 种情况。
第二行表示进行了 $2$ 次配对，那么有 $2$ 种情况
- 第 $i$ 个球与没配对的 $j+1$ 个盒子配对，共有 $j+1$ 种。
- 第 $i$ 个盒子与没配对的 $j+1$ 个球配对，共有 $j+1$ 种。
共有 $(j+1)\times (j+1)$ 种情况
第三行表示进行了 $0$ 次配对，那么有 $1$ 种情况。
状态转移方程：
```dp[i][j][k]=(2*j+1)*dp[i−1][j][k−2*j]+(j+1)*(j+1)*dp[i−1][j+1][k−2*j]+dp[i−1][j−1][k−2*j]```
## abc139
### $e$ 题：
每次只进行肯定合法的比赛，也就是某两个人正好按顺序都是对方。如果在一轮中找不到这样的比赛，就输出 ```−1```，如果所有玩家该进行的比赛都打完了就输出答案。实现过程中，我们可以用一个数组来记录每个人按顺序应该比的下一个人，假设这个数组是 $now$，那么只要 $a_{a_{i,now_i},now_{a_{i,now_{i}}}}= i$（意思就是 $i$ 按顺序应该比的人也是 $i$ 应该比的人的应该比的人），那么这场比赛一定可以举办，就先举办，并且这两个人今天不能再和其他人比。
## abc137
### $d$ 题：
可以考虑贪心，价值从大到小枚举，先把这个价值取到，也就是在 $1\ldots m-a_i+1$ 中从大到小找，找到最接近且小于且这天没有做过的。但可以知道代码复杂度是 $O(N^2)$，很明显，会超时，但再找的时候，可以用并查集找最接近且小于且这天没有做过的。
### $e$ 题：
考虑每走一步就减去一个 $p$，题目转换为了一个最长路题目。接下来考虑何时是可以一直走，显然是存在一个正权环，跑最长路的时候加一个判断即可。
## P1886
学习了单调队列。
## abc140
### $e$ 题：
单调栈。
### $f$ 题：
贪心，发现一定是先生成大的再生成小的，并且大的数一定去生成刚好小于它的那个数。
## abc141
### $e$ 题：
看到求两个完全相同的子串时，我们可以发现其与求最长公共子串相似，只不过是在同一个字符串中求。因此我们可以使用求最长公共子串类似的 dp 转移。
状态转移：
```
if(s[i]==s[j]&&f[i-1][j-1]<=j-i-1)
f[i][j]=f[i-1][j-1]+1,maxn=max(maxn,f[i][j]);
```
### $f$ 题：
线性基，考虑贪心。
## P3812
学习线性基，于是顺便做了一些相关的题。
## abc143
### $e$ 题：
根据数据（$1 \le n \le 300$），所以很容易想到```floyd```，那么可以先跑一遍，那么的出了每个点对其他地方的最短距离，而每次两个点之间的最短距离不超过 $L$ 时，就可以先让假设他们这两点要用一桶油（所以答案肯定不会超过正确答案），然后再跑一遍，记录最少用油。
然后最后的答案要减去第一次就加满的油。
## abc145
### $e$ 题：
简单的```01```背包。
### $f$ 题：
如果后面那列比前面那列矮或者相等，前面在处理的时候就会顺便把这一列处理掉，所以不用管；如果后面那列比前面这列高，就需要考虑这一列是否需要改动。因为可以改成任意值，所以可以当成把这一列直接删掉。
## abc146
### $e$ 题：
给每一个数赋予对区间长度 $-1$ 的贡献，一段长度为 $L$ 的区间就会产生 $−L$ 的贡献，然后用区间和加上这个贡献就是最后的区间和减去区间长度。最后这个 $−1$ 直接在原数上减一就可以了。
## abc148
### $f$ 题：
如果一个点到 $u$ 的距离小于它到 $v$ 的距离，那么 $T$ 就不会在这个点被 $A$ 追到。然后再暴力搜一遍就好了。
## abc147
### $e$ 题：
直接一个```dp```，很容易得到一个状态转移方程：
```cpp
vis[i+1][j][k+c[i+1][j]]=1;
vis[i+1][j][abs(k-c[i+1][j])]=1;
vis[i][j+1][k+c[i][j+1]]=1;
vis[i][j+1][abs(k-c[i][j+1])]=1;
```
其中，$i,j$ 表示当前转移的位置，$k$ 表示红蓝两种颜色之差。
### AT_abc114_c：
暴力搜索。
### P1196：
并查集水题。
### P1440：
单调队列版子。
### P3865
```RMQ```板子。
## abc152
### $d$ 题：
### $e$ 题：
不难看出，是要求 $\sum_{i=1}^N \frac{lcm}{A_i}$。首先，找出所有数的 ```lcm```。但由于```lcm```需要采用质因数分解来求得最小公倍数，首先把所有 $a_i$ 分解质因数，找出每个质因子出现的最大次数,相乘即可。
### AT_abc119_c
暴力搜索，直接枚举，直到达到条件。
### AT_abc128_f：
直接枚举有 $A-B$ 和 $k$ 即可。
### AT_abc119_d：
二分，找到里 $x$ 最近的点跳过去。
## abc153：
### $d$ 题：
很容易可以模拟出怪兽分裂的过程。
### $e$ 题：
完全背包，状态转移方程如下：
```
if(i-a[j]<0) dp[0]=min(dp[i]+b[j],dp[0]);
else dp[i-a[j]]=min(dp[i-a[j]],dp[i]+b[j]);
```
### $f$ 题：
贪心，从左往右进行模拟。当需要消灭坐标位置为 $x$ 的怪物时，考虑用二分求出 $x-2 * D$ 到 $x$ 范围内对 $x$ 有影响的怪物坐标点。
## abc154
### $d$ 题：
做完前缀和后，直接求：
$$\max^{n}_{i=k}s_i-s_{i-k}$$
### $e$ 题：
```01```背包板子题。
### P2240
考虑贪心，直接按照价值比从大到小排序，再直接拿最大的。
## abc155
### $d$ 题：
二分查找，不过要找到第 $K$ 大的数，还要分正负两种情况。
### $e$ 题：
一道```dp```题，只需要再多开一维记录上一次有没有进位，注意要从后往前，这样修改了前面也好修改，状态转移方程：
```
f[i][0]=min(f[i+1][0],f[i+1][1]+1)+s[i]-'0';
f[i][1]=min(f[i+1][0],f[i+1][1]-1)+(10-(s[i]-'0'));
```
## abc156
### $d$ 题：
求出所有花的搭配方案总和，再减去不合法的两种。式子就是：
$$\sum^{n}_{i=0}C_n^i=2^n$$
### $e$ 题：
枚举空房子的数量，每次答案就是 $C_n^i \times C_{n-1}^{n-i+1}$。
## abc157
### $d$ 题：
使用并查集，再加一个容斥原理。
### $e$ 题：
树状数组板子题，直接修改和查询。
### P3857：
线性基，其实每个开关的组合就是异或，其实就是一道板子题。
### P4301：
其实也是一道线性基板子题，根据[P2197 【模板】nim 游戏](https://www.luogu.com.cn/problem/P2197)可以轻松得出结论：如果先手要胜利，则后手无论拿掉哪几堆都弄不出异或和为 $0$ 的情况。
### P4570：
又是一道线性基板子题，主要用的是贪心。
### AT_abc099_c：
完全背包
## abc158
### $d$ 题：
模拟一下，但是可以转换为判断是否为反的，然后再在开头和结尾加入字母。
### $e$ 题：
因为 $p$ 是质数，所以当两个子串表示的数在模 $p$ 的意义下同余时，其中一个串在另一个串的尾部时，两串对应的数相减，余数相抵消，得到的串就一定也能被 $p$ 整除。
### $f$ 题：
直接倒着来，可以看到每个机器人最多可以往后影响多少个机器人，因为如果可以影响到一个机器人，那么那个机器人可以影响到的也是这个机器人可以影响到的。
## abc162
### $f$ 题：
可以记录一个前缀和，分别处理单数位的，和双数位的，然后因为要向下取整，那么需要分 $2$ 种情况，一种情况是 $n$ 为偶数：那么就需要找到从哪里断掉，再利用前缀和求出和，另一种情况是 $n$ 为奇数，那么可以用```dp```，记录这位之前，它的最大值以及他现在已经断了几次。
## abc214
### $d$ 题：
用并查集维护树，权值乘上链接两树的大小之积可以得出每个边权的贡献。
### $e$ 题：
贪心，首先现将区间按左端点从小到大排序，如果后面有一个区间实在需要这个点（就是右端点到了我们找到的位置），那么这个点让给这个区间，如果有两及以上的区间都需要，那么直接无解。
### $f$ 题：
动态规划，也就是要你求有多少个不同的子串，但是如果两个字符有相等的就会重复，那么就可以不用算了。
状态转移方程：
```
f[i]=(f[i]+f[j])%Mod;
if(j>=1&&s[i-1]==s[j]) break;
```
### P6397：
考虑二分，二分时间。
## *树链剖分板块*
### P3384：
直接把这个树变成一个序列，然后再利用刚排完的序来一个线段树，就可以通过了。
### P6098 [USACO19FEB]Cow Land G：
先把这棵树变为一个序列，然后使用线段树维护区间异或值，由于异或满足结合律所以先计算一个个的区间异或值最后异或在一起的结果和要求的路径异或值相等，那么可以直接得到答案。
### P3976 [TJOI2015]旅游：
先把这棵树变为一个序列，然后用线段树维护四个值：
1.区间最大值。
2.区间最小值。
3.从左至右的最值之差。
4.从右至左的最值之差。
为什么要维护这四个值呢？因为对于同一个区间，从左到右和从右到左所得到的答案是不同的，所以要按方向分开维护。
### P7735 [NOI2021] 轻重边
考虑给每个点都染上色，重边就就是两端点颜色是相同的，否则为轻边。然后用线段树维护每个点的颜色。在同样先求出点 $a$ 和 $b$ 的最近公共祖先 $Lca$，然后统计路径 $(a,Lca)$ 和 $(b,Lca)$ 上的重边数即可。
### P4719 【模板】"动态 DP"&动态树分治
虽然不是用树链剖分做的，但是因为数据过水，我们可以用树形```dp```直接算出答案。
### P4074 [WC2013] 糖果公园
树上加带修莫队，利用欧拉序把树上莫队转化为普通莫队，然后可以用树链剖分求出他的最近公共祖先。