NOIP2004虫食算

描述

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045
+ 8468#6633
= 44445506678
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。

现在，我们对问题做两个限制：
首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。

其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。

BADC
+ CRDA
= DCCC
上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解

格式

输入格式

输入包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。

输出格式

输出包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。

样例1

样例输入1[复制]

5 ABCED BDACE EBBAA

1
2
3
4

5
ABCED
BDACE
EBBAA

样例输出1[复制]

1 0 3 4 2

1

1 0 3 4 2

限制

每个测试点1s

题解

这个随便搜索一下就有90了。。。

然后加个剪枝
判断还未枚举到的列，若有一列3个字母都确定了，但有无进位都不满足，说明当前的字母顺序错误，直接EXIT.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<queue>
#include<map>
#define pa pair<int,int>
#define mod 1000000007
#define inf 1000000000
#define ll long long
#define dfsnxt(x,y,v) y==2?dfs(x-1,1,v):dfs(x,y+1,v)
using namespace std;
int n,mx,v[30],ans[30];
bool flag,used[30];
int a[30],b[30],c[30];
char ch[30];
void dfs(int x,int y,int val)
{
	for(int i=1;i<=x;i++)
	{
		int t1=v[a[i]],t2=v[b[i]],t3=v[c[i]];
		if(t1==-1||t2==-1||t3==-1)continue;
		if(((t3-(t1+t2))%n+n)%n>mx)return;
	}
	if(flag)return;
	if(x==0)
	{
		for(int i=0;i<n;i++)ans[i]=v[i];
		flag=1;
		return;
	}
	if(y==1)
	{
		if(v[a[x]]!=-1)
			dfsnxt(x,y,val);
		else 
			for(int i=n-1;i>=0;i--)
				if(!used[i])
				{
					used[i]=1;
					v[a[x]]=i;
					dfsnxt(x,y,val);
					v[a[x]]=-1;
					used[i]=0;
				}
	}
	else 
	{
		int t1=v[a[x]],t2=v[b[x]],res=v[c[x]];
		if(v[b[x]]!=-1)
		{
			int sum=t1+t2+val;
			if(sum%n==res)
				dfsnxt(x,y,sum/n);
			else if(res==-1)
			{
				used[sum%n]=1;
				v[c[x]]=sum%n;
				dfsnxt(x,y,sum/n);
				v[c[x]]=-1;
				used[sum%n]=0;
			}
		}
		else 
			for(int i=n-1;i>=0;i--)
				if(!used[i])
				{
					int sum=t1+i+val;
					if(sum%n!=res&&res!=-1)continue;
					if(res==-1)
					{
						if(used[sum%n])continue;
						used[sum%n]=1;v[c[x]]=sum%n;
					}
					used[i]=1;v[b[x]]=i;
					dfsnxt(x,y,sum/n);
					v[b[x]]=-1;used[i]=0;
					if(res==-1)
					{
						used[sum%n]=0;v[c[x]]=-1;
					}
				}
	}
}
int main()
{
	scanf("%d",&n);mx=2*n-2;mx/=n;
	scanf("%s",ch+1);
	for(int i=1;i<=n;i++)a[i]=ch[i]-'A';
	scanf("%s",ch+1);
	for(int i=1;i<=n;i++)b[i]=ch[i]-'A';
	scanf("%s",ch+1);
	for(int i=1;i<=n;i++)c[i]=ch[i]-'A';
	memset(v,-1,sizeof(v));
	dfs(n,1,0);
	for(int i=0;i<n;i++)
		printf("%d ",ans[i]);
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<set>

#include<queue>

#include<map>

#define pa pair<int,int>

#define mod 1000000007

#define inf 1000000000

#define ll long long

#define dfsnxt(x,y,v) y==2?dfs(x-1,1,v):dfs(x,y+1,v)

using namespace std;

int n,mx,v[30],ans[30];

bool flag,used[30];

int a[30],b[30],c[30];

char ch[30];

void dfs(int x,int y,int val)

{

for(int i=1;i<=x;i++)

{

int t1=v[a[i]],t2=v[b[i]],t3=v[c[i]];

if(t1==-1||t2==-1||t3==-1)continue;

if(((t3-(t1+t2))%n+n)%n>mx)return;

}

if(flag)return;

if(x==0)

{

for(int i=0;i<n;i++)ans[i]=v[i];

flag=1;

return;

}

if(y==1)

{

if(v[a[x]]!=-1)

dfsnxt(x,y,val);

else

for(int i=n-1;i>=0;i--)

if(!used[i])

{

used[i]=1;

v[a[x]]=i;

dfsnxt(x,y,val);

v[a[x]]=-1;

used[i]=0;

}

else

{

int t1=v[a[x]],t2=v[b[x]],res=v[c[x]];

if(v[b[x]]!=-1)

{

int sum=t1+t2+val;

if(sum%n==res)

dfsnxt(x,y,sum/n);

else if(res==-1)

{

used[sum%n]=1;

v[c[x]]=sum%n;

dfsnxt(x,y,sum/n);

v[c[x]]=-1;

used[sum%n]=0;

}

else

for(int i=n-1;i>=0;i--)

if(!used[i])

{

int sum=t1+i+val;

if(sum%n!=res&&res!=-1)continue;

if(res==-1)

{

if(used[sum%n])continue;

used[sum%n]=1;v[c[x]]=sum%n;

}

used[i]=1;v[b[x]]=i;

dfsnxt(x,y,sum/n);

v[b[x]]=-1;used[i]=0;

if(res==-1)

{

used[sum%n]=0;v[c[x]]=-1;

}

int main()

{

scanf("%d",&n);mx=2*n-2;mx/=n;

scanf("%s",ch+1);

for(int i=1;i<=n;i++)a[i]=ch[i]-'A';

scanf("%s",ch+1);

for(int i=1;i<=n;i++)b[i]=ch[i]-'A';

scanf("%s",ch+1);

for(int i=1;i<=n;i++)c[i]=ch[i]-'A';

memset(v,-1,sizeof(v));

dfs(n,1,0);

for(int i=0;i<n;i++)

printf("%d ",ans[i]);

return 0;

}

hzwer.com _ Home | http://hzwer.com

描述

格式

输入格式

输出格式

样例1

样例输入1[复制]

样例输出1[复制]

限制

题解

分类目录

热门文章

Myfriends

近期评论