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

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 && cｗ 学长请客吃饭之后又去商量什么秘密东西去了….