奥运

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

 

 

Recommend

lcy

 

1.离散

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

  接下来n行每行读入两个数字 p1，p2 表示城市p1到p2

有道路，并不表示p2到p1有道路 (0<=p1,p2<2^32)

 

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             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
           
            num) 26 r=mid-1; 27 else if(tom[mid]
            
             =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\n"); 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\n",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 }//离散化 finsh101 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 }
            
           
          
         
        
       
      

 

 

 |   |  |