Soi final training

以梦为马,不负韶华

阅读全文大概需要 1分钟
本文总阅读量
Posted by yjjr's blog on May 26, 2019

本文长文/高能预警

由于博主过于懒惰和菜鸡,打算把未来50天内的大多数训练题目全部放在此博文中,将会不定时更新

所有代码全部位于Onedrive共享文件夹

DP

CF802K 树形DP

无意中做到了瑞士HC2 EPFL的题目,果然很SOI,很侧重思维性


题意:给定一棵树,可以从一个点开始在树上行走,每条边上有一个宝物价值为$w$,每个节点最多访问$k$次,求能够得到的最大价值

$f[x][1]$表示访问完以$x$节点为根的子树后返回到$x$的父节点所能得到的最大价值

$f[x][0]$表示访问完以$x$节点为根的子树后不返回$x$的父节点所能得到的最大价值

CF261D 结论+暴力

题意:给出数列$B$,请假定一个数列$A$,使得其长度为$n\times t$,使得$A$序列为若干个$B$组成,求出序列$A$的最长上升子序列数

表面上看十分不可做,无法把$A$序列求出来并计算LCS

但显然当$t\geq min(n,maxb)$时,答案是$a$中不同的个数

剩下的可以直接暴力

因为LCS的总增量一定小于等于$maxnb\times n$

CF285D DP+容斥+组合

题意:$n$个数的全排列$p_i$,对于每个全排列$p_i$,若$abs(p_i - 1)=1$,则位置$i$为好,询问$n$个数的全排列中存在多少个恰好$k$个好位置的排列

设$f[i][j][0/1][0/1]$表示前$i$位,存在至少$j$个位置满足条件的计数值,两个$0/1$分别表示数字$i$有没有使用过和数字$i+1$有没有使用过

每次转移判断该位置是否满足条件,如果不满足条件的话就添加一个空数字(可以直接乘上阶乘)

但这样的排列中还会存在一些大于$k$个好位置的排列,所求的为至少$k$个好位置

要得到最终的答案还需要一个trick

存在一个容斥原理的模型

$ans=f[n][k]-C(k+1,k)\times f[n][k+1] + C(k+2,k)\times f[n][k+2]……C(n,k)\times f[n][n]$

因为取模数较大为$1e9+7$,所以只能使用逆元处理

CF50D 二分+概率DP

题意:给定若干点和一个爆炸中心点的位置坐标,如果要想使得其爆炸失败(小于$k$个点爆炸)的概率满足不大于给定值$F/1000$,求出最小爆炸半径

很明显先二分答案之后概率DP检验

$f[i][j]$表示前$i$个坐标中存在$j$个爆炸的概率

只需要枚举是否爆炸进行状态方程的转移即可

时间复杂度$O(T\times n^2)$

线段树

CF482B 线段树+位运算

题意:给出序列的长度$n$和$m$次询问,对于每次询问给出$l_i,r_i,q_i$,满足$a[l_i]\& a[l_i+1]\& … \& a[r_i] = q_i$,请你求出原序列${ a_i }$

先按照题意给出的询问将原数组修改,之后再次询问一次看是否符合条件

注意线段树操作的时候要把极大值inf每一位都赋值为1(在这里WA了半小时)

CF833B DP+线段树优化

题意:给出长度为$n$的序列,可以将其划分为$k$段,最大化每段中出现的不同种类数字个数之和

用$f[i][j]$表示前$i$个书分为$j$段的最大价值

$f[i][j]=\max { f[k][j-1]+query(k+1,i) } (0\leq k < i)$

然后发现从$a[i]$上次出现的位置$lst[a[i]]$到当前位置中的这些$f$值都需要$+1$,那么可以第一重循环枚举$K$,之后每次重构线段树进行优化

时间复杂度$O(nk\log n)$

CF383C dfs序分层+线段树

题意:给出长度为$n$的序列,支持如下操作:

  • 查询一个点权值
  • 修改以这个点$x$为根的子树中所有节点的权值,奇数层+val,偶数层-val

先dfs将树中每个节点分层,之后记录两个权值,分别是对应的+/-答案

CF633H

题意:给出长度为$n$的序列,每次询问给出$l_i,r_i$,请求出$a[l_i]…a[r_i]$之间的斐波那契权值

其中斐波那契权值定义为:将子序列排序去重,$P(a)=a_1\times F(1) + a_2\times F(2) + … + a_i\times F(i)$,其中$F(i)$指斐波那契数列

莫队处理询问,线段树处理修改和答案

对于莫队,由于区间内的数和顺序和数量无关,所以可以看成集合进行操作

首先离散化并对每个数进行计数,只有数量在$0$和$1$之间变化时才进行线段树的答案修改操作,否则实际上对答案无影响

对于线段树,pushup可以使用矩阵完成

其中$[1][2]$是答案的矩阵,$[2][2]$是$fib$的矩阵

结果发现常数优秀的暴力可以水过去。。。。

CF686D 树的重心

题意:给出大小为$n$的树和$q$次询问,每次询问以$x$点为根的子树中重心的编号

当合并两棵树的时候,新的树的重心一定在原本的两个重心的路径上

CF191C 树上差分

题意:给出大小为$n$的树和$m$次操作,每次操作将路径上的边都染色一次,最后询问每条边被染色的次数

将$(x,y)$节点$+1$,$lca(x,y)$节点$-2$,最后统计前缀和即可

CF842C

题意:给出大小为$n$的树,每个节点的权值为$a[i]$,询问每个节点到根节点的路径上所有点权值的最大公约数$gcd$,其中你可以把路径上一个节点的权值变为$0$,使$gcd$最大化

经典

HDU1028 母函数/DP

母函数学习课件

本题母函数$(1+x+x^2+x^3+x^4+…)\times (1+x^2+x^4+x^6+…)\times (1+x^3+x^6+x^9+…)…$


DP方法

$f[i][j]$表示把自然数$i$划分为所有元素不大于$j$的方案数

$f[i][j]=f[i-j][j]+f[i][j-1]$

POJ2442 堆/优先队列

题意:给出$n$个长度为$m$的数列,一共$m$次让你每次从各个数列中选一个数相加成新的数列,让你求该数列的前$n$小的值

每次将前$i-1$行求出的$n$个最小值和第$i$行的前$n$小值求和放入优先队列

HDU1010 DFS+奇偶性剪枝

题意:给出迷宫入口出口,询问能否恰巧在$k$步的时候到达出口

常规DFS+剪枝

  • 如果已经存在解
  • 当前距离超过$k$
  • 当前点到出口最小距离过长
  • 当前点到出口最小距离的奇偶性与答案不符

POJ1742 多重背包可行性

常规多重背包三重循环

如果只需要检测可行性,只需要两重循环

每次对选取的次数进行限制即可

POJ2411 状压DP

题意:给出$n\times m$的矩形,用$1\times 2$的方块覆盖,不重叠并且要求完全覆盖,不能越界,询问完全覆盖的方案数

设计状态$f[i][S]$表示第$i$行状态为$S$时的方案数

对于横放,我们可以将两块砖都设计为$11$

对于竖放,为了防止冲突,将上面的设为$0$,下面的设置为$1$

之后逐格讨论状态即可,要手动移动循环变量

POJ2255 二叉树遍历

给定先序和中序遍历,求出后序遍历

直接递归即可

SGU199 LIS输出解

二维LIS,按指定域排序后,求出最长上升子序列

本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr