10.9 模拟考试题解报告

10.9 模拟考试题解报告

扯

数据比较友好没有卡什么稀奇古怪的东西

或者说数据友好过头了... ~~错估数据水分导致挂分~~

考试过程

顺次来的时间也比较平均除了第一题基本上每个题都是一个小时左右第一题的时间分到了第三题上

策略有一点失当其实还算在预期之内只是有些取舍不当

一开始题没读清楚废了点时间以为那个格子是大格就是可以圈出一片区域后来发现是限制了一格...(写完之后测大样例没过才发现...)

没有想到什么方法...(菜

然后就把每个线的位置存下来每个询问直接扫一遍暴力判断

然后过了大样例

算了一下复杂度发现复杂度比较玄学跟颜色的种类有关...

如果构造数据把 (n) 和 (k) 放满然后只上一种颜色每次询问的复杂度可以卡到 (O(m))

然后上界就到了 (O(km)) 了

又看了一眼数据范围

(1 leq n, m, k leq 5 imes 10^4)

汗... = =

这个 (n) 和 (m) 是同级的

应该不会有出题人对着这个方法卡吧... 大概?

没想到优化(BS 行为

于是听天有命就跑路了...

首先想到的是二分

然后想到的是贪心

然后 BS 都没写(雾

之前有一次 T1 贪心写假直接爆零害怕了...

然后考虑 (dp)

状态比较好设然后转移的边界有一点假导致复杂度有一点假...

然后发现下标好像不一定是整数...

把所有数乘二 (dp) 方程不变

然后发现复杂度有点玄学...

复杂度上界是可以卡到 (O(nm^2)) 的

如果整出一个 (n) 不是很大但是 (K) 很小 (M) 很大的数据把后面的这个 (m^2) 卡满就玩完了... = =

应该不会有出题人对着这个方法卡吧... 大概?

那个最小值好像可以处理一下?

算了跑路了

这个题看着就很 (dp) 然后开始想 (dp)

(dp) 的式子也比较显然的亚子然后细节好像有亿点多...

因为循环顺序和特判的加一调了好久好久...

过了大样例之后看了一眼数据范围

对于 (25\%) 的数据 (n leq 20)

对于另外 (25\%) 的数据 (t_i leq 10)

对于全部数据 (1 leq t_i leq n leq 5 imes 10^5)

然后这两个数据正好是 (dp) 数据的两维... = =

然后只写了一部分就跑路了...

其实应该按照 (n) 分开因为第一部分是可以写暴力的... 然后用 (dp) 过另一个就有五十分了

链的数据就是一个最长不降子序列然后 BS 没看这一部分(白送二十五分没要...

然后直接开 T4

然后 T4 不会写爆零了...

得分情况

100 + 70 + 25 + 0 = 195

T3 有点亏... 仔细写一下的话应该能到 (75)

T1 和 T2 的玄学做法好像没人卡只有 T2 挂了五分? ~~这都不卡数据jiao造的吧~~

后来发现 T3 的数据 (n) 的那一维开到 (10^5) (t) 的那一维开到 (100) 两部分都能过?

那纠结个*啊错估数据水分导致挂分???

题解

T1

开 (vector) 对每个颜色暴力存位置对于每个询问暴力找位于指定两个位置之间的位置横着找一遍竖着找一遍记一下数量然后乘起来

这个做法的理论复杂度是可以卡到 (O(KM)) 的 ~~但是出题人没卡把这个做法放过去了~~

在颜色数量比较多的时候复杂度是可以的只要构造数据只有一种颜色复杂度就满了

正解是开二维 (map) 直接存两种颜色之间颜色的个数复杂度 (O(K)) 可能带着一个 (map) 的 (log)

代码

这里的代码是上面那个暴力

T2

先写一下 BS 的七十分的 (dp) ... 表示这个题做过...

下面默认将 (a) 数组 (M) 和 (K) 都乘上了 (2)

状态: 设 (f_{i, j}) 表示前 (i) 个数第 (i) 个数是 (j) 的时候的两数组差的最大值的最小值

转移:

[f_{i, j} = max_{j = 2K(i - 1)}^{minleft(M, M - 2K(n - i) ight)}left(min_{k = maxleft(0, 2K(i - 2) ight)}^{minleft(M - 2K(n - i + 1), j - 2K ight)} left(f_{i - 1, k} ight), |j - a_i| ight) ]

然后可以发现这个 (dp) 的复杂度有点玄

如果在 (i) 层的状态比较少的话这玩意应该是挺快的但是如果构造数据将 (n) 调的不是非常大 (K = 1) 然后把 (M) 卡到满这个式子的复杂度可以卡到 (O(nM^2)) 的程度... ~~但是出题人没卡把这个做法放过去了~~

还是因为一些未知错误挂掉了 (5) 分

转移里面的那个 (min) 应该是可以想办法优化掉的

(dp) 的分数上界只有 (75) 分... 感觉不会有这么苟的数据优化也没必要了

代码

正解

二分 + 贪心

二分最大值每次放的时候在值域里将 (b) 尽量的往前放

正确性的话可以考虑在值域中某一位置两数组的差的绝对值不超过二分值就不影响答案因为每个位置会影响后面的数具体来说会把后面的数往后挤所以在每一个位置允许的范围内尽量的往前放本身不会影响答案而且可以给后面的数留出更多的空间答案不会变劣

代码

T3

这题看着就比较 (dp)

设 (f_{u, j}) 表示在以 (u) 为根的子树中选取的点集中点权最大为 (j) 时的最大点集

转移考虑子树的选取情况

[f_{u, j} = sum_vleft(max_kleft(f_{v, k} ight) ight) + [j geq a_u] imes left [max_kleft( left[f_{v, k} = max_k(f_{v, k}) ight] imes k ight) leq a_u ight] ]

只能说这个式子好丑..

第二项那一坨东西表示的是

(u) 点子树集合中选的点集的权值超过 (u) 点的点权同时其所有孩子转移过来的状态中选择点集中点权的最大值没有超过 (u) 点的点权

只有这两个条件同时满足的时候 (u) 点本身才能放入点集中

所以循环的枚举顺序需要把 (j) 放在最外层处理其所有孩子记录所有转移位置中 (k) 的最大值结合 (j) 的值判断这个点是否可选

卡一下数组大小这个 (dp) 可以过五十分

然后是链的情况

其实就是求一个最长不升子序列在 (dfs) 的时候维护一下就好了

代码

又看了一下

发现上面那个 (dp) 不用那么麻烦的

其实有这样的一个式子

[f_{u, j} = maxleft(f_{u, j}, f_{u, j - 1} ight)\ f_{u, j} = left(sum_v f_{v, j} ight) + left[a_u = j ight] ]

稍微改变了一下数组含义维护了一个前缀最大值

题目的正解是线段树合并 + 整体 dp

但是不是很会这里说另一种方法

考虑链的那一部分分是一个 (LIS) 问题从根向叶子维护一个最长不升子序列

那么原题相当于是一个树上的 (LIS) 问题从叶子向根维护的是一个最长不降子序列

序列上转移到当前位置的是前面所有位置树上则是所有子节点

[f_u = max_v(f_v + 1)[a_v leq a_u] ]

对于一个点 (u) 已经有了其所有孩子中的最长不降子序列如果能将所有的孩子放到一起在里面找到转移的位置进行转移就好了

做法也比较暴力直接将 (dp) 数组改成 (set) 暴力启发式合并所有孩子将 (a_u) 插进去二分第一个大于 (a_u) 的位置删掉就好了

复杂度是两只 (log) 一只是合并一只是插入

代码

T4

咕~