省选2018 九省联考 Day1 解题报告

Posted by

T1

题解

首先如果要在一个格子上下棋首先要在它的左边上边以及左上方的所有格子下棋,于是下棋过程中棋盘总是被分成两部分;

观察到\(n\)和\(m\)都很小,考虑状压轮廓线,我们从棋盘左下角走到右上角,设向上一步为\(1\),向右一步为\(0\),这样就能表示出下棋的每一个状态,记忆化搜索转移即可;

代码

T2

题解

对于45%的数据:

首先观察到整个图是一个森林(算上\(0\)节点就是一棵树),先将权值从小到大排序,对于每个节点各子节点所在的子树,将比较大的权值区间分配给编号较小的子树,比如:

假设\(k=2\),先将\(val[1]\)分配给\(1\)号节点,然后将\(val[n-siz[2]+1,\ldots,n]\)分配给以\(2\)为根的子树,\(val[n-siz[2]-siz[3]+1,\ldots,n-siz[2]]\)这个下标区间分配给以\(3\)为根的子树……

之后将\(n-siz[2]+1\)分配给\(2\)号节点,以此类推;

对于100%的数据:

上述方法在权值有重复的时候会出现错误,栗子:

输入:

4 2
1 1 1 2

输出:

1 1 2 1

而贪心得出的结果是1 1 1 2;

这时改变贪心的思路,按照题意,先贪\(1\)号节点,再贪\(2\)号节点;

将权值从大到小排序,设\(f[i]\)表示第\(i\)个权值左边已经被预定的数的数量,则第\(i\)个数左边可用的数的数量为\(i-f[i]\);

对于一个节点\(u\),在权值序列中找到一个位置\(pos[u]=x\),使得\(val[x\ldots n]\)中,可用的数的数量至少为\(siz[u]\);

然后预定\(siz[u]\)个数,即将\(f[x\ldots n]\)都加上\(siz[u]\);

当遇到一个节点有父亲时,先将父亲的预定额去掉,即将\(f[pos[fa[u]]\ldots n]\)都减去\(siz[fa[u]]-1\);

上述操作都可以用线段树完成。

代码

T3

题解

标算太复杂,不如直接暴力:枚举每个节点,首先标记出比该节点权值大的节点,然后统计恰好包含\(k\)个已标记节点的连通块的数量,这是一个树形DP,然后将结果乘上该节点权值即可;

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注