- 2024-03-01P4690 [Ynoi2016] 镜中的昆虫 题解
题目链接:镜中的昆虫经典题了,我们首先回顾下颜色数的常见做法统计:对每个位置维护一个\(pre_i\),表示与当前位置相同的颜色上一次出现位置。那么我们分讨一下。查询\([l,r]\)得到颜色数,对于\(pre_i<l\)的\(i\)点,显然它就是这个区间内\(a_i\)对应颜色出现的第一个位置,我们
- 2023-11-07Maximum Balanced Circle
here首先根据题意,我们不难有数字是连续的这种感悟。而且限制是值域上的,从下标入手发现难以突破,便从值域上入手。从小到大考虑每个数字,然后dp,可以参考这篇题解。至于方案的输出,有两种情况。只有自己\(i\)和\(i-1\),直接输出即可。有自己和\(i-1\)的环,定义print输出环,且最大
- 2023-10-27CF777题解
分析先对每一列都做DP寻找极长单调不降区间,能够得到若干极长单调不降区间,只要询问的区间是这些区间的子区间,那么说明在这个区间内必有一列的这个区间是单调不降的。思考如何快速判断子区间。用\(f_{x}\)表示以\(x\)为所有左端点为\(x\)的区间的右端点最大值,那么对于
- 2023-07-24卡特兰数
概念以下看似毫不相关的问题均属于Catalan数列:\(n\)个节点构成的无标号、区分左右儿子的二叉树数量为\(Cat_n\)\(n\)个节点构成的无标号、区分儿子的有根树数量为\(Cat_{n-1}\)\(n\)个左括号与\(n\)个右括号组成的合法序列有\(Cat_n\)种\(n\)个元素按照大小进
- 2023-06-25「JOISC 2020 Day2」遗迹
「JOISC2020Day2」遗迹题目大意:给定长度为\(2n\)的序列\(h_i\),满足对于所有\(k\in[1,n]\),均存在两个\(i\)满足\(h_i=k\),定义“地震”为如下操作:对于所有\(i\in[1,2n]\),当且仅当\(h_i>0\)且对于所有\(j>i\)都有\(h_i\neqh_i\)时,\(h_i\leftarrowh
- 2023-04-13ABC297Ex - Diff Adjacent
ABC297Ex-DiffAdjacent题目链接。\(\text{difficulty}=4.5,3\)。\(\text{tags}=多项式,生成函数,容斥\)。首先如果直接计数不相邻的那么至少需要记录当前的和以及最后一个数是什么,复杂度无法接受。那么考虑容斥。接下来对于一个固定的序列\(a_1,a_2,\dots,a_m\)考虑。
- 2023-01-12闲话/社论 23.1.12
u群看到的一道题挺好玩的,写篇博客参考资料:20210620省队互测-qwaszx题解,qwaszx;某篇没有链接的知乎回答,EI,Rebelz.定义一个\(1,2,\cdots,n\)的排列是好的,当
- 2022-11-21Day7
上午题题目:AGC058D虑定义一个连续的\(abc,bca,cab\)是极长的上升子段,考虑若干个极长的上升子段一定是不交的,所以这么定义没有问题。考虑容斥,顷定有\(k\)个极长上
- 2022-08-15洛谷 P1654 OSU!
思路考虑\(DP\)转移,设\(F[i]\)表示长度为\(i\)序列的期望分数。得到如下转移:\(F[i]=(F[i-1]-A[i-1]+A[i])p_i+F[i-1](1-p_i)\)其中\(A[i]\)的意义是:以\(i\)