首页 > ACM题库 > HDU-杭电 > hdu 2254 奥运-快速幂-[解题报告]C++
2014
01-04

hdu 2254 奥运-快速幂-[解题报告]C++

奥运

问题描述 :

北京迎来了第一个奥运会,我们的欢呼声响彻中国大地,所以今年的奥运金牌 day day up!
比尔盖兹坐上鸟巢里,手里摇着小纸扇,看的不亦乐乎,被俺们健儿的顽强拼搏的精神深深的感动了。反正我的钱也多的没地方放了,他对自己说,我自己也来举办一个奥运会,看谁的更火。不过他的奥运会很特别:
1 参加人员必须是中国人;
2 至少会加法运算(因为要计算本人获得的金牌数)
他知道中国有很多的名胜古迹,他知道自己在t1 到 t2天内不可能把所有的地方都玩遍,所以他决定指定两个地方v1,v2,如果参赛员能计算出在t1到t2天(包括t1,t2)内从v1到v2共有多少种走法(每条道路走需要花一天的时间,且不能在某个城市停留,且t1=0时的走法数为0),那么他就会获得相应数量的金牌,城市的总数<=30,两个城市间可以有多条道路
,每条都视为是不同的。

输入:

本题多个case,每个case:
输入一个数字n表示有n条道路 0<n<10000
接下来n行每行读入两个数字 p1,p2 表示城市p1到p2有道路,并不表示p2到p1有道路 (0<=p1,p2<2^32)
输入一个数字k表示有k个参赛人员
接下来k行,每行读入四个数据v1,v2,t1,t2 (0<=t1,t2<10000)

输出:

本题多个case,每个case:
输入一个数字n表示有n条道路 0<n<10000
接下来n行每行读入两个数字 p1,p2 表示城市p1到p2有道路,并不表示p2到p1有道路 (0<=p1,p2<2^32)
输入一个数字k表示有k个参赛人员
接下来k行,每行读入四个数据v1,v2,t1,t2 (0<=t1,t2<10000)

样例输入:

6
1 2
1 3
2 3
3 2
3 1
2 1
3
1 2 0 0
1 2 1 100
4 8 3 50

样例输出:

0
1506
0

点击打开hdu 2254

思路: 矩阵乘法

分析:

1 题目给定一个有向图,要求t1-t2天内v1-v2的路径的个数

2 假设有向图的邻接矩阵为A,那么A表示的是有向图中走一步能够到达哪些点的方案数,那么A^n表示的是走n步能够到达哪些点的方案数

3 根据离散数学里面的可达矩阵的性质,我们知道一个有向图的邻接矩阵的前n次幂的和即为可达矩阵,那么要求[t1-t2]之内的路径的条数,因为题目说了t1 = 0的时候为0。那么假设邻接矩阵为A,那么要求的就是A^(t1-1)+A^(t1)+…+A^t2,为什么是从t1-1开始呢,因为邻接矩阵本身代表走一步的结果

3 还有点的范围很大,边数很少,所以我们应该要进行离散化

4 但是数据量很大,对于具体的一组我们应该要事先求出具体的每一个矩阵,然后直接使用即可


代码:

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-08-25                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ***********************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef __int64 int64;
const int MOD = 2008;
const int MAXN = 10000;
const int N = 30;

int n , pos;
int64 num[2*MAXN];
struct Edge{
    int64 x;
    int64 y;
};
Edge e[MAXN];

struct Matrix{
    int mat[N][N];
    Matrix operator*(const Matrix& m)const{
        Matrix tmp;
        for(int i = 0 ; i < pos ; i++){
            for(int j = 0 ; j < pos ; j++){
                tmp.mat[i][j] = 0;
                for(int k = 0 ; k < pos ; k++){
                    tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;
                    tmp.mat[i][j] %= MOD;
                }
            }
        }
        return tmp;
    }
};
Matrix ma[MAXN];

int search(int64 x){
    int left = 0;
    int right = pos-1;
    while(left <= right){
        int mid = (left+right)>>1;
        if(num[mid] == x)
            return mid;
        else if(num[mid] < x)
            left = mid+1;
        else
            right = mid-1;
    }
    return -1;
}

void init(Matrix &m){
    memset(m.mat , 0 , sizeof(m.mat));
    sort(num , num+pos);
    pos = unique(num , num+pos)-num;
    for(int i = 0 ; i < n ; i++){
        int x = search(e[i].x);
        int y = search(e[i].y);
        m.mat[x][y]++;
    }
}

void Pow(Matrix m){
    ma[0] = m;
    for(int i = 1 ; i < MAXN ; i++)
        ma[i] = ma[i-1]*m; 
}

void solve(){
    Matrix m;
    init(m);
    Pow(m);

    int64 v1 , v2;
    int k , t1 , t2;
    scanf("%d" , &k);
    while(k--){
        scanf("%I64d%I64d%d%d" , &v1 , &v2 , &t1 , &t2); 
        if(t1 > t2 || t2 == 0){
            puts("0");
            continue;
        }
        int x = search(v1); 
        int y = search(v2); 
        if(x == -1 || y == -1){
            puts("0");
            continue;
        }
        int sum = 0;
        for(int i = t1-1 ; i < t2 ; i++){
            sum += ma[i].mat[x][y]%MOD;
            sum %= MOD;
        }
        printf("%d\n" , sum);
    }
}

int main(){
    while(scanf("%d" , &n) != EOF){
        pos = 0; 
        for(int i = 0 ; i < n ; i++){
            scanf("%I64d%I64d" , &e[i].x , &e[i].y);
            num[pos++] = e[i].x;
            num[pos++] = e[i].y;
        }
        solve();
    }
    return 0;
}

解题转自:http://blog.csdn.net/chenguolinblog/article/details/10300023


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。