欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

算法训练 cNteSahruPfefrlefe C/C++

程序员文章站 2022-07-03 18:30:58
资源限制时间限制:1.0s 内存限制:256.0MB问题描述Preston Digitation是一个对纸牌魔术很专业的魔术师。完美洗牌这件事情Preston不能做得恰到好处。完美洗牌是将52张牌分两半然后完美的交叉起来,所以牌的下半部分最上面的牌将被放在洗牌后的牌顶。如果我们把这些牌标为0(牌顶)-51(牌底),那么一次完美洗牌后的结果会像这样:26 0 27 1 28 2 29 3 30 4 31 5 32 6...51 25Preston发现每次洗牌他最多犯一次错误。例如,...

资源限制

时间限制:1.0s 内存限制:256.0MB

问题描述

	Preston Digitation是一个对纸牌魔术很专业的魔术师。完美洗牌这件事情Preston不能做得恰到好处。完美洗牌是将52张牌分两半
	然后完美的交叉起来,所以牌的下半部分最上面的牌将被放在洗牌后的牌顶。如果我们把这些牌标为0(牌顶)-51(牌底),那么一次
	完美洗牌后的结果会像这样:
	26 0 27 1 28 2 29 3 30 4 31 5 32 6...51 25
	Preston发现每次洗牌他最多犯一次错误。例如,2号牌跟28号牌会互换,结果像这样:
	26 0 27 1 2 28 29 3 30 4 31 5 32 6...51 25
	这些对两个相邻卡牌的交换是Preston犯的唯一一个错误。一次洗牌后,他会很容易发现他在哪里和为什么犯这个错误,但是在几
	次洗牌后这会变得越来越困难。
	他希望你写一个程序来确定他的错误。

输入格式

输入包含多组数据。
  第一行一个整数表示数据组数。
  对于每组数据将有一行52个整数表示经过1到10次洗牌后的牌组。输出格式  对于每组数据,输出这组数据序号。
  接着是洗牌的次数。
  如果没有错误 输出"No error in any shuffle"
  否则,对于每次错误 输出"Error in shuffle N at location M"
  N表示犯错误的洗牌次数,M表示交换的两张牌的位置。洗牌次数从1开始计算,而位置值取第一张牌所在位置(牌顶为0),在上面的例子中,卡牌位置为4和5(编号为2和28)是错误的,所以在这例中我们用4。错误按洗牌次数N递增输出,如果某次洗牌没有错误则不输出它。如果有多种方案,选择错误数最小的方案输出(数据保证有一个最小错误方案)。

样例输入

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

样例输出

Case 1
Number of shuffles = 1
Error in shuffle 1 at location 4
Case 2
Number of shuffles = 1
No error in any shuffle
Case 3
Number of shuffles = 9
Error in shuffle 3 at location 3
Error in shuffle 7 at location 11
Error in shuffle 8 at location 38

数据规模和约定

见题目描述

思路

剪枝
1)构造十次正确交换状态,通过差异函数判断目标需要几次变换才能变为第i次正确交换,差异值不大于当前洗牌数,则说明给出的洗牌次数就是当前统计到的洗牌次数
2)根据前面统计到的洗牌次数,枚举错误去判断。
3)枚举错误时,每次都计算一次差异值,如果差异值大于剩余洗牌数,则无效,直接剪枝,减少时间开销

代码

#include<cstdio>
#include<memory>
#include<cmath>
#include<cstring>
int go[52], correct[11][52], card[52],next[52], err[11], ans[11];
int n, i, j, dfs, errors, best, cases, s;
/*元素的去向为go[],每次洗牌的正确序列为correct[][],当前洗牌序列为card[52]
下次洗牌序列为next[],第i次洗牌发生错误的位置为err[], 最后得出结果为ans[],差异函数值为dfs,
当前错误总次数为errors,最少错误总次数为best,测试用例编号为cases,测试用例数为s*/
void anti_shuffle(int n)     //反向洗牌
{
	int tmp[52], i;
	for (i = 0; i < 52; i++)
	tmp[correct[n][i]] = next[i]; //反向洗牌后的序列存在临时数组
	 memcpy(next, tmp, sizeof(tmp)); //更新序列
}
int differents(int *a, int *b)//求a和b序列的差异函数值
{
 	int i, j, s;
 	int step[52], go[52];
	memset(step, 0, sizeof(step));
 	for (i = 0; i < 52; i++)
  		go[a[i]] = b[i];
 	s = 0;
 	for(i = 0;i<52;i++)
  		if (!step[i])
  		{
			j = i;
   			while (!step[j])
   			{
   	 			step[j] = 1;
    				j = go[j];
    				s++;
   			}
   			s--;
  		}
 	return s;
}
void trytrytry(int i)  //以递归方式枚举每一次洗牌的错误位置
{
 	int j, save[52];
 	dfs = differents(card, correct[i]);
 	if (dfs > i) return;  //若差异函数值比剩余的洗牌次数大,则停止递归
 	if (!i)
 	{
  		if (errors < best)
  		{
 			best = errors;
   			memcpy(ans, err, sizeof(err));
  		}
  		return;
 	}
	memcpy(save, card, sizeof(card)); //把当前的扑克牌序列保留一份
 	err[i] = -1;             //错误位置为-1,表示这次洗牌没有出错
 	for (j = 0; j < 51; j++)//枚举出错位置
 	{
  		memcpy(next, card, sizeof(card));
  		next[j] += next[j + 1];
  		next[j + 1] = next[j] - next[j + 1];
  		next[j] -= next[j + 1];
  		dfs = differents(next, correct[i]);
  		anti_shuffle(1);
  		memcpy(card, next, sizeof(card));
  		errors++;
  		err[i] = j;
  		if (errors + dfs < best) trytrytry(i - 1);
  		errors--;
 		err[i] = -1;
  		memcpy(card, save, sizeof(card));
 	}
 	memcpy(next, card,sizeof(card));
 	anti_shuffle(1);
 	memcpy(card, next, sizeof(card));
 	trytrytry(i - 1);
 	memcpy(card, save, sizeof(card));
}
int main()
{
 	for (i = 0; i < 52; i++)
 	{
  		go[i] = 26 * (1 - i % 2) + i / 2;  
  		correct[0][i] = i;
	}
 	for (i = 1; i <= 10; i++)  //正确洗牌十次,记录结果
  		for (j = 0; j < 52; j++)
   			correct[i][j] = correct[i - 1][go[j]];
 	scanf("%d", &s);
	for (cases = 1; cases <= s; cases++)
 	{
  		for (i = 0; i < 52; i++)
   			scanf("%d", &card[i]);
  		for (i = 0; i < 11; i++)
  		{
   			dfs = differents(card, correct[i]);
   			if (dfs <= i)  //若差异函数值不大于洗牌数,说明给出的扑克牌
    				break;     //序列的洗牌次数就是当前的洗牌次数
  		}
  		printf("Case %d\nNumber of shuffles = %d\n", cases, i);
  		if (!dfs)
		{
		 	puts("No error in any shuffle\n");
		   	continue;
		 }
		 n = i;
  		best = dfs + 1;
  		errors = 0;
  		trytrytry(i);
	  	for (i = 1; i <= n; i++)
	  		 if (ans[i] > -1)
				 printf("Error in shuffle %d at location %d\n", i, ans[i]);
	 	 puts("");
	 }
	 return 0;
}
	

本文地址:https://blog.csdn.net/weixin_42418736/article/details/107251556