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≤1012,B≤A+106,2≤P≤B1≤A≤B≤10^{12},B≤A+10^6,2≤P≤B

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

  • [Summary]
    好像实力交错程序了qwq

Color

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

  • [Hint]
    1≤N,M,Q≤500001≤N,M,Q≤50000

  • [Solution]
    直接分块（大约1500一块）是可以卡过去的…
    然而可以在线莫队，就是预先处理出一些询问的答案转移过来。

Day 2

Pudding

  • [Description]
    n个大小不超过106的数，有两种操作，一种把所有数x变成y，第二种询问整个序列有多少数字段，一个数字段是序列中一段连续相同的数字。

  • [Hint]
    n≤105

  • [Solution]
    链表+启发式合并

  • [Summary]
    想到了链表，然而没时间打了。

Prison

  • [Description]
    同HNOI2008越狱，数据范围$n≤10^{12},m≤10^8}
  • [Solution]
    考虑不合法方案数，易得ans=mn−m∗(m−1)n−1ans=m^n−m∗(m−1)^{n−1}
  • [Summary]
    简直是组合数学做多了的后遗症- -
    一看又是这种组合水题，根本没想什么，随手推了个式子：

ans=m∗∑i=0n−2(m−1)imn−2−ians=m∗\sum_{i=0}^{n−2}(m−1)^im^{n−2−i}

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

SPFA

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

  • [Hint]
    n≤5000,m≤20000n≤5000,m≤20000

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

  • [Summary]
    人还是太naive

总结

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

Comment