NOI2015刷题记录

不贴代码,稍微讲讲思路

Day 1 T1 程序自动分析:

第一眼看吓死我了,还以为有什么坑。结果它还真是个裸的并查集。。。

T2 软件包安装器:

树剖一下,线段树维护一下就好啦~我是在每次操作前先单点查询当前点的状态,再区间查询并修改(查询和修改显然可以一起做)

T3 寿司晚宴:

一开始不会~(≧▽≦)/~啦啦啦

首先选了一个数相当于选了它的质因数集合,不用管指数。然后我们发现n是500,小于根号n的质数只有8个,就可以状压了,那么大于根号n的质数呢

每个数大于根号n的质因数显然最多只有1个,然后因为大于根号n的质数同样只能选一个,所以我们把数按它大于根号n的质因数排序,没有就是1,大于根号n的质因数相同的数处理一下就好了。

用f[now][i][j][k]表示当前选到第now个数,第一个人选了i这个集合,第二个人选了j这个集合,k是0..2,0表示两个人都没选这个数,1表示第一个人选了,2表示第二个人选了,然后就可以转移了,但有点恶心。。。now这一维可以滚动,所以开f[2][256][256][3],不会炸

这题还是满有价值的

Day 2 T1荷马史诗:

第一眼吓死我了,完全不会啊,然后就愉快地抄题解去了。~(≧▽≦)/~啦啦啦

首先满足任意两个不同的串没有公共前缀,并且是在k进制下,其实就是要构造一个k叉的哈弗曼树,然后我就长姿势了。。。

因为k较小,所以我们用一个堆存每个节点,每次弹出最小的k个合并起来,类似于二叉的哈夫曼树。注意题目要求最长字符串长度最短,所以比较的第一关键字是值,第二关键字是深度。为了实现上面的过程,我们还要“补全”这棵树,因为共有n个点,最后合并成1个,每次合并会减少(k-1)个点,所以判断(n-1)%(k-1)是否为0,若不是,则加入k-1-(n-1)%(k-1)个权值为0,深度为1的点。

T2品酒大会:

首先r-1相似肯定包含了r相似的情况,这题又是求公共前缀的长度,所以先用后缀数组求一遍height,从大到小将集合合并起来,可以用并查集实现,维护联通快的size,max和min,因为可能是负数乘负数。

T3小园丁与老司机:

不会~(≧▽≦)/~啦啦啦,等以后更强了再来搞这题吧~

注:NOI2016太难啦,我都不会,只A了区间。。。

原文地址:https://www.cnblogs.com/lujiaju6555/p/6706304.html