首页 > ACM题库 > HDU-杭电 > hdu 2605 Snake-数论-解题报告]C++
2014
02-12

hdu 2605 Snake-数论-解题报告]C++

Snake

问题描述 :

Snake is a popular game , and I believe most of us had played it . The Original game is that you can control a snake to eat the magic bean and after the snake eat one magic bean , the length of the snake’s body will get longer .But today we are talking about a new game. These are the rules of the new Snake Game :
1. The length of the snake’s body won’t change even though it eat a magic bean.
2. Some pairs of the beans have a relation , that is, one of them can not be eaten until another one had been eaten . We call the latter “the key bean” . For example , if A can’t be eaten until B had been eaten ,we say “B is the key bean of A”. (That means when A can’t be eaten , the snake can not move into the grid where A is.)
3. The snake could not move to a wall or its body.Befor it move,it will chooses an adjacent vacant square of its head,which is neither a stone nor occupied by its body.
Figure 1 and figure2 shows how the snake move


Figure 1


Figure 2

输入:

The first line contain a integer T (T <= 10).Followed by T cases. Each case contain five parts.
The first part: six integers ,H,W,L,K,R,N,(H <= 20 , W <= 20 , L <= 8 , K <= 7 ) means the height of the map , the width of the map , the length of the snake’s body, the number of the magic beans . the number of the relations , the number of the wall respectively.
The second part: L lines , each line contain two integer hi ,wi, indicating the original position of each block of snake’s body, from B1(h1,w1) to BL(hL,wL) orderly, where 1<=hi<=H, and 1<=wi<=W,1<=i<=L.
The third part: K lines ,each line contain two integer hi ,wi , indicating the position of each magic bean , from MB1(h1,w1) to MBK(hK,wK) orderly, where 1<=hi<=H, and 1<=wi<=W,1<=i<=K.
The fourth part : R lines , each line contain two integer A ,B means “A is the key bean of B ”. The A and B may appear several times , but “one bean will have only one key bean”.
The fifth part: N lines , each line contain two integer hi ,wi , indicating the position of each wall , from W1(h1,w1) to WN(hN,wN) orderly, where 1<=hi<=H, and 1<=wi<=W,1<=i<=N.

输出:

The first line contain a integer T (T <= 10).Followed by T cases. Each case contain five parts.
The first part: six integers ,H,W,L,K,R,N,(H <= 20 , W <= 20 , L <= 8 , K <= 7 ) means the height of the map , the width of the map , the length of the snake’s body, the number of the magic beans . the number of the relations , the number of the wall respectively.
The second part: L lines , each line contain two integer hi ,wi, indicating the original position of each block of snake’s body, from B1(h1,w1) to BL(hL,wL) orderly, where 1<=hi<=H, and 1<=wi<=W,1<=i<=L.
The third part: K lines ,each line contain two integer hi ,wi , indicating the position of each magic bean , from MB1(h1,w1) to MBK(hK,wK) orderly, where 1<=hi<=H, and 1<=wi<=W,1<=i<=K.
The fourth part : R lines , each line contain two integer A ,B means “A is the key bean of B ”. The A and B may appear several times , but “one bean will have only one key bean”.
The fifth part: N lines , each line contain two integer hi ,wi , indicating the position of each wall , from W1(h1,w1) to WN(hN,wN) orderly, where 1<=hi<=H, and 1<=wi<=W,1<=i<=N.

样例输入:

1
8 9
5 2
1 8
5 2
6 2
6 3
6 4
6 5
4 2
2 6
2 1
2 5
3 5
4 4
4 5
4 6
5 6
5 7
6 7

样例输出:

21

典型的指数型母函数因为最后是取模,所以最后一定有周期,注意周期起始位置不一定从第一个开始实际上该题从>=3开始以20为周期

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;

int cal(int x,int y)  
{  
   int ans=1;  
   while(y)  
   {  
     if(y&1)  
       ans=(ans*x)%100;  
     y>>=1;  
    x=(x*x)%100;  
   }  
   return ans;  
} 
int rr[25];
int main()
{
    __int64 n,nn;
    for(int i=1; i<=20; ++i)
    {
      rr[i]=cal(2,i+20-1);
      rr[i]=rr[i]*rr[i]+rr[i];
      rr[i]%=100;
    }
    while(scanf("%I64d",&n)&&n!=0)
    {
      long long count=0;
      while(n--)
      {
        count++;
        scanf("%I64d",&nn);
        printf("Case %d: ",count);
        if(nn==1) printf("2\n");
        else if(nn==2) printf("6\n");
        else 
        {
          nn=(nn+19)%20+1;
          printf("%d\n",rr[nn]);
        }
      }
      printf("\n");
    }
    return 0;
}

 


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。