第三届郑州轻工业学院校赛流水帐~

于 2011年04月10日 发布在 吐槽, 算法&&ACM 跳到评论

A.水题..注意从两个门开始搜

B.矩阵快速幂求第n个fibnacci数,但是当时比赛的时候不知道这个算法阿…依稀记得算法导论的视频上有个矩阵运算,然后我就坐在那里一直YY……最后……居然yy出来了,我了个汗阿…..但是不会求时间复杂度,但是我好像感觉比那个幂预算稍微慢点…..附上代码,路过的大牛,指导下把..

#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
struct node {
    LL a[2][2];
    void ass(int aa,int b,int c,int d){
        a[0][0]=aa;
        a[1][0]=c;
        a[0][1]=b;
        a[1][1]=d;
    }
}F[45];
struct node multi(struct node x,struct node y){
    node ans;ans.ass(0,0,0,0);
    for( int i = 0;i<2;i++ )
        for( int j = 0; j < 2; j++ ){
            for( int k = 0; k < 2; k++)
                ans.a[i][j] += (x.a[i][k]*y.a[k][j])%2011403;
            ans.a[i][j] %= 2011403;
        }
    return ans;
}
LL fib[45];
int main(void)
{
    LL i,j,l,n,cases;
    node ans;
    fib[0]=fib[1]=1;
    F[0].ass(0,1,1,1);
    F[1].ass(0,1,1,1);
    for( i= 2; i<=44;i++ ){
        fib[i] = fib[i-1] + fib[i-2];
        F[i] = multi(F[i-2],F[i-1]);
    }
    cin >> cases;
    while( cases-- ){
        cin >> n;
        if( n==0 ){cout<<1<<endl;continue;}
        i = 44;
        while( fib[i] > n ) i--;
        ans = F[i];
        n -= fib[i];
        while(n){
            while( fib[i] > n ) i--;
            n -= fib[i];
            ans = multi(F[i],ans);
        }
        cout<< ans.a[1][1] << endl;
    }
    return 0;
}

C.水题.btw && zxy为此贡献了6次wa,我重写一遍….过了…

D.欧拉回路,,我了个去阿.  刚开始比赛时候太草率了,没有判连通就开始判断度了…..zxy同学,图论女神,,顺利A掉…

E.是我想复杂了?应该是很水的阿…这不是重点,,,重点是zxy同学竟然用广搜过了..神奇的队友阿.提醒下没过的,当大写锁定时候,还可以按下shift输入小写~

F.签名题

G.Lattice Path? C(N+M,N)~ btw给的思路,,我敲代码

H.DP最长**子序列?

I.我以幽怨的眼神盯着他….出题的轻工学长说,,,,我们不打算让你们全部A的…看懂题了,,各种没思路

J.坑爹阿….是<100还是<=100????  题目描述不清除阿..有木有阿,,有木有?

几点:

1.见了群友阿…没好好说话,人多,要是能一块吃饭多好…..

2.没有什么算法…..因为精心准备的模板没有用上….

3.差一题ak,丧心阿 ~~~~

4.gb && cw 学长请客吃饭之后又去商量什么秘密东西去了….

本文共有 8条评论 | 沙发:文章评论

  1. superbin说道:

    B题是矩阵乘法+二分快速求幂。
    题目没有什么算法是为了确保营养,让没学过什么算法的同学也有的做。
    那个秘密东西是什么呢?

  2. 小媛在努力说道:

    现在才看到~伟大的党姐~

  3. gb说道:

    不知道怎么的,突然想起来神赛,再拿过第六之后就只有第二拿了。。。。。。
    然后我这个第二一直存在着,第一居然都换掉了。。压力真大。。。

  4. gb说道:

    不对,应该说,我明年要是去的话必然很淡定了。。。。。

  5. gb说道:

    。。额。。不要这么说,压力会很大很大的。。。。

    话说明年怎么组队也是一个问题的说。。。恩 需要商量

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)