CF533D Landmarks

一个房子两侧是承重柱,中间是独立柱

一个独立柱承受两侧柱子的中间部分的承重

超过承重回塌,问

$dp_i$表示前i个柱子,第i个选座最后保留的柱子case下,前一个选中的柱子最近在哪里

然后转移有$dp_i=max_{2*d_j+dp_j\leq x_i}x_j$

这样我们可以判断在不加入柱子的情况下会不会塌

单调栈维护方式就是维护一个递减的$2*d_j+dp_j$的最大的$x_j$,然后二分这个合法位置查询这个最大值即可

(好像直接弹出也是对的2333)

先正着dp,再反着dp,计算出每根柱子在两个方向剩下来的能支持长度,$v_1,v_2$,左边选了i,右边选了j,则d至少要$(x_j-x_i)/2$的空间!

v求法:(以v1为例)

$v_{1i}=2dp_i-(x_i-x_j)$

那么我们只需要满足$v1_i+v2_j\geq (x_j-x_i)/2$

这个也需要单调栈维护一下即可,因为我们要最小化新柱子的d

#2461. 「2018 集训队互测 Day 1」完美的队列

考虑求$f_i$表示某种操作最早被弹出的时间

分块

对于队列序列分块,考虑一个颜色什么时候被干掉,你会发现相当于在操作序列上twopointers,一块一块的处理

维护l,r,满足对于r时刻导致前l的都被删除的时刻

然后我们考虑一个块,维护每个位置还剩多少位置,l向后移动相当于区间-,然后r向后移动相当于少一个操作,就是区间+,然后如果操作完这个块内还有剩余位置,说明这个颜色还是合法的!

也就是说,我们只看l这个位置的答案,相当于还有多少次使得这个东西out干净了,维护这个东西可以分块$O1$修改

如果是散块的,就对应至多$m \sqrt n$次散块操作,所以是可以暴力的

考虑单点,用一个vector记录散块修改的信息

然后大块(一整块的修改)我们用数组预处理,$pre_i$表示前i个操作有多少个整块修改,再用$id_i$表示第i个大块操作的id是啥

用twopointers去算一个元素的删除时间是具体在哪两个操作之间

你会发现我们有$pre$和$id$数组就可以辅助定位这个信息,即从i开始向后扫过去知道pre+???满足超过这个$a_i$了

然后有了这些信息我们就可以得到一个操作的信息了,$f_i=min{整块,散块散点}$这样子

#3193. 「ROI 2019 Day2」机器人高尔夫球赛

矩阵很大,但是关键点(影响dp值)的点很少

考虑$(i,j),(i+1,j),(i+2,j)(i,j+1),(i,j+2)(i+1,j+1)$都为空的时候我们有没有什么规律

推导后得出:

上面因为中只有一个min的改成f(就是只考虑先手一个人的),等价推导即可qwq

所以我们最后只需要对于一个点,找出那些相邻的六个点提出来dp即可....就是下面画出来的

然后就是一些复杂的组合计数qwq,考虑每个关键点被算几遍,显然是向左上的一个对角线

CF708D Incorrect Flow

你会发现1,n的出入平衡是对于1,n单独两个点说的,不是整个网络流量平衡qaq

MCMF是最小费用最大流,前半部分是

AT5202 [AGC038E] Gachapon

F(x)为取了n个数还没结束的EGF

$F(x)=e^x-\prod_{i=1}^n(e^{a_ix}-\sum_{j=0}^{b_i-1}\frac{(a_i)^j}{j!}x^j)$

这里$a_i$是i个数被选中的概率,相当于都超过然后减去这样子qwq

然后我们有:

MinMax容斥做法:

考虑计算$E(min(T))$,即一个集合的一个元素达到$B_i$的一个最小时间qwq

我们可以根据势能函数的定义方法去求这个状态的期望,即对于每个这个状态的先决局面,用他们转移到下一个状态的期望步数*他们出现的概率

于是我们有所有这个状态的前若干步状态的期望和,$c_i$表示某个局面的概率:

$E=(-1)^{|T|+1}\frac{S}{\sum a_i}\sum_{0<=c_i<b_{x_i}}\frac{\sum {c_i}! }{\prod_{i=1}^n(c_i!)}\prod(\frac{a_{x_i}}{\sum{a_{x_i}}})^{c_i}$

