|
Posted on 2011-09-08 23:14 Uriel 阅读(903) 评论(6) 编辑 收藏 引用 所属分类: 考研&保研复试上机题
这套还行,稍有点小水 1. 递推数列 典型的矩阵应用啊~POJ挺多道这种题的 又NC地调试语句忘擦掉就交。。
//2009年清华大学计算机研究生机试真题 递推数列
#include<stdio.h> #include<stdlib.h> #include<string.h> #define N 10000
typedef int M[2][2];
M c, mtx;
void copy(M x, M y) { for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j) x[i][j] = y[i][j]; }
void AC(M x, M y) { M z; int i, j, k, t; for(i = 0; i < 2; ++ i) for(j = 0; j < 2; ++j) { t = 0; for(k = 0; k < 2; ++k) if(x[i][k] && y[k][j]) { t = (t + (x[i][k] % N) * (y[k][j] % N)) % N; } z[i][j] = t; } copy(x, z); }
void Cal(int k) { if(k == 1) { copy(mtx, c); return; } Cal(k >> 1); AC(mtx, mtx); if(k & 1) AC(mtx, c); }
int main() { int a0, a1, p, q, k, ans; while(~scanf("%d %d %d %d %d", &a0, &a1, &p, &q, &k)) { if(!k) { printf("%d\n", a0 % N); } else if(k == 1) { printf("%d\n", a1 % N); } else { c[0][0] = p; c[0][1] = q; c[1][0] = 1; c[1][1] = 0; Cal(k - 1); a0 %= N; a1 %= N; ans = (mtx[0][0] * a1 + mtx[0][1] * a0) % N; printf("%d\n", ans); } } return 0; } 2. 代理服务器 一开始理解错题意了,其实是很水很暴力的贪心,因为访问顺序是一定的,所以只要每次找出可以访问的服务器最多的那个代理服务器就行
//2009年清华大学计算机研究生机试题 代理服务器 #include<stdio.h> #include<stdlib.h> #include<string.h>
int n, m, cnt; char nIP[1010][16], mIP[5010][16];
int main() { int i, j, np, mp, mx, time; while(~scanf("%d", &n)) { for(i = 0; i < n; ++i) scanf("%s", nIP[i]); scanf("%d", &m); for(i = 0; i < m; ++i) scanf("%s", mIP[i]); np = mp = time = 0; while(mp < m) { mx = 0; for(i = 0; i < n; ++i) { cnt = 0; for(j = mp; j < m; ++j) { if(strcmp(nIP[i], mIP[j])) cnt++; else break; } if(cnt > mx) { mx = cnt; np = i; } } if(!mx) break; time++; mp += mx; } if(!mx) { puts("-1"); } else printf("%d\n", time - 1); } return 0; }
Feedback
# re: 清华大学计算机研究生机试题-2009年[未登录] 回复 更多评论
2012-02-09 15:29 by
LZ,很高兴看到你的博客。对于第一题递推数列,能够解释一下什么情况下是典型的矩阵应用呢?
# re: 清华大学计算机研究生机试题-2009年 回复 更多评论
2012-02-09 17:56 by
@lee 矩阵是用来加速运算的,像这种递推式,直接算的话复杂度O(n),用矩阵做的话就可以降到log级别。。 主要是一些能构造出转移矩阵,转化为矩阵连乘的题,
# re: 清华大学计算机研究生机试题-2009年 回复 更多评论
2012-03-27 16:15 by
@Uriel
能劳烦解释一下第一个程序吗,太深奥了看不懂 啊
# re: 清华大学计算机研究生机试题-2009年 回复 更多评论
2012-03-27 16:28 by
@Bice 这。。几句话说不清楚。。 大致过程就是找递推式,构造转移矩阵,然后求第N项就化为矩阵连乘问题 ps:ACM常见题。。,网上有N多介绍
# re: 清华大学计算机研究生机试题-2009年 回复 更多评论
2012-03-27 17:56 by
请问,对于第一题的题意,难道是我理解错了吗,递推式不是已经在题目中给出了吗?能否讲解一下题意 http://ac.jobdu.com/problem.php?id=1081
# re: 清华大学计算机研究生机试题-2009年 回复 更多评论
2012-03-27 18:08 by
@Johnnyao 是给了啊,所以这题只要构造转移矩阵就行了,像这题的话转移矩阵就是 [p q] [1 0] 计算过程就是 [p q] ^ k - 1 [a1] [1 0] * [a0]
|