首页 > ACM题库 > HDU-杭电 > HDU 4350-Card-模拟-[解题报告]HOJ
2015
05-23

HDU 4350-Card-模拟-[解题报告]HOJ

Card

问题描述 :

Bearchild is playing a card game with himself. But first of all, he needs to shuffle the cards. His strategy is very simple: After putting all the cards into a single stack,
he takes out some cards in the middle, from the L-th to the R-th when counting from top to bottom, inclusive, and puts them on the top. He repeats this action again
and again for N times, and then he regards his cards as shuffled.

Given L,R and N, and the initial card stack, can you tell us what will the card stack be like after getting shuffled?

输入:

First line contains an integer T(1 <= T <= 1000), which is the test cases.
For each test case, first line contains 52 numbers(all numbers are distinct and between 1 and 52), which is the card number of the stack, from top to bottom.
Then comes three numbers, they are N, L and R as described. (0<=N<=109, 1<=L<=R<=52)

输出:

First line contains an integer T(1 <= T <= 1000), which is the test cases.
For each test case, first line contains 52 numbers(all numbers are distinct and between 1 and 52), which is the card number of the stack, from top to bottom.
Then comes three numbers, they are N, L and R as described. (0<=N<=109, 1<=L<=R<=52)

样例输入:

1
13 2 10 50 1 28 37 32 30 46 19 47 33 41 24 52 27 42 49 18 9 48 23 35 31 8 7 12 6 5 3 22 43 36 51 40 26 4 44 
17 39 38 15 14 25 16 29 20 21 45 11 34
902908328 38 50

样例输出:

Case #1: 26 4 44 17 39 38 15 14 25 16 29 20 21 45 13 2 10 50 1 28 37 32 30 46 19 47 33 41 24 52 27 42 49 18 
9 48 23 35 31 8 7 12 6 5 3 22 43 36 51 40 11 34

来源:http://acm.hdu.edu.cn/showproblem.php?pid=4350

题意:有52张扑克,每次从中间抽取一部分放到前面,问经过n次抽取后,扑克的顺序是什么。

思路:模拟题,我们可以先求出来循环节,之后n对循环节取余,之后再暴力就可以了,签名题。话说,今天被uestc虐的好惨。。

代码:

#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <cstdio>
#include <algorithm>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
int num[55],num2[55];
const int N = 52;
bool isok(int dit[55],int rp){
	bool flag = true;
	for(int i = 1; i <= rp; ++i){
		if(dit[i] != num[i]){
		  flag = false;
		  break;
		}
	}
	return flag;
}
__int64 fun(int lp,int rp){
	int num3[55];
	int k = 0;
	__int64 cnt = 0;
	while(1){
		k = 1;
	  for(int i = lp; i <= rp; ++i)
		 num3[k++] = num2[i];
	  for(int i = 1;i < lp; ++i)
		  num3[k++] = num2[i];
	  cnt++;
	  if(isok(num3,rp)){
	    break;
	  }
	  for(int i = 1; i <= rp; ++i)
		  num2[i] = num3[i];
	}
	return cnt;
}
void solve(__int64 x,int lp,int rp){
	int dit[55],dit2[55];
	for(int i = 1; i <= 52; ++i)
		dit[i] = num[i];
	while(x--){
	  int k = 1;
	  for(int i = lp; i <= rp; ++i)
		  dit2[k++] = dit[i];
	  for(int i = 1; i < lp ;++i)
		  dit2[k++] = dit[i];
	  for(int i = 1; i <= rp; ++i)
		  dit[i] = dit2[i];
	}
	printf("%d",dit[1]);
	for(int i = 2; i <= rp; ++i)
		printf(" %d",dit2[i]);
	for(int i = rp+1;i <= 52; ++i)
		printf(" %d",num[i]);
	printf("\n");
}
int main(){
	//freopen("1.txt","r",stdin);
	int numcase;
	scanf("%d",&numcase);
	for(int ca = 1; ca <= numcase; ++ca){
	  CLR(num,0);
	  CLR(num2,0);
	  for(int i = 1; i <= N; ++i)
		  scanf("%d",&num[i]);
	  int lp,rp;
	  __int64 cnt;
	  scanf("%I64d%d%d",&cnt,&lp,&rp);
	  for(int i = 1; i <= rp; ++i)
		  num2[i] = num[i];
	  __int64 x = fun(lp,rp);
	 // printf("x = %d\n",x);
	  __int64 y = cnt % x;
	  printf("Case #%d: ",ca);
	  if(y == 0){
		  printf("%d",num[1]);
	    for(int i = 2; i <= N; ++i)
			printf(" %d",num[i]);
		printf("\n");
		continue;
	  }
	  solve(y,lp,rp);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wmn_wmn/article/details/7848692