hdu 2254 奥运 **

奥运

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1936 Accepted Submission(s): 491

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

1.离散

2.注意重边的情况时，M_hxl.mat[l][r]++;

接下来n行每行读入两个数字 p1，p2 表示城市p1到p2有道路，并不表示p2到p1有道路 (0<=p1,p2<2^32)

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<algorithm>
  6 using namespace std;
  7 
  8 
  9 struct node
 10 {
 11     int mat[33][33];
 12 }M_hxl,qqq[10002];
 13 struct st
 14 {
 15     int l;
 16     int r;
 17 }f[10003];
 18 int hxl[20005],tom[20005],hlen,tlen;
 19 
 20 int EF(int l,int r,int num)//二分查找
 21 {
 22     int mid=(l+r)/2;
 23     while(l<r)
 24     {
 25         if(tom[mid]>num)
 26         r=mid-1;
 27         else if(tom[mid]<num)
 28         l=mid+1;
 29         else return mid;
 30         mid=(l+r)/2;
 31     }
 32     return mid;
 33 }
 34 
 35 struct node cheng(node cur,node now,int n)
 36 {
 37     node ww;
 38     memset(ww.mat,0,sizeof(ww.mat));
 39     int i,j,k;
 40     for(i=1;i<=n;i++)
 41     for(k=1;k<=n;k++)
 42     if(cur.mat[i][k])
 43     {
 44         for(j=1;j<=n;j++)
 45         if(now.mat[k][j])
 46         {
 47             ww.mat[i][j]=ww.mat[i][j]+(cur.mat[i][k]*now.mat[k][j])%2008;
 48             if(ww.mat[i][j]>=2008)
 49             ww.mat[i][j]%=2008;
 50         }
 51     }
 52     return ww;
 53 }
 54 
 55 void make_ini(int n,int m)
 56 {
 57     int x,y,start,end,i,l,r,j;
 58     int sum;
 59     for(i=1;i<=m;i++)
 60     {
 61         scanf("%d%d%d%d",&l,&r,&start,&end);
 62         if(start>end)
 63         swap(start,end);
 64         x=EF(1,tlen,l);
 65         y=EF(1,tlen,r);
 66         if(l!=tom[x] || r!=tom[y])//加了更严谨
 67         {
 68             printf("0
");
 69             continue;
 70         }
 71         sum=0;
 72         for(j=start;j<=end;j++)
 73         {
 74             sum=sum+qqq[j].mat[x][y];
 75             if(sum>=2008)
 76             sum%=2008;
 77         }
 78         printf("%d
",sum);
 79     }
 80 }
 81 
 82 int main()
 83 {
 84     int n,m,i,l,r;
 85     while(scanf("%d",&n)>0)
 86     {
 87         hlen=tlen=0;
 88         for(i=1;i<=n;i++)
 89         {
 90             scanf("%d%d",&f[i].l,&f[i].r);
 91             hxl[++hlen]=f[i].l;
 92             hxl[++hlen]=f[i].r;
 93         }
 94         sort(hxl+1,hxl+1+hlen);
 95         tom[1]=hxl[1];tlen=1;
 96         for(i=2;i<=hlen;i++)
 97         {
 98             if(hxl[i]!=hxl[i-1])
 99             tom[++tlen]=hxl[i];
100         }//离散化 finsh
101         memset(M_hxl.mat,0,sizeof(M_hxl.mat));
102         for(i=1;i<=n;i++)//构建矩阵
103         {
104             l=EF(1,tlen,f[i].l);
105             r=EF(1,tlen,f[i].r);
106             M_hxl.mat[l][r]++;//这个...！！题目什么意思么。
107         }
108         qqq[1]=M_hxl;
109         for(i=2;i<=10000;i++)
110         qqq[i]=cheng(qqq[i-1],M_hxl,n);
111         scanf("%d",&m);
112         make_ini(n,m);
113     }
114     return 0;
115 }

Statistic | Submit | Discuss | Note