|
|
Posted on 2011-09-08 23:14 Uriel 阅读(893) 评论(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]
|