恶心题……
数据专业卡Trie没有节操
但是也可以卡数据
存儿子的指针也动态开就可以了

第二问实际上就是Fibonacci数列……
我比较2b用了矩阵乘法，其实滚动数组就可以，而且高精完全不需要压位
#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;
}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

帅气！秒杀。。。。。

快排+二分+高精压位的斐波那契 ^_^

var n,m,i,j,l,t,x,y,mid:longint;

a,b:array[0..10000] of string;

f:array[-1..10000,0..500] of longint;

procedure qsort(l,r:longint);

var i,j:longint;

s,mid:string;

begin

i:=l; j:=r; mid:=a[(l+r) div 2];

repeat

while a[i]mid do dec(j);

if ij;

if l

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：169ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 72ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 291ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：544ms

超囧题……

第一问 二分

第二问 高精斐波那契 必须压位 我压了9位……

123行 创纪录了……

orz suning 秒杀的牛……

高精不压位也行，设一个最高位标志

Trie爆内存了……

后来用二分。

先把原来字符串排序，然后每次只取相同长度比较，找到最前位置和最后位置。

第二问就是Fib数列

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

type

aa=array[1..10000]of string;

var

a,b:aa;

c:array[1..10000,0..10000]of longint;

t:string;

n,m,i,j,sum,k:longint;

procedure qsort(l,r:longint);

var i,j:longint;mid:string;

begin

i:=l;j:=r;mid:=a[(i+j)shr 1];

repeat

while(a[i]mid)do dec(j);

if ij;

if l

这题不是很难，第一问和第二问并无什么关系。

第一问不能用枚举，10000*10000铁定超时，所以用二分法，先将原字符串快排，因为前缀必定会比原字符小，所以可以通过确定一个前缀在有序字符串中的位置来判断前缀，判断时只看头尾指针，二分到一半若满足条件，就跳出循环。

关于第二问，则是标准的斐波那契数列，因为有10000项，要用高精！

我晕倒，原来高精度有一万多位，我才开到一千，4次才AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 40ms

├ 测试数据 06：答案正确... 103ms

├ 测试数据 07：答案正确... 181ms

├ 测试数据 08：答案正确... 477ms

├ 测试数据 09：答案正确... 586ms

├ 测试数据 10：答案正确... 680ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2067ms

提交了五次!!!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案错误...程序输出比正确答案长

├ 测试数据 06：答案错误...程序输出比正确答案长

├ 测试数据 07：答案错误...程序输出比正确答案长

├ 测试数据 08：答案错误...程序输出比正确答案长

├ 测试数据 09：答案错误...程序输出比正确答案长

├ 测试数据 10：答案错误...程序输出比正确答案长

---|---|---|---|---|---|---|---|-

请问有哪些原因可能导致这种错误？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 72ms

├ 测试数据 07：答案正确... 150ms

├ 测试数据 08：答案正确... 509ms

├ 测试数据 09：答案正确... 650ms

├ 测试数据 10：答案正确... 838ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2219ms

var

i,j,k,n,m,q:longint;

a:array[1..10000]of string;

b:array[1..10000]of string;

c:array[1..5000,0..1]of integer;

procedure qsort(s,t:longint);

var

i,j:longint;

x,k:string;

begin

i:=s; j:=t;

x:=a[(i+j)shr 1];

while i

fib不晓得 用公式可以吗？？？

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 134ms

终于过了

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 103ms

├ 测试数据 10：答案正确... 88ms

原来高精超了·····

hoho 1000000000进制

可怜我少打一个零！！

好题啊！！啥也不说了 附上代码供您参考

#include

#include

#define LEN 100000

#define MAXn 10000

#define MAXm 10000

#define MAXlen 254

long n,m,ans,permutation[LEN+10],last1[LEN+10],last2[LEN+10];

char name[MAXn+10][MAXlen+10];

void let_num_be_num_plus_num(long *c,long *a,long *b)

{

long i,len;

len=(a[0]>b[0])?a[0]:b[0];

for(i=1;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：103ms

楼上不用mod似乎有道理，瞧我慢的。

为什么我没用矩阵

才25MS？

大概是没MOD吧

ansistring 太慢 用了必超

总算用string混过去了 不过仍然很慢

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 134ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 291ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：662ms

高精用万位存的话，会快很多。

144行。。半年来破纪录的长度。。。

貌似最近二分很流行。。。