Noip2021模拟测试赛一

A 游戏

$A$ 先从 $(1,1)$ 移动到 $(2,m)$$B$ 再从 $(1,1)$ 移动到 $(2,m)$。

容易知道$A$ 移动一定是先右移任意格再下移一格最后右移到 $(2,m)$。

最终会剩下右上角左下角两个区域没取。$B$ 只能取其中一个区域。

所以 $O(m)$ 枚举暴力计算答案。

B 公司补偿

简单 DP 非常容易但由于 $d$ 极大所以会爆。

但是可以发现确定工资后最多只有 $n$ 种不同工资。

我们只考虑工资之间的大小关系再用 DP 计算。

这时要使用组合数但是可能有重所以容斥。

C 无聊的线段

如果我们固定选择线段的权值的范围 $[l,r]$显然将权值在 $[l,r]$ 之内的线段全部选择。

容易发现$l,r$ 一定是某一个线段的权值因为不是线段的权值的 $l,r$ 不优。

发现$l$ 增大时为了满足要求 $r$ 不会减小。

所以双指针 $O(n)$。

问题来了怎么判断是否满足要求

我们用并查集线段覆盖的节点还是其他

线段树区修区查。

对于一个新增线段 $[l,r]$ 我们让 $[l,r-1]$ 的点值全部加 $1$。减去则相反。

查询则查询 $[1,m-1]$ 的最小值是否为 $0$。

Noip2021模拟测试赛二

B 点对游戏

可以发现每个人取的节点数量是固定的所以我们考虑单独计算假设为 $x$。

由于完全随机所以每个节点被选取的概率也是一样的为 $\frac{C_{n-2}^{x-2}}{C_n^x}$。

然后就是计算得分发现只需要计算距离为幸运数的点对的个数即可。

点分治

最终答案乘上 $\frac{C_{n-2}^{x-2}}{C_n^x}=\frac{x(x-1)}{n(n-1)}$。

Noip2021模拟测试赛三

A 选举

首先想到贪心发现不行。

那就 DP。考虑 $f_i$ 代表 $i$ 之前最大答案。然后发现 $f_i$ 转移非常鬼畜需要 $O(l-r)$。

$$f_i=ma{x}_{j=l}^r(f_j+[\sum _{k=j+1}^i\left]\right)$$

额。。。那个 $[]$ 就自行理解一下吧主要是我不知道怎么表示

尝试优化。发现区间 $[j+1,i]$ 的和可以使用前缀和求出一下称为 $s$。

就变成了有关 $s_i$ 和 $s_j$ 大小关系的式子。

那么我们开一个值域线段树下标为 $s_i$。

记录什么呢节点 $[L,R]$ 记录 $[i-l,i-r]$ 内每个 $s_j\in [L,R]$ 的 $f_j$所有 $f_j$拿单调队列储存

对于每个 $i$我们在线段树上查询

• $s_j\in (-\infty ,s_i)$ 的最大 $f_j$
• $s_j=s_i$ 的最大 $f_j$
• $s_j\in (s_i,+\infty )$ 的最大 $f_j$。

就可以计算答案了。

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

B 蛋糕

欸欸额这题要画图先不写了吧。

可以自己推一下。

C 魔法树

被施了魔法的树就是点分树。

满足的条件是每个节点都是其子树的重心。

或者$\forall u,{\max }_{v\in so{n}_u}(si{z}_v)\le \frac{si{z}_u}{2}$

Noip2021模拟测试赛四

A

Noip2021模拟测试赛十一

A

可以发现对于每个连通块如果答案不是 $-1$则确定一个点的值其他点的值都能确定。而且每个联通块中编号最小的点的值可以随意确定。

所以我们对于每个连通块编号最小的点排序从后往前推。

然后发现 $k\le 100$所以不存在需要更改两个节点的值的情况。

最后一个编号最小的节点标为 $k-1$然后前面的编号最小的节点全部标为 $0$。

推一遍得出答案冲突就是 $-1$。