天天看點
傳回

HDU 2254解題報告 奧運

奧運

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 2334    Accepted Submission(s): 598

Problem Description 北京迎來了第一個奧運會，我們的歡呼聲響徹中國大地，是以今年的奧運金牌 day day up!

比爾蓋茲坐上鳥巢裡，手裡搖着小紙扇，看的不亦樂乎，被俺們健兒的頑強拼搏的精神深深的感動了。反正我的錢也多的沒地方放了，他對自己說，我自己也來舉辦一個奧運會，看誰的更火。不過他的奧運會很特别：

1 參加人員必須是中國人；

2 至少會加法運算（因為要計算本人獲得的金牌數）

他知道中國有很多的名勝古迹，他知道自己在t1 到 t2天内不可能把所有的地方都玩遍，是以他決定指定兩個地方v1,v2，如果參賽員能計算出在t1到t2天（包括t1,t2）内從v1到v2共有多少種走法(每條道路走需要花一天的時間，且不能在某個城市停留,且t1=0時的走法數為0)，那麼他就會獲得相應數量的金牌，城市的總數<=30,兩個城市間可以有多條道路

，每條都視為是不同的。

Input 本題多個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)

Output 對于每組資料中的每個參賽人員輸出一個整數表示他獲得的金牌數（mod 2008）

Sample Input

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

Sample Output

0
1506
0

Source HDOJ 2008 Summer Exercise（4）- Buffet Dinner  

Recommend lcy   |   We have carefully selected several similar problems for you:   2256  2294  3117  2842  3519    不得不說，這是我所做過的矩陣題目中比較神的一道。不是題的難度大，而是資料比較神奇。把int改成long long就過不了。坑了一下午一直找不到WA的原因，後來才發現是題的問題。在圖論中，關系矩陣的n次方，表示經過k步可以到達的狀态。與floyd算法的dp思想有關。因而可以用矩陣快速幂求解。在本題中設關系矩陣為A,則題目所求為A^(t1)+A^(t1+1)+……+A^(t2)的值。而A^0=E。也就是任意不同的兩個點之間經過0步的走法是0種。

       此外還需要說的就是本題中要用map對點進行離散化，還要考慮兩個點之間可能有重邊，而我們計算方法數的時候要将他們算成是不同的。各種坑爹資料。。醉的一陣一陣的。。

       下面寫出幾種不同的參考代碼以及由于題目資料有問題而導緻過不了的代碼。

       AC代碼1：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<ctime>
#include<cstdlib>
#include<iomanip>
#include<utility>
#define pb push_back
#define mp make_pair
#define CLR(x) memset(x,0,sizeof(x))
#define _CLR(x) memset(x,-1,sizeof(x))
#define REP(i,n) for(int i=0;i<n;i++)
#define Debug(x) cout<<#x<<"="<<x<<" "<<endl
#define REP(i,l,r) for(int i=l;i<=r;i++)
#define rep(i,l,r) for(int i=l;i<r;i++)
#define RREP(i,l,r) for(int i=l;i>=r;i--)
#define rrep(i,l,r) for(int i=1;i>r;i--)
#define read(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<11
using namespace std;

int n,k,num;
const int mod=2008;
struct mat
{
    int d[33][33];   //這裡用int型，可以AC
} A,E;
map<int,int>m;

mat multi(mat a,mat b)
{
    mat ans;
    REP(i,1,num)
    {
        REP(j,1,num)
        {
            ans.d[i][j]=0;
            REP(k,1,num)
            if(a.d[i][k]&&b.d[k][j])
                ans.d[i][j]=(ans.d[i][j]+(ll)a.d[i][k]*b.d[k][j])%mod;  //由于是int型，防止溢出，強制轉換
        }
    }
    return ans;
}

mat add(mat a,mat b)
{
    mat ans;
    REP(i,1,num)
        REP(j,1,num)
            ans.d[i][j]=(a.d[i][j]+b.d[i][j])%mod;
    return ans;
}

mat quickmulti(mat a,int n)   //矩陣快速幂
{
    if(n==0) return E;
    if(n==1) return a;
    mat ans=E;
    while(n)
    {
        if(n&1)
        {
            n--;
            ans=multi(ans,a);
        }
        else
        {
            n>>=1;
            a=multi(a,a);
        }
    }
    return ans;
}

