【NOIp2004提高组】食虫算题解

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：

 43#9865#045

+  8468#6633

 44445509678

其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是555和333，第二行的数字是555。

现在，我们对问题做两个限制：

首先，我们只考虑加法的虫食算。这里的加法是$N$进制加法，算式中三个数都有$N$位，允许有前导的$0$。

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

 BADC

+CBDA

______

 DCCC

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

输入输出格式

输入格式：

包含四行。

第一行有一个正整数$N(N \le 26)$

后面的三行，每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有$N$位。

输出格式：

一行，即唯一的那组解。

解是这样表示的：输出$N$个数字，分别表示$…A,B,C,…$所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。

输入输出样例

输入样例#1：

5

ABCED

BDACE

EBBAA

输出样例#1：

1 0 3 4 2

说明

对于30％的数据，保证有$N \le 10$

对于50％的数据，保证有$N \le 15$

对于全部的数据，保证有$N \le 26$

题目链接

题解

对于这道题，很明显可以总结出它的模型，将问题转化为已知$N$元一次方程组以及$N$元不等式的求解问题。也就是说可以通过高斯消元来解决。

在这之前，要先知道高斯消元是什么。

答：高斯消元就是加减消元。

对于一个$N$元方程组，我们可以将它转化为矩阵乘法的形式，或者一个矩阵的形式。比如说下面这个方程组：

$ x +y = 10 x - 3y = 6$

可将其转化为：

\[\begin{Bmatrix}1 & 1\\1 & -3\end{Bmatrix}\begin{Bmatrix}x & y\end{Bmatrix} =\begin{Bmatrix}10 \\ 6\end{Bmatrix}（1）
\]

也可转化为

\[\begin{matrix}1 & 1 & 10 \\1 & -3 & 6\end{matrix}
\]

而后，将每一层的方程处理后与下面的方程相加消去一个未知数，一般情况下，当消除第$i$层时，消掉第$i$个未知数。

这样消元的矩阵呈现出倒三角型，如图所示：

\[\begin{Bmatrix}a_{11} & a_{12} & a_{13} & a_{14} & ... & a_{1n} \\ a_{21} & a_{22} & a_{23} & a_{24} & ... & a_{2n} \\ ...&...&...&...&...&... \\ a_{n1} &...& ... &...&...& a_{nn} \end{Bmatrix} （2）
\]

\[\begin{Bmatrix}a_{11} & a_{12} & a_{13} & a_{14} & ... & a_{1n} \\ 0 & a_{22} & a_{23} & a_{24} & ... & a_{2n} \\ 0 & 0 & a_{33} & ... & ...&a_{3n} \\...&...&...&...&...&... \\ 0 & 0 & 0 & 0 & ...& a_{nn} \end{Bmatrix}\begin{Bmatrix}c_1 \\ c_2 \\ c_3 \\ ...\\ c_n\end{Bmatrix} = \begin{Bmatrix}b_1 \\ b_2 \\ b_3 \\ ... \\ b_n \end{Bmatrix} (3)
\]

如果不好理解，我们可以先模拟下上述过程，先举个例子：

在这里要注意一下，我们往往是将这个系数绝对值最大的方程转移到被减的这一行，这样就可以减小误差

所以我们先将矩阵变成这样

然后将方程化简，使要被消去的未知数系数为1，方便后面消元

1 -8/7 10/7 3

4 -5 6 12

1 -2 3 6

然后与下面的式子加减消元，消去未知数，即系数化为0；

1 -8/7 10/7 3

0 -3/7 2/7 0

0 -6/7 11/7 3

然后这时候第一列就被化简完成

第二第三行同理，最终会被化简为上图$(3)$式

那么我们可以根据上述的过程模拟出高斯消元代码：

#include<bits/stdc++.h>

const double EPS = 1e-8;

double b[111][111];

int n;

