算法训练 cNteSahruPfefrlefe C/C++
- 作者: 愿意吧
- 来源: 51数据库
- 2021-07-12
资源限制
时间限制：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;
}
