THUWC2020

THUWC2020

Day1

T1

桌上写着 k 个数
有 k 个人先后依共 n 次来到桌上,每次手上拿着新的 k 个数。如果第 i 次来的第 pi 个人找到桌上写的 k 个数字中的他的数字严格小于他手上当前拿的 k 个数字中他所对应的数字,则把桌上的 k 个换成自己手上的 k 个数字。

n 1e5
k 20

解法 :
二分加线段树查区间 max 两个log本地极限数据1s直接过了
改成线段树上二分一个log 本地0.4秒

T2

有 n个点 m条边有边权的有向图,每次指定一个起点和最多走的步数 s ,每次在一个点选择出边到的点编号最小的,问最后到那个点停下。停下就是走完了限定的步数或者没有出边了。(经过一个边就把权值减一,权值为0就没那条边了)

n m 1e5
w 1e18
s 1 e9

解法:
同一时刻所有的边的情况只可能是棵基环树森林使用 lct 维护

T3

给定一颗树和一个整数 X 。每次询问一个标号区间的点内的新图的连通块个数,两个点在新图中有连边当且仅当它们之间距离小于等于 X。

n 3e5
m 6e5
X<n

解法:

DAY2

T1

给定 n 个形如 a|x|+bx+c 的函数和初值 s 要求排列 n 个函数使得最终结果最大
n a b c 绝对值15

解法:
如果 c等于 0 则转移只跟是正数还是负数有关 记录最大最小即可
否则由于 c 的缘故可能把正负性改了
于是记录-1515到+1515是否能表示以及最大最小值来做n*2∧n dp即可

T2

给定 m 条有向边 保证不存在环 使用dfs 的方法建出一颗外向树。每次询问 ban 掉 u 到 v 的树链后 v 子树内不可达节点个数,保证询问的 u 一定是 v 祖先

m q 1e5

解法: 半支配点相关

T3

给定一棵树,每个点上有值且不重复
每次询问提取一条链后形成的一个排列
有多少种排列进行 k 次冒泡排序的第二步后会形成该链的排列

n q 1e5

解法:
n方都不会。。。