20221005
简单点
题目背景
今天有个巨佬不讲题德，出了个题，说他是乱出的水题。
他出的可不是水题啊，Trie树，后缀树，AC自动机，训练有素；后来听说他打了三年NOI，看来是，
有备而来。
题目描述
有一个非常 easy 的字符串\(S\)，\(S\)由四种字符e，a，s，y组成。\(S\)的下标从1开始。
接下来有\(m\)组询问，每组询问会给出一个区间\([l,r]\)，代表\(S\)的子串\(S_{L,R}\)。询问你这个子串的简单程
度。
一个字符串\(T\)的简单程度是如下定义的：
如果\(T\)存在这样的子序列：该序列由"easy"反复出现 次拼接而成。那么，\(T\)中所有此满足条件的子
序列的最大\(k\)值就是\(T\)的简单程度。
例如：字符串"eeaasey"的简单程度就是1，"eaeasyeasyea"的简单程度是2。
对于字符串的子序列的定义：是从字符串中选择任意字符，在不改变相对位置的情况下拼接而得到的
序列。
输入格式
第一行，一个字符串\(S\)。
第一行，一个正整数\(m\)。
接下来\(m\)行，每行两个正整数\(l,r\)，代表询问的子串。
输出格式
对于每组询问，输出子串的简单程度。
样例 #1
样例输入 #1
easy
3
1 4
2 4
1 3
样例输出 #1
1
0
0
样例 #2
样例输入 #2
eeaseyaesasyy
4
1 13
2 12
2 10
3 11
样例输出 #2
2
2
1
0
提示
【数据范围】
对于25%的数据，满足\(|S|,m\le2\times10^{3}\)
对于70%的数据，满足\(|S|,m\le5\times10^{4}\)
对于100%的数据，满足\(|S|\le10^{5},m\le3\times10^{5}\)
时间限制1.00s
内存限制512.00MB
树上异或
题目背景
George有一棵含有 个结点的树，树上每个点有一个非负整数权值\(w_{i}\)。
题目描述
但是George忘记树上每个点的权值了，他只记得第\(i\)个结点的\(w_{i}\)在一个区间\([l_{i},r_{i}]\)范围内。
此外，他还记得每树上每对相邻结点的异或值，并记在了这对结点的边上。
现在，他想知道，这棵树有多少种不同的\({w_{i}}\)序列能满足上述限制。
输入格式
第一行，一个正整数\(n\)。
接下来\(n\)行，第\(i\)行有两个整数\(l_{i},r_{i}\)。
接下来\(n-1\)行，每行三个整数\(u,v,w_{u}\bigoplus w_{v}\)。表示在树上的点\(u,v\)之间有一条边，以及\(u,v\)点上的权值的异或值。
输出格式
输出一行，一个整数，表示答案。
样例 #1
样例输入 #1
4
0 7
1 6
2 5
3 4
1 2 0
1 3 7
2 4 6
样例输出 #1
2
提示
对 10% 的数据，满足\(0\le l_{i},r_{i},n\le10^{3}\)
对 30% 的数据，满足\(n\le10^{4}\)
另有 20% 的数据，满足\(l_{i},r{i}\)是\(2\)的整数次幂
对 100% 的数据，满足\(n\le10^{5},0\le l_{i},r_{i},w_{i}\bigoplus w_{v}<2^{30}\)
时间限制2.00s
内存限制256.00MB
循环同构串
题目背景
因为题目简单，同学们开开心心的研究起了字符串的性质。
题目描述
如果将字符串\(S=s_{1},s_{2}...s_{n}\)的所有字符左移一位，然后让第一位字符移动到最后一位，即构成新的
字符串：\(S'=s_{2},s_{3}...s_{n},s_{1}\)。这个操作称为字符串的左移。
比如字符串\(orz\)左移一次得到字符串\(rzo\)。
若\(S\)串能够通过若干次左移之后变成\(T\)串，我们就称\(S\)和\(T\)循环同构，
现在给你一个长度为\(n\)的字符串\(S\)，询问字符串\(S\)是否满足以下条件：
- 存在一个整数\(k>1\)，满足\(k\)是\(n\)的因数。
- 将\(S\)分成\(k\)段子串，每段等长，长度为\(\frac{n}{k}\)。
- 存在一个字符串\(T\)，与上述的\(k\)段子串都循环同构。
如果存在\(k,T\)满足上述三个条件，那么就输出 Yes ，否则输出 No 。
输入格式
一行，一个整数\(t\)，表示有\(t\)组数据。
对于每组数据，输入两行：
第一行，一个整数\(n\)，表示字符串长度。
第二行，一个长度为\(n\)的字符串。
输出格式
对于每组数据，输出对应的 Yes 或者 No
样例 #1
样例输入 #1
6
1
a
2
aa
3
aab
4
abba
6
abcbcc
8
aaaaaaaa
样例输出 #1
No
Yes
No
Yes
No
Yes
提示
【数据范围】：
对20%的数据满足，\(n\le100\)
对40%的数据满足，\(n\le1000\)
对100%的数据满足，\(n\le5\times10^{6},t\le20\)
字符串仅由小写字母组成。
保证单个输入文件的大小不超过4Mb
数据可能还有更细致的梯度。
时间限制2.00s
内存限制512.00MB
标签：20221005,输出,样例,满足,字符串,数据,输入 From： https://www.cnblogs.com/thanktothelights/p/16756365.html