| 日期 | 任务||目标 | 题目 | 完成情况 | 算法 | 易错点 | 思维难度 | 总结 |
|---|---|---|---|---|---|---|---|
| 2022/4/28 | 入门经典P220-P240 | 汤姆斯的天堂梦 | AC | 动态规划 | 循环嵌套 | 查看题解 | 输入数据存不下时，输入的时候运算 |
| 归并排序 | AC | 分治 | 循环嵌套，范围限制 | 程序实现能力 | 分治法，递归 | ||
| 2022/4/29 | 动态规划 | 矩形嵌套 | 动态规划 | 路径记录 | 注意变量含义，动态规划，有向无环图注意链表，跳过未连接数值 | ||
| 2022/4/30 | 入门经典第6章 | 二叉树存在问题 | |||||
| 2022/5/1 | 入门经典第7章 | 停在回溯法 | |||||
| 2022/5/2 | Polya定理 | Let It Bead | AC | Polya | Polya定理G应包含所有置换方式，旋转，翻转。加入的置换方式越多，排除的重复种类越多 | ||
| Necklace of Bead | AC | Polya | Polya定理G应包含所有置换方式，旋转，翻转 | ||||
| 2022/5/3 | Invoker | AC | Polya | 注意取模 | t=tn%mod和t=n%mod不一样 | ||
| color | AC | Polya | 中上 | 在Polya定理中，若G不纳入翻转情况，则不会排除翻转所产生的重复情况，欧拉函数，定义最小公倍数，和其中一个因数，可以求出另一个因数的个数 | |||
| Count the Tetris | AC | Polya 高精度 | 程序实现能力 | 定义结构体，重载运算符，进行高精度运算，正方形的G会包含沿对角线翻转。当运行出错时，修改过程中，通过输出语句判断哪里死循环等 | |||
| 2022/5/4 | 解决考试题目 | 铺地砖 | AC | 随机 | 易 | 进一法 | |
| 超速 | AC | 暴力 | 易 | 数据范围小时，暴力 | |||
| 打印图像 | AC | 递归 | 中 | 二维数组的值进行修改，可以换行修改，根据数值转换成字符输出，递归的每一层为下一层做准备，注意空格数量 | |||
| 单色三角形 | AC | 暴力 | 易 | 手动开O2，#pragma GCC optimize(2) | |||
| 年终大奖 | WA AC | 图 | 中 | 有向无环图，通过链接，注意取等，动态数组从零开始，.size()求其长度，一维的样子本质二维，.push_back()放在末尾，全部只适用于动态数组 | |||
| 猜数游戏 | 待解决，先学方法 | 线段树，二分答案，排序；并查集；链表 | 无 | ||||
| 排列区间 | 待解决，先学方法 已解决 | 分治+线段树||ST表；哈希；单调栈 | 无 | ||||
| K峰区间 | 待解决，先学方法 已解决 | 分治+线段树||ST表；哈希；单调栈 | 无 | ||||
| 2022/5/5 | 学习并查集，解决猜数游戏 | 无 | |||||
| 网络流学习 | 无 | ||||||
| ST表学习 | OK | 无 | |||||
| 5月6号 | 运用ST表解决问题 | ST表模板题 | AC | ST表 | 数组f[i][j]左右值的取等，第二指针的取值 | 普及- | |
| 牛客小白赛 | 三进制 | AC | 易 | 读取输入，用字符串类型，可方便分离数位 | |||
| 老板的礼物 | AC | 易 | 标记，清空标记 | ||||
| 5月7号 | 解决考试题目 | 排列区间 | AC | ST表查询 | |||
| K峰区间 | Ac | 用pre表示重复出现的数的位置，枚举最大值，若差值小于重复出现的数的位置，成立 | |||||
| 5月8号 | 最大字段和 | AC | 前缀和 | 循环嵌套注意开始下标 | 普及- | for(int i=1;i<=N;i++)for(int i2=1;i2<=i;i2++) ans=max(ans,m[i]-m[i2-1]); i2-1包含只去i=1的情况5月9号 | |
| 5月10号 | 填坑 | 线段树模板（2） | AC | modify( ){if(l>=L&&r<=R){pushup( );return 下穿标记时，要计算sum 乘法时，初始值为1 | 普及+/提高 | ||
| 跑路 | AC | 动态规划求最短路 倍增 | 普及+/提高 | 两条2k-1的路可以看成2k的一条路，以时间为路的权值，求最短路 | |||
| 数学计算 | AC | 以时间轴建立线段树 | 每棵树的初始值为1 | 提高+/省选- | 在线解答，输入一个数值，插入线段树上，返回时计算答案 | ||
| 生活大爆炸 | AC | 小模拟 | 普及- | ||||
| 5月11号 | 动态规划引入 | 选择数字 | AC | 单调队列优化动态规划 | f[head]里存放的是数值 | 提高+/省选- | 求选择多少个数最大，反向思考，删多少个数最小，用单调队列维护 |
| 采药 | AC | 动态规划 | 普及- | 01背包问题，转移方程从上一层转移过来，枚举可用空间，1 3 2和1 2 3 是一种情况 | |||
| 疯狂采药 | AC | 动态规划 | 普及- | 完全背包问题，转移方程是从同一层转移过来，也是枚举可用空间 | |||
| 挖地雷 | AC | 记忆化搜索，DFS | bool数组只返回1 0 | 普及- | 用vector记录路径，.push_back()倒叙输出 | ||
| 弗洛伊德 | 最短路 | 弗洛伊德求最短路，暴力N的三次方，两定点，循环枚举中间的点，满足三角形不等式则替换 | |||||
| 迪杰斯特拉 | 最短路 | 定原点，定汇点，贪心选择下一节点，每次更改一个节点，N的平方 | |||||
| A* | 最短路 | 在迪杰斯特拉算法的基础上，加入了F（x）一代价函数，更加合理 | |||||
| 2022/5/12 | 线性动态规划 | 炼制宝剑 | AC | 单调队列优化动态规划 | 普及+/提高 | 动态转移方程有很多种，找到方程中的定值，变量，可以进行单调队列，找到上层式子，k的取值范围，设置窗口，随j的值滑动，考虑到要顺序放置，贡献与当前锅内的原料有关，所以考虑将这两个东西加入 dp 式。 | |
| 动态规划引入 | 单调队列模板题 | AC | 单调队列 | 普及- | 注意head和tail的值，id[tail]里存放n数组中的位置 | ||
| 动态规划引入 | 排列组合 | AC | 易 | Cn r==C n n-r，边算边除 | |||
| 入门经典P270—P280 | 例题未解决 | ||||||
| 2022/5/13 | 线性动态规划 | 最长公共子序列 | AC | 二分优化DP | 普及+/提高 | 全排列：1—n，每个数各不相同，且全部出现 求最长公共子序列，A序列地址单调递增，将B序列值等价替换成A序列的地址，则求B的最长上升子序列 | |
| 线性动态规划 | 摆花 | AC | 记忆化搜索，DFS | 普及- | 记忆化搜索，函数定义为“int”，比较方便 | ||
| 动态规划 | 普及- | 动态转移方程——dp[i][j]=dp[i][j]+dp[i-1][j-k].max呢？灵活点，方案数加法原则 | |||||
| 2022/5/14 | 洛谷月赛 | 连线 | AC | 暴力深搜+广搜 | 范围 | ||
| 连续数求和 | AC | 解方程 | 等差数列求和公式多种，选择合适的公式 | ||||
| 环上最远点 | T，带解决 | 二分+贪心 | |||||
| 走在夜晚的莲台野 | AC | 贪心+数学推理 | 注意范围 | ||||
| 2022/5/15 | ABC251 ABCDE | Six Characters | AC | 字符串 | ABC | 字符串赋值，‘A’或string a;string b;string c;c=a+b; | |
| ABC251 ABCDE | At Most 3 | AC | 暴力 | ABC | |||
| ABC251 ABCDE | Takahashi and Animals | AC | 动态规划 | ABC | N位是否取对第一位有影响，分类讨论，跑两次，比较m,n | ||
| 2022/5/16 | ARC140 A | Right String | AC | 暴力 | ARC | 将字符串首位扔向末尾，重复次数与最小循环节相等 | |
| ABC249 AB | Jogging | AC | scanf输入7个数，%d若只有6个，不会报错,但会出错 | ABC | |||
| ABC249 AB | Perfect String | AC | 输入字符 s[i]-'a'是转化成整形的运算 | ABC | |||
| ABC249 AB | Just K | 待解决 | ABC | 递归选择和处理 | |||
| ABC249 AB | Index Trio | 待解决 | ABC | 暴力枚举，3方算法；标记存在，2方算法；因数枚举，根号算法 | |||
| 2022/5/17 | ARC139 A | Trailing Zeros | AC | 二进制 | 数组大小大大大（3个小时的血泪） | ARC | 位运算开2的平方倍，特别快 |
| ARC138 A | Larger Score | AC | 双指针 | 初始值赋值 | ARC | 多种方法：1.双指针，以k为节点，先左右排序，又指针为主动点，左指针为从动点，在设定初始值时，可以设为最值，在一定情况下不会更改，也可以设为负值，在运行时特判； 2.线段树维护区间最值，用LOG的时间进行查询区间最值 | |
| 2022/5/18 | ABC251 ABCDE | Poem Online Judge | AC | map 数组 | ABC | map<A,B>maps;其中，map为关键字，A为指针类型，B为值，maps为变量名称 | |
| ABC251 ABCDE | At Most 3 | AC | 100进制 | ABC | 用一些数字组合成一个数，将目标数转换为一定的进制，二进制需要320个砝码，不符合题意，一百进制需要300个，刚好符合题意 | ||
| ARC137 AB | Coprime Pair | AC | 暴力 | ARC | 每两个素数之间的差值最多在50左右，暴力枚举 | ||
| ARC137 AB | Count 1's | AC | 贪心+动态规划 | ARC | 站在0或1的角度，可将1和0转化成1和-1，求最大连续字段和 | ||
| 2022/5/19 | ARC135 | Floor, Ceil | AC | 暴力+记忆化搜索 | ARC | map数组下表可以开到1e18，不可超过long long，可用与较大数的记忆化搜索 | |
| ARC135 | XOR to All | AC | 暴力+异或（位运算，不相等时，为一） | ARC | 一个数列，选取一个数异或其他所有数，只有最后一次异或有作用，暴力枚举每一个数，在二进制下，数据范围小于等于2的60次方，优秀的暴力，存下每一位的一的个数；<<位运算，左移N位，2的N次方，甚至比调用还快 | ||
| ARC135 | Sum of Three Terms | AC | 贪心 | ARC | 运算每一位，求出各对应位的最小值，用贪心的思想设为零 | ||
| 2022/5/20 | 忘了 | ||||||
| ABC252 ABC | ASCII code | AC | 字符串 | ABC | 将ASXII数码转化为字符输出 | ||
| ABC252 ABC | Takahashi's Failure | AC | 排序 | ABC | |||
| ABC252 ABC | Slot Strategy | AC | ABC | 暴力搜索，逐位比较 | |||
| 问题 A: 表达式最值1 | AC | ||||||
| 问题 B: 网购礼物(增加一组数据) | AC | ||||||
| 牛客小白赛 | 跳跃 | 除法会有精度误差，应该转化成乘法 | |||||
| 2022/5/22 | 入门经典 | wector map quere | 未解决 | ||||
| 2022/5/23 | CF | Digit Minimization | AC | 入门 | 做题时，先想清楚，否则浪费更多时间 | ||
| CF | Z mod X = C | AC | 构造 | 普及- | 说不清如何构造，输出a+b+c，b+c,c… | ||
| UVA | UVA816 | 未解决 | 输入有点恶毒… | ||||
| ABC 246 ABCD | Four Points | AC | ABC | 分类讨论或者找共同点if判断 | |||
| Get Closer | AC | ABC | 浮点型，printf 用 f，保留12位小数 0.12f | ||||
| Coupon | AC | 贪心 | 注意i的范围，要取值所有范围 | ABC | 说不上是贪心，一眼可以看出来 | ||
| 2022/5/24 | UVA | UVA816 | 放弃，差输出格式 | 迷宫问题，求最短路，在Bfs的基础上面，限制了方向，进行方向转换，转化成迷宫问题，在打印路径时，可以递归打印或者递推打印，递归容易炸栈，递推可以用vector；此外，恶心的输入考察字符串转整型，scanf最好不要输入string，用cin比较好，scanf输入char时，会读取空格，要加&符号，如要跳过空格，%d\0%c%d，在“%d”和“%c”之间打上空格；记录路径时，注意状态，应包含3个状态，避免覆盖 | |||
| ABC 246 ABCD | variable Function | AC | 勉强算的上双指针的思想 | ABC | 暴力枚举，双指针，O(n)的时间复杂度，妙 | ||
| CF | Column Swapping | WA | sort排序，不要与地址联系上，它会怎么排序，是交换排序还是选择排序，说不准 | sort相同数字的相对位置有可能会被改变，但手写归并。。。 | |||
| 2022/5/25 | CF | AGAGA XOOORRR | AC | 异或和 | 满足题目要求的数列最终可以简化成2或3个相等的数，因此暴力枚举划分区域；异或可以反推，因此算前缀和以节省一层循环 | ||
| 编写题目 | 完成 | ||||||
| 2022/5/26 | CF | book | AC | 拓扑排序和链式前向星 | 每一本书的前置章节，是拓扑排序中的小于，用拓扑跑最长路，跑完后，若出现有点还有连边，则为环 | ||
| ARC132 | Permutation Grid | AC | 诈骗 | ARC | 考试一直没明白为什么只有唯一解，后将整篇文章翻译后，给的是一个排列，下次要把题目翻译完全 | ||
| Shift and Reverse | AC | ARC | 考试时看样例没看出规律，题目中给出绝对有解这一条件，反推回去，得出结论 | ||||
| 2022/5/27 | ARC131 | Two Lucky Numbers | AC | 诈骗 | ARC | 给出两个数，每个1e8，输出的值小于1e18…将两个数拼到一起 | |
| Grid Repainting 4 | AC | 暴力 | ARC | 700的数据范围，是个矩阵，纯爆搜 | |||
| Zero XOR | AC | XOR | ARC | 求异或，异或，不相等则为一，删除一个数，异或和为0，在博弈论中，先手只有第一次和最后一次可以赢；2进制的位运算中，注意优先级，低的可怜，打括号 | |||
| 洛谷 | P1347 排序 | AC | 提高+/省选- | 这道题很妙，首先，要确定元素的顺序，在每一次的拓扑过程中，只可加入一个点，若两个点同时加入，则无法确定；在拓扑排序的过程中，若出现环，则会至少两个点没有进入拓扑序，通过判断是否遍历了每一个点，来判断是否有环 | |||
| 2022/5/28 | 洛谷 | P1137 旅行计划 | AC | 普及+/提高 | 有比蓝题还难的绿题，也有比黄题还简单的绿题 | ||
| NFLS | 问题 A: 正方形 | AC | 正方形可以倾斜，保留两点之间插值的正负 | ||||
| NFLS | 问题 B: 最小的x | AC | 数论 | 转化成平方差公式，枚举因数 | |||
| NFLS | 问题 C: 简单的迷宫 | AC | BFS | 广搜，在方向转换上dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}，循环 | |||
| NFLS | 问题 D: 子矩阵 | AC | 二维前缀和 | ||||
| 2022/5/29 | 洛谷 | P3367 【模板】并查集 | AC | 普及- | 路径压缩 | ||
| 洛谷 | P1873 [COCI 2011/2012 #5] EKO / 砍树 | AC | 二分查找 | 注意死循环 | 普及/提高- | 二分查找 | |
| 2022/5/30 | ARC130 | Remove One Character | AC | 查找 | 要求删除字符，结果不变，只可删除相邻的两个相同字符，定义一个last和cnt，相等cnt++，否则为1 | ||
| Colorful Lines | AC | 重点是覆盖，且只求最后一次？？？倒叙离线，map |
|||||
| 洛谷 | P3368 【模板】树状数组 2 | AC | 普及/提高- | 这两个树状数组，确实比线段树好写，适用于单点修改，区间查询，差分：区间修改，单点查询，但注意判断越界，在查询的过程中不得小于0，add过程中，不得大于maxn | |||
| 洛谷 | P3374 【模板】树状数组 1 | AC | 普及/提高- | ||||
| 2022/5/31 | ARC129 | Smaller XOR | AC | 这异或……第一步做对，一异或零不变，可利用性质，两个一为零，考试傻了，将一个数转化成二进制后没有使用原数，反到锲而不舍的把二进制转化成十进制…傻逼 | |||
| Range Point Distance | AC | 说不上贪心，毕竟有点假，找到最右边的左端点和最左边的右端点，若左边任然在左边，输出0，否则输出左减右向上取整…（这是第二题？？？找回自信，秒切，样例都不带测+_+ | |||||
| 洛谷 | P1168 中位数 | AC | 树状数组 | 普及+/提高 | 首先，离散化，然后建一棵权值线段树，通过树状数组查询找的是前缀和的特性，判断这是第几个数；在离散化的时候，注意原数与离散化后的数建立联系，原数的下标比较合适 | ||
| 洛谷 | P5057 [CQOI2006]简单题 | AC | 树状数组+异或和 | 普及/提高- | 异或运算自带可逆性，建一棵异或和树状数组 | ||
| 2022/6/1 | 洛谷 | P1379 八数码难题 | AC | 提高+/省选- | 这个。。。那个。。。用BFS，but撞运气，几乎算得上一个暴力，纯暴力 | ||
| ARC128 | Gold and Silver | AC | ARC | 一道贪心，但是干感觉写假了，估计还要看一看，在高处买金，在低处买银，因为题目要求最后全是金，记录购买次数，若为奇数，则舍去最后一次 | |||
| Balls of Three Colors | AC | ||||||
| 2022/6/15 | ARC126 | Make 10 | AC | 三为奇数，若数量落单，可省略，翻倍转化成6，分类讨论 | |||
| ABC221 | A - Seismic magnitude scales | AC | ABC | 签到题 | |||
| B - typo | AC | 注意在交换后要换回来 | 签到题 | ||||
| C - Select Mul | AC | 两种情况，递归分类讨论，分完类进行计算，注意最后换回来，算得上一个解答树的生成过程 | |||||
| 记忆\程序\洛谷\树状数组&&线段树\求逆序对.cpp | P1168 中位数 | AC | 树状数组 | 普及- | 先求出所有序对的个数，然后减去非严格顺序对的个数 | ||
| 2022/6/16 | ABC221 | D - Online games | AC | 离散化 | ABC | 离散化后分类讨论，unique去重，全完重后，返回值减去“c||c+1。。。”为去重后序列长度，lower_bound找到数值，将他以地址为下标赋值给a【i】数组，在搜寻原数值c【i】询问 | |
| ARC125 | A - Dial Up | AC | BFS思想 | 最开始疯狂分类讨论，写假了，在一个序列中找数，要最短距离，可以用BFS的思想，类似于找分类讨论中的共同点 | |||
| 2022/6/17 | 洛谷 | SP3267 DQUERY - D-query | AC | 普通莫队 | 提高+/省选- | 普普通通的莫队，无，我称ta为二维 | |
| 洛谷 | P1903 [国家集训队] 数颜色 / 维护队列 | AC | 带修莫队 | 提高+/省选- | 普通莫队的加强版，每一个点在被查询时，可能被修改了不同的次数，所以加上一个时间轴，在结构体中加入一个cnt，表示在它之前有几次单点修改，算得上三维莫队，l，r，t；以l所在块为第一关键字，r所在块为第二关键字，t为第三关键字，当三个关键字完全匹配时，可进行查询操作，l,r指针移动和普通莫队一样，将此次q的cnt于上次cnt像比较，多的减去，少的加上，网上有些方法要把原数和被修改的数都记下来，实际上用swap交换两个的值，可以省一些空间；在单点修改的时候，只有修改的点在查询区间里，才会对now有所改变；map使用自带log，时间上会炸；带修莫队因为是三维，所以块长pow(N,2.0/3)... | ||
| 洛谷 | P1972 [SDOI2009] HH的项链 | AC | 莫队思想+树状数组 | 提高+/省选- | 经过非严格证明，若查询区间中存在相同的数，可以用区间最后一个替代前面所有。So，记下每一个数的前驱，则只要r递增，便可在每一次加入一个新数的时候，把他前面的数删掉，注意在对一个数据的多次使用中，记得确保他的正确性 | ||
| ARC125 | B - Squares | AC | 数论 | ARC | 将xx-y转化成完全平方式子，（x-k）（x+k）=y，枚举较小的数，枚举到根号下N，因为（x+y）+（x-y）为2x，所以两个因数奇偶相同，可以直接算出答案 | ||
| 洛谷 | CF1311F Moving Points | AC | 二维偏序&&树状数组 | 提高+/省选- | 有可能是二维偏序的板题，没看题解——。。。多个点的移动，只需要判断一个点在它左边且速度比它要小，可以先以v为第一关键字排序，but but若第一关键字相等，以id为第二关键字排序，没注意到。。。结果写了对拍——，建两棵树状数组，一颗表示它前面有多少个点，一棵表示他前面的点的id和，all*id（itself）-id（sum）。。。 | ||
| 2022/6/18 | 洛谷 | P3379 【模板】最近公共祖先（LCA） | 100分 | 暴力 | 普及/提高- | 暴力没什么特殊滴 | |
| AC | 倍增 | 把我整哈了，在倍增的过程中，必须确保当前节点的父节点已经被赋上它的父节点的值，因此，倍增必须有一个顺序，有深度为第一关键字从小到大排序的顺序 | 普及/提高- | 倍增也就是在暴力的基础上“小小”的改了一些，从1000到1400，不多不多，f[x][i]=f[f[x][i-1]][i-1]倍增一下它的一级祖先，二级祖先，每次从二维20开始，依次递减，只有倍增后深度小于等于才可以跳，两个同时跳的时候，要求两个跳了以后不相等；有两种情况，一种是两点在两条不同的链上，此时，他们的f[x][i]会相等，但它们自己不会相等，第二种是两个点在同一条链上，则在让二者深度相同的时候，便会让二者变成同一个点，So，在最后输出的时候特判一下，a==b？a:f[a][0]... | |||
| ABC256 | A - 2^N | AC | 位运算 | 位运算地位比较尴尬 | ABC | 2的N次方：1<<N | |
| B - Batters | AC | 题目有点小长 | ABC | 无 | |||
| C - Filling 3x3 array | AC | 暴力 | 诈骗 | ABC | 在一个3*3的矩形中，求有多少种填法，单行单列和<=30，明显的暴力，枚举（1，1）（1，2）（2，1）（2，2）四个点,可以确定这个矩形，(1,3)(2,3)两个点可以用单行和求，但(3,3)既要满足单行，也要满足单列 | ||
| D - Union of Interval | AC | 差分 | ABC | 要求用最小的区间表示一连串左闭右开的区间，单点修改会T，所以用上了差分 | |||
| 学习二维偏序求LIS | OK | 二位偏序，x从小到大排序，y从大到小排 | |||||
| 学习树链剖分 | |||||||
| 2022/6/19 | CF802 | A. Optimal Path | AC | 贪心 | Div.2 | 最开始被吓到了，想到了单源最短路，结果是贪心，走的路线是“L”旋转180 | |
| B. Palindromic Numbers | AC | 高精 | Div.2 | 模拟除法，直接加一个借位变量即可，从后往前 | |||
| 2022/6/20 | ABC256 | F - Cumulative Cumulative Cumulative Sum | WA | 树状数组&&线段树 | ABC——F | 一个式子，是与求和相关的，每次查询一个区间的和，有单点修改，用线段树或树状数组维护，凡是与修改值有关的区间，扔到数据结构里，每棵树维护一个单项式 | |
| E - Takahashi's Anguish | AC | 拓扑排序 | ABC | 每个人有一个讨厌的人，通过拓扑排序，删掉链，剩下的全是环，找到每一个环的最小值，加到一起 | |||
| AC | 并查集 | 并查集判环，若当前加入的数值已经在这一个集合，表示会形成一个环 | |||||
| ABC244 | A - Last Letter | AC | ABC | 乱整 | |||
| B - Go Straight and Turn Right | AC | 模拟 | ABC | 乱整 | |||
| C - Yamanote Line Game | AC | 交互 | ABC | 刷新标准输出，在输出后加上fflush(stdout); | |||
| D - Swap Hats | AC | ABC | 以上考场就降智，我真是服了，暴力模拟，直接交换位置 | ||||
| 2022/6/21 | 洛谷 | P3371 【模板】单源最短路径（弱化版） | AC | 迪杰斯塔拉 | 普及/提高- | ||
| P4779 【模板】单源最短路径（标准版） | bellman-frod | 普及/提高- | |||||
| 2022/6/22 | ARC124 | A - LR Constraints | AC | 模拟 | ARC | 题目描述中，出现了两个‘i'，这两个’i'其实是一个‘i'，直接把我整懵了 | |
| B - XOR Matching 2 | AC | 暴力 | ARC | 难以想象ARC的第二题会出现纯暴力 | |||
| 2022/6/23 | ARC124 | C - LCM of GCDs | AC | 暴力 | ARC | 好吧，第三题也是一个暴力。。。一个不是特别简单的暴力，但情况只有那么几种，暴力枚举情况OK | |
| D - Yet Another Sorting Problem | AC | 图论 | ARC | 这也是一道图论，分双色环，单色环，将单色环通过更改可以变为双色环，统一处理 | |||
| E - Pass to Next | WA | 动态规划 | ARC | 麻了麻了，怼不出来，一道动态规划，长得像数论，不要脸，给你一个式子，在一顿操作后，合并同类项，结果是求方案数。。。离谱，在状态转移方面，有大量的枚举，通过压缩状态，绕过去 | |||
| ARC23 | A - Arithmetic Sequence | AC | ARC | ||||
| B - Increasing Triples | AC | ARC | |||||
| 6月24 | ARC123 | C - 1, 2, 3 - Decomposition | AC | ARC | |||
| D - Inc, Dec - Decomposition | AC | ARC | |||||
| ABC243 | A - Shampoo | AC | 模拟 | ABC | 乱整 | ||
| B - Hit and Blow | AC | 模拟 | ABC | 乱整 | |||
| C - Collision 2 | AC | 结构体 | ABC | 一个二维平面，判断是否相撞，结构体搞一手 | |||
| D - Moves on Binary Tree | AC | 数据结构 | ABC | 一棵树，但数据范围过大，打高精度也会T，但上行和下行可以相互抵消，将抵消的删除，可以用链表，但这玩意单调的，可以用栈 | |||
| E - Edge Deletion | AC | 多源最短路 | ABC | 要求删掉一些边，不改变图的连通性，不给变点与点之间的距离，就相当于用一些边去松弛另一些边，跑Floyd | |||
| 6月25 | ABC257 | A - A to Z String 2 | AC | 模拟 | ABC | 乱整 | |
| B - 1D Pawn | AC | 模拟 | ABC | 乱整 | |||
| C - Robot Takahashi | AC | 前缀和*2 | ABC | 按照wi进行排序，发现0，1无序，从前往后做一边1的前缀和，从后往前做一边0的前缀和，再暴力枚举 | |||
| 2022/6/26 | ARC143 | A - Three Integers | AC | 小模拟 | ARC | 通过减数，让A，B相等，再看C | |
| 2022/6/27 | ARC143 | B - Counting Grids | AC | 结论 | ARC | 一个正方形，要求不存在一个数是一行的最大数，一列的最小数,小推一下，可以发现至多一个数同时违反，所以枚举每一个数求解 | |
| D - Jumping Takahashi 2 | AC | 最短路 | ABC | 求最少训练次数就是求到达每个点所需最小，跑一边floyd，让点与点之间距离最小，接下来，为确保图是联通的，找到单点出发到所有点的最大值，在最大值中取最小值 | |||
| E - Addition and Multiplication 2 | AC | 字典序 | ABC | 先判断位数，在通过字典序排顺序 | |||
| 2022/6/28 | ARC122 | A - Many Formulae | AC | 记忆化 | ARC | 一串数字，往其中插入加号，减号，求有几种答案，可以用爆搜+记忆化，当然DP也可以 | |
| ARC122 | B - Insurance | AC | 前缀和+模拟 | ARC | 一道模拟题，正解是三分，但O(n)扫一遍，枚举也不是问题，先化简式子，做一遍前缀和，扫一遍就行 | ||
| 2022/6/29 | ABC254 | A - Last Two Digits | AC | ABC | 乱整 | ||
| B - Practical Computing | AC | ABC | 乱整 | ||||
| C - K Swap | AC | 分内讨论+排序 | ABC | 选择一个数ai，交换a[i+k]，这里可以发现编号模K相同的数是一组，可以形成升序，因此，按照余数分组，排序，最后穿插比较，看是否符合要求 | |||
| 2022/6/30 | ARC121 | A - 2nd Greatest Distance | AC | 枚举 | ARC | 找到最大值和次大值 | |
| B - RGB Matching | WA | 分内讨论 | ARC | 三种狗，不同的ai，以种分块，得3，以ai分块，得MAXN，显而易见，颜色分块比较合适，再判断奇偶，双指正扫一遍，若右指针当前值超过左指针，左指针增长，反之亦然 | |||
| C - Odd Even Sort | WA | 冒泡排序 | ARC | 无力 | |||
| ABC245 | E - Wrapping Chocolate | AC | 二位偏序 | ABC | 每个巧克力和盒子都有长和宽，不可旋转，因此，我们可以吧他们放在一个序列里，按X从大到小排序，这样，若要在序列中加入巧克力，目前盒子的长都大于当前巧克力，只需要找到第一个宽大于当前巧克力宽的盒子，将它从序列里删除，扫一遍，若能配对，输出Yes，否则No | ||
| F - Endless Walk | AC | 拓扑排序 | ABC | 这道题要求找出多有的点，最终会走到环上，这里，除了从环上伸出来的链，其它的点都是答案，我们可以通过拓扑排序，记录从环上伸出来的链，减去N，便是答案。 | |||
| 2022/7/1 | ARC121 | C - Odd Even Sort | AC | 暴力 | 时间复杂度分析 | ARC | 哎，考场时间复杂度分析错误，写炸了，一道暴力题 |
| D - 1 or 2 | AC | 冒泡排序 | ARC | 一个序列，可以证明最大值加最小值与次大值加次小值的min一定是最有，反之亦然，所以只需要判断是否合并两数，这里可以通过往序列开头加0，一个数合并0，不变，方便编写 | |||
| B - RGB Matching | WA 摆烂 | 分内讨论 | ARC | 无语了，程序太难写了，分内讨论，加上奇偶 | |||
| ABC242 | A - T-shirt | AC | 模拟 | ABC | 乱整 | ||
| B - Minimize Ordering | AC | 排序 | ABC | 这年头，竟然还有人不知道字符串可以直接排序？？？就是我 | |||
| C - 1111gal password | AC | 动态规划 | ABC | 1e7这个限制，是一道题的保险时间复杂度，比较综合，有些时候，1e8轻松53ms | |||
| 2022/7/2 | ARC120 | A - Max Add | AC | 模拟 | ARC | 每一个数列之间有传递关系，记录上一个初始最大值和增加最大值，唉，有点动规的影子 | |
| B - Uniformly Distributed | AC | 结论 | ARC | 一个点，只能到右方和下放，要求给每个格子染色，最后，走任意路线经过颜色相同个数相同，只需要用45度斜线扫一遍 | |||
| C - Swaps 2 | AC | 排序 | ARC | 一个数的值，与他位置相关，减去位置的改变，就是它的本质 | |||
| ABC242 | G - Range Pairing Query | AC | 莫队 | ABC | 莫队板子题 | ||
| ABC258 | A - When? | AC | 模拟 | ABC | 乱整 | ||
| B - Number Box | AC | 模拟 | ABC | 乱整 | |||
| C - Rotation | AC | 字符串 | ABC | 一个字符串上有一个滑动窗口，先把字符串复制几节，方便计算 | |||
| D - Trophy | AC | 暴力 | ABC | 纯暴力。。。 | |||
| 7月4号 | ABC241 | A - Digit Machine | AC | 模拟 | ABC | 乱整 | |
| B - Pasta | AC | 模拟 | ABC | 乱整 | |||
| C - Connect 6 | AC | 可以通过某种方法不管越界方案，但一定要判其不合法，正方形四个方向，水平，垂直，和两个倾斜 | ABC | 越界的特殊处理方法：越界后的值不在改变，给一个极大值或极小值，后面特判不合法 | |||
| D - Sequence Query | AC | STL | ABC | 3中操作，加入一个数，查询小于它的数，大于它的数，K《5，用multiset，外加迭代器，先二分查找到它本身，在用迭代器调整位置，lower_bound-c返回实际下标，-c-1返回查询区间下标，从0开始 | |||
| E - Putting Candies | AC | 找规律 | ABC | ||||
| F - Skate | 摆烂 | BFS | ABC | 一种奇特的BFS，每次移动，不求移动距离，只求转弯次数，而且图比较大，每次只会横向移动或者纵向移动，一个数组装x，一个数组装y，本来用map<int,set |
|||
| 7月5号 | ARC119 | A - 119 × 2^23 + 1 | AC | 倍增 | ARC | 一个式子，中b为2的指数，这log的枚举，简直就是暴力 | |
| B - Electric Board | AC | 模拟 | ARC | 一道排序的模拟题，却因为两个序列，长度不一样，直接写挂，最后在两个数中间插0，来弥补两个序列长度不相等 | |||
| C - ARC Wrecker 2 | AC | 结论 | ARC | 每次操作，会对连个相邻的数加减，就是对奇偶数上总和同时加减，要求符合条件，区间奇偶之和相等，一个式子最后变成当前奇数减去当前偶数，用map记录出现次数，搞 | |||
| 7月6号 | E - Pancakes | AC | 区间交 | 在求区间交时，r的最大值要和当前r取最小值 | ARC | 每次翻转，只会对开头饼子和结尾饼子产生作用，外加绝对值，相当于在平面直角坐标系中，有两条有向线段，这两条线段初始方向最好相同，不然在找区间交时，还要求两条线段方向不同，找区间交时，按照l从小到大进行排序，然后每次记录排除自身外的r最大值，r在和当前枚举r取最小值，再用r-l求出区间交 | |
| 7月7号 | ABC240 | A - Edge Checker | AC | 模拟 | ABC | 乱整 | |
| B - Count Distinct Integers | AC | 模拟 | ABC | 乱整 | |||
| C - Jumping Takahashi | AC | 动态规划 | 一直有个问题待解决 | ABC | 100的n,10000的距离，动态规划枚举每一个距离，最终是所有可能结果，解决多段决策问题 | ||
| D - Strange Balls Takahashi | AC | 模拟 | ABC | 模拟一个栈，面对相同的数字，将多个数字压缩在一起，用结构体封装 | |||
| E - Ranges on Tree | AC | 构造 | ABC | 这读题把我整哈了，数学不好，题都读不好 | |||
| F - Sum Sum Max | AC | 结论 | ABC | 做两边前缀和，输出最大的数，第一遍前缀和可以用高斯求和解决，不过需要注意，在界线处要处理二者相加仍为正数 | |||
| 7月8号 | ARC118 | A - Tax Included Price | AC | 考虑取整 | ARC | 读题痛苦，语言鸿沟，问每一个自然数，通过一个式子转化，这个式子无法转换出来的第N小的数，N=1e5，推式子，主要问题是进位，一次向上取整 | |
| B - Village of M People | AC | 结论 | ARC | 每一项，分配一个数，要求最后差值的绝对值最小，用优先队列priority_queue，虽然自带log，但T不了，对于1e5来说，只是一个较大的常数 | |||
| C - Coprime Set | AC | 构造 | ARC | 题意：要求一个序列，任意两个数都不互质，gcd（all）==1，i!=jsoa[i]!=a[j],序列长度为2500，任何一个数不得超过1e4，先构造N-1个数含有2这一因子，N有3,5,7,11组成，确保gcd为1，这里需要找到2500个数，包含3,5,7,11中的一个甚至多个，还要求各不相等，相比较构造，1开始的自然数排列是一个天然的可以找出3,5,7,11这些质因子的升序排列，只需要排除不含3,5,7,11这些因子的数即可 | |||
| D - Hamiltonian Cycle | 摆烂，有时间再改，先口胡一下 | 构造 | ARC | 题目中给出一堆同于式子，吓人的很，刨开取模，就只是对一个数的乘除，每次只乘一个a或b，除一个a或b，我们可以列一个表格，从a的零次方一直到a的l次方，纵向b的零次方到b的K次方，满足不重复，根据题意,一个人从原点出发，延表格走一圈，中途不经过相同的点，相当于找一条曼哈密顿。。哈密尔顿。。。回路，（叫啥不重要），这条回路一次经过的数就是答案，所谓的取模，只是一个假象；在一个图中找这种回路，目前没有很好的算法，跑暴力，N！，回溯加剪枝 | |||
| 7月9号 | ARC118 | E - Avoid Permutations | 嘴巴选手 | dp+容斥 | ARC | 一道题结结实实整了一天半，看了不少东西，勉强会了，这里题目中有两种障碍物，第一种是已经确定的障碍物，第二种是未确定的障碍物，确定的障碍物由a[i]表示，所有的障碍物组成1到N的排列。首先，考虑两种情况，第一种图很小，障碍物很多，固定，这种情况不用说了，一眼题；第二种是图很多，障碍物很少，枚举每一个障碍物，两两之间的方案数可以由组合式直接求出，最后用容斥原理处理，这里，我们找到经过一个，两个到N个障碍物的路线条数，其中两个的有部分会包含一个，三个的有部分会包含2个，所以用容斥，求出区间并，再用总方案减去容斥的数目；升级一下，用5维DPdp[i][j][k][0\1][0\1]。。。看着就吓人，k表示已经经过几个障碍物，第四位表示这一行是否有障碍物，第五维表示这一列是否有障碍物，每次00到10的转移，实际上是跨了两步，第一步是在这个方格块上放上障碍物，然后向右或向下转移，此时同行or同列不在确定，变为01or10，因此当转移到最后00是全程撞着障碍物走的路线，每次再乘一个方案数，最后容斥一下 | |
| 2022/7/11 | ARC117 | A - God Sequence | AC | 模拟 | ARC | 乱整 | |
| B - ARC Wrecker | AC | 别想太复杂，考场想的是炸楼方案加容斥原理结果动不了手 | ARC | 这道题，一条线从上往下扫，最大的会一点一点减少，第二高的可以选择减少，但独自减少的只会是大于第三高的哪一点，所以加法原理跑一遍 | |||
| C - Tricolor Pyramid | AC | ARC | 杨辉三角特点：(C从上往下)C(1,n),C(i,n),A | ||||
| D - Miracle Tree | AC | ARC | |||||
| 2022/7/12 | ABC239 | A - Horizon | AC | 模拟 | ABC | 乱整 | |
| B - Integer Division | AC | 模拟 | ABC | ||||
| C - Knight Fork | AC | 模拟 | ABC | ||||
| D - Prime Sum Game | AC | 模拟 | ABC | ||||
| E - Subtree K-th Max | AC | ABC | |||||
| F - Construct Highway | AC | ABC | |||||
| ARC118 | E - Avoid Permutations | AC | ARC | 见上 | |||
| 2022/7/13 | ARC116 | A - Odd vs Even | AC | ARC | 乱整 | ||
| B - Products of Min-Max | AC | ARC | 乱整 | ||||
| 洛谷 | P3919 【模板】可持久化线段树 1（可持久化数组） | AC | 提高+/省选- | 每次修改，都新建一个节点，继承上一个相同位置节点的左儿子和右儿子信息，在加上此次值的修改 | |||
| 2022/7/14 | ARC116 | C - Multiple Sequences | AC | ARC | 一道挺妙的题，要求你求出序列的个数：这个数是上一个数的倍数，所有数的大小不超过N,这里因为倍数包含一，所以dp时，算上一后枚举的量会暴增，因此，在dp时刨除一倍，那么只需要dp18层，一倍的情况，提出来分类讨论，用插板法还是隔板法，求组合数 | ||
| D - I Wanna Win The Game | AC | ARC | 异或和，位运算，明显的按位dp，枚举当前为的1的个数，值为方案数，加上一个组合数，跑一边 | ||||
| 2022/7/15 | ABC238 | E - Range Sums | AC | ABC | 并查集判断连通 | ||
| 2022/7/16 | ABC238 | F - Two Exams | AC | ABC | 二位偏序+dp | ||
| 2022/7/18 | 无意义 | ||||||
| 2022/7/19 | 啊啊啊，树剖调了一天 | ||||||
| 2022/7/20 | 洛谷 | P3384 【模板】轻重链剖分/树链剖分 | AC | 树链剖分 | 线段树modify也要pushup，血色 | 提高+/省选- | 哈哈哈哈哈哈，线段树。。。。。。 |
| 洛谷 | P7735 [NOI2021] 轻重边 | AC | 树链剖分 | 省选/NOI- | 2021noi的签到题，感觉还勉强，这码力，考场上敲4k代码加debug，得压到一个小时甚至30分钟以下，一道树链剖分板题，外加一点线段树的应用，树链剖分，主要是线段树长，剖树的部分，也就1，2k；题目要求每次将路径变为重边，与其路径上相连的边变为轻边，就是要通过一种方法，区分不同的边，相当于每次给路径染上一条独一无二的颜色，则可以天然区分此次的边以及与其相连的边，凡是两个相邻的点，若颜色相等，则是重边，这里，query返回值，还有一些线段树查询不同值时，可以返回一个结构体，咋不做选择，全要 | ||
| 2022/7/21 | 洛谷 | P3765 总统选举 | AC | 平衡树+线段树||vector | 省选/NOI- | 这道题与投票相关，要求一个人的获得票数超过区间的一半时，获胜，这里采用摩尔投票法，当票数与当前值相等时，cnt++，不等时，cnt--，如果为零，则goal换一下，这样，最终获胜者（伪），如果票数超过区间一半，则一定会是他，但也可能不是，因此要用查询一个区间投票数，这里采用平衡树，也有骚操作vector（常数小），快速查询一个区间内个数，本来是开权值线段树，但M了，若按相对值插入，则会T（毕竟可以是一条链） | |
| ，就splay一下，保持平衡，减少时间复杂度 | |||||||
| 洛谷 | P3976 [TJOI2015]旅游 | AC | 树链剖分 | 省选/NOI- | 树链剖分板梯，题目中有一句话：让这条路径上的点都加v，明显的树链剖分标志。题目中主要问题是找的路径上的两个点，一个mini,一个maxn，而且最大值的最小值之后。。。当我们将一棵树剖成一条链时，一个点往上跳，在线段树中是往左侧走，因此左端点和右端点应该分开讨论，在线段树维护从左往右走的ans，后从右往左走的ans，此区间mini，maxn。在往上跳的过程中，也许会跳多个链，因此有多个ans，用pushup让ans保持最优 | ||
| 2022/7/22 | 洛谷 | 普通平衡树调了一天 | 失败 | ||||
| 2022/7/23 | 洛谷 | P3369 【模板】普通平衡树 | AC | 平衡树 | 提高+/省选- | 虚假的紫题：小蓝的好友。真正的紫题：模板——普通平衡树。。。码量大，子问题多，debug痛苦 | |
| 洛谷 | P5906 【模板】回滚莫队&不删除莫队 | AC | 回滚莫队 | 省选/NOI- | 莫队，以左端点所在区间为第一关键字，右端点为第二关键字排序，右端点O（N），左端点根号N。回滚莫队，右端点一直往右走，左端点每次从段的最右边往左，这样，就不存在删除操作，每次都是加入操作，对于一些题目，删除比较困难，可以采用回滚莫队 | ||
| 2022/7/25 | 洛谷 | P3722 [AH2017/HNOI2017]影魔 | AC | 线段树 | 省选/NOI- | 任意一个点对，想要有贡献，需要至少一个点是区间最大值，如果另一个点是区间次大值，则会有另一种贡献，否则，没有贡献，对于两个区间合并，时间复杂度为mn，无法承受，以每个点为端点，找到左侧第一个大于他的点，右侧第一个大于他的点，三点为a,b,c，则a与区间bc一种贡献，c与区间ab一种贡献，abc三点有一种贡献，将询问离线进行排序，左为第一关键字，右为第二关键字，从左到右扫一遍，对于一个点，记下他身上相关的左右询问端点，是左端点就减，右端点就相加，用的的东西其实比较多，而且还是穿插着的，前缀和，线段树，求左右端点用单调栈，复杂 | |
| 2022/7/26 | 洛谷 | P3293 [SCOI2016]美味 | AC | 主席树 | 省选/NOI- | 这道题纯暴力，手开o3可以水过去。正解：首先，要查询一段值域中是否有数，可以建立一个值域线段树，但是要求外加上一个区间，会挂，值域线段树会打破区间限制，因此还要对每个区间建立值域线段树，会MLE，这时候就要上主席树，以节省空间，利用两个区间之间的可减性，类似于区间求第k大值（没写，口胡）。计算过程中有异或。。。要求值最大，就要贪心，确定当前值最高位，然后确定最高位满足要求的值域，在此区间中查找值域，贪心的思想 | |
| 洛谷 | P4146 序列终结者 | AC | 平衡树 | 省选/NOI- | 吐了，没想到，这是一道平衡树的模板题，但是将平衡树的所有功能都用上了，就变成了紫题，这道题展现了splay的lazy标记和tag标记的强大之处，splay的旋转，会保持不同点之间的相对位置，因此，旋转时会保持不变，到时候交换左儿子和右儿子即可，另带一句，查询区间l,r,将l+1转到根节点，r-1转至根节点下面第一个位置，则它的做儿子全部是有目标区间组成 | ||
| 2022/7/27 | 洛谷 | P3707 [SDOI2017]相关分析 | AC | 线段树 | 省选/NOI- | 给一个特别长的柿子，由前缀和，平方和，乘积和。。。一系列可以用线段树维护的东西组成，干！！！线段树一边过样例，只有一个bug的辉煌。。。精度卡我60分 | |
| 2022/7/28 | 洛谷 | P2611 [ZJOI2012]小蓝的好友 | AC | 平衡树 | 有点问题。。。if else（待解决） | 省选/NOI- | 要求找到至少包含一个棋子的方格，用一条扫描线，从上往下扫，每一行，找到一个离扫面线最近的且在扫描线上方的棋子，左+1乘上右+1,，在乘上纵，大致思路这样没错，但有些恶心的，每一个点在每一纵列都会产生贡献，点的贡献是左侧的方格到最侧的第一个棋子，右侧同理，查询方格数符合平衡树的左儿子数量。。。平衡树维护（插入一条广告：我在写这份做题记录时，是8月5号，放假当天，机房秉着法不责众的理念，打算中午跑掉，结果zzs于我写记录时，跑来说下午放） |
| 2022/7/29 | ARC112 | A - B = C | AC | 模拟 | ARC | 乱搞 | |
| B - -- - B | AC | 模拟 | ARC | ||||
| 洛谷 | P5386 [Cnoi2019]数字游戏 | WA | 莫队 | NOI/NOI+/CTSC | 摆烂 | ||
| 2022/7/30 | 洛谷 | P5337 [TJOI2019]甲苯先生的字符串 | AC | 矩阵 | 提高+/省选- | 每次转移都一样，将转移写成一个矩阵 | |
| 2022/8/1 | 洛谷 | P4967 黑暗打击 | AC | 矩阵 | 省选/NOI- | 曲线可以写成一个递推式 | |
| P7453 [THUSCH2017] 大魔法师 | AC | 矩阵 | 省选/NOI- | 线段树的标记无法合并，冲矩阵 | |||
| 2022/8/2 | 洛谷 | P3834 【模板】可持久化线段树 2 | AC | 主席树 | 提高+/省选- | 顺带写的 | |
| 2022/8/3 | 洛谷 | P7913 [CSP-S 2021] 廊桥分配 | AC | 前缀和 | 普及+/提高 | 不是单调，或者单峰，只好前缀和暴力枚举 | |
| P3195 [HNOI2008]玩具装箱 | AC | dp斜率优化 | 省选/NOI- | 将dp式子化简成上面差，下面积的形式，从而单调队列开搞 | |||
| P3648 [APIO2014] 序列分割 | AC | dp斜率优化 | 省选/NOI- | 有可能是维护上凸包，也可能是下凸包 | |||
| 2022/8/4 | 洛谷 | P3935 Calculating | AC | 数论 | 提高+/省选- | 实际上式子是一个因数个数式子 | |
| P2260 [清华集训2012]模积和 | AC | 数论分块 | 省选/NOI- | 对于x,y两个同步数论分块，r=min（n/(n/l1),n/(n/l2)) | |||
| 2022/8/24 | ARC111 | B-Reversible Cards | AC | 图论 | ARC | 每次进行决策，且决策具有后效性，妈耶，图论，一次决策一条边，一个端点一个决策值 | |
| Too Heavy | AC | 图论 | ARC | 相比上一道题，这是一道大众题，每次在交换是，存在一个问题，便是在选择交换桥梁时，如果选择再交换环之外的点，会增加操作次数，如果选择交换环之内的点，则再最后一次操作时，换i-1，i也会归为 | |||
| 2022/8/25 | ARC110 | 三道一眼题 | AC | ARC | 无 | ||
| 2022/8/26 | ARC109 | 三道一眼题，真的 | AC | ARC | |||
| 8月27题 | ARC108 | Keep Graph Connected | AC | 生成树 | ARC | 首先，跑一颗生成树，没什么要求，然后从根节点开始，赋值 | |
| 2022/8/29 | Magneti | 洛谷 | AC | 连续段dp | 提高+/省选- | 区间dp，放置磁铁，要求每个磁铁之间不相交，首先，磁铁之间有些空位，比较麻烦，我们可以先放置磁铁，将每个磁铁收尾相连，最后用插板法插入空格，得到最终方案，dp[i][j]表示到第i个磁铁，产生了j个联通块的方案数，对于每个磁铁，可以将磁铁放置于联通块的首或尾，对于放置与中间的数值，因为插入不是特别好处理，我们可以新开一组，将他单个放一块，进行区间合并，通过他将两个联通块接到一起，则他自己被插入到中间去了- | |
| 2022/8/31 | 网络流板题 | 洛谷 | AC | 提高+/省选- | |||
| P3280 [SCOI2013]摩托车交易 | 洛谷 | AC | 最大生成树 | 省选/NOI- | 每次行动想要走载重最大的路线，且无须在意路径长短，而图个规模比较大，我们可以先跑一颗最大生成树，因此移动就变成了树上问题，车手携带黄金不可超过路径上线，则需要找出路径上最小的边，树链剖分 | ||
| 2022/9/2 | P7215 [JOISC2020] 首都 | 洛谷 | AC | 淀粉质 | 省选/NOI- | 给出每一个城镇和城镇属于的城市，要求合并一些城市，要求最后的城镇之间的互相连接，最多只可经过属于同一个城市的城镇到达任意一个城镇（也属于这个城市），关于这道题，用淀粉质，点分治用于处理树上路径问题，相比树链剖分，点分治是从一个点出发到所有的点，不确定最终到达地点在哪，但树链剖分知起点和终点，路径确定,淀粉质路径分两种，经过当前的点和不经过当前的点，分类讨论OK | |
| 2022/9/3 | 线段树合并 | 洛谷 | AC | 查分，淀粉和 | 省选/NOI- | 雨天的尾巴，树上差分，用于线段树合并，每次发放的是一条路径，可以用树链剖分，但麻烦了一点，可以用树上差分，这里可以从下往上，也可以从上往下，随意，u和v加一，lca和lca的父亲减一，对于差分的值进行加减，这里是线段树进行加减，线段树加减也叫合并 | |
| 2022/9/6 | Or Plus Max | 洛谷 | AC | 高维前缀和 | 省选/NOI- | 每次要求的是对于每个集合的数值求最值，不同集合之间有包含关系，那么初始值可以赋为当前集合上线那个数的值，然后求前缀和，集合选与不选，高维前缀和 | |
| 2022/9/19 | P3388 【模板】割点（割顶） | 洛谷 | AC | 割点 | 普及+/提高 | 从点出发在不经过父亲节点的情况下，可以到达的最小的节点，若节点编号大于父节点，父节点是割点 | |
| 2022/9/20 | P5787 二分图 /【模板】线段树分治 | 洛谷 | AC | 扩展域并查集 | 省选/NOI- | 线段树优化建图的适用范围是连边和区间有关，比如一个区间内的点都向某个点连边，一个点向一个区间内的所有点连边，甚至一个区间内每个点向一个区间内每个点连边，这些边的规模是 n2 的情况使用线段树优化建图之后边的规模就是 nlogn 了。感觉线段树分治就是线段树优化建图 | |
| 2022/10/3 | CF1325D Ehab the Xorcist | 洛谷 | AC | 生成 | 普及+/提高 | 可以发现，要满足要求，最多拆成3个，可以合并 | |
| 2022/10/5 | 洛谷 | 每个人在一个区间工作，求所有人一起工作的时间 | AC | 区间交 | 无 | 求区间交，最大l和最小r | |
| 10月9月 | 洛谷 | P3809 【模板】后缀排序 | AC | Hash | 省选/NOI- | 目前敲的是log^2的，先字符串Hash一下，在比较是二分，找到最大相等前缀，比较后一位，字符串Hash是将字符串看作进制，base要大于那个什么码 | |
| 2022/10/10 | 程序\模拟赛\联考\第15场\pro.pdf | 程序\模拟赛\联考\第15场\queue.cpp | AC | LIS | 联考 | 要求不和谐度最小，研究一下，可以发现只要a[i]<a[j]时，两者才不会两边，就是求LIS，过程中保存路径，可以发现，要无法替代，只有至始至终的没有别替换或只有一个数可以接到无法被替换的数之前 | |
| 程序\模拟赛\联考\第15场\pro.pdf | 程序\模拟赛\联考\第15场\tree.cpp | AC | 连续段dp | 联考 | 又一道连续段dp，要求每个点的val大于其儿子的val，但是我们无法保存它的每一种状态，当然也不知道，那么连续段，首先从小到大进行排序，那么右侧节点可以将左边任意点合并，因为要顺序，乘上一个排列作为贡献，dp[i][j]表示到i为止j颗子树的方案书，要dp[N][1]; | ||
| 程序\模拟赛\联考\第16场\problem.pdf | 程序\模拟赛\联考\第16场\guide.cpp | AC | 找规律 | 联考 | 给的一个置换方案，将当前节点置换为当前序列的总和取反，再次计算总和发现，就是swap(a[i],sum); | ||
| 2022/10/11 | 程序\模拟赛\联考\第16场\problem.pdf | 程序\模拟赛\联考\第16场\ambiguous_true.cpp | AC | 倍增 | 联考 | 题目要求的二倍的大概范围， | |
| 程序\模拟赛\联考\第15场\pro.pdf | 程序\模拟赛\联考\第15场\grocery.cpp | AC | st表 | 联考 | 这道题，我们记录T，F的数量比较麻烦，记T为-1，F为一，则可以抵消，那么合法区间必须符合s[u-1]==s[v]，那么对于一个询问，我们找到最小值中最左边的和最小值最右边的，那么，对于询问l到u-1，找到能做扩展的最大长度，左右同理 | ||
| 2022/10/12 | 程序\模拟赛\联考\第17场\down\statement.pdf | 程序\模拟赛\联考\第17场\monster.cpp | AC | 分开计算 | 联考 | 。。。涨教训了，最开始感觉像是高维前缀和，结果3个小时寄了，前缀和重要的是包含关系，而今天那题木有，题目中的两个值，可以分开求解，分开求解 | |
| 程序\模拟赛\联考\第17场\climb.cpp | AC | ST表 | 联考 | 题目要求的是最优策略，我们可以从各种变量中找不变的量，对于一个等式，可以将各种变量移项，将相等的放到一起，方便分类讨论 | |||
| 待改 | 联考 | 打表：找规律 | |||||
| 2022/10/13 | 程序\模拟赛\联考\第18场\down\statement.pdf | 吹牛 | AC | 。。。 | 联考 | 我要找最大值，但不是区间最大值，不需要ST表，一个问题，有很多解决方法，最好用最简单最直接的方法 | |
| 塔图因 | AC | 卡常 | 联考 | 首先，它问的是截断每条边的总贡献，但是每条边的权值都特别小，可以对每个边权分别考虑，总共减去多算，卡常，用DFS序，正着一遍，到起一遍 | |||
| 夏兜 | 待改 | 联考 | 转移终点确定，可以从终点转移的起点 | ||||
| 2022/10/17 | 程序\模拟赛\联考\第19场\down\offical.pdf | 按为排序 | AC | 联考 | 找两个数同一组，只要mod后相等即可 | ||
| 鲍勃的数学题 | AC | 联考 | 爆搜枚举，将题目要求的数用一个式子表示 | ||||
| 最大字段和 | AC | 联考 | 查询区间，可以分块拼接 | ||||
| 2022/10/19 | 考试第21场 | 哼哼串 | AC | dp | 联考 | 计数用dp，dp的状态必须小，dp[1000][1000][1...]这种状态多大，肯定T | |
| 2022/10/20 | 考试第22场 | 火事 | 摆 | 差分 | NOI/NOI+/CTSC | 每次延续的区间可以表示成一个平行四边形，延伸后是个三角形，容斥一手，对于区间分类讨论，从四个点分别容斥 | |
| 彩色的云 | AC | 概率DP | NOI/NOI+/CTSC | 首先，钦定一个云留到最后，对于一个式子进行消元，求出初值以及转移值，特别麻烦，转移的期望步数不一定是一。。。值得在做一遍 | |||
| 无向图存成有向图 | AC | 换根DP||记忆化 | unoder_mapO(1)但是没有顺序，用于记忆化，换根DP：当我们把一个跟当做跟节点时：可以将其与原本的父节点比较，然后通过比较的差值（计算方法一定），再次从根节点DFS，找出一各个节点为根的值 | ||||
| 一个和LCA像的式子 | AC | 笛卡尔线段树 | 最后是式子是两个叶子节点的和减去起二倍LCA的值，用笛卡尔树模拟分治 | ||||
| 2022/10/22 | 第23场 | 我的 | AC | dijie | dijie优先队列里要装val，外部的已经修改了 | 倒着跑dijie，从根节点带着1出发 | |
| 小鸡 | AC | 枚举 | 要求一一对应疑惑和相等，总共N种，一一枚举check | ||||
| 八岁 | AC | 网络流 | 对于包含关系的，连边，则将所有变连接到一起，则求最小链覆盖=最小路径覆盖，有包含关系的连边，然后直接跑网络流，对于一个点，拆成两个点，有包含关系的，连一条边，若走这条边，相当于二者在同一条链上，用总点数减去最大流，就是最小链覆盖 | ||||
| 了 | 摆 | ||||||
| 2022/10/24 | 第24场 | 啊 | AC | 双指针 | 要求找出所有矩形，01矩阵中1的个数在某一区间，在枚举过程中，左指针表示区间下界，右指针上界；双指针用于在一个固定范围中，求解左右端点，这里一侧指针移动单调，则另一侧也单调 | ||
| 波 | AC | 狄利克雷...缀和 | 求每一行任意两个数的gcd总和，不好求，可以求出所有的gcd的倍数，做狄利克雷前缀和，然后在做倒狄利克雷前缀和解决 | ||||
| 2022/10/26 | 第25场 | 线 | AC | dp | 每个粒子一个方向，求最右边粒活到最后的概率（完结） | ||
| 2023/2/14 | 策略游戏 | 三个操作：1&2.a,b同时减一加一 3.同时除以gcd | 记忆化搜索 | 可以发现，a,b之间的差值只有在3操作会变，所以一个a的值，一个差值，进行记忆化搜索 | |||
| 2023/2/15 | problem | 三个操作，对区间每个数去min(a[i],v),max(a[i],v),区间的和累加入sum,求所有不同种操作序列中sum的总和 | 期望？？？ | 对所有可能的情况求某个值的和，可以考虑用期望解决问题。期望可以转为概率。对值域将期望转成概率。 | |||
| dance | 在序列中尾部每一个数字后添加数字，以使序列单调递增，求最少添加量 | 模拟 | 对于每个数字，考虑若等于上一个数字，则选择继承，最多在后面继承2e5为，所以虽然我们在模拟的时候继承从最后面开始没有错，但从第15位开始也没有错，而且更加简便好些 | ||||
| stone | 在一个棋盘上放置石子，要求每一个棋子距离当行对角线距离不等 | 构造 | 遇上构造题，打表找规律 | ||||
| 2023/2/17 | 城市天际线 | n个点，m条边，x个强联通分量，要求一些点在同一强联通分量当中 | 构造 | 首先，一个图的点数越多，可容纳上界越高，尽可能选择多的点，在一个图中 | |||
| 2023/2/18 | 矩阵 | 三种操作，行左右移动，列左右移动，行列置换求逆 | 矩阵 | 对于N*N个点，我们要进行同样操作M次，那么对于每一个点，可以表示为一个三元组(x,y,v)，然后我们用矩阵将后面的M次操作结合一个下，在对于每一个点操作 | |||
| 可怜 | 构造一个序列，要求i<j<k<l,S[i-j]!=s[k-l]，字典序最小 | 构造 | 对于相邻的情况，在图上连边，走过就删 | ||||
| 2023/2/21 | 除雪 | 对于一棵树，每次让路径上的值减一，求全部减为0的次数 | 树形dp | 记录到当前及其子树删完的最小代价，以及可以向上延伸的点的个数，贪心处理一下 | |||
| 景点距离 | 求一颗树上点对数量，要求距离小于等于K | 随便搞 | 题中有多次询问，每次会删除一条边，这里可一倒序枚举，将加边改为删边 | ||||
| 等差数列 | 一个等差数列，超过p会mod p，给你这个序列，求首相和公差，这里p为质数 | 哈希表 | 首先，因为p为质数，所以前p个会落在各自不同的地方，那么选择任意两个数的差值kd，在2N<=p的情况下，对序列中的每一个数加上kd，会有k个数飞出序列，在2N>p的情况下，去原序列的补集 | ||||
| 2023/2/22 | 生命游戏 | 图上有一些点，每次回向四周扩散，求生长成给出图形的最长时间 | BFS | 首先二分时间，然后check，对于每一个无法到达的点，删除从他出发，T步之内可以到达的点，然后所有可行点开始BFS | |||
| 相似序列 | 每次给出询问区间，要求两个询问区间在排序之后，至多有两个位置不同 | 主席树，Hash，二分 | 对于一个序列的Hash,首先离散化，使得每一个数紧凑，此时变成了一个字符串Hash | ||||
| 对于每次查询的区间，因为已经变成至于线段树，那么必须再加上一个主席树，对于排序之后的桶，要求两个桶不相同的点差值为一，且相邻 | |||||||
| 疑惑平方和 | 求序列中两两之间，异或之后的平方 | 计数 | 对位数进行拆分,f_i_j_l表示a_i异或上a_j的第l位的值，乘上2^l | ||||
| 在计算过程中，我们将平方拆开，发现要求一个点对的两个数位，我们在计算个数的时候避免交叉匹配，我们对于每一个数记录两位 | |||||||
| 硬币称重 | 一堆硬币，有一个假币，可轻可重，最坏情况找出这个硬币要对少次 | dp | |||||
| 2023/2/24 | 排列 | 构造序列，两两之间差值为2，求方案数 | 矩阵 | 首先，打表找规律，发现可以矩阵递推 | |||
| 2023/2/25 | 撰写博客 | 一个序列，删除一些字符，要求不出现任何子串为题目给出 | 看毛片 | 首先，看毛片，看出每个子串，然后dp[i]表示删掉字符i，前面不存在子串的贡献，可以从之前转移过来，单调队列，用deque | |||
| 2023/2/27 | max卷积 | 求N^N级别的东西，有特性 | 搞 | 实际上有权值的数不多，可以拿出来枚举 | |||
| 序列修改 | 一个序列A和一个序列C,Ci是A1-Ai中不同数字的个数，序列的权值是i*Ci的和，求只修改一个值的代价 | 数据结构 | 修改的代价包含一个绝对值。。。按照大小分类讨论一下 | ||||
| 2023/2/28 | 哀 | 两个操作，对所有I mod k 属于[l,r]全部加上x，另一种是区间求和 | 分块 | 以根号N为块长，大于根号N的块有小于根号N个，所以每次差分分块，小于根号N的K对应的位置多，数值小于根号N,所以用一个二维数组单独为维护，查询的时候用根号N便利每一个mod k ==I 的数组，累加修改值 |
