A. Oulipo
Description
给出两个字符串 s1,s2（只有大写字母），求 s1 在 s2 中出现多少次。例如：s1="ABA",s2="ABAABA",答案为 2。
解题思路：
KMP 算法的模板，也可以用拓展 KMP 解决。
代码示例：
#include<cstring>
#include<cstdio>
const int N = 1e6+10;
int nex[N]; //nex[i] = T[i,n-1]与T[0,n-1]最长公共前缀
char S[N],T[N]; //S为目标串,T为模式串
int extend[N];
void getNex(char* str){
/*计算nex数组*/
int len = strlen(str) ,i = 0, j, p0 ;
nex[0] = len;
while(i+1 < len && str[i] == str[i+1]) i++;
nex[1] = i; p0 = 1;
for(int i = 2;i < len;i++){
if(nex[i-p0]+i < nex[p0]+p0) nex[i] = nex[i-p0];
else {
j = nex[p0]+p0-i;
if(j < 0) j = 0;
while(i+j < len && str[j] == str[j+i]) j++;
nex[i] = j; p0 = i;
}
}
}
void exKMP(char* str1,char *str2){
/*计算str2与str1的所有后缀的最长公共前缀长度,存放在extend数组中*/
int i = 0,j,p0,l1 = strlen(S), l2 = strlen(T);
getNex(str2);
while(i < l1 && i < l2 && str1[i] == str2[i]) i++;
extend[0] = i;p0 = 0;
for(int i = 1;i < l1;i++){
if(nex[i-p0]+i < extend[p0]+p0) extend[i] = nex[i-p0];
else{
j = extend[p0]+p0-i;
if(j < 0) j = 0;
while(i+j < l1 && j < l2 && str1[j+i] == str2[j]) j++;
extend[i] = j; p0 = i;
}
}
}
int solve(){
/*计算并输出答案*/
int l1 = strlen(S), l2 = strlen(T), ans = 0;
exKMP(S,T); int len = strlen(T);
for(int i = 0;i < l1;i++)
if(extend[i] == len) ans++;
return ans;
}
int t;
int main(){
scanf("%d",&t);
while(t--){
scanf("%s%s",T,S);
printf("%d\n",solve());
}
return 0;
}
B. 图书管理
Description
图书管理是一件十分繁杂的工作，在一个图书馆中每天都会有许多新书加入。为了更方便的管理图书（以便于帮助想要借书的客人快速查找他们是否有他们所需要的书），我们需要设计一个图书查找系统。该系统需要支持 2 种操作：
- add(s) 表示新加入一本书名为 s 的图书。
- find(s) 表示查询是否存在一本书名为 s 的图书。
解题思路：
该题本意是用 hash 解决，但是我偷懒直接用 map 了。。。
代码示例：
#include<bits/stdc++.h>
using namespace std;
map<string ,int> mp;
string str;
int n;
void add(string s){
string tmp = "";
for(int i = 4;s[i];i++) tmp += s[i];
mp[tmp] = 1;
}
void Find(string s){
string tmp = "";
for(int i = 5;s[i];i++) tmp += s[i];
if(mp.count(tmp)) cout << "yes" << endl;
else cout << "no" << endl;
}
int main(){
scanf("%d",&n);
getchar();
for(int i = 1;i <= n;i++){
getline(cin,str);
if(str[0] == 'a') add(str);
else Find(str);
}
return 0;
}
C. Power Strings
Description
给定若干个长度 ≤10^6 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3 个 ab 连接而成。
解题思路：
本题是循环节问题，有个结论：若字符串 s 是由某个长度为 x 的子串循环构成，那么必定有 s[1,n-x] = s[x, n]。而根据 nex 数组的定义，nex[n] 就是 s[x, n] 的长度 n-x。
因此如果该题有解，则 n % (n-nex[n])为 0，答案就是 n/(n-nex[n)。
代码示例：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6+10;
char str[N];
int nex[N];
void getNex(char* str){
memset(nex,0,sizeof nex);
for(int i = 2,j = 0;str[i];i++){
while(j > 0 && str[i] != str[j+1]) j = nex[j];
if(str[i] == str[j+1]) j++;
nex[i] = j;
}
}
void solve(){
/*计算答案并输出*/
getNex(str);
int n = strlen(str)-1;
if(n%(n-nex[n])) puts("1");
else printf("%d\n",n/(n-nex[n]));
}
int main(){
while(scanf("%s",str+1) && str[1] != '.'){
str[0] = '*';
solve();
}
return 0;
}
D. Seek the Name, Seek the Fame
Description
给定若干字符串（这些字符串总长 ≤4×10^5 ），在每个字符串中求出所有既是前缀又是后缀的子串长度。例如：ababcababababcabab，既是前缀又是后缀的：ab，abab，ababcabab，ababcababababcabab。
解题思路：
依然是利用 KMP 算法中的 nex 数组求解。首先该串本身是最长的“既是前缀又是后缀”的子串，下一个满足条件的子串是 s[1,nex[n] ] ，下下个是 s[1, nex[ nex[n] ] ]，... 。
道理很简单，就是想起来有点绕；如果存在一个长度为 x 的子串 son“既是前缀又是后缀”，那么有 s[1,x] = s[n-x,n] = son，那么它的长度不还是不超过 nex[n] 吗？所以上述方法可以从大到小遍历所有可能的长度（不是所有子串！）。
代码示例：
#include<cstdio>
#include<set>
#include<cstring>
using namespace std;
const int N = 4e5+10;
char str[N];
int nex[N];
void getNex(char *s){
memset(nex,0,sizeof nex);
int len = strlen(s);
for(int i = 2,j = 0;i < len;i++){
while(j > 0 && s[i] != s[j+1]) j = nex[j];
if(s[i] == s[j+1]) j++;
nex[i] = j;
}
}
int ans[N];
void solve(){
getNex(str); int n = strlen(str)-1;
int cnt = 0; ans[++cnt] = n;
while(nex[n]){
ans[++cnt] = nex[n];
n = nex[n];
}
for(int i = cnt;i > 1;i--) printf("%d ",ans[i]);
printf("%d\n",ans[1]);
}
int main(){
//freopen("123.txt","r",stdin);
while(~scanf("%s",str+1)){
str[0] = '#';
solve();
}
return 0;
}
E. friends
Description
有三个好朋友喜欢在一起玩游戏，A 君写下一个字符串 S，B 君将其复制一遍得到 T，C 君在 T 的任意位置（包括首尾）插入一个字符得到 U。现在你得到了 U，请你找出 S。
解题思路：
本题如果用 nex 或者 hash 求解，细节有点多，当然细心点应该是能写出来的。我的解题思路很简单，O(N)复杂度，主要基于如下基本推论：
- 如果 n 为偶数，无解。
- 如果前 n/2+1 个字符通过删去一个，可以等同于后 n/2 个字符，则匹配成功。
- 如果后 n/2+1 个字符通过删去一个，可以等同于前 n/2 个字符，则匹配成功。
- 如果 2 和 3 都匹配成功，且两个得到的原串不同，则说明解不唯一。
代码示例：
#include<cstdio>
#include<cstring>
const int N = 2e6+10;
char str[N],tmp[N],s1[N],s2[N];
int n,nex[N],tot;
char ans1[N],ans2[N];
bool check(char *s1,char *s2){
tot = 0; bool flag = false;
int i = 1,j = 1;
while(i <= n/2 && j <= n/2+1){
if(s1[i] != s2[j]){
if(flag) return false;
flag = true; j++;
if(s1[i] != s2[j]) return false;
}
tmp[tot++] = s1[i];
i++ , j++;
}
tmp[tot] = '\0';
return true;
}
void solve(){
if(n%2 == 0){
puts("NOT POSSIBLE"); return;
}
for(int i = 1;i <= n/2;i++) s1[i] = str[i];
for(int i = 1;i <= n/2+1;i++) s2[i] = str[i+n/2];
bool flag1,flag2;
flag1 = check(s1,s2);
for(int i = 0;i <= n/2;i++) ans1[i] = tmp[i];
for(int i = 1;i <= n/2+1;i++) s1[i] = str[i];
for(int i = 1;i <= n/2;i++) s2[i] = str[i+n/2+1];
flag2 = check(s2,s1);
for(int i = 0;i <= n/2;i++) ans2[i] = tmp[i];
if(flag1 && flag2){
bool f = true;
for(int i = 1;i <= n/2;i++)
if(ans1[i] != ans2[i]) f = false;
if(!f){
puts("NOT UNIQUE"); return;
}
}
if(flag1 || flag2){
if(flag1) puts(ans1);
else puts(ans2);
return;
}
puts("NOT POSSIBLE");
}
int main(){
scanf("%d%s",&n,str+1);
str[0] = '#'; solve();
return 0;
}
F. A Horrible Poem
Description
给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。
解题思路：
这个是最短循环节问题，另外本题卡常十分严格。为了快速求解，本题还用到了线性筛、滚动哈希优化等策略。
首先是基础的字符串循环节知识。如果字符串 s 是由某个子串循环得到，|s| = n，那么
循环节的长度一定是 len 的约数，包括最短循环节。因此一个策略就是对于 n 的所有约数，挨个判断是否为最短循环节的长度，而判断原理如下：
- 如果字符串 s 的最短循环节长度为 x ，那么必然有 s[1, x] = s[n-x, n] 。
我们可以通过滚动哈希技巧来在 O(1)时间完成判断。那么现在主要花费的时间在于找寻 n 的约数上，一般做法，于是这种做法总复杂度为。
但是这题卡常很严重，这样还是会超时。于是就要利用质因数分解定理在时间内完成约数分解，总时间复杂度为。
代码示例：
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 5e5+10;
const int Q = 2e6+10;
char str[N];
int n,q;
typedef unsigned long long ull;
ull hsh[N],bse[N] , b = 31; //采用无符号长整形,通过自然溢出省去取模
bool check(int l,int r,int x){
/*判断x是否为子串s[l,r]的最短循环节长度*/
ull h1 = hsh[r-x] - hsh[l-1]*bse[r-x+1-l];
ull h2 = hsh[r] - hsh[l-1+x]*bse[r-x+1-l];
return h1 == h2;
}
int v[N],primes[N];
void getPri(){ //线性筛
int cnt = 0;
for(int i = 2;i <= n;i++){
if(!v[i]){
primes[cnt++] = i;
v[i] = i;
}
for(int j = 0;j < cnt;j++){
if(primes[j] > v[i] || primes[j]*i > N)
break;
v[i*primes[j]] = primes[j];
}
}
}
void ask(int l,int r){
/*回答子串s[l,r]的最短循环节长度*/
int len = r-l+1, ans = len, d = len;
while(d != 1){
int tmp = v[d];
while(d%tmp == 0 && check(l,r,ans/tmp)) d /= tmp,ans /= tmp;
while(d%tmp == 0) d /= tmp;
}
printf("%d\n",ans);
}
void solve(){
/*预处理出hash数组,v数组*/
getPri(); bse[0] = 1;
for(int i = 1;i <= n;i++){
hsh[i] = hsh[i-1]*b + str[i]-'a';
bse[i] = bse[i-1]*b;
}
}
inline int read() {
int x=0,f=1; char c=getchar();
while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); }
while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); }
return x*f;
}
int main(){
n = read();
scanf("%s",str+1); str[0] = '#';
q = read();
solve();
for(int i = 1,l,r;i <= q;i++){
l = read(); r = read();
ask(l,r);
}
return 0;
}
G. Beads
Description
Zxl 有一次决定制造一条项链，她以非常便宜的价格买了一长条鲜艳的珊瑚珠子，她现在也有一个机器，能把这条珠子切成很多块（子串），每块有 k（k>0）个珠子，如果这条珠子的长度不是 k 的倍数，最后一块小于 k 的就不要拉（nc 真浪费），保证珠子的长度为正整数。 Zxl 喜欢多样的项链，为她应该怎样选择数字 k 来尽可能得到更多的不同的子串感到好奇，子串都是可以反转的，换句话说，子串（1，2，3）和（3,2,1）是一样的。写一个程序，为 Zxl 决定最适合的 k 从而获得最多不同的子串。例如：这一串珠子是： (1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1)。
k=1 的时候，我们得到 3 个不同的子串：(1),(2),(3)
k=2 的时候，我们得到 6 个不同的子串： (1,1),(1,2),(2,2),(3,3),(3,1),(2,3)
k=3 的时候，我们得到 5 个不同的子串： (1,1,1),(2,2,2),(3,3,3),(1,2,3),(3,1,2)
k=4 的时候，我们得到 5 个不同的子串： (1,1,1,2),(2,2,3,3),(3,1,2,3),(3,1,2,2),(1,3,3,2)
解题思路：
刚开始时间复杂度算错了，n + n/2 + n/3 + n/4 + ... + 1 是调和级数，时间复杂度并不高，因此两层循环加上 滚动哈希 O(1)的判断是可以很快通过的。
代码示例：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
typedef unsigned long long ull;
int col[N] , n;
ull hsh[N],hsh2[N],bse[N] , B = 1e9+7;
map<ull,int> vis;
vector<int> ans;
int tc , mx , k;
void solve(){
bse[0] = 1; int cnt = 0;
for(int i = 1;i <= n;i++)
hsh[i] = hsh[i-1]*B+col[i], bse[i] = bse[i-1]*B;
for(int i = n;i >= 1;i--)
hsh2[i] = hsh2[i+1]*B+col[i];
for(int i = 1;i <= n;i++){
vis.clear(); cnt = 0;
for(int j = i;j <= n;j += i){
ull h1 = hsh[j] - hsh[j-i]*bse[i];
ull h2 = hsh2[j-i+1] - hsh2[j+1]*bse[i];
if(vis.count(h1*h2) == 0){
vis[h1*h2] = 1; cnt++;
}
//printf("%llu %llu\n",h1,h2);
}
//printf("%d %d\n",cnt,mx);
if(cnt == mx) ans.push_back(i);
else if(cnt > mx) {
ans.clear(); ans.push_back(i); mx = cnt;
}
}
printf("%d %d\n",mx,ans.size());
for(int i = 0;i < ans.size();i++) printf("%d ",ans[i]);
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",col+i);
solve();
return 0;
}
H. Antisymmetry
Description
对于一个 01 字符串，如果将这个字符串 0 和 1 取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如 00001111 和 010101 就是反对称的，1001 就不是。
现在给出一个长度为 N 的 01 字符串，求它有多少个子串是反对称的。
解题思路：
01 串的题目真是变化多端啊。要想解决本题首先要得出几个推论：
- “反对称”的串长度一定是偶数。
- 如果一个子串是“反对称”的，那么它一定关于中轴线，左右 01 对应（如 0101）。
- 如果一个串是“反对称”的，那么和它共中轴线的子串也是“反对称”的。
然后就发现和回文串的性质有些相似，仅有 2 点不同，就是回文串长度可以为奇，以及回文串是关于中轴对称而不是相反。
那么我们依然可以利用 Manacher 算法，只不过将判等 改为判“反”即可。当然也要用通配符“#”来填充，因为所有“反对称” 的串长度必须为偶，所以我们在“#”上进行计算，以此来保证长度为偶数。
代码示例：
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
char str[N],s2[2*N];
int n,len[2*N];
bool check(char a,char b){
if(a == '#' && b == '#') return true;
if(a == '1' && b == '0') return true;
if(a == '0' && b == '1') return true;
return false;
}
void solve(){
s2[0] = '$',s2[1] = '#';
for(int i = 1;i <= n;i++){
s2[i<<1] = str[i-1];
s2[(i<<1)+1] = '#';
}
s2[n*2+2] = '\0';
int mx = 0, mid;
for(int i = 1;i < 2*n+2;i += 2){
if(i < mx) len[i] = min(len[2*mid-i],mx-i);
else len[i] = 1;
while( check(s2[i-len[i]], s2[i+len[i]]) ) len[i]++;
if(len[i]+i > mx){
mx = len[i] + i;
mid = i;
}
}
long long ans = 0;
for(int i = 1;i < 2*n+2;i++) ans += len[i]>>1;
printf("%lld\n",ans);
}
int main(){
//freopen("123.txt","r",stdin);
scanf("%d",&n);
scanf("%s",str);
solve();
return 0;
}
I. 门票(tickets)
Description
已知数列, ，请问给定 A，B 和 C，该数列在第几项第一次出现重复？
解题思路：
map 太慢了啊，我测试了读入输出，测试了乘法和取模，就是没有怀疑 map，浪费很多时间。
手写 hash 函数，利用邻接表来消除冲突，如此一来快了很多。
代码示例：
#include<cstdio>
#include<cmath>
typedef long long ll;
const int N = 2181271;
ll a,b,c;
double A;
struct Node{
ll dat;
Node* nex;
Node(ll dat):dat(dat){nex = NULL;}
Node(){ nex = NULL; }
}head[N];
bool check(ll x){
int h = x%N;
//printf("%d %lld\n",h,x);
Node* p = head[h].nex;
while(p != NULL){
//printf("%lld\n",p->dat);
if(p->dat == x) return true;
p = p->nex;
}
return false;
}
void Add(ll x){
int h = x%N;
// printf("%d %lld\n",h,x);
Node* p = head[h].nex;
Node *q = &head[h];
while(p != NULL) q = p,p = p->nex;
q->nex = new Node(x);
//printf("%lld\n",p->dat);
}
void solve(){
ll res = 1; Add(res);
for(int i = 1;i < 2e6;i++){
res = (res*a+res%b)%c;
if(check(res)){
printf("%d\n",i); return;
}
Add(res);
}
puts("-1");
return;
}
int main(){
//freopen("123.txt","r",stdin);
scanf("%lld%lld%lld",&a,&b,&c);
solve();
return 0;
}
J. 收集雪花(snowflakes)
Description
不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来，作为礼物送给在南方的同学们。一共有 n 个时刻，给出每个时刻下落雪花的形状，用不同的整数表示不同的形状。在收集的过程中，同学们不希望有重复的雪花。你可以从任意 a 时刻开始，在 b 时刻停止。a 到 b 时刻中间的雪花也都将被收集。他们希望收集的雪花最多。
解题思路：
这个用 hash 有点难写，难在重置哈希表。我用的是离散化 + 双指针，只需要维护左边界即可。如果当前雪花第二次出现，那么知道它上一次出现位置是 v[p] ，所以先用当前区间长度更新答案，再将左边界更新为 v[p] + 1。
正确性证明就不写了，很显然。
代码示例：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int a[N], b[N], n, v[N];
int main(){
//freopen("123.txt","r",stdin);
scanf("%d",&n);
for(int i = 1;i <= n;i++) scanf("%d",a+i),b[i] = a[i];
sort(a+1,a+1+n);
int tot = unique(a+1,a+1+n)-a-1;
int ans = 0,l = 1;
for(int i = 1;i <= n;i++){
int p = lower_bound(a+1,a+tot+1,b[i])-a;
if(v[p] >= l){
ans = max(ans,i-l);
l = v[p]+1;
}
v[p] = i;
if(i == n) ans = max(ans,i-l+1);
}
printf("%d\n",ans);
return 0;
}
欢迎来到这里！
我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。
注册 关于