CQU&SCU Union Training I - Searching and Strings

前言

为期10天的第一次训练结束~ 时间好快。学到了好多知识~ 不过后缀数组还是不敢碰呀,算是这个专题的一个小遗憾吧。


A. 双剑合并

题意

从两个大小最大为1e6的数组中分别找出一个数,使得这两个数的异或和最大。

分析

  1. 1e6啊,暴力肯定不行了。把其中一个数组中的数字看成二进制,相当于是查找另一个数组中能把这个数中高位0位填了的数中效益最大的那个数。怎么查询呢?
  2. 于是我试着二分查询补码,结果:GG。

思考

  1. 坑点: 无。
  2. 技巧: 将其中一个数组建立成trie树,然后另一个数组中的数在其中查询。注意:建树要从二进制位的高位往低位建树,查询同理。这样才能保证异或和最大。

B. 单词替换

题意

将一个长度最长为5e6的字符串中的单词A替换成单词B,输出替换后的字符串。

分析

  1. 单词替换,kmp匹配即可。

思考

  1. 坑点: 使用strlen多次计算长度,可能导致TLE。
  2. 技巧: 在kmp匹配的时候,当模式串匹配成功后,不用退出,接着匹配。一边匹配一边输出答案。

C. 01的时间

题意

输出不超过466的正整数由0和1构成的最小倍数。

分析

  1. 从1开始bfs,每次优先放0,接着放1,用char来存答案。
  2. 没有标记,直接MLE。

思考

  1. 坑点: 1)本题会爆long long,但是不会爆unsigned long long。2)bfs不标记会MLE。
  2. 技巧: 考虑一个很长的数字(长度>100),需要问这个数能否被某个数整除,我们可以直接从左往右解析这个数字,一边解析一边取模。本题可以借鉴这种做法,将模作为状态来标记,所以整个搜索空间最多466。每次取出数字优先添加0,之后添加1即可。

D. GooZy的游戏时间

题意

将小正方形进行平移,使得最终构成一个大正方形,并且两正方形邻接的三角形上数字相同。有解输出Possible,无解Impossible。最多25个小正方形。

分析

  1. 暴力查找
  2. TLE

思考

  1. 坑点: 会出现24个全都相同的矩形,搜索空间爆炸。
  2. 技巧: 将相同的矩形预处理在一起,当前位置该矩形不行,那么其它所有和这个矩形一样的矩形也一定不能放在这个位置。
  3. 神之样例(还不知道怎么剪枝能过)<由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

题意

在一个$600 \times 600$的图中,需要从S点走到E点,但是有个计时器在计时,超过($\geq k$)就会爆炸,中间有R点,可以重置计时器时间为0,问能否走到E点?

分析

  1. bfs。结构体中存放当前的位置x和y,以及走了dis的时间,另开一个全局数组dis[i][j]记录到达点(i,j)炸弹的时间。每次向炸弹时间比该处小就能转移。

思考

  1. 坑点: 刚开始标程神之T++,算不算坑点,23333
  2. 技巧: 可以预处理起始点、终点、R点的最短距离,跑一遍最短路即可。(然而我没预处理直接bfs也过了= =。)

F. 表达式

题意

初始只有x,可以用已有的值对当前值进行乘或者除,问:到达$x^n$需要的最少步骤是几步?($n \leq 1000)$

分析

  1. 贪心啊,每次倍增!嗯,就是这么搞。
  2. 结果是WA。

思考

  1. 坑点: 没有,953这个样例很友好地给了出来。
  2. 技巧: 迭代加深搜索,枚举深度。一个强力剪枝:当当前最大可能值在之后一直自乘,都无法到达n,就可以返回。

G. 神舟的宝藏

题意

用给定的进制和数,构成N的最小倍数。

分析

  1. 这不是进阶版的C题吗?

思考

  1. 坑点: 无。
  2. 技巧: 抓住状态空间,用char数组存答案。其它同C题。

H. DNA序列

题意

构造一个DNA序列,使得其子序列能够组成给出的N个DAN序列中的任意一个。($N \leq 8, 长度 \leq 5$)

分析

  1. 迭代加深试试。
  2. 剪枝不够强力T了。

思考

  1. 坑点: 剪枝不强,AAAAA,CCCCC,GGGGG,TTTTT这个样例是过不了的。
  2. 技巧: 首先,当某个串还差X才能构造出来,然而剩余深度小于X,那么可以肯定这之后就不用访问了,这是小剪枝。其次,用来构造的字符一定要是这N个串中所拥有的,否则加了白加,小剪枝。最后,每次统计所有串中,单串最长的A次数、C次数、G次数、T次数,他们的和就是需要构成的串至少需要的长度,这样倒着建立串,就能根据这个强力剪枝!

I. 小冰和小娜

题意

问:能否从起点到达终点,使得车轮的颜色起点和终点一样?能输出最少时间,否则-1。(车轮有五种颜色,每次转向或者前行消耗一个时间,移动一次变换一次颜色。)

分析

  1. bfs,开四维数组记录到达点(x,y)方向为z,颜色为c所需要的最少时间。

思考

  1. 坑点: 转向和前行都得消耗时间。
  2. 技巧: 老老实实写BFS即可。

J. TooEasy Or TooDifficult

题意

求字符串最长回文串,求区间最大异或和。

分析

  1. 最长回文串easy,manacher即可。异或和没想法。

思考

  1. 坑点: MZ的次方数好可怕,以为不能用快速幂搞定Orz。
  2. 技巧: 区间异或和可以转换为从0开始区间连续的异或和,变成一个值,两个这样的值异或,就是它们的非公共区间异或和了。所以我们用trie来存异或值,这样就变成了求两个数的最大异或和,套用A题思路即可。

K. 奶牛合影

题意

求长度最大为3e5的环上,哪个点开始,字典序最小。

分析

  1. 典型的最小表示法呀。

思考

  1. 坑点: 无。
  2. 技巧: 会最小表示法就OK啦。

M. 奶牛硬盘

题意

用1000进位和1024进位来计算内存,所少计算的百分率是多少?最大到YB。

分析

  1. 数字相除,数字部分没用啊,那答案不就是固定的?来来来,打表。嗯,对了,特判0。
  2. 标程没有特判0,所以你特判就是错的。

思考

  1. 坑点: 标程错了= =
  2. 技巧: 不打表的话,只需每次记录下1000和1024的比率,根据单位乘就能得到结果了。

N. 奶牛情书

题意

给出不多于60个单词,长度不超过100,求至少包含其中一个单词,长度为M($M \leq 100$)的文本的构造方式有多少种?

分析

  1. 好难= =。后来看挑战知道是字符串dp,需要自动机预处理。
  2. 没有考虑ABA CCCCCCABAC这种情况下,第二个字符串中包含了需要出现的串ABA,而我们的做法是:答案 = 所有可能情况 - 不可能情况,所以这里需要对fail数组处理一下。

思考

  1. 坑点: 串中还会包含串。
  2. 技巧: 用自动机预处理每个前缀能够到达的转移,在构建fail数组时,如果当前字符串的fail是禁止串,那么当前串也要标为禁止串。然后$dp[i + 1][nxt[j][k]] = dp[i][j]$ ; (nxt[j][k]即:第j个前缀加上第k个字符后能够转移到的前缀)

具体代码点击下方传送门:)

传送门


广告时间

Java学习网站: how2j

VPS: VPS

梦想世界上每个人都能给我一元钱,2333