10.14字符串专题解题报告

1.品茶

这道题直接模拟。。没什么好说的

上代码:

// <tea.cpp> – 10/14/15 08:21:31
// 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;
int ans;
char jp[20001];
int main()
{
freopen(“tea.in”,”r”,stdin);
freopen(“tea.out”,”w”,stdout);
int n;
cin>>n;
getchar();
while(n–){
gets(jp);
int l=strlen(jp);
int kai=0;
for(int i=0;i<l;i++){
if(jp[i]==’Q’||jp[i]==’W’||jp[i]==’E’||jp[i]==’R’||jp[i]==’q’||jp[i]==’w’||jp[i]==’e’||jp[i]==’r’){
kai++;if(kai==l/2+1)break;
}
}
if(kai==l/2+1)ans++;
}
cout<<ans;
return 0;
}

2.归途

这道题据说难点在分析题目

然而我第一眼就看出来是看。。KMP算法

虽然忘记怎么写了

但是我存了一份XD 直接蒯

很多人没用读入优化T了

然而因为没开longlong跪了两个点

代码:

// <journey.cpp> – 10/14/15 08:21:31
// 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;
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 getlonglong(){
long long 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;
}
int X,next[100010];
long long tl;
long long t[100010];
int l[100010],p[100010];
void getnext(int lens)
{
next[0]=next[1]=0;
for(int i=1;i<lens;i++){
int j=next[i];
while(j&&p[i]!=p[j])j=next[j];
next[i+1]=p[i]==p[j]?j+1:0;
}
}
int kmp(int lens,int lent)
{
int i,j=0;
for(i=0;i<lent&&t[i-1]<=tl;i++){
while(j&&l[i]!=p[j])j=next[j];
if(l[i]==p[j])j++;
if(j==lens)return t[i-1];
}
return -1;
}
int main()
{
freopen(“journey.in”,”r”,stdin);
freopen(“journey.out”,”w”,stdout);
cin>>X;
while(X–){
int n=getint(),m=getint();
for(int i=0;i<m;i++){
int a=getint(),b=getint(),c=getint(),d=getint();
l[a-1]=b;l[a]=c;t[a-1]=d;
}
for(int i=1;i<m;i++)t[i]+=t[i-1];
int P=getint();
for(int i=0;i<P;i++)p[i]=getint();
tl=getlonglong();
getnext(P);
int e=kmp(P,m+1);
if(e==-1)cout<<“NO”<<endl;
else cout<<“YES “<<e<<endl;
}
return 0;
}

PS:之后我又自己写了一遍KMP

3.钢琴手

这道题说要用AC自动机

然后AC自动机的基础是Trie树和KMP

先去学一下 晚上再做XD

4.幸福

这道题是后缀数组

晚上再做XD

说点什么

您将是第一位评论人!

提醒
wpDiscuz