洛谷1013 进制位

题意

给出一个加法表，一个字母代表一个数字。求加法的进制，以及每个大写字母代表的数字。

数字个数 $N\le 8$ 。（行数 $\le 9$）

题解

结论：

1. 一定是 $N$ 进制。
2. 每一行有几个二位数，这个数就是几。

证明：

因为有 $N$ 个不同的数，所以最少 $N$ 进制。

假设为 $N+1$ 进制，那么一定有一个数没有出现，假设为 $k$ 。

1. $k=0$ 或 $k=1$，而 $1+N=10$ ，矛盾。
2. $1 < k \le N$ ，而 $1+(k-1)=k$ ，矛盾。

其它 $> N$ 进制的情况同理，所以一定是 $N$ 进制，结论 $1$ 得证。

数字为 $0..N-1$ ，所以结论 $2$ 显然。

有上面的结论后这道题就很好做了。每个数的值都可以预处理出来，记为 $ans[]$ ；同时把字母与数字的对应关系记为 $mp[]$ 。

然后枚举每个数，检验有没有矛盾，如果有就直接输出 ERROR 。最后把 $ans[]$ 全部输出即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,ans[15],mp[26];
char s[15][15][3];

inline bool check(int x,int y) //检验 (x,y)
{
    int sum=ans[x]+ans[y]; //和
    int cur=s[x][y][1]-'A'; //处理十位
    if (sum>=n-1 && mp[cur]!=1) return 0; //如果和 >=n-1 但没有进位
    if (sum>=n-1) sum-=n-1,cur=s[x][y][2]-'A'; //处理个位
    if (mp[cur]!=sum) return 0; //不相等
    return 1;
}

signed main()
{
    n=read();
    for (int j=1;j<=n;j++) scanf("%s",s[1][j]+1);
    for (int i=2;i<=n;i++)
    {
        int cnt=0;
        for (int j=1;j<=n;j++)
        {
            scanf("%s",s[i][j]+1);
            cnt+=strlen(s[i][j]+1)>=2;
        }
        ans[i]=cnt;
        mp[s[i][1][1]-'A']=cnt;
    }
    for (int i=2;i<=n;i++) for (int j=2;j<=n;j++) if (!check(i,j)) return 0&puts("ERROR!");
    for (int i=2;i<=n;i++) printf("%c=%d ",s[i][1][1],ans[i]);
    return !printf("\n%d",n-1);
}