10.23字符串专题解题报告

1.幸运序列

因为循环的情况只有一个

就是447->474->447->474…

所以特判一下 O(n)扫一遍即可

代码：

// <lucky.cpp> - 10/23/15 08:20:46
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')getchar(),fh=-1;
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
int main(){
	freopen("lucky.in","r",stdin);
	freopen("lucky.out","w",stdout);
	int n=getint(),k=getint(),a[100002];
	for(int i=1;i<=n;i++)scanf("%1d",&a[i]);
	for(int i=1;i<=n&&k;i++){
		if(a[i]==4&&a[i+1]==7){
			if(i&1)a[i+1]=a[i],k--;
			else{
				if(a[i-1]==4){
					if(k&1)a[i]=7;
					break;
				}
				a[i]=a[i+1];k--;
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<a[i];
	return 0;
}

// <lucky.cpp> - 10/23/15 08:20:46

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')getchar(),fh=-1;

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

int main(){

freopen("lucky.in","r",stdin);

freopen("lucky.out","w",stdout);

int n=getint(),k=getint(),a[100002];

for(int i=1;i<=n;i++)scanf("%1d",&a[i]);

for(int i=1;i<=n&&k;i++){

if(a[i]==4&&a[i+1]==7){

if(i&1)a[i+1]=a[i],k--;

else{

if(a[i-1]==4){

if(k&1)a[i]=7;

break;

}

a[i]=a[i+1];k--;

}

for(int i=1;i<=n;i++)cout<<a[i];

return 0;

}

2. 無名

F**K THIS STUPID STRING HASH

一开始用的trie树存但是超时了

然后按正解的字符串hash来

然后调了一个晚上

TMD

再也不相信什么hash碰撞率低了

题解：

首先O(n^2)求出所有原串中前缀和后缀的位置

然后枚举各个前缀后缀组合

找到一个就hash标记

之后发现一样的就跳过

代码：

// <noname.cpp> - 10/23/15 08:20:46
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <map>
#include <set> 
using namespace std;
typedef long long lol;
const long long MOD=1000000097ll;
const long long SD=173ll;

int getint(){
	int res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch = getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return res;
}
long long pow(long long a,int b){
	long long ans=1;
	while(b!=0){
		if(b&1)ans=ans*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ans;
}
map <long long,bool> h;
char s[2001],a[2001],b[2001];
bool pre[2001],sub[2001];
int ls,la,lb,ans;
lol hash[2002];
int main(){
	freopen("noname.in","r",stdin);
	freopen("noname.out","w",stdout);
	scanf("%s",s);scanf("%s",a);scanf("%s",b);
	ls=strlen(s);la=strlen(a);lb=strlen(b);
	for(int i=0;i<ls-la+1;i++){
		int j;
		for(j=0;j<la&&s[i+j]==a[j];j++);
		if(j==la)pre[i]=1;
	}
	for(int i=ls-lb;i>=0;i--){
		int j;
		for(j=0;j<lb&&s[i+j]==b[j];j++);
		if(j==lb)sub[i]=1;
	}
	hash[0]=0;
	hash[1]=s[0]-'a'+1;
	for(int i=2;i<=ls;i++)hash[i]=(hash[i-1]*SD+s[i-1]-'a'+1)%MOD;
	for(int i=0;i<ls-la+1;i++)
		if(pre[i])
			for(int j=i+max(0,la-lb);j<=ls-lb;j++){ 
				int l=i+1,r=j+lb-1+1,ha=(hash[r]-hash[l-1]*pow(SD,r-l+1)%MOD+MOD)%MOD;
				if(sub[j]&&!h[ha]){
					h[ha]=1;
					ans++;
				}
			} 
	cout<<ans<<endl;
	return 0;
}

// <noname.cpp> - 10/23/15 08:20:46

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <ctime>

#include <map>

#include <set>

using namespace std;

typedef long long lol;

const long long MOD=1000000097ll;

const long long SD=173ll;

int getint(){

int res=0;

char ch=getchar();

while(ch<'0'||ch>'9')ch = getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return res;

}

long long pow(long long a,int b){

long long ans=1;

while(b!=0){

if(b&1)ans=ans*a%MOD;

a=a*a%MOD;

b>>=1;

}

return ans;

}

map <long long,bool> h;

char s[2001],a[2001],b[2001];

bool pre[2001],sub[2001];

int ls,la,lb,ans;

lol hash[2002];

int main(){

freopen("noname.in","r",stdin);

freopen("noname.out","w",stdout);

scanf("%s",s);scanf("%s",a);scanf("%s",b);

ls=strlen(s);la=strlen(a);lb=strlen(b);

for(int i=0;i<ls-la+1;i++){

int j;

for(j=0;j<la&&s[i+j]==a[j];j++);

if(j==la)pre[i]=1;

}

for(int i=ls-lb;i>=0;i--){

int j;

for(j=0;j<lb&&s[i+j]==b[j];j++);

if(j==lb)sub[i]=1;

}

hash[0]=0;

hash[1]=s[0]-'a'+1;

for(int i=2;i<=ls;i++)hash[i]=(hash[i-1]*SD+s[i-1]-'a'+1)%MOD;

for(int i=0;i<ls-la+1;i++)

if(pre[i])

for(int j=i+max(0,la-lb);j<=ls-lb;j++){

int l=i+1,r=j+lb-1+1,ha=(hash[r]-hash[l-1]*pow(SD,r-l+1)%MOD+MOD)%MOD;

if(sub[j]&&!h[ha]){

h[ha]=1;

ans++;

}

cout<<ans<<endl;

return 0;

}

3.字符串转换

这道题本来是打的暴力想骗点分的结果莫名A掉了

呵呵

枚举就好了

代码：

// <trans.cpp> - 10/23/15 08:20:46
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch = getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return res;
}
char a[1000002],b[1000002];
int la,lb;
bool src3(int w,int p){
	for(int i=0;i<w;i++)if(a[la-i-1]!=b[i+p])return 0;
	return 1;
}
void src2(int i,int p){
	if(src3(la-p-i,i)){cout<<p-1<<" "<<p+i;exit(0);}
	if(p+i==la)return;
	if(b[i]==a[i+p])src2(i+1,p);
}
void src1(int i){
	if(i==la-1)return;
	if(a[i]==b[la-1-i])src1(i+1);
	src2(0,i+1);
} 
int main(){
	freopen("trans.in","r",stdin);
	freopen("trans.out","w",stdout);
	cin.getline(a,1000001);
	cin.getline(b,1000001);
	la=strlen(a);lb=strlen(b);
	if(la!=lb){cout<<"-1 -1";return 0;}
	src1(0);
	cout<<"-1 -1";
	return 0;
}

// <trans.cpp> - 10/23/15 08:20:46

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0;

char ch=getchar();

while(ch<'0'||ch>'9')ch = getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return res;

}

char a[1000002],b[1000002];

int la,lb;

bool src3(int w,int p){

for(int i=0;i<w;i++)if(a[la-i-1]!=b[i+p])return 0;

return 1;

}

void src2(int i,int p){

if(src3(la-p-i,i)){cout<<p-1<<" "<<p+i;exit(0);}

if(p+i==la)return;

if(b[i]==a[i+p])src2(i+1,p);

}

void src1(int i){

if(i==la-1)return;

if(a[i]==b[la-1-i])src1(i+1);

src2(0,i+1);

}

int main(){

freopen("trans.in","r",stdin);

freopen("trans.out","w",stdout);

cin.getline(a,1000001);

cin.getline(b,1000001);

la=strlen(a);lb=strlen(b);

if(la!=lb){cout<<"-1 -1";return 0;}

src1(0);

cout<<"-1 -1";

return 0;

}