Dispwnl

Crazy Up

[HNOI2018]转盘

题目题解假设起点固定，那么走的长度肯定是一圈$+x$ 这样如果先停留时间$x$，再从$x+1$走的话就可以直接走一圈完事了所以这样只用求开始在起点停留多少时间然后$+n-1$即可设$t_i=T_i-i$，表示走到这里物品刚好出现需要停留的时间则有答案为$\min_{i=1}^n(\max(t_{i…2n})+i)$ 这样可以线段树维护了，根据右区间最大值来递归更新左区...

Posted by Dispwnl on April 25, 2019

[HEOI2013]SAO

题目题解发现题目给定的是个树结构，设$f_{i,j}$表示$i$在$i$的子树里排名为$j$的方案数，现在要合并$u$和$v$（$v$为$u$儿子）的答案，假设$v<u$，则有 $f_{u,i+j}=\sum_{i=1}^{siz_u}\sum_{j=1}^{siz_v}\sum_{k=1}^{j}f_{u,i}f_{v,k}{j+i-1\choose i-1}{siz_u-...

Posted by Dispwnl on April 25, 2019

[CF235C]Cyclical Quest

题目题目大意给一个主串和多个询问串，求询问串的所有样子不同的周期同构出现次数和 Examples input baabaabaaa 5 a ba baa aabaa aaba output 7 5 7 3 5 input aabbaa 3 aa aabb abba output 2 3 3 题解写完之后发现以前写过这道题emmmm 破环成链，然...

Posted by Dispwnl on April 25, 2019

[TJOI2015]组合数学

题目题解如果把一条路径看成一条链，把这个网格图看成一个$DAG$，这个题就是求$DAG$的最小链覆盖（链的值为覆盖点的最大值）一看到链覆盖我就想到网络流，一想到网络流我就点开了…… 嗯嗯嗯好的我知道了要做一遍传递闭包把可以相交的最小路径覆盖转化为了路径不能相交的最小路径覆盖然后跑个网络流就好啦果然很简单嘛可以转换一下思路，有定理：最小链覆盖=最大独立点集一看...

Posted by Dispwnl on April 24, 2019

[TJOI2015]线性代数

题目题解把题目中给的式子拆开后得到：$\sum_{i=1}^{n}\sum_{j=1}^{n}A_jB_{j,i}A_i-\sum_{i=1}^nA_iC_i$ 注意到$A$只有$0/1$两种取值，所以可以看成选了$B_{j,i}$之后必须选$-C_i,-C_j$，把代表$B_{j,i}$的点向代表$-C_i,-C_j$的点连边，这样就转化成了一个最大权闭合子图问题了，最小割解决即...

Posted by Dispwnl on April 24, 2019

[CF1139D]Steps to One

题目题目大意给定一个空序列$a$和一个整数$m$，每次可以往序列里加入一个数$x(x\in [1,m])$，求当所有数的$\gcd$为$1$时的期望次数 ### Examples input 1 output 1 input 2 output 2 input 4 output 333333338 题解加入数之后$\gcd$肯定是单调不升的，...

Posted by Dispwnl on April 24, 2019

[ARC073F]Many Moves

题目题目大意在一行中有$n$个格子，从左往右编号为$1$到$n$。有$2$颗棋子，一开始分别位于位置$A$和$B$。按顺序给出$Q$个要求，每个要求是如下形式：给出一个位置$x_i$，要求将两个棋子中任意一个移动到位置$x_i$。将一颗棋子移动一格需要花费$1$秒，就是说将棋子从$X$位置移动到$Y$位置需要花费$\vert X-Y\vert $秒。为了回答要...

Posted by Dispwnl on April 24, 2019

[ARC071D]Infinite Sequence

题目题目大意求有多少个无限长的由${1,2…,n}$组成的序列$a1,a2…$满足以下条件: 1.第$n$个及以后的元素是相同的，即若$n\le i,j,ai=aj$。 2.对于每个位置$i$，紧随第ii个元素后的$ai$个元素是相同的，即若$i<j<k≤i+ai,aj=ak$ 输入$n$,请输出序列数量 $\bmod 1000000007$ Sample Inp...

Posted by Dispwnl on April 24, 2019

[BJOI2019]奥术神杖

题目题解因为是几个数相乘还开根，所以可以对每个值取$\ln$，这样把乘法化成了加法，开根号化成除法，设神力值（取$\lg$）的和为$T$，共有$n$个咒语，最终神力值为$t$，有 $T=t\times n$ 一脸分数规划的样子，可以二分$t$，对每个值都$-t$ 这样可以建出$AC$自动机在上面$dp$了，设$f_{i,j}$表示填到第$i$位转移到自动机第$j$个节点的最大值...

Posted by Dispwnl on April 23, 2019

[BJOI2019]删数

题目题解首先对于一个数列它的答案为数轴上$1\sim n$中每个数能往左覆盖它的个数个点，答案就是$1\sim n$中没有被覆盖的点因为最后满足条件的情况肯定是$1\sim n$上有且只有一层覆盖（想象一个接力的过程），修改一个数可以看成把某个重叠的部分挪到空白处这样可以用线段树维护区间$0$的个数，需要支持区间修改和区间查询写的有点自闭……借鉴了题解的代码 ...

Posted by Dispwnl on April 23, 2019