题解

59 条题解

  • 0
    @ 2014-04-29 16:35:27

    恶心题……
    数据专业卡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;
    }

  • 0
    @ 2009-11-06 15:37:45

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2009-10-20 16:25:11

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-09-17 21:58:17

    编译通过...

    ├ 测试数据 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 秒杀的牛……

  • 0
    @ 2009-07-29 14:44:28

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

  • 0
    @ 2009-07-13 21:19:33

    Trie爆内存了……

    后来用二分。

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

    第二问就是Fib数列

  • 0
    @ 2009-05-05 19:24:34

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2009-05-03 11:04:18

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

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

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

  • 0
    @ 2008-12-06 16:18:54

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

  • 0
    @ 2008-10-27 19:08:02

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    提交了五次!!!!

  • 0
    @ 2008-10-26 16:04:36

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-10-21 15:46:26

    编译通过...

    ├ 测试数据 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

  • 0
    @ 2008-10-17 15:44:48

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

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

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

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

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

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

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

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

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

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

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

    终于过了

  • 0
    @ 2008-10-14 18:10:30

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

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

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

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

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

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

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

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

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

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

    原来高精超了·····

    hoho 1000000000进制

  • 0
    @ 2008-10-13 18:59:18

    可怜我少打一个零!!

  • 0
    @ 2008-10-10 22:29:34

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

    #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

  • 0
    @ 2008-10-10 19:03:07

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-10-06 19:01:43

    为什么我没用矩阵

    才25MS?

    大概是没MOD吧

  • 0
    @ 2008-10-05 19:44:56

    ansistring 太慢 用了必超

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

  • 0
    @ 2008-10-05 18:58:23

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

信息

ID
1458
难度
6
分类
字符串 | 线性代数 | 矩阵乘法高精度 点击显示
标签
递交数
522
已通过
127
通过率
24%
被复制
2
上传者