题目链接:https://nanti.jisuanke.com/t/44105

题意

题意就是给你一些四则运算的等式,等式的格式是 x op y = z,其中x,y,z都是字符串,表示某个进制下的数字,op是运算符,包括+,-,*,/。

现在有1\~36进制可供选择,你需要找到某个进制使得等式成立,输出满足等式的所有进制,找不到就输出invalid。

其中,1\~9进制用数字1-9表示,10~35进制用字母a-z表示,36进制用0来表示。注意,在等式中的0还是表示0,不是表示36。

同时,在任意进制下,等式中的三个数字转换成十进制后必须在[1,2^32^-1]区间内。

思路

题意也算比较好懂,基本上一看就知道是模拟,因为实际上就是进制转换(这刚学C语言就会做?),数据量也比较小。模拟也不见得就很好写,有很多细节要注意。

  1. 在等式中的0还是表示0,不是表示36;在输出进制时,若要表示为36进制,则输出0。
  2. 特判,要特别注意一进制! 本来一进制应该只包含0,但是题目规定一进制用1代替0,也就是说在本题中,一进制只能包含1,比如等式11 - 10 = 1,在一进制下就不成立,因为10包含了0。
  3. inf=(1<<32)-1,这肯定是错的,因为1默认是int,1<<32直接爆int,所以要写成(1ll<<32)-1。1ll等价于(long long)1,也就是必须要先把1强制转换一下。

因为第二点,wa了无数次,也是教训。

为什么说在本题中,一进制只能包含1,看一下题目描述:
在这里插入图片描述
在这里插入图片描述

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,inf=(1ll<<32)-1;//记得写1ll转换成long long,这里容易错
ll T;
char a[N],b[N],c[N];
ll to_ll(char x)
{
    if(x>='1'&&x<='9')return x-'0';
    else if(x>='a'&&x<='z')return x-'a'+10;
    else return 0;
}
ll to_char(ll x)
{
    if(x>=1&&x<=9)return x+'0';
    else if(x>=10&&x<=35)return x+'a'-10;
    else return '0';
}
ll get_sum(char s[],ll bas)//将字符串转换成bas进制下的数值
{
    ll n=strlen(s);
    ll ans=0;
    ll tmp=1;
    for(ll i=n-1;i>=0;i--)
    {
        if(tmp<0||tmp>inf||ans>inf||ans<0)return -1;
        ll x=to_ll(s[i]);
        //printf("x=%lld s[i]=%c\n",x,s[i]);
        ans+=x*tmp;//tmp是bas的次方
        tmp*=bas;
    }
    return ans;
}
ll get_mx(char s[])//得到字符串中最大的单个数字
{
    ll n=strlen(s);
    ll mx=0;
    for(ll i=0;i<n;i++)
    {
        ll x=to_ll(s[i]);
        mx=max(mx,x);
    }
    return mx;
}
bool have0(char s[])//判断字符串中是否有0
{
    for(int i=0;s[i];i++)
    {
        if(s[i]=='0')return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        char opt,dengyu;
        cin>>a>>opt>>b>>dengyu>>c;
        //printf("a=%s opt=%c b=%s dengyu=%c c=%s\n",a,opt,b,dengyu,c);
        ll mx1=get_mx(a);
        ll mx2=get_mx(b);
        ll mx3=get_mx(c);
        ll mx=max(max(mx1,mx2),mx3);
        //printf("mx=%lld\n",mx);
        if(opt=='+')
        {
            bool flag=0;
            ll i;
            for(mx==1?i=mx:i=mx+1;i<=36;i++)//遍历可能的进制
            {
                ll s1=get_sum(a,i);
                ll s2=get_sum(b,i);
                ll s3=get_sum(c,i);
                //printf("i=%lld %lld+%lld=%lld\n",i,s1,s2,s3);
                if(!(s1>=1&&s1<=inf&&s2>=1&&s2<=inf&&s3>=1&&s3<=inf))continue;//满足题目范围
                if(i==1&&(have0(a)||have0(b)||have0(c)))continue;//一进制不能包含0
                if(s1+s2==s3)
                {
                    flag=1;
                    printf("%c",to_char(i));
                }
            }
            if(flag)printf("\n");
            else printf("invalid\n");
        }
        else if(opt=='-')
        {
            bool flag=0;
            ll i;
            for(mx==1?i=mx:i=mx+1;i<=36;i++)
            {
                ll s1=get_sum(a,i);
                ll s2=get_sum(b,i);
                ll s3=get_sum(c,i);
                if(!(s1>=1&&s1<=inf&&s2>=1&&s2<=inf&&s3>=1&&s3<=inf))continue;
                if(i==1&&(have0(a)||have0(b)||have0(c)))continue;//一进制不能包含0
                if(s1-s2==s3)
                {
                    flag=1;
                    printf("%c",to_char(i));
                }
            }
            if(flag)printf("\n");
            else printf("invalid\n");
        }
        else if(opt=='*')
        {
            bool flag=0;
            ll i;
            for(mx==1?i=mx:i=mx+1;i<=36;i++)
            {
                ll s1=get_sum(a,i);
                ll s2=get_sum(b,i);
                ll s3=get_sum(c,i);
                if(!(s1>=1&&s1<=inf&&s2>=1&&s2<=inf&&s3>=1&&s3<=inf))continue;
                if(i==1&&(have0(a)||have0(b)||have0(c)))continue;//一进制不能包含0
                if(s1*s2==s3)
                {
                    flag=1;
                    printf("%c",to_char(i));
                }
            }
            if(flag)printf("\n");
            else printf("invalid\n");
        }
        else if(opt=='/')
        {
            bool flag=0;
            ll i;
            for(mx==1?i=mx:i=mx+1;i<=36;i++)
            {
                ll s1=get_sum(a,i);
                ll s2=get_sum(b,i);
                ll s3=get_sum(c,i);
                if(!(s1>=1&&s1<=inf&&s2>=1&&s2<=inf&&s3>=1&&s3<=inf))continue;
                if(i==1&&(have0(a)||have0(b)||have0(c)))continue;//一进制不能包含0
                if(s1%s2==0&&s1/s2==s3)
                {
                    flag=1;
                    printf("%c",to_char(i));
                }
            }
            if(flag)printf("\n");
            else printf("invalid\n");
        }
    }
    return 0;
}
/*
1
11 - 10 = 1

ans:23456789abcdefghijklmnopqrstuvwxyz0

1
1 + 1 = 2
ans:3456789abcdefghijklmnopqrstuvwxyz0
*/