poi2015 bzoj4377-4386训练

时间:2021-08-01 00:19:54

就按时间顺序写吧

完成度:10/10

3.30

bzoj4385 首先一定是删去连续d个数,然后枚举终点,起点显然有单调性,用单调队列乱搞搞就可以啦

bzoj4378 首先才结论:可行当且仅当把所有大于s的数全变成s然后看所有的数的和大于等于c*s,然后两个树状数组分别维护<=s的和及个数即可,注意需要离散化

3.31

bzoj4377 设一段的起点处的数为x,则m个限制条件就可以转化为x在若干个区间(或两个区间的并)里面,然后把这些区间交起来就得到了x的范围,算出个数然后减去最后m-1个数(没有连续m个数在之后)即可。

bzoj4379 显然,枚举断开的边,然后最短的就是把两边的直径中点连起来,最长的就是把两边的直径端点连起来。然后dp一发算出每个点为根的子树直径和把这个子树删去后的直径,然后直接计算即可

4.1

bzoj4380 dp[i][j][k]表示[i,j)区间内最小值不小于k的答案(只考虑走的路在[i,j)内的人),预处理出每个区间内最大费用限制>=x的人的数量,然后是否有k及k的位置即可,方案就是记录当前是否有k及k的位置然后dfs即可

4.2

bzoj4382 显然,对于每种字符,它们把圆环分为若干段,两个位置可行当且仅当对于每个字符这两个位置在同一段内,然后给每个字符的每个段编一个号,hash即可

4.3

bzoj4381 算法复合,先预处理出每个点开始每次往上走z步到达的点和一直走下去的和,取一个lim,对于z<lim的直接由预处理回答即可,z>=lim的直接暴力在树上跑即可,取lim=sqrt(n),则复杂度为预处理n*sqrt(n),询问最大sqrt(n)*log(n)。要注意各种细节,被细节wa在第一个点了一晚上。。。

bzoj4383 首先建出一些虚点表示第i个限制,比其他点大的点连一条有向边到这个限制,权值为1,然后这些限制向区间内其他点连边,权值为0。用线段树优化后一个连边过程,即k个限制把区间分为至多k+1段,每次暴力询问一段即可。然后进行拓扑排序,若有环则无解,记录每个点的最小值即可,若不符合各方面题目条件则无解。

4.5

bzoj4384 设a[i][0],a[i][1],a[i][2]分别为i的前缀中B,C,S个数,则三种字母互不相同等价于a[i][0]-a[j][0]!=a[i][1]-a[j][1],a[i][0]-a[j][0]!=a[i][2]-a[j][2],a[i][1]-a[j][1]!=a[i][2]-a[j][2],等价于(a[i][0]-a[i][1],a[i][1]-a[i][2],a[i][2]-a[i][0])与j的对应三元组对应不同,于是按第一维排序,第二维建立树状数组,存储的是i最大值、最小值,第三维与最大值不同的次大值,第三维与最小值不同的次小值。注意实现细节和常数(树状数组常数都嫌大哪还有什么数据结构常数不大)

4.6

bzoj4386 矩阵乘法,一个点拆成3个点,分别表示原来的点、原来的点走出去1、原来的点走出去2,连边,所有边长度为1,再建一个超级源和所有原来的点连边,超级汇从所有原来的点连边,超级汇再连一个自环,然后长度<=c路径数=矩阵^(c+2)的超级源到超级汇的路径数量,倍增计算即可。暴long long差评、有重边差评、卡常数差评、21020ms的tle了21232ms的ac了差评

终于完结撒花啦!