比赛情况 我太菜了 A题 加减乘除不会 B题 二元一次方程不会 C题 gcd不会 就会一个D题二分答案大水题，本来想比赛最后一分钟来一个绝杀，结果 Wrong Answer on test 4 比赛总结 问题1：有点读不懂题目。 解决方法：读题目后如果发现没有看懂，再多读几遍样例，看看样例的解释，大概就懂了。（如果再读不懂就得锻炼自己的阅读理解了） 问题2：花了点时间想了个假题。 解决方法：其实就是没有看懂题目，和问题1一样的方法去解决。 问题3：卡在一个题动不了。导致后面会做的题没去做。 解决方法：因为有些知识点确实不太擅长，比如我在C题想了20min假题，又想了30...

前言 矩阵是一种较为基础的数学工具，OI里面好像不常考？，反正学完数学一本通里的矩阵，做一些矩阵的应用感觉就应该可以了。行列式也是很有趣的东西，我花时间钻研了一下。下面归纳总结一下我做过的一些矩阵的题型 如果定义这种不会请百度吧 -> 百度矩阵 矩阵乘法 矩阵里面最主要的一种。下面是矩阵乘法的一些题。 矩阵快速幂 P3390模板题 基础。 矩阵加速递推数列 P1939模板题 加速加法递推直接设状态转移矩阵就好了。 石头游戏 其实想清楚了石头要从一个格子转移到另一个格子，就可联想到用矩阵来表示格子与格子间的的转移。码量有点大。 Codeforces 1182E Product Or...

目标 && 前言 近期的目标就是刷《算法竞赛——进阶指南》这本书 先花两三天左右把 0x00 基本算法 刷完，好的题目我录下来。 用一两天快速地把 0x10 基本数据结构 刷完，因为比较简单。好的题目录下来。 0x20 搜索 先放在这边，因为我觉得搜索比较毒瘤，过了初赛再刷搜索，顺便提高代码能力。 0x30 数学知识 数学我不太擅长，先留着 0x40 数据结构进阶 马上就要开学了，这个看看一周到一周半的时间能不能刷完，好的题目我会录下来。 0x50 动态规划 刷完上面这个就要赶紧刷下面这个，两周到三周，重难点，好的题录下。 0x60 图论 两到三周 刷完这里水平应...

动态规划学习 前言 以前我也算是接触过一点DP，陆陆续续学了一些背包问题，线性动规和区间动规。现在我再次发现了动规的重要性，决定在暑假里专门刷一些动规题。这篇blog主要记录我刷过的一些DP题。 引用 _皎月半撒花 大佬的一段话 动态规划自古以来是凌虐萌新的分水岭，但有些认为并没有这么重要——会打暴力，大不了记忆化。但是其实，动态规划学得好不好，可以彰显出一个的基本素养——能否富有逻辑地思考一些问题，以及更重要的——能否将数学、算筹学（决策学）、数据结构合并成一个整体并且将其合理运用。 推荐 （大佬的blog） <什么是动态规划> —— by知乎大佬 <入门DP总结&...

比赛情况 1h才写出T1 100pts + T2 50pts（都是简单dp可还行）。然后就去颓废了。颓废完来康康T3的暴力，wow，T3咋这么难呢！？期望概率好像不太会了，退了吧qwq。 所以最后 100+50+0=150pts, rank 22。 比赛总结 说实话比赛前还有些紧张呢，但是我这次吸取了经验，牢记dalao之前对我讲的，“花2h肝T1，T2是值得的。”(CSP-S就是因为花2h+肝T3暴力，让我留下了终身的遗憾)，于是安心写T1，T2，稳扎稳打拿下150pts 在这次比赛学到了一个简单的树状数组优化dp。 T1 0还是1 定义 f[i,0/1] 表示使用完前 i ...

比赛情况 2h才刀了A,B,C,D。E题的套路做的少，不过ygt大佬给我讲完思路后赛后2min就AC了这题。 比赛总结 比赛时不用担心“时间短，要做多快”，这样会匆匆忙忙，反而会做得慢。比赛时应该要不紧不慢，理性思考，内心平静，题目反而会迎刃而解。 这次比赛又看错了题（B,D）。 解决办法：这次比赛看错题是因为不够细心，不够细心是因为急躁，怕做不完。所以沉稳冷静的分析，反而能更好地完成比赛。 那么就开始上题解吧！ A cf常出的分类讨论题（OI好像不考？）。 如果三个人的位置互不相同，我们希望最左和最右的两个人尽量靠近，中间这个人走不走没有影响。 如果有两个人位置相同，问题就转化为...

