赛时第一眼以为是虫食算那样的题。
赛时脑子抽了,想了一个最优解?
性质:正确状态必然是其中一个状态操作一次变换来的。
这很显然,所有的状态都应该能被正确状态操作一次后变换而成。反过来,所有的状态操作一次后都可以变换成正确状态。
于是可以枚举所有第一个状态操作一次后产生的状态,再与第 $2-n$ 个状态检验是否能通过一次操作来变换过去。
先考虑如何枚举第一个状态操作一次的状态。
1 只转其中一个。
$0-9$ 中除了与原来状态一样的,都可以是一次操作后的状态。
2 转相邻的两个。
题目中说要转相同幅度,所以枚举转的幅度即可,让两个数字都加上转动幅度即可。
注意:当转完后的数字 $>9$ 时,需要让其减掉 $10$ 。
然后考虑如何检验。
1. 两个状态中不同的数字的个数 $ >2 $ 。
因为一次操作最多转相邻的两个,所以这样则必然不能通过一次操作达到。
2. 不同的数字的个数为 $1$ 。
那就转那一个数字就可以,所以必然能通过一次操作达到。
3. 不同的数字的个数为 $2$ 。
若这两个不相同的数字的位置不相邻,则不能通过一次操作达到。
若相邻,则要看其转动的幅度是否相同,让检验的和被检验的两个数字相减即可,检验差是否相同。
注意:若差为负数,那就让差加上 $10$ 。
时间复杂度 $O(n)$ 。
赛时code
#include <iostream>
#include <cstdio>
using namespace std;
int a[10][5], n;
int ans, b[7];
bool check()
{
for (int i=1;i<n;i++)
{
int d = 0;
for (int j=0;j<5;j++)
if (b[j] != a[i][j])
d ++;
if (d > 2 || d == 0)
return false;
if (d == 1)
continue;
for (int j=0;j<4;j++)
if (b[j] != a[i][j])
{
if (b[j + 1] == a[i][j + 1])
return false;
int c1 = b[j] - a[i][j], c2 = b[j + 1] - a[i][j + 1];
if (c1 < 0)
c1 += 10;
if (c2 < 0)
c2 += 10;
if (c2 != c1)
return false;
break;
}
}
return true;
}
int main()
{
cin >> n;
for (int i=0;i<n;i++)
for (int j=0;j<5;j++)
cin >> a[i][j];
for (int i=0;i<5;i++)
b[i] = a[0][i];
for (int i=0;i<5;i++) // turn one
{
for (int j=0;j<10;j++)
if (j != a[0][i])
{
b[i] = j;
if (check())
ans ++;
}
b[i] = a[0][i];
}
for (int i=0;i<4;i++) // turn two
{
b[i] = a[0][i];
for (int j=1;j<10;j++)
{
b[i] = a[0][i] + j;
if (b[i] > 9)
b[i] -= 10;
b[i + 1] = a[0][i + 1] + j;
if (b[i + 1] > 9)
b[i + 1] -= 10;
if (check())
ans ++;
}
b[i] = a[0][i];
}
printf("%d\n", ans);
return 0;
}
/*
it takes me about 90 minutes!!!
100 ?!
*/
写这个耗费我近一个半小时。