Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
这套还行,稍有点小水

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 lee
LZ,很高兴看到你的博客。对于第一题递推数列,能够解释一下什么情况下是典型的矩阵应用呢?

# re: 清华大学计算机研究生机试题-2009年  回复  更多评论   

2012-02-09 17:56 by Uriel
@lee
矩阵是用来加速运算的,像这种递推式,直接算的话复杂度O(n),用矩阵做的话就可以降到log级别。。
主要是一些能构造出转移矩阵,转化为矩阵连乘的题,

# re: 清华大学计算机研究生机试题-2009年  回复  更多评论   

2012-03-27 16:15 by Bice
@Uriel
能劳烦解释一下第一个程序吗,太深奥了看不懂 啊

# re: 清华大学计算机研究生机试题-2009年  回复  更多评论   

2012-03-27 16:28 by Uriel
@Bice
这。。几句话说不清楚。。
大致过程就是找递推式,构造转移矩阵,然后求第N项就化为矩阵连乘问题
ps:ACM常见题。。,网上有N多介绍

# re: 清华大学计算机研究生机试题-2009年  回复  更多评论   

2012-03-27 17:56 by Johnnyao
请问,对于第一题的题意,难道是我理解错了吗,递推式不是已经在题目中给出了吗?能否讲解一下题意
http://ac.jobdu.com/problem.php?id=1081

# re: 清华大学计算机研究生机试题-2009年  回复  更多评论   

2012-03-27 18:08 by Uriel
@Johnnyao
是给了啊,所以这题只要构造转移矩阵就行了,像这题的话转移矩阵就是
[p q]
[1 0]
计算过程就是
[p q] ^ k - 1 [a1]
[1 0] * [a0]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理