比赛情况 bq. A题 Wrong Answer on test 2 , E题sb题没切。bqbqbq. 比赛总结 bq. 那就直接上题解吧！^-^ A 数位dp，分类讨论，注意细节。 Talk is cheap.Show me the code. #include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); ...

Problem ACwing 题目地址 Solution 好题，代码短，思维性强，细节多。 我们应该推导出以下两条性质： 让我们来手玩一下样例，样例排序后应该是这样子的：0 3 3 6 6 9，其中相同的数在排序后的序列是连续的一段，而双端队列中元素应该是序列中连续的一段。（并没有用） 双端队列添加元素，先是添加一个到中间，再是往两边插入数字，假设双端队列中一段元素分别是 ，且 是第一个加入的元素。记 表示这个元素在原序列中的下标，那么就有 。（这个性质就很重要了） 考虑一个双端队列，用函数 来形象的表示这个数列的特征（当然这个函数是离散的，为了形象，将他连续），函数的图像如下...

Problem Luogu 题目地址 ACwing 题目地址 Sulotion 代码短，思维强，实现妙（就算猜出性质也不一定会实现），神仙题啊，科科（我太菜了而已）。 首先有一个显然的性质：选出来的这 对点一定相邻。 根据这个性质，我们做第一步问题转换：记两个点 和 之间的距离为 ，那么我们就得到一个长度为 的数组 ，我们要在 中选出 个数，并且这 个数两两不能相邻。 （做到这里就不会了是吧？）既然没有什么头绪，我们就从 的情况逐步推起，考虑像 [算进]序列 （就是上一题，虽然这两题看起来毫无联系的样子）一样用数学归纳法解决问题。 显然我们要选 ，并且记这个数为 ...

Problem Luogu 题目地址 ACwing 题目地址 Sulotion 代码短，思维强，实现妙（就算猜出性质也不一定会实现），神仙题啊，科科（我太菜了而已）。 首先有一个显然的性质：选出来的这 \(k\) 对点一定相邻。 根据这个性质，我们做第一步问题转换：记两个点 \(i\) 和 \(i+1\) 之间的距离为 \(D_i\)，那么我们就得到一个长度为 \(n-1\) 的数组 \(D\)，我们要在 \(D\) 中选出 \(k\) 个数，并且这 \(k\) 个数两两不能相邻。 （做到这里就不会了是吧？）既然没有什么头绪，我们就从 \(k=1\) 的情况逐步...

Problem ACwing 题目地址 Solution 好题，代码短，思维性强，细节多。 我们应该推导出以下两条性质： 让我们来手玩一下样例，样例排序后应该是这样子的：0 3 3 6 6 9，其中相同的数在排序后的序列是连续的一段，而双端队列中元素应该是序列中连续的一段。（并没有用） 双端队列添加元素，先是添加一个到中间，再是往两边插入数字，假设双端队列中一段元素分别是 \(x_1,x_2...x_n\) ，且 \(x_m\) 是第一个加入的元素。记 \(ID(x_i)\) 表示这个元素在原序列中的下标，那么就有 \(ID(x_1)>ID(x_2)>...&g...

Problem 洛谷P2827 题目地址 Solution 直接用优先队列模拟可以得到不少的分数，时间复杂度 \(O(m \log m),m<=7*10^6\) ，但是并不能通过此题，我们要考虑挖掘一些性质优化时间复杂度。 假设现在有两条蚯蚓，长度分别记为 \(x_1,x_2\)，且满足 \(x_1>=x_2\)。 令 \(l_1\) 表示 \(x1\) 切掉后 \(\lfloor px_1 \rfloor\) 这部分（left左边），\(r_1\) 表示切掉后 \(x_1 - \lfloor px_1 \rfloor\) 这部分（right右边），\(l_2,r_2\)...

Problem ACwing 题目地址 Solution 低级套路题。 二分边长，二维离散化前缀和预处理，贪心双指针判定即可。 时间复杂度 \(O(n^2 \log n)\)，因为离散化了，\(n<=500\) Code Talk is cheap.Show me the code. #include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9') { if(...

题目地址 ACwing题目地址 Solution 套路题。不会做只是我没见过这个套路而已 突破口： 但是整条防线上也最多只有一个位置有奇数个防具 我们知道一个原理 ：偶+偶=偶，奇+偶=奇。 又因为我们可以快速算出一个前缀和，比如说算出 \(x\) 之前有多少个防具，（用等差数列的一些公式快速\(O(1)\)算出，因为有 \(n\) 个等差数列所以算一次前缀和的的时间是 \(O(n)\)）。记 \(x\) 的前缀和为 \(S(x)\) 我们又发现如果答案（奇数）在 \(p\) 这个位置，\(\forall x \in [0,p)\) \(S(x)\) 都是偶数，而 \(\fora...