|
|
Posted on 2011-09-08 23:14 Uriel 閱讀(923) 評論(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]
|