blog杂题

Hrbust - 1846

题意:序列每个格子允许放O和X,求长度为n的序列中至少存放m个连续的O的方案数

容斥+dp

设$dp[i]$为长度为$i$时的合法方案数

转移的个数来自于上一个状态的合法序列后面接上O和X,既$dp[i-1]*2$

也有可能来自于本来不合法的方案,转移后就合法了,那先固定一部分状态,因为转移后才合法,所以假定序列中[i-m+1,i]全部为O,那么前面就可以为所欲为,有$2^{i-m}$个状态,但$2^{i-m}$中会有合法方案的存在,因此需要减去已经合法的$dp[i-m]$个方案,剩下的是不合法的方案后面接上$[i-m+1,i]$的全O的方案数.(然而这连样例都过不了)

YY了一下认为可能是非法方案转移途中还不到最后一位就合法了,而这已经囊括在$dp[i-1]$的范畴中,所以后半部分方程歪掉了,那就在$[i-m+1,i]$置为O,而$i-m$处置为X,表示必须转移到最后一位才能形成合法的方案,那么转移用到的非法方案数为$2^{i-m-1}-dp[i-m-1]$

两部分加起来就可以了

https://paste.ubuntu.com/p/mYQPpgTb9N/


HDU - 4370

给定$n*n$矩阵$C_{i,j}$,求构造一个$n*n$的01矩阵$X_{i,j}$

$X_{i,j}$满足约束第1行的和为1,第$n$列的和为1,其余的第$i$行的和等于第$i$列的和

使得$\sum C_{i,j}*X_{i,j}$最小

由于剧透,得知转化为图,节点1的出度为1,节点n的入度为1,其余$1<i<n$节点入度等于出度,$C_{i,j}$为$i→j$的权值

入度与出度相等意味着非起始点/终点或是可能有环,需要分别讨论1和n是否各自形成环,或者只是1到n的简单路径,对比一下权值即可

https://paste.ubuntu.com/p/pY2gVmJxkf/


FZU - 2234

题意:求双调最短路的最大价值

来回的过程可看作是两个人同时在起点走到终点,但物品只能取一次,但时间无法承受$O(n^4)$

因为走的是最短路,对于某个人已经走了$k$的长度,可以得到$x_i+y_i=k+2$

因此设$dp[k][x_i][y_i]$为走了k的长度时第一人在横坐标$x_i$而第二个人在横坐标$x_j$的最大价值

如果坐标相等则把两个物品的价值除二看作只拿一次

https://paste.ubuntu.com/p/nssf9KynCF/


Codeforces - 337D

题意:给出一棵n个点的树和m个标记的点,求存在多少个点离最远的标记点不超过d

不错的树形DP(换根大法好)

令$f[i]$为$i$与$i$子树下距离标记点最远的距离,若不存在则为$-\infin$(保证后面加法的正确性)

令$g[i]$为$i$与$i$子树以外的距离标记点最远的距离,若不存在则为$-\infin$

那么答案就是$max(f[i],g[i])≤d$的$i$的个数

$f[i]$很容易搞,只需$f[u]=max(f[u],f[v]+1)$

$g[i]$则需要考虑$i$的父亲以及$i$的兄弟,$g[u]=max(g[u],g[fa]+1,f[v]+2)$

很显然每个$u$对兄弟$v$的枚举可以被菊花树卡飞

那么需要一个简单优化,记录对于每个节点$fa$记录$f[]$最大的儿子节点$best[fa]=v$

那么对于枚举到本来就是一个父亲的$best$节点$u$时,对$g[u]$则需要暴力枚举所有兄弟,而不是$best$的节点时,$g[u]=max(g[u],g[fa]+1,f[best[fa]]+2)$

https://paste.ubuntu.com/p/9JcQYSjGHx/


Codeforces - 675E

题意:$n$个车站,每个车站$i$可花费用1到达车站$[i+1,a_i]$,设$p[i][j]$为$i$到$j$的最小费用,求$\sum_{1≤i<j≤n}p[i][j]$,$n<10^6$

代价为定值下可贪心的dp

设$dp[i]$为$\sum_{i≤u<v≤n}p[u][v]$,那么答案就是$\sum_{i=1}^{n-1}dp[i]$

考虑怎么转移,首先可以知道的是对于$i→[i+1,a_i]$费用为1,$i→[a_{i+1},a_{i+2},...,a_{a_i}]$费用为2,以此类推

但$[a_{i+1},a_{a_i}]$是非单调的,仍需要维护最大值让每次转移尽量远,令这个存在最大值的下标为$m$

那转移方程就是$dp[i]=dp[m]+[(n-i)-(a_i-m)]$

YY一下正确性,每次转移都按照这样的贪心策略,对于每一个$i$而言肯定是一种最快到达$n$的方案之一?

其实这样看的话这题不算是DP,只是一种记忆化手段

https://paste.ubuntu.com/p/xwHRv4SqSn/


Hrbust - 1256

题意:给出$n$个人,要求组建$k$支队去打铁,每支队的战力为$a[i]+a[j]+a[k]+b[i][j]+b[i][k]+b[j][k]$,求最高总战力

范围$n<19$状压DP优化

首先$O(n^3*2^n)$没戏,需要压常数,参考dalao的发言,由于状态总是3个出现,与其暴力三层枚举,不如用k-1次凑数来更新答案,这样复杂度是$O(能过)$

https://paste.ubuntu.com/p/2wd72Ddg6B/


Codeforces - 611D


HDU - 6070

题意:求$\frac{cnt[l,r]}{r-l+1}$的最小值,$cnt[l,r]$表示区间$[l,r]$的数值种类

分数规划问题考虑二分答案$mid$,有$cnt[l,r]≤(r-l+1)*mid$,次数需要维护种类数和长度的关系,不好check

把式子改为$cnt[l,r]+(l-1)*mid≤r*mid$,每次check枚举右端点,左边用线段树更新答案,每次插入新的r更新只会影响cnt的值,只要记录各类型前一个值在哪即可,既维护一个动态的后缀

(感觉自己的counting能力太弱了)

https://paste.ubuntu.com/p/dtDGK6YPJT/


Codeforces - 817D

题意:求$\sum max(a[l,r]) - \sum min(a[l,r])$

喜闻乐见单调栈

首先求最小的部分,

对于每个$i$,它能扩展到的极左边界为$l[i]$,使得$a[j]>a[i],j∈[l[i],i-1]$,并对应求出极右边界$r[i]$,使得$a[j]≥a[i],j∈[i,r[i]]$

此时$i$对答案的贡献为$(i-l[i]+1)*(r[i]-i+1)$,注意包含$i$的区间个数应该是两边都有$i$的交集!

同理,维护最大的部分,对于每个$i$,$a[j]<a[i],j∈[l[i],i-1]$,并且$a[j]≤a[i],j∈[i,r[i]]$

https://paste.ubuntu.com/p/kY2Ws2bfG6/


Codeforces - 478D

题意:r个红方块和g个绿方块,要求第$i$行搭$i$个同色方块,求总共有多少种方案


Codeforces - 366C

题意:给出$a[1...n],b[1...n]$,求$\frac{\sum a[i]}{\sum b[i]}=k$且$\sum a[i]$尽量大的集合方案,输出$\sum a[i]$


观赏题:CF669D/51nod-1021

OJ挂了:CSU1809

回收站:HDU4472/CF550C/CF660C

标签: 算法, 学习

添加新评论