13.3.18 考试小记

发布于 2018-03-15  11.58k 次阅读


题目一天比一天神。最恶心的是今天的题没!有!题!解!

三道题都敲暴力,所幸暴力都没挂所以分数还好。

 

T1

在树上选出“广义上的LIS”。

首先很容易能想到一个O(n^2)的DP,f[i][j]表示以i为根的子树中最小权值大于等于j的最大点数,把它打出来就有50分了。

某同学提出了一个O(2^最大深度)的暴力算法,就是枚举一条链上的选择情况,然而这样就能有90分了,因为出题人太懒,造了9棵非常随机的树,期望O(2^logn)(可能第10棵也是随机的= =)。

考虑用别的方法优化n^2的DP。wq同学考场上用了3h+写出了一种毒瘤线段树做法,我下午一直尝试用treap实现这个过程不过最后弃坑了。写一写DP方程:

$$F[u][j]= [ j \leq s[u] ] + \sum_{v} f[v][k]$$

这样的转移实际上类似于区间加法,如果不想使用毒瘤数据结构的话,还可以使用类似差分的思想来做,让新的f'[i][j]的后缀和表示f[i][j],那么,每次转移只要把f'的对应位置相加就好了。为什么这样是对的?因为差分叠加起来之后还是合法的差分,所以每一个后缀和就等价于新的f值。同样的,对于前面的布尔表达式,还是相当于一个区间加法,我们依旧差分处理,给j加一,j的前驱减一即可。

这种差分转移DP的思路非常神,也算是学到新科技了。

 

T2

完全不想写这一题啊,这道题就是纯粹的乱搞。但是本着对自己负责的态度,还是写一下乱搞思路吧。

先只考虑两种元素的时候,一段连续的较大元素贡献的区间数就是“等差数列前缀和的前缀和”,考虑一下边界情况,就是两边连起来的情况,然后就做完了。

多个元素也是一样,把元素从小到大排序,每次插入所有相同元素然后照样算就好了。

 

T3

感觉是这三道里相对最简单的一题。

不论是暴力打表还是用坐标系转换,都可以发现答案的式子其实就是:

$$\sum _{i=0} ^{B} C_{A}^{i} C_{A+B-i}^{A},A=\frac{n+m}{2},B=\frac{n-m}{2}$$

因为模数是100003,所以很容易就能使用lucas暴力计算。而Lucas的过程,其实就是把原数拆成p进制,所以现在可以考虑使用数位DP的思路来计算这些玩意。

枚举p进制的位数,枚举i在p进制下当前位的值,那么第一个C直接算,而第二个C就出现了当前位下A+B-i<0的情况。实际上,我们只要手动模拟p进制借位就好了,设f[i][0/1]表示第i位不需要/需要向i+1位借位的值,之后讨论一下就做完了,思路非常清真。

 

虽然这次考试的题目思路都非常值得学习,但是还是要D这个出题人!题面里数据范围是错的!3个样例是错的!题目没有题解!!!大大的差评!!!!!

本文隐藏内容 登陆 后才可以浏览


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974