int main(){

  scanf("%d", &n);

  for(int i = 0; i < n; i++){ //方便起见，我们从0开始编号

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

      scanf("%lf", &b[i][j]);

    scanf("%lf",&b[i][n]);

  }

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

    int pos = i;

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

      if(fabs(b[i][j]-b[pos][i]) <= EPS) pos = j; //调整矩阵

    for(int j = 0; j <= n; j++) std::swap(b[i][j], b[pos][j]);

    if(fabs(b[i][i]) <= EPS){ printf("No Solution\n"); return 0;}

    for(int j = i+1; j <= n; j++) b[i][j] /= b[i][i];  // 化简方程

    for(int j = 0; j < n; j++) if(i != j) for(int k = i+1; k <= n; k++) b[j][k] -= b[j][i]*b[i][k]; // 消元

}

  for(int i = 0; i < n; i++) printf("%.2lf\n", b[i][n]);

  return 0;

}

再回到这道题，就很容易得出解了。

与高斯消元不同的是，这里的解也是未知数，但是未知数的范围是确定的，所以要列出矩阵

根据样例可以列出矩阵：

\[\begin{bmatrix} -1 & 0 & 0 & 1 & 1 \\ -1 & 0 & 1 & 0 & 1 \\ 1 & -1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & -1 \end {bmatrix} \begin{bmatrix} A\\B\\C\\D\\E \end {bmatrix} = \begin{bmatrix} {0\ \ \ \ \ or\ \ \ \ \ n }\\{0\ \ or\ \ -1\ \ or\ \ n-1}\\{0\ \ or\ \ -1\ \ or\ \ n-1}\\{0\ \ or\ \ -1\ \ or\ \ n-1}\\{0\ \ or\ \ -1\ \ or\ \ n-1} \end {bmatrix}
\]

由此可以得出代码：（由于博主比较弱，代码一旦超过50行就会引起不适，故高斯消元部分压了部分行。

#include<bits/stdc++.h>

#define MAXN 26

int n,equ,var,d[MAXN+10],x[MAXN+10];bool vis[MAXN+10];char s[3][MAXN+10];

typedef int matrix[MAXN+10][MAXN+10];matrix a,g;

int gcd(int a,int b) {	int t;	while(b) {t=a%b;a=b;b=t;}	return a;}

bool check() {

	memset(vis,0,sizeof vis);

	for(int i=1; i<=n; i++) {		x[i]=0;

		for(int j=1; j<=n; j++)	x[i]+=g[i][j]*d[j];

		if(x[i]%a[i][i]||x[i]/a[i][i]<0||x[i]/a[i][i]>=n||vis[x[i]/a[i][i]]) return 0;

		x[i]/=a[i][i];		vis[x[i]]=1;

	}

	return 1;

}

void dfs(int i) {

	if(i==n) {

		if(check()) {

			for(int i=1; i<n; i++)	printf("%d ",x[i]);

			printf("%d\n",x[n]);   exit(0);

		}return ;

	}d[i]=1;	dfs(i+1);

        d[i]=0;	dfs(i+1);

}

int main() {

	scanf("%d", &n);	scanf("%s%s%s",s[0],s[1],s[2]);

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

		for(int j=0; j<2; j++) a[n-i][s[j][i]-'A'+1]++;

		a[n-i][s[2][i]-'A'+1]--;

	}

	for(int i=1; i<=n; i++)   g[i][i]=n,g[i][i-1]=-1;

	g[1][0]=0;	equ=var=n;

	for(int row=1, col=1; row<=equ&&col<=var; row++,  col++) {   int mxr=row; // 高斯消元，压行写法, 方便从字符中处理。

		for(int i=row+1; i<=equ; i++)

			if(abs(a[i][col])>abs(a[mxr][col])) mxr=i;

		if(mxr!=row)	std::swap(a[row],a[mxr]), std::swap(g[row],g[mxr]);

		if(!a[row][col]) {row--;continue;}

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

			if(i!=row&&a[i][col]) {

				int lcm=a[i][col]/gcd(a[i][col],a[row][col])*a[row][col];

				int t1=lcm/a[i][col],t2=lcm/a[row][col];

				for(int j=1; j<=var; j++) {

					g[i][j]=t1*g[i][j]-t2*g[row][j];

                                        a[i][j]=t1*a[i][j]-t2*a[row][j];

				}

			}

	}

        dfs(1);

}