首页 > ACM题库 > HDU-杭电 > HDU 4566-Circle Game[解题报告]HOJ
2015
07-25

HDU 4566-Circle Game[解题报告]HOJ

Circle Game

问题描述 :

  You must have some knowledge with circle games in ACM problems, such as Joseph Ring problem. Today we are going to introduce a new circle game described as follows. There is a circle which contains M points, numbered from 0 to M-1. At first, n students stand in different points of the circle. It is possible that more than one student stand in the same point. For each second, each student moves one step forward in clockwise direction. The following picture gives us an example of that M equals to 8 and n equals to 3. Initially, the first student S1 stands in the point 0, the second student S2 stands in the point 2 and the third student stands in the point 7. After 2 seconds, they will change their positions as the right part of the picture.
So Easy!

At the beginning of the game, Tracy writes down the positions of all students. Then he will go to sleep and students will abide by the above rules to make this game run until Tracy wake up. After a period of time, Tracy wakes up. He finds it is very hard to identify where the first student S1 stands in and where the second student S2 stands in and so on, because all students are the exactly similar and unable to be distinguished. So Tracy records all the positions of students and writes down the XOR sum of these positions (The XOR sum of an array A means A[0] xor A[1] xor … A[n-2] xor A[n-1] and xor is the exclusive or operation, for example 0111 xor 1011 = 1100). Now Tracy wants you to help him to know how many seconds he had slept. To simplify the problem, the number of points is always a power of 2 like 2m.
Furthermore, Tracy knows that the time he slept is not greater than T. Please note that the time Tracy slept must be greater than zero. There may have many different periods of time corresponding with the above conditions.

输入:

  There are several test cases, each test case firstly contains four integers n, m, S, T. S is the XOR sum of students’ positions when Tracy wakes up. Another 3 integers n, m, T are described as the above. Then n integers will follow in the next line, which represent the positions of students initially. The input will finish with the end of file.
0 < n <= 100000, 0 < m <= 50, 0 <= S< 250, 0 < T <= 1016 and the student position is in the range [0, 2m).

输出:

  There are several test cases, each test case firstly contains four integers n, m, S, T. S is the XOR sum of students’ positions when Tracy wakes up. Another 3 integers n, m, T are described as the above. Then n integers will follow in the next line, which represent the positions of students initially. The input will finish with the end of file.
0 < n <= 100000, 0 < m <= 50, 0 <= S< 250, 0 < T <= 1016 and the student position is in the range [0, 2m).

样例输入:

3 3 7 5
0 2 7
5 3 7 5
1 2 3 4 5
4 4 0 10
1 3 5 7
6 5 18 100
22 10 18 20 2 10

样例输出:

1
0
4
50
Hint

For the first test case, the following table explains that only “2 seconds” matched the restrictions.

So Easy!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <vector>
#include <ctime>
using namespace std;

typedef long long LL;
const int N = 100000;
const int M = 50;
const LL MAXS = 1LL<<50;
const LL MAXT = (LL)1e16;

inline LL two( int x ) { return 1LL<<x; }

// f means <=, g means >
LL  f[M+1][N+5], g[M+1][N+5], a[N+5];
int rank[2][2][N+5];
int n , m;
LL  s;