其中我们相当于枚举了每一个$c_i$啊,然后就是相当于一个可重全排列每一个的概率走到下个局面期望步数

所以说我们就对于这个式子,算一个容斥dp,看看题目,$\sum B_i ,\sum A_i,n \leq 400$

有个容斥dp状态很严谨的定义f_{i,j,k}表示上式中考虑了前i个数,然后$\sum A$为j,$\sum B$为k的所有集合按照上述式子中除掉$\sum A,\sum C$有关项的乘积之和

那么转移就考虑这个数选择的次数对于式子的贡献,会影响A和C

具体的,我们再变变形

$E=(-1)^{|T|+1}\frac{S}{\sum a_i}\sum_{0<=c_i<b_{x_i}}\frac{\sum{c_i}!}{\prod_{i=1}^n(c_i!)}\prod a_{x_i}^{c_i}(\frac{1}{\sum{a_{x_i}}})^{\sum c_i}$

也就是说我们要$\prod (c_i!)$和$\prod a_{x_i}^{c_i}$和$-1^?$

#6271. 「长乐集训 2017 Day10」生成树求和 加强版

首先变成一个带单位根的数域的运算,让乘法代替三进制加法

$x_1,x_2,x_3$对应用$111,1w,w^2,1,w^2w$三个东西代替边权得到的结果

然后$a_0,a_1,a_2$表示正常的答案,即mod 3这一位是1的方案数这样子

然后我们考虑求解方程,因为w是三次单位根,有$w^3=1$,可以解出来这个方程.....

具体的,我们相当于用w(三次单位根)来代替边权,使其满足三进制加法中对于3取模的过程

$w*w*w=1$,所以我们可以列这样三个方程

系数均为一,$a_0+a_1+a_2=x_1$,其中$x_1$是我们直接矩阵树求出来的答案

系数为$1,w,w^2$,$a_0+a_1w+a_2w^2=x_2$

系数为$1,w^2,w^4$即$1,w^2,w$形式是一样的

那么我们根据这三个方程得出$x_1,2,3$就可以反解出之前$a$

也就是说我们还是要构造多项式的,但是系数可以变换来解方程

同理说不定能推广到n进制,但是复杂度也要乘上一个n

GYM102331H

区间k个最长不交子段和最大,这个k超级大

答案关于k是凸的,wqs二分

$val[0/1][0/1][i]$表示左端点有没有选,右端点有没有选,选了i个区间的最大值,这要$nlogn$的空间

然后考虑wqs二分后,选出这个最大的任意多的使得和最大

就是说在log段区间上每一段区间上二分一下,找到这个区间的最优方案

然后这log段区间一起要dp一下,$dp_{i,0/1}$表示i这个区间节点最后一个点有没有选,转移考虑这个区间选上哪一段就好了,相当于在这个凸包上二分出最优方案,据说这个是闵可夫斯基和......

CF1361E James and the Chase

之前刷题的时候做过了

首先考虑怎么判断一个点是好点,没有横跨边就是好点

找到一个好点怎么判断,对于一个点子树内的一个返祖边,首先不能有多于一条,这样会假掉

然后再考虑这个点的返祖边能走到哪个点,假如能走到g,那么这个点是好的当且仅当g是好的

因为我们可以发现对于g子树内的我们只有从u->返祖到g或者从u直接走过去一种方案

g子树外的点,因为g只有一条走过去的方案,所以u也是

写的时候考虑找到一个返祖边就返回上去就好了

TC10748

根据加密方式可知,只加密一次得到的相邻两端结尾一定不同的

只有一次加密$dp_{i}=\sum_{j=0}^{i-1}dp_{j}[s_j!=s_i]$

两次加密怎么办啊?

我们考虑只维护每一段的结尾的dp值,然后维护一个$pre$

$pre_c$表示这个位置以及之前所有位置他的这一位是c的数字的dp值之和

考虑解密一次的序列,我们只需要维护每一段末尾的dp值和pre值,然后再去解密这个解密第一次的序列

