CF VP 记录
刷了蛮久 CF 了，一直忘记写记录，现在想起来就写一下。 CF 1697 (2022.7.28) A,B 无意义水题。 C 把操作等价于 $b$ 的移动，只能在 $a$ 中向左移，在 $c$ 中向右移。 把 $a$，$c$ 提出来之后看对应的两个 $b$ 之间有没有不能跨过得即可。 D 操作 1 的 26 已经提示了每种字母只能用一次操作 1 。 那么一个很 naive 的想法就是对于每种字母求出他们最后的位置，每次扩展的时候暴力询问，但这样是 27000 次的。 然后又发现这东西可以二分，那么就做完了。 E (赛后) dp 还是太菜了 /kk 根据题意，两个点可以同色当且仅当他们互为最近点对。 那么我们可以把图拆成数个联通块，连通块中两两曼哈顿距离相等，连通块中的点要么..
7月26日闲话
上午模拟赛怒切倒数，赚了 wyy 30块。 晚上大家都要狗卷，单排 VP 。 捏妈的，差点 2100 冲不出来了。 多索雷斯复刻了，夏活还会远吗。
7月20日闲话
学习了一些底层。 起因是这道题，使用了 set 中的一些性质。 set::find **参数：**该函数接受一个强制性参数element ，该元素指定要在集合容器中搜索的元素。 **返回值：**该函数返回一个迭代器，该迭代器指向在集合容器中搜索的元素。如果找不到该元素，则迭代器将指向集合中最后一个元素之后的位置 我之前没想过这玩意能求区间的包含关系。 但这道题里面，只需要重定义一下 < ，find 一下就能找到包含的区间。 struct node{ int l,r; bool operator <(const node &x)const{ return r<x.l; } }; 原因是这样的： set 中判断元素是否相等： 当 A<B和 B<A 都为假时..
7月19日闲话
上午打模拟赛，保龄了。什么时候才能不挂分？什么时候才能不挂分？什么时候才能不挂分？ 快进到 NOIP 也保龄 /hx 。 虽然没有大样例，@wyy332623 依旧是阿克神，吊打我。 下午晚上 VP 了两场，调 E 调到崩溃。 晚上扫雷，赌狗不得 house 。
CF407C Curious Array 题解
前言 优秀的高阶差分/前缀和练习题。 Solution 思路 题意很清晰，不加以赘述。 注意到区间修改，但是我们发现修改的不同，因此设法将其转化为相同的值。 经过打表或手膜等一系列方式，我们发现修改值之间存在一些美妙的关系。 考虑差分。 $k=1$ 时 一次差分后的差分序列的值均为 1 ，可以配合数据结构修改。 但更好的方法是二次差分，转化为形如 ${1,0,0,0… ,-1}$ 单点修改的形式。 $k=2$ 时 经过一次差分我们发现其转化为了上述 $k=1$ 的形式。 直接三次差分。 $k = x$ 时 我们从 $k$ 较小的情况推广，容易发现我们修改的应该是 $k+1$ 阶差分数组。 这也不难通过组合意义证明，另一篇题解已经讲得很清楚了。 具体实现 我们发现在具..
7月15日闲话
一如既往的摆。 今天是星期五，我想吃疯狂星期四，但是绍一方圆四公里没有 KFC 。 但是有金拱门，最近疯狂送福利，4个人去白嫖了 15 个鸡块和三杯雷碧，人均二十出头。 晚上看着长长的题单陷入了沉思，决定开摆。 开了一场 VP ，第一次 div2 场切了 E ，非常兴奋。 赛后一看， 果然也就这个水平了。
7月14日闲话
摆烂。 率性哥 ldz 教授率性技巧。 晚上开了一场 div.2 ，差点 1700 的 D 都打不出来了。 差不多退役得了 /lh 。
7月13日闲话
保龄。 upd：蹭了一顿饭。
CF746F Music in Car 题解
无内鬼，来点主席树做法。 其实是因为不会 stl。 Solution 看这个连续区间加上，区间长度不限制，还有 $t$ 的单调性，考虑双指针。 那么复杂度瓶颈就在如何快速计算区间中前 $w$ 大的数的时间的一半。 区间前 $k$ 大，考虑主席树。 其实就是经典区间第 $k$ 大的变种，实现起来并不是特别困难。 时间复杂度 $O(n\log n)$ 。 Code //#pragma GCC optimize(3) #include<bits/stdc++.h> #define N 500005 using namespace std; int read(){ int x=0,w=1; char ch=getchar(); while(ch>'9'||ch<..
组合数学学习笔记
数学还是太菜了 \kk 。 组合数和排列数 定义 高中数学选修三内容。 定义排列数 $A_n^m$ 为从 $n$ 个不重复的元素中选 $m$ 个按一定顺序排列的方案数。 根据乘法原理易得 $$ A_n^m=n\times (n-1)\times … \times(n-m+1)=\frac{n!}{(n-m)!} $$ 定义排列数 $C_n^m$ 为从 $n$ 个不重复的元素中选 $m$ 个的方案数。 由排列数公式易得 $$ C_n^m=\dbinom{n}{m}=\frac{n!}{m!(n-m)!} $$ 也就输排列数除去 $n!$ ，简单易懂。 推广 二项式定理 $$ (x+y)^n=\sum\limits_{i=0}^n \dbinom{n}{i}x^iy^{n-i} $$ ..