竞赛讨论区 > 【题解】2020牛客NOIP赛前集训营-提高组(第二场)

【题解】2020牛客NOIP赛前集训营-提高组(第二场)

头像
鸡尾酒QAQ
编辑于 2020-10-20 22:39:10 APP内打开
赞 5 | 收藏 0 | 回复6 | 浏览2153

before the contest

我是本次比赛出题人鸡尾酒,由于水平比四糸智乃姐姐菜很多,所以出的题也会比她友好一些。在大学中打比赛的时候经常被打星的中学生吊打,深知中学生的强大,给中学生们出题确实是一件体力活,对于题目的不严谨指出还希望大家多多包涵。

ps:T3 是请四糸智乃姐姐帮忙出的,如果觉得毒瘤,请大家一起攻击她。

T1 GCD

20pt

直接根据题意算即可

40pt

我们发现,将 x 进行素因子分解,如果只能分解出一个素数 y,那么 f(x) = y。否则 f(x) = 1。

所以我们可以枚举每个素数,然后枚举它的次方,复杂度约为 O(nlogn)

100pt

我们还可以通过修改线性筛的模板来预处理每个 x 的 f(x) 值,复杂度 O(n)

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263355

T2

我们可以用 dp 进行预处理,dp[i] 代表对于询问的数字为 i 时的答案。(1 代表包含,0 代表不包含)

首先对于输入的所有数字 a[i] 可得 dp[a[i]] = 1。

然后我们倒着枚举值域,对于任意一个数字 x,如果 dp[x] = 1,那么去除其中任意一位二进制上的 1,对应的 dp 值仍为 1

用 O(nlogn) 的时间进行预处理,之后就可以 O(1) 回答每次查询了。详见代码:

for(int i = maxn; i >= 0; i--){
    for(int j = 0; j < 20; j++)//枚举去掉哪个位置的 1
        if(dp[i] && (i >> j & 1))
            dp[i-(1<<j)] = 1;
}

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263362

T3 前缀

30pt

如果t中未包含s中没有的字符,直接暴力循环匹配。否则就是-1

60pt

不处理高精度大数,用int储存出现的整数

100 pt

如果s串不循环,并且没有通配符"*",那么这个问题就是一个经典的序列自动机问题。
序列自动机其实就是一个next指针数组。它储存了每个位置跳转到下一个最近的某字符的位置。
举个例子,比如字符串"acdea"中next[1]['a']就是5。这表示从第1个位置匹配一个最近的'a'是在第5个位置。
next数组的预处理也相当简单,只要倒着for一遍记录每个字符最近的位置,然后拷贝到当前位置的next数组中即可。
比起用语言表达,可能看代码来的更快。

for(int i=n;i;i--){
    for(int j=0;j<26;++j) 
        next[i-1][j]=next[i][j];
    next[i-1][s[i]-'a']=i;
}

有了这个思路之后我们就魔改序列自动机自己造一台新的自动机。
首先解决"s串是一个无限循环串"的问题。
为了解决这个问题我们需要把原序列机的首尾相接变成环。
这个首先顺着遍历一遍查找每个字符第一次出现的位置,称为first。
将last和first接起来,然后倒着遍历求next。

然后想办法解决"*"的问题。一般来说自动机都不太能处理通配符,比如AC机和后缀机。
也不是说它们不能处理,而是"*"在其他的自动机中一般都代表26种出边。不和记忆化搜索配套使用复杂度基本接受不了。
但是序列自动机next数组的含义是能够满足匹配的下一个最近的位置,那对于i来说就是i+1嘛。

接下来想办法解决数字的问题。先假设出现的数字不是大数,比如在int范围内。
这个next指针说起来也不过就是链表结构。有线性结构的地方,就有倍增。
所以这里将链表结构改造成倍增链表

如果输入的整数是大数,倍增链表总不能无止境的倍增下去吧。对于这个地方,因为s串是一个“循环”串。
这就代表我输入单一字符进行转移的时候,自动机总是成环的。所以预处理循环节,发现对于每个字符,循环节长度就是它在原本的s串中出现的次数。
所以这里要手写一个高精度除以单精度,要同时知道商和余数。
注意最后一轮不能跑满,而是倍增过去。

也可以直接算出要跳到哪个字符,记一下每种字符第 i 个在哪,每个字符是这种的第几个,就可以直接算不用倍增

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263370

T4 移动

这个题不会输出 -1,因为在最晚 1e9 秒后,所有闸门都将开启,这时候一定可以安全走到终点。一些人没有得满分的原因就是在某些测试点中输出了 -1。

20pt

我们可以离散化之后进行动态规划 代表 i 时刻到达 j 位置是否可行(用 0/1 表示)。注意,此时的 i 不代表第 i 秒,而是离散化后的第 i 个时刻,离散化时只关注每个闸门开,关的时间,即我们会从 n 个信息提取出 2n 个时刻。

一定是从 转移过来的,我们只需要枚举 k,然后判断是否可以转移即可。但是这样复杂度是 O(n³)。

40pt

使用前缀和优化状态转移,即可优化到 O(n²)

100 pt

我们还是将时间离散化,记录每一道闸门开启的时间段以及对应的闸门编号,总共大约有 n+m 个时间段。f[i] 表示第 i 段时间内牛牛最早能在第几秒到达这一位置。(“这一位置”指的是此时间段对应的闸门编号)
转移就是牛牛往左/右走一步可以走到哪些闸门开启的时间段(就是可以先等一会再走)
用类似最短路的方法来实现 dp 的枚举。即向优先队列中塞入一个结点 Node{id,x,time} id 为时间段编号,x 为闸门编号,time 为当前时间。优先队列按照 time 排序,每次选出一个 time 最小的 Node ,向它周围的两个闸门进行转移。转移时找到对应闸门开启的时间,要同时满足当前闸门与被转移的闸门都开启才可以转移。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263389

After the contest

没想到才 4 个 ak 啊,可能是细节有点多,T3 T4 全做对不太容易

但是大家的平均得分显然比上一场高,因为 T1 T2 都很友好(有个人 11min 就连杀两题)

第一个人不到 80min 就 ak 了,真的勇,还好是 OI 赛制,大家看不到榜,所以不丢人(雾)

6条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