P1013 [NOIP1998 提高组] 进制位

· · 题解

传送门：biubiu!

题目的意思非常的简单，就是某进制下通过一些数字的加法运算，来推演这些数字。

但是，某蒟蒻想了足足一晚上，才理解了下面两个解题的关键……（这是对这篇题解的一点点补充）

第一点：该表进制为 N-1。

首先假设该表中有二位数（不可能存在三位或以上的数），那么这个二位数（假设是 AC），那么显然的有 A=1。

那如果没有两位数，怎么办？

稍稍思考一下，不可能存在没有两位数的情况。因为考虑 N \ge 3，所有至少两个数。两个数最小为 0 和 1，那么显然，会产生 1+1=2。而 2 要么是该进制下的一个两位数，要么就是一个新的数；显然，若 2 是一个新的数，那么又会产生 1+2=3 和 2+2=4……如此下去，表中的 N-1 个数必然是 N-1 进制下的 0 \sim N-2 ，也就必然会产生两位数。

第二点：每行有几个两位数，那么这个数就是几。

假设已知当前的表为 k 进制，考虑一个数它为 x，那么 x+k-x \sim x+k-1 必然都是两位数，一共 x+k-1-(x+k-x)+1=x+k-1-x-k+x+1=x 个。所以，一行有几个两位数，这个数就是几。

理解这两点，我们就可以非常轻松地打代码啦。

记得加上无解的判定，一定要考虑全面。

#include <bits/stdc++.h>
using namespace std;

string s,d[10][10];
int N;
char ans[10];
int ans2[10];
map<char,int> t;
void check(int x,int y) {
    if(x!=y&&ans2[x]==ans2[y]) {
        cout<<"ERROR!"<<endl;
        exit(0);
    }
    if(d[x][y].size()==2&&t[d[x][y][0]]!=1) {
        cout<<"ERROR!"<<endl;
        exit(0);
    }
    if(d[x][y].size()==1) {
        if(ans2[x]+ans2[y]>=N-1) {
            cout<<"ERROR!"<<endl;
            exit(0);
        }
        int a=ans2[x]+ans2[y];
        if(a!=t[d[x][y][0]]) {
            cout<<"ERROR!"<<endl;
            exit(0);
        }
    }
    if(d[x][y].size()==2) {
        if(ans2[x]+ans2[y]<N-1) {
            cout<<"ERROR!"<<endl;
            exit(0);
        }
        int a=ans2[x]+ans2[y];
        if(a%(N-1)!=t[d[x][y][1]]) {
            cout<<"ERROR!"<<endl;
            exit(0);
        }
        if(t[d[x][y][0]]!=1) {
            cout<<"ERROR!"<<endl;
            exit(0);
        }
    }
    return ;
}

int main() {
    cin>>N;
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j++) {
            cin>>s,d[i][j]=s;
            if(i==0) continue;
            if(j==0) ans[i]=s[0];
            else if(s.size()==2) ans2[i]++;
        }
        if(i!=0) t[ans[i]]=ans2[i];
    }
    for(int i=1;i<N;i++) for(int j=1;j<N;j++) check(i,j);
    for(int i=1;i<N;i++) cout<<ans[i]<<"="<<ans2[i]<<" ";
    cout<<endl<<N-1<<endl;
    return 0;
}

求求过吧。