mat solve(mat a,int n)       //二分矩陣多項式
{
    if(n==1) return a;
    mat ans=solve(a,n/2);
    mat res=add(ans,multi(quickmulti(a,n/2),ans));
    if(n%2==1) res=add(res,quickmulti(a,n));
    return res;
}

int main()
{
    CLR(E.d);
    rep(i,0,33)
    E.d[i][i]=1;
    while(~scanf("%d",&n))
    {
        CLR(A.d);
        m.clear();
        num=0;     //num計算的是實際的點數
        REP(i,1,n)
        {
            int p1,p2;
            scanf("%d%d",&p1,&p2);
            if(!m[p1]) m[p1]=++num;
            if(!m[p2]) m[p2]=++num;
            ++A.d[m[p1]][m[p2]];  //考慮重邊，是以要用++
        }
        scanf("%d",&k);
        rep(i,0,k)
        {
            int v1,v2,t1,t2;
            scanf("%d%d%d%d",&v1,&v2,&t1,&t2);
//            if(!m[v1]||!m[v2])   //此時加不加這個判斷都能AC，另一種解法不加就WA
//            {
//                printf("0\n");
//                continue;
//            }
            v1=m[v1],v2=m[v2]; //轉換成離散化後對應的點的編号
            if(!t1) t1++;  //t1=0的時候不用考慮
            if(t1<=t2)  
            {
                mat ans=solve(A,t2-t1+1);
                mat ans1=quickmulti(A,t1-1);
                ans=multi(ans,ans1);
                printf("%d\n",ans.d[v1][v2]%mod);  //這裡用%d輸出就能AC
            }
            else
                printf("0\n");
        }
    }
}

同樣的代碼，隻是把矩陣裡面數組的類型改成long long，最終用%I64d輸出就會WA。坑爹不償命。。

HDU 2254解題報告 奧運

WA的代碼：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<ctime>
#include<cstdlib>
#include<iomanip>
#include<utility>
#define pb push_back
#define mp make_pair
#define CLR(x) memset(x,0,sizeof(x))
#define _CLR(x) memset(x,-1,sizeof(x))
#define REP(i,n) for(int i=0;i<n;i++)
#define Debug(x) cout<<#x<<"="<<x<<" "<<endl
#define REP(i,l,r) for(int i=l;i<=r;i++)
#define rep(i,l,r) for(int i=l;i<r;i++)
#define RREP(i,l,r) for(int i=l;i>=r;i--)
#define rrep(i,l,r) for(int i=1;i>r;i--)
#define read(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<11
using namespace std;

int n,k,num;
const int mod=2008;
struct mat
{
    ll d[33][33];
}A,E;
map<int,int>m;

mat multi(mat a,mat b)
{
    mat ans;
    REP(i,1,num)
    {
        REP(j,1,num)
        {
            ans.d[i][j]=0;
            REP(k,1,num)
                if(a.d[i][k]&&b.d[k][j])
                    ans.d[i][j]=(ans.d[i][j]+(ll)a.d[i][k]*b.d[k][j])%mod;
        }
    }
    return ans;
}

mat add(mat a,mat b)
{
    mat ans;
    REP(i,1,num)
        REP(j,1,num)
          ans.d[i][j]=(a.d[i][j]+b.d[i][j])%mod;
    return ans;
}

mat quickmulti(mat a,int n)
{
    if(n==0) return E;
    if(n==1) return a;
    mat ans=E;
    while(n)
    {
        if(n&1)
        {
            n--;
            ans=multi(ans,a);
        }
        else
        {
            n>>=1;
            a=multi(a,a);
        }
    }
    return ans;
}

mat solve(mat a,int n)
{
    if(n==1) return a;
    mat ans=solve(a,n/2);
    mat res=add(ans,multi(quickmulti(a,n/2),ans)); 
    if(n%2==1) res=add(res,quickmulti(a,n));
    return res;
}

