前言
为期10天的第一次训练结束~ 时间好快。学到了好多知识~ 不过后缀数组还是不敢碰呀,算是这个专题的一个小遗憾吧。
A. 双剑合并
题意
从两个大小最大为1e6的数组中分别找出一个数,使得这两个数的异或和最大。
分析
- 1e6啊,暴力肯定不行了。把其中一个数组中的数字看成二进制,相当于是查找另一个数组中能把这个数中高位0位填了的数中效益最大的那个数。怎么查询呢?
- 于是我试着二分查询补码,结果:GG。
思考
- 坑点: 无。
- 技巧: 将其中一个数组建立成trie树,然后另一个数组中的数在其中查询。注意:建树要从二进制位的高位往低位建树,查询同理。这样才能保证异或和最大。
B. 单词替换
题意
将一个长度最长为5e6的字符串中的单词A替换成单词B,输出替换后的字符串。
分析
- 单词替换,kmp匹配即可。
思考
- 坑点: 使用strlen多次计算长度,可能导致TLE。
- 技巧: 在kmp匹配的时候,当模式串匹配成功后,不用退出,接着匹配。一边匹配一边输出答案。
C. 01的时间
题意
输出不超过466的正整数由0和1构成的最小倍数。
分析
- 从1开始bfs,每次优先放0,接着放1,用char来存答案。
- 没有标记,直接MLE。
思考
- 坑点: 1)本题会爆long long,但是不会爆unsigned long long。2)bfs不标记会MLE。
- 技巧: 考虑一个很长的数字(长度>100),需要问这个数能否被某个数整除,我们可以直接从左往右解析这个数字,一边解析一边取模。本题可以借鉴这种做法,将模作为状态来标记,所以整个搜索空间最多466。每次取出数字优先添加0,之后添加1即可。
D. GooZy的游戏时间
题意
将小正方形进行平移,使得最终构成一个大正方形,并且两正方形邻接的三角形上数字相同。有解输出Possible,无解Impossible。最多25个小正方形。
分析
- 暴力查找
- TLE
思考
- 坑点: 会出现24个全都相同的矩形,搜索空间爆炸。
- 技巧: 将相同的矩形预处理在一起,当前位置该矩形不行,那么其它所有和这个矩形一样的矩形也一定不能放在这个位置。
- 神之样例(还不知道怎么剪枝能过)<由fly提供>:
1
5
1 1 1 1
1 1 2 1
1 1 3 1
1 1 4 1
1 1 6 1
2 1 1 1
2 1 2 1
2 1 3 1
2 1 4 1
2 1 6 1
3 1 1 1
3 1 2 1
3 1 3 1
3 1 4 1
3 1 6 1
4 1 1 1
4 1 2 1
4 1 3 1
4 1 4 1
4 1 6 1
5 1 1 1
5 1 2 1
5 1 3 1
5 1 4 1
5 1 6 1
E. RunningPhoton's Nightmare
题意
在一个的图中,需要从S点走到E点,但是有个计时器在计时,超过()就会爆炸,中间有R点,可以重置计时器时间为0,问能否走到E点?
分析
- bfs。结构体中存放当前的位置x和y,以及走了dis的时间,另开一个全局数组dis[i][j]记录到达点(i,j)炸弹的时间。每次向炸弹时间比该处小就能转移。
思考
- 坑点: 刚开始标程神之T++,算不算坑点,23333
- 技巧: 可以预处理起始点、终点、R点的最短距离,跑一遍最短路即可。(然而我没预处理直接bfs也过了= =。)
F. 表达式
题意
初始只有x,可以用已有的值对当前值进行乘或者除,问:到达需要的最少步骤是几步?(
分析
- 贪心啊,每次倍增!嗯,就是这么搞。
- 结果是WA。
思考
- 坑点: 没有,953这个样例很友好地给了出来。
- 技巧: 迭代加深搜索,枚举深度。一个强力剪枝:当当前最大可能值在之后一直自乘,都无法到达n,就可以返回。
G. 神舟的宝藏
题意
用给定的进制和数,构成N的最小倍数。
分析
- 这不是进阶版的C题吗?
思考
- 坑点: 无。
- 技巧: 抓住状态空间,用char数组存答案。其它同C题。
H. DNA序列
题意
构造一个DNA序列,使得其子序列能够组成给出的N个DAN序列中的任意一个。()
分析
- 迭代加深试试。
- 剪枝不够强力T了。
思考
- 坑点: 剪枝不强,AAAAA,CCCCC,GGGGG,TTTTT这个样例是过不了的。
- 技巧: 首先,当某个串还差X才能构造出来,然而剩余深度小于X,那么可以肯定这之后就不用访问了,这是小剪枝。其次,用来构造的字符一定要是这N个串中所拥有的,否则加了白加,小剪枝。最后,每次统计所有串中,单串最长的A次数、C次数、G次数、T次数,他们的和就是需要构成的串至少需要的长度,这样倒着建立串,就能根据这个强力剪枝!
I. 小冰和小娜
题意
问:能否从起点到达终点,使得车轮的颜色起点和终点一样?能输出最少时间,否则-1。(车轮有五种颜色,每次转向或者前行消耗一个时间,移动一次变换一次颜色。)
分析
- bfs,开四维数组记录到达点(x,y)方向为z,颜色为c所需要的最少时间。
思考
- 坑点: 转向和前行都得消耗时间。
- 技巧: 老老实实写BFS即可。
J. TooEasy Or TooDifficult
题意
求字符串最长回文串,求区间最大异或和。
分析
- 最长回文串easy,manacher即可。异或和没想法。
思考
- 坑点: MZ的次方数好可怕,以为不能用快速幂搞定Orz。
- 技巧: 区间异或和可以转换为从0开始区间连续的异或和,变成一个值,两个这样的值异或,就是它们的非公共区间异或和了。所以我们用trie来存异或值,这样就变成了求两个数的最大异或和,套用A题思路即可。
K. 奶牛合影
题意
求长度最大为3e5的环上,哪个点开始,字典序最小。
分析
- 典型的最小表示法呀。
思考
- 坑点: 无。
- 技巧: 会最小表示法就OK啦。
M. 奶牛硬盘
题意
用1000进位和1024进位来计算内存,所少计算的百分率是多少?最大到YB。
分析
- 数字相除,数字部分没用啊,那答案不就是固定的?来来来,打表。嗯,对了,特判0。
- 标程没有特判0,所以你特判就是错的。
思考
- 坑点: 标程错了= =
- 技巧: 不打表的话,只需每次记录下1000和1024的比率,根据单位乘就能得到结果了。
N. 奶牛情书
题意
给出不多于60个单词,长度不超过100,求至少包含其中一个单词,长度为M()的文本的构造方式有多少种?
分析
- 好难= =。后来看挑战知道是字符串dp,需要自动机预处理。
- 没有考虑ABA CCCCCCABAC这种情况下,第二个字符串中包含了需要出现的串ABA,而我们的做法是:答案 = 所有可能情况 - 不可能情况,所以这里需要对fail数组处理一下。
思考
- 坑点: 串中还会包含串。
- 技巧: 用自动机预处理每个前缀能够到达的转移,在构建fail数组时,如果当前字符串的fail是禁止串,那么当前串也要标为禁止串。然后 ; (nxt[j][k]即:第j个前缀加上第k个字符后能够转移到的前缀)
具体代码点击下方传送门:)
广告时间