HDU 3689, UVA 11468 - c++编程基础

memset(ok,-1,sizeof(ok));
for(i=0;i<100;i++)pp[i]=0;
k=0;
for(i=1;i<=n;i++){
scanf("%s %lf",s,&tem);
if(ok[s[0]]==-1)
ok[s[0]]=k++;
pp[ok[s[0]]]+=tem;
}
nn=k;
scanf("%s",s);
int len=strlen(s);
if(len>m || insert(s)==0){
printf("0.00");
putchar('%');
putchar('\n');
continue;
}
makefail();
dps();
}
}

UVA 11468

[cpp] view plaincopyprint #include
#include
#include
#include
#include
#define N 500
using namespace std;
int nn,m;
int ok[200];
double pp[200];
int next[N][70],fail[N],flag[N],pos;
char s[100];
int newnode(){
int i=0;
memset(next[pos],0,sizeof(next[pos]));
fail[pos]=flag[pos]=0;
return pos++;
}
void insert(char * s){
int i,p=0;
for(i=0;s[i];i++){
int k=ok[s[i]];
int &x=next[p][k];
p=x x:x=newnode();
}
flag[p]=1;
}
void makefail(){
int i;
queueq;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i int v=next[u][i];
if(v==0)next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
flag[v]|=flag[fail[v]];
}
}
}
}
double dp[110][N];
void dps(){
int i,j,k,p;
double ans=0;
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1;i<=m;i++){
for(j=0;j if(flag[j])continue;
for(p=0;p int v=next[j][p];
dp[i][v]+=dp[i-1][j]*pp[p];
}
}
}
for(j=0;j if(!flag[j])
ans+=dp[m][j];

printf("%lf\n",ans);
}
int main(){
int i,k,n,cou;
char s[25][25],str[10];
double tem;
int t,T;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d",&k);
for(i=0;i

memset(ok,-1,sizeof(ok));
for(i=0;i<100;i++)pp[i]=0;
cou=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%s %lf",str,&tem);
if(ok[str[0]]==-1)
ok[str[0]]=cou++;
pp[ok[str[0]]]+=tem;
}
nn=cou;
scanf("%d",&m);

pos=0,newnode();
for(i=0;i makefail();
printf("Case #%d: ",t);
dps();
}
}

#include
#include
#include
#include
#include
#define N 500
using namespace std;
int nn,m;
int ok[200];
double pp[200];
int next[N][70],fail[N],flag[N],pos;
char s[100];
int newnode(){
int i=0;
memset(next[pos],0,sizeof(next[pos]));
fail[pos]=flag[pos]=0;
return pos++;
}
void insert(char * s){
int i,p=0;
for(i=0;s[i];i++){
int k=ok[s[i]];
int &x=next[p][k];
p=x x:x=newnode();
}
flag[p]=1;
}
void makefail(){
int i;
queueq;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
for(i=0;i int v=next[u][i];
if(v==0)next[u][i]=next[fail[u]][i];
else q.push(v);
if(u&&v){
fail[v]=next[fail[u]][i];
flag[v]|=flag[fail[v]];
}
}
}
}
double dp[110][N];
void dps(){
int i,j,k,p;
double ans=0;
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1;i<=m;i++){

HDU 3689, UVA 11468 (二)