NOIP2015 - 模拟考试Ⅴ

2015.10.03-04

闲吹

状态世况日下…

Day 1

Language

[Description]

给出不超过5000个长度不超过30的字符串,求状态数最少的自动机的状态数。

[Solution]

大致的思路:按深度合并状态,后继状态相同即可合并,哈希记录后继状态。

[Summary]

实力脑补了一个错误的贪心。

Set

[Description]

你想将[A,B]内的所有自然数分成若干个集合。
一开始每个数自己是一个集合,两个集合可以合并的条件是:存在两个数i,j分别处于这两个集合,且i,j均为一个至少为P的素数的倍数。若如此,则将两个集合合并。
问最后有多少个集合。

[Hint]

$1≤A≤B≤10^{12},B≤A+10^6,2≤P≤B$

[Solution]

并查集。
有相同大于P的质数因子的数可以合并。而且因为[A,B]长度最多为$10^6$,只有$10^6$以下的质数可能在此区间出现两次,所以只用讨论P到$10^6$间的素数就可以了。

[Summary]

好像实力交错程序了qwq

Color

[Description]

给定一个长度为n的元素大小为1~M的整数序列,对于某个元素值C来说,C在[L,R]内的权值定义为C在这段区间出现次数的平方。给出Q个询问,询问区间[L,R]内颜色内颜色 [a,b]的权值总和。

[Hint]

$1≤N,M,Q≤50000$

[Solution]

直接分块(大约1500一块)是可以卡过去的…
然而可以在线莫队,就是预先处理出一些询问的答案转移过来。

Day 2

Pudding

[Description]

n个大小不超过$10^6$的数,有两种操作,一种把所有数x变成y,第二种询问整个序列有多少数字段,一个数字段是序列中一段连续相同的数字。

[Hint]

$n≤10^5$

[Solution]

链表+启发式合并

[Summary]

想到了链表,然而没时间打了。

Prison

[Description]

同HNOI2008越狱,数据范围$n≤10^{12},m≤10^8$

[Solution]

考虑不合法方案数,易得

$$ans=m^n-m*(m-1)^{n-1}$$

[Summary]

简直是组合数学做多了的后遗症- -
一看又是这种组合水题,根本没想什么,随手推了个式子:

$$ans=m*\sum_{i=0}^{n-2}(m-1)^im^{n-2-i}$$

意思是枚举第一个重复的元素。
其实式子是对的,但是没第一个那么好求,而且计算是$O(n)$的,我实力用矩阵加了加速…调了两个多小时qwq其它两道题都暴力走人了,结果这题还是打挂了qwwq
看到水题一定要清醒啊…不要太J动qwq…

SPFA

[Description]

给你一张含有n个点m条边的连通无向图,n个询问,询问删掉点i后,1号点到多少个点的最短路长度会发生变化。

[Hint]

$n≤5000,m≤20000$

[Solution]

难点主要就在判断一条边是否为最短路上的边。
然后其实很简单:(u,v)在最短路上当且仅当dis[u]+w[u][v]=dis[v]或dis[v]+w[u][v]=dis[u].
后面随便怎么搞都可以了- -

[Summary]

人还是太naive

总结

感觉每天考都要考蠢啊,感觉就这样考考考就这样晕进了联赛考场,感觉时间过得飞快也并没有做什么….