注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【恶心题】【水题】遥控车  

2014-04-29 16:42:20|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

@遥控车onVijos
恶心题
其实是水题但是做了好长时间
主要是数据专业卡Trie没有节操……
Trie各种MLE
最后我坚守节操没有用二分,想办法卡了一下数据就过了
存儿子的指针也动态开就可以了

第二问完全没有必要写矩阵乘法,我主要是想复习一下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
using namespace std;

int zhi(char cc){
if('a'<=cc&&cc<='z') return cc-'a'+1;
if('A'<=cc&&cc<='Z') return -(cc-'A'+1);
return 0;
}
const int N = 800000+1;
int n,m,ans,ROOT,T1,T2;
int next2[N*26],next1[2][N];
short tree[N*26];
struct Big{
int n,d[4001];
Big(){memset(d,0,sizeof(d));n=1;}
Big operator = (int a){
memset(d,0,sizeof(d));
for(n=0;a;a/=10)
d[++n]=a%10;
if(n==0) n=1;
return *this;
}
void print(){ for(int i=n;i>=1;i--)printf("%d",d[i]); }
};
Big operator * (const Big &a,const Big &b){
Big c;int i,j;
c.n=a.n+b.n+1;
for(i=1;i<=a.n;i++)
for(j=1;j<=b.n;j++)
c.d[i+j-1] += a.d[i]*b.d[j];
for(i=1;i<=c.n;i++){
c.d[i+1]+=c.d[i]/10;
c.d[i]%=10;
}
while(c.d[c.n]==0&&c.n>1)c.n--;
return c;
}
Big operator + (const Big &a,const Big &b){
Big c;
if(b.n>a.n) c.n = b.n+1;
else c.n = a.n+1;
for(int i=1;i<=c.n;i++){
c.d[i]+=a.d[i]+b.d[i];
c.d[i+1]=c.d[i]/10;
c.d[i]%=10;
}
while(c.d[c.n]==0&&c.n>1)c.n--;
return c;
}
struct matrix{
int n,m;
Big d[2][2];
void print(){
for(int j=0;j<m;j++){
for(int i=0;i<n;i++)
d[i][j].print();
printf("\n");
}
}
}FZ,DP;
matrix operator * (const matrix &a,const matrix &b){
//if(a.m!=b.n){cerr<<"ERROR"<<endl;}
int i,j,k;matrix c;
for(i=0;i<a.n;i++)
for(j=0;j<b.m;j++)
for(k=0;k<a.m;k++)
c.d[i][j] = c.d[i][j] + (a.d[i][k]*b.d[k][j]);
c.n=a.n;c.m=b.m;
return c;
}
matrix pow(matrix a,int k){
k-=1;matrix re=a;
for(;k;k>>=1,a=a*a)
if(k&1) re=re*a;
return re;
}
int main(){
//pre-set
FZ.n=1;FZ.m=2;FZ.d[0][0]=0;FZ.d[0][1]=1;
DP.n=2;DP.m=2;
DP.d[0][0]=0;DP.d[1][0]=1;
DP.d[0][1]=1;DP.d[1][1]=1;
//freopen("input.txt","r",stdin);
int i,j,a,b;char cc;
ROOT=++T1;
next1[0][ROOT]=next1[1][ROOT]=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
cc=' ';int r=ROOT;
tree[r]++;
while(cc==' '||cc=='\n'||cc=='\r') cc=getchar();
while((a=zhi(cc))!=0){
b=abs(a);
int &l1 = next1[a>0][r];
if (l1==0)l1=++T2;
int &l2=next2[(l1-1)*26+b];
if(l2==0)l2=++T1;
r=l2;tree[r]++;
cc=getchar();
}
}
for(i=1;i<=m;i++){
cc=' ';int r=ROOT;
while(cc==' '||cc=='\n'||cc=='\r') cc=getchar();
while((a=zhi(cc))!=0){
if(r){
b=abs(a);
int &l1 = next1[a>0][r],&l2=next2[(l1-1)*26+b];
r=l2;
}
cc=getchar();
}
ans+=tree[r];
}
printf("%d\n",ans);
//p2
if(n==1) {printf("1\n");return 0;}
DP=pow(DP,n-1);
FZ=FZ*DP;
Big ans1 = FZ.d[0][0]+FZ.d[0][1];
ans1.print();
return 0;
}


  评论这张
 
阅读(14)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017