void solve( LL t , LL &ans1, LL &ans2) {
   fill( f[0], f[0]+n+1, 0 );
   fill( g[0], g[0]+n+1, 0 );
   f[0][0] = 1;
   int bits[55], bitt[55];
   for( int i = 0 ; i < m; ++i ) {
        bits[i] = (s&two(i))>0;
        bitt[i] = (t&two(i))>0;
   }

   rank[0][0][0] = n;
   rank[0][1][0] = 0;
   for( int i = 1; i <= n; ++i ) {
        rank[0][0][i] = i-1;
   }

   for( int i = 1; i <= m; ++i ) {
        int cur = i&1, pre = cur^1 ;
        fill( f[i], f[i]+n+1, 0 );
        fill( g[i], g[i]+n+1, 0 );

        // radix sort, from large to small
        for( int j = 0 ; j < 2; ++j ) rank[cur][j][0] = 0;
        for( int j = 1 ; j >= 0; –j ) {
             for( int k = 1 ; k <= rank[pre][j][0]; ++k ) {
                  int idx = rank[pre][j][k];
                  if( a[idx] & two(i-1) ) rank[cur][1][ ++rank[cur][1][0] ] = idx ;
                  else rank[cur][0][ ++rank[cur][0][0] ] = idx ;
             }
        }

        int oneCnt = 0, curOnes = rank[cur][1][0], curZeros = rank[cur][0][0];
        // update i bit with i-1 bit
        for( int j = 0; j <= n; ++j ) {
             int idx = -1, presize1 = rank[pre][1][0];
             if( j > presize1 ) {
                 idx = rank[pre][0][j-presize1];
             } else {
                  if( j > 0 ) idx = rank[pre][1][j];
             }

             // when j = 0 ==> idx = -1;
             if( idx != -1 && (a[idx]&two(i-1)) != 0 ) {
                 ++oneCnt;
             }
             int tBit = bitt[i-1];

             // do nothing
             int curOne = curOnes + j – 2*oneCnt;
             if( (curOne&1) == bits[i-1] ) {
                 if( tBit == 0 ) {
                     f[i][ oneCnt ] += f[i-1][j];
                     g[i][ oneCnt ] += g[i-1][j];
                 } else {  // less than
                     f[i][ oneCnt ] += f[i-1][j]+g[i-1][j];
                 }
             }

             // add 1<<(i-1);
             curOne = curZeros – j + 2*oneCnt;
             int nextOne = j + curOnes – oneCnt;
             if( (curOne&1) == bits[i-1] ) {
                 if( tBit == 0 ) {
                     g[i][ nextOne ] += g[i-1][j] + f[i-1][j];
                 } else {  // less than
                     f[i][ nextOne] += f[i-1][j];
                     g[i][ nextOne] += g[i-1][j];
                 }
             }
        }

        //for( int j = 0; j <= n; ++j )  cout<<i<<” “<<j<<” “<<f[i][j]<<” “<<g[i][j]<<endl;
   }
   ans1 = ans2 = 0;
   for( int i = 0 ; i <= n; ++i ) {
        ans1 += f[m][i];
        ans2 += g[m][i];
   }
   ans2 += ans1;
   return ;
}

int main() {
    LL  t;
    //freopen(“CircleGame.in”,”r”,stdin);
    //freopen(“large.out”,”w”,stdout);
    int start = clock();
    //cout<<MAXT<<” “<<MAXS<<endl;
    while( scanf(“%d%d%lld%lld”,&n,&m,&s,&t) != EOF ) {
           //assert( n > 0 && n <= N );
           //assert( m > 0 && m <= M );
           //assert( s >= 0 && s < MAXS );
           //assert( t > 0 && t <= MAXT );
           if( t > MAXT ) {
               cerr<<t<<” “<<MAXT<<endl;
           }
           LL x = 0;
           for( int i = 0 ; i < n; ++i ) {
                scanf(“%lld”,&a[i]);
                x ^= a[i];
                //assert( a[i] >= 0 && a[i] < 1LL<<m );
           }

           LL M = 1LL << m, loops = t/M;
           LL ans1, ans2;
           solve( t%M ,ans1, ans2);
           loops *= ans2;
           loops += ans1;
           if( x == s ) loops–;
           printf(“%lld\n”, loops);
           //printf(“ans1=%lld %lld\n”, ans2, loops);
    }
    //printf(“%lf\n”,(clock()-start)*1.0/CLOCKS_PER_SEC);
    return 0;
}

 

参考:http://blog.csdn.net/spark_007/article/details/9017257