你会发现我们解密第一次后的序列至多只会有n段,虽然可能很长,但是第二次解密只需要本质不同的那n段

因此我们的转移就是考虑把每一段的最后一个元素提出来,然后把这个元素拿出来dp,于是你会发现我们需要第一次解密后的所有和这个不相等的位置(参照最上面式子)的dp值之和拿过来转移这个第二段

因此我们的转移就是枚举上个分界点,然后把分界点之前的pre除了这一段的最后一个数外的其他结尾的和找出来,然后转移这个数的dp值

$dp_i+=\sum pre_{j,y},y!=x$

要小心长度为1和开头的段,此时我们可能不合法....

TC11779

考虑最终的代价一定是所有单词出现次数*哈夫曼树深度和

然后考虑从频率从大到小考虑每个单词

那么对于所有单词,$dp_{i,j,k,h,p}$考虑了i,i+1,i+2的点,然后已经放了前j个单词,深度为i的有k个,i+1有h个,i+2有p个的最小代价和达到最小代价的方案数

按深度从小到达dp,注意这个深度是带权深度,而我们只可能从i这一层向下长,长的边权只有223三种qwq

转移枚举当前选了多少个深度为i的点,加入选了x个,剩下的都会向下一层扩展,即深度为$i+2$的会增加$2*(k-x)$,深度为i+3的会增加k-x个这样子....

先考虑所有单词都可区分,那么我们乘上一个$C(k,x)*x$!

算方案数的时候钦点每个频率相同的单词不一样,然后如果每一段深度相同频率相同的单词,加入有x个,可以除掉这个$x!$,这个$x!$就是单词和编码任意两两匹配的方案数

滚动这个i这一维啊

H. Horrible Cycles

二分图满足某个性质的简单环计数.....

考虑我们是从小到大的考虑是否$a_i$把左边的点加入前面所有的环中啊

然后考虑一个右边的点,首先两个出入点不能相同否则会提前成环

要不然就是两个点选完后,你会发现一个点还能连一个出边,一个还能链一个入边,这个东西就相当于一个新点,又因为我们减少了两个,所以-1

每次我们右边多出新点都要用组合数选出来,右边的转移式子就是$dp_{i,j}->C_{x,k}->dp_{i,j+k}$,$x=a_i-a_{i-1}$

左边的转移就是这个点选不选啊,如果$j>1$可以加入环,否则转移到ans里面qwq(环停下来了)

但是说二元环在这里面会算一次,所以要剪掉二元环啊!

#431. 【集训队作业2018】time map

$n^2$怎么做啊

直接用暴力维护每个节点的信息,然后暴力在树上跳,每个操作做到$O(n)$还是很简单的

没有修改

考虑预处理每个节点有奇数个1/偶数个1的时候的得到的权值和,树上dp一下即可

线段树维护a数组,区间and,支持区间or和,区间and和

我们会发现,直接用tag维护$\&a|b xor c$即可,就能支持下传标记了

然后你会发现每一次修改跳的之后只会跳换方向至多log次,而倍增只会有log次

这个倍增就是维护某个点不断跳左儿子跳$2^i$会到达哪里,跳右儿子$2^i$跳到哪里,这样子我们只需要向某个方向倍增直到和初始节点的值不同就好了,这样暴力3个log,注意我们是广义线段树,所以查询这个and值要一个$log$ qaq

怎么省掉求值啊

当前向左区间$[l,r]$,就可以线段树二分出最小的x使得$val[l,x]=val[l,r]$

你会发现向右走这个x是连续的呵呵....有个图

所以二分出这个之后再去倍增这个x即可,倍增找到这个点就能路径求个和啦!

时间复杂度就是$O(nlognlogw)$

#105. 【APIO2014】Beads and wires

考虑蓝边怎么来的吧

等于以某个为根,蓝边要直上直下的qaq

那么我们给这个树染色后存在一个根存在一组匹配能满足蓝边直上直下的

$dp_{i,0/1}$表示考虑到i子树的点,i是否是一条长度为2的路径的中点,子树内的最长的蓝边和是啥

转移较为容易,换根dp即可

然后就能知道答案了qwq

TC11305

其实就相当于具体划分每一段a的方案数,而每一段都是要刚好整除分开的