int main()
{
    CLR(E.d);
    rep(i,0,33)
      E.d[i][i]=1;
    while(~scanf("%d",&n))
    {
        CLR(A.d);
        m.clear();
        num=0;
        rep(i,0,n)
        {
            int p1,p2;
            read(p1);read(p2);
            if(!m[p1]) m[p1]=++num;
            if(!m[p2]) m[p2]=++num;
            ++A.d[m[p1]][m[p2]];
        }
        scanf("%d",&k);
        rep(i,0,k)
        {
            int v1,v2,t1,t2;
            scanf("%d%d%d%d",&v1,&v2,&t1,&t2);
            if(!t1) t1++;
            v1=m[v1],v2=m[v2];
            if(t1<=t2)
            {
                mat ans=solve(A,t2-t1+1);
                mat m1=quickmulti(A,t1-1);
                ans=multi(ans,m1);
                printf("%I64d\n",ans.d[v1][v2]);
            }
            else
                printf("0\n");
        }
    }
}

AC代碼2：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<ctime>
#include<cstdlib>
#include<iomanip>
#include<utility>
#define pb push_back
#define mp make_pair
#define CLR(x) memset(x,0,sizeof(x))
#define _CLR(x) memset(x,-1,sizeof(x))
#define REP(i,n) for(int i=0;i<n;i++)
#define Debug(x) cout<<#x<<"="<<x<<" "<<endl
#define REP(i,l,r) for(int i=l;i<=r;i++)
#define rep(i,l,r) for(int i=l;i<r;i++)
#define RREP(i,l,r) for(int i=l;i>=r;i--)
#define rrep(i,l,r) for(int i=1;i>r;i--)
#define read(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<11
using namespace std;

int n,k,num;
const int mod=2008;
struct mat
{
    int d[33][33];
} A,E;
map<int,int>m;

mat multi(mat a,mat b)
{
    mat ans;
    rep(i,0,num)
    {
        rep(j,0,num)
        {
            ans.d[i][j]=0;
            rep(k,0,num)
                if(a.d[i][k]&&b.d[k][j])
                    ans.d[i][j]=(ans.d[i][j]+(ll)a.d[i][k]*b.d[k][j]%mod)%mod;
        }
    }
    return ans;
}

mat add(mat a,mat b)
{
    mat ans;
    rep(i,0,num)
        rep(j,0,num)
            ans.d[i][j]=(a.d[i][j]+b.d[i][j])%mod;
    return ans;
}

mat quickmulti(mat a,int n)
{
    mat ans=E;
    while(n)
    {
        if(n&1) ans=multi(ans,a);
        a=multi(a,a);
        n>>=1;
    }
    return ans;
}

mat solve(mat a,int n)
{
    if(n<=0) return quickmulti(a,0);
    ll b=(n+1)/2;
    mat ans=solve(a,b-1);
    mat res=add(ans,multi(quickmulti(a,b),ans));
    if(n%2==0) res=add(res,quickmulti(a,n));
    return res;
}

int main()
{
    CLR(E.d);
    rep(i,0,33)
      E.d[i][i]=1;
    while(~scanf("%d",&n))
    {
        CLR(A.d);
        m.clear();
        num=0;
        REP(i,1,n)
        {
            int p1,p2;
            scanf("%d%d",&p1,&p2);
            if(!m[p1]) p1=m[p1]=++num;
            else p1=m[p1];
            if(!m[p2]) p2=m[p2]=++num;
            else p2=m[p2];
            ++A.d[p1-1][p2-1];
        }
        scanf("%d",&k);
        rep(i,0,k)
        {
            int v1,v2,t1,t2;
            scanf("%d%d%d%d",&v1,&v2,&t1,&t2);
            if(!m[v1]||!m[v2])   //這種AC的姿勢必須寫上這個判斷，如果不寫這個判斷就會WA..總之資料太神了。。orzorzorzorz
            {
                printf("0\n");
                continue;
            }
            v1=m[v1]-1,v2=m[v2]-1;
            mat ans=solve(A,t1-1);
            mat ans1=solve(A,t2);
            printf("%d\n",(ans1.d[v1][v2]-ans.d[v1][v2]+mod)%mod);
        }
    }
}

神資料。。orzorzorzorz

圖論 矩陣 ACM algorithm HDU 矩陣快速幂
上一篇: HDU 4686解題報告 Arc of Dream
下一篇: HDU 2602 解題報告

繼續閱讀