題目描述
所謂蟲食算,就是原先的算式中有一部分被蟲子啃掉了,需要我們根據剩下的數字來判定被啃掉的字母。來看一個簡單的例子:
+43a9865a045008468a663344445506978
其中a代表被蟲子啃掉的數字。
根據算式,我們很容易判斷:第一行的兩個數字分别是5和3,第二行的數字是5。
現在,我們對問題做兩個限制:
首先,我們隻考慮加法的蟲食算。這裡的加法是N進制加法,算式中三個數都有N位,允許有前導的0。
其次,蟲子把所有的數都啃光了,我們隻知道哪些數字是相同的,我們将相同的數字用相同的字母表示,不同的數字用不同的字母表示。
如果這個算式是N進制的,我們就取英文字母表午的前N個大寫字母來表示這個算式中的0到N-1這N個不同的數字:但是這N個字母并不一定順序地代表0到N-1)。
輸入資料保證N個字母分别至少出現一次。
+BADCCBDADCCC
上面的算式是一個4進制的算式。很顯然,我們隻要讓ABCD分别代表0123,便可以讓這個式子成立了。
你的任務是,對于給定的N進制加法算式,求出N個不同的字母分别代表的數字,使得該加法算式成立。輸入資料保證有且僅有一組解。
輸入
輸入檔案alpha.in包含4行。第一行有一個正整數N(N<=26),後面的3行每行有一個由大寫字母組成的字元串,分别代表兩個加數以及和。這3個字元串左右兩端都沒有空格,從高位到低位,并且恰好有N位。
輸出
輸出檔案alpha.out包含一行。在這一行中,應當包含唯一的那組解。解是這樣表示的:輸出N個數字,分别表示A,B,C……所代表的數字,相鄰的兩個數字用一個空格隔開,不能有多餘的空格。
樣例輸入
Copy (如果複制到控制台無換行,可以先粘貼到文本編輯器,再複制)
5
ABCED
BDACE
EBBAA
樣例輸出
1 0 3 4 2
【資料規模】
對于30%的資料,保證有N≤10;
對于50%的資料,保證有N≤15;
對于全部的資料,保證有N≤26
ps:再給你一組小資料,如果調不出來你可以手動跑一下
輸入:
2
AB
AB
BA
輸出:
0 1
分析:以個位為第一列,di表示第i列的進位情況,對于第i列,如果豎式是 +⋯⋯⋯⋯⋯⋯aibici⋯⋯⋯⋯⋯⋯
那麼顯然有 (ai+bi+di−1)modn=ci
去掉模運算得到
ai+bi+di−1=ci+kn
由于這是豎式加法,那麼 顯然k就是di。
那就有 ai+bi+di−1=ci+n∗di
将常數項移到右邊去 ai+bi−ci=n∗di−di−1
至此,方程列完了。
我們枚舉di,進行求解。
顯然 dn , d0 都是0,是以,我們隻需要枚舉 2n−1 次,高斯消元的時間複雜度是 O(n3) ,是以總的時間複雜度是 O(2n−1n3) ,當然,這顯然不夠快,考慮優化。
我們發現,我們改變的隻有常數項,是以,我們隻做一次高斯消元。通過這次高斯消元,我們顯然可以求出未知數的系數,那對于 常數項呢?
優化從這裡開始
設第i個方程的 化簡後的常數項為 Ai ,
設高斯消元之後得到的未知數的系數為 K
那麼,高斯消元後的矩陣就是這個樣子的⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢K10⋮000K2⋮00⋯⋯⋱⋯⋯00⋮kn−1000⋮0knA1A2⋮An−1An⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥
我們再用一個數組 gi,j 來儲存第i個方程的 化簡後的常數項和 dj 的關系
即 Ai=∑j=1ngi,j
那麼顯然,初始時, gi,j=5,gi,i−1=−1;
那高斯消元後,也就是這個樣子
⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢K10⋮000K2⋮00⋯⋯⋱⋯⋯00⋮Kn−1000⋮0Kng1,1g2,1⋮gn−1,1gn,1g1,2g2,2⋮gn−1,2gn,2⋯⋯⋱⋯⋯g1,n−1g2,n−1⋮gn−1,n−1gn,n−1g1,ng2,n⋮gn−1,ngn,n⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥
每次枚舉出d數組的取值後,我們就可以用 O(n2) 的時間算出常數項 Ai ,總的時間複雜度變為 O(2n−1n2) ,但由于很多取值不用 O(n2) 的時間即可判定為不可行 (看我的check()函數),是以時間時間會比較短。
你看懂了嗎,我猜你沒看懂,那看看我舉的例子:
我們來分析一下樣例:
5
ABCED
BDACE
EBBAA
那麼,我們可以列出矩陣
⎡⎣⎢⎢⎢⎢⎢⎢⎢−1−110100−10101100100101100−15−100005−100005−100005−100005⎤⎦⎥⎥⎥⎥⎥⎥⎥
高斯消元後矩陣變為
⎡⎣⎢⎢⎢⎢⎢⎢⎢−300000−300000−300000300000−1−33−15180−16180−1506−21−33−3−83318−151516−15−1500−5⎤⎦⎥⎥⎥⎥⎥⎥⎥
枚舉dj,根據增廣矩陣的右邊算出常數項即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 26
int n,equ,var,d[MAXN+10],x[MAXN+10];
typedef int matrix[MAXN+10][MAXN+10];
matrix a,g;
bool vis[MAXN+10];
char s[3][MAXN+10];
void Read(int &x){
char c;
while(c=getchar(),c!=EOF)
if(c>='0'&&c<='9'){
x=c-'0';
while(c=getchar(),c>='0')
x=x*10+c-'0';
ungetc(c,stdin);
return;
}
}
void read(){
Read(n);
scanf("%s%s%s",s[0],s[1],s[2]);
int i,j;
for(i=0;i<n;i++){
for(j=0;j<2;j++)
a[n-i][s[j][i]-'A'+1]++;
a[n-i][s[2][i]-'A'+1]--;
}
for(i=1;i<=n;i++)
g[i][i]=n,g[i][i-1]=-1;
g[1][0]=0;
equ=var=n;
}
int gcd(int a,int b){
int t;
while(b){
t=a%b;
a=b;
b=t;
}
return a;
}
void gauss_jordan(){
int i,j,row,col,mxr,lcm;
for(row=col=1;row<=equ&&col<=var;row++,col++){
mxr=row;
for(i=row+1;i<=equ;i++)
if(abs(a[i][col])>abs(a[mxr][col]))
mxr=i;
if(mxr!=row)
swap(a[row],a[mxr]),swap(g[row],g[mxr]);
if(!a[row][col]){
row--;
continue;
}
for(i=1;i<=equ;i++)
if(i!=row&&a[i][col]){
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(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];
}
}
}
}
bool check(){
int i,j;
memset(vis,0,sizeof vis);
for(i=1;i<=n;i++){
x[i]=0;
for(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 print(){
for(int i=1;i<n;i++)
printf("%d ",x[i]);
printf("%d\n",x[n]);
}
void dfs(int i){
if(i==n){
if(check()){
print();
exit(0);
}
return;
}
d[i]=1;
dfs(i+1);
d[i]=0;
dfs(i+1);
}
int main()
{
read();
gauss_jordan();
dfs(1);
}
另有搜尋算法,請見【搜尋】[NOIP2004]蟲食算