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 学长请客吃饭之后又去商量什么秘密东西去了….
B题是矩阵乘法+二分快速求幂。
题目没有什么算法是为了确保营养,让没学过什么算法的同学也有的做。
那个秘密东西是什么呢?
仰慕一下轻工神学长。。。
秘密东西。。??什么?
笨哇,人家学长问你最后一行说的什么东西…
现在才看到~伟大的党姐~
不知道怎么的,突然想起来神赛,再拿过第六之后就只有第二拿了。。。。。。
然后我这个第二一直存在着,第一居然都换掉了。。压力真大。。。
不对,应该说,我明年要是去的话必然很淡定了。。。。。
明年我们看你夺冠
💡
。。额。。不要这么说,压力会很大很大的。。。。
话说明年怎么组队也是一个问题的说。。。恩 需要商量