Soi final training

以梦为马,不负韶华


本文总阅读量
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$的矩阵

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

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