[洛谷 P5238] 整数校验器

题目描述

有些时候需要解决这样一类问题:判断一个数 x 是否合法。

x 合法当且仅当其满足如下条件:

  • x 格式合法,一个格式合法的整数要么是 0,要么由一个可加可不加的负号,一个 1 到 9 之间的数字,和若干个 0 到 9 之间的数字依次连接而成。
  • x 在区间 [l, r] 范围内(即 l≤x≤r)。

你需要实现这样一个校验器,对于给定的 l,r,多次判断 x 是否合法。

输入格式:

第一行三个整数 l, r, T,表示校验器的校验区间为 [l,r],以及需要校验的 x 的个数。

接下来 T 行,每行一个 x,表示要校验的数,保证 x 长度至少为 1 且仅由 ‘0’~’9′ 及 ‘-‘ 构成,且 ‘-‘ 只会出现在第一个字符。

输出格式:

输出共 T 行,每行一个整数,表示每个 x 的校验结果。

校验结果规定如下:0 表示 x 合法;1 表示 x 格式不合法;2 表示 x 格式合法且不在 [l,r] 区间内。

输入样例:

-3 3 4
0
00
-0
100000000000000000000

输出样例:

0
1
1
2

说明:

对于 100% 的数据,0≤T≤512,l, r 在 64 位有符号整型范围内(即 −263≤l≤r≤263−1)。

保证输入文件大小不超过 128KB。数据在 linux 下生成,没有 ‘\r’ 字符。

以下为部分特殊限制(互不包含):

  • 有 5% 的数据,T=0。
  • 有 25% 的数据,保证 x 格式一定合法。
  • 有 30% 的数据,保证如果 x 格式合法,那么 x 一定在 64 位有符号整形范围内。

其中有一个不计分的 hack 测试点,用于考察 long long 边界数字的判断,如果是 100 分 UnAC 的话,那么可能是你没有考虑这一种情况。

解题思路

此题无非就是对每一个输入的数字进行判断,若是有效数字则进行范围判断,全程使用 string 操作即可

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<sstream>
using namespace std;

int t;
string l,r;
int cmp(string a,string b)
{
    #define small 0
    #define dengyu 1
    #define big 2
    if(a[0]=='-' && b[0]!='-')
        return small;
    
    if(a[0]!='-' && b[0]=='-')
        return big;
    
    if(a[0]=='-')
    {
        if(a.size()>b.size())
            return small;
        if(a.size()<b.size())
            return big;
        
        for(int i=1;i<a.size();i++)
        {
            if(a[i]>b[i])
                return small;
            else if(a[i]<b[i])
                return big;
        }
        return dengyu;
    }
    if(a.size()>b.size())
        return big;
    if(a.size()<b.size())
        return small;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]<b[i])
            return small;
        else if(a[i]>b[i])
            return big;
    }
    return dengyu;
}
void check(string tmp)
{
    if(tmp[0]=='-')
    {
        if(tmp.size()>1)
        {
            if(tmp[1]=='0')
            {
                printf("1\n");
                return;
            }
        }
        else
        {
            printf("1\n");
            return;
        }
    }
    if(tmp[0]=='0' && tmp.size()!=1)
    {
        printf("1\n");
        return;
    }
    
//    printf("yes\n");
//    return;
    
    //经过筛选,为有效数字 
    
    if(cmp(tmp,l)!=0 && cmp(tmp,r)!=2)
        printf("0\n");
    else
        printf("2\n");
    return;
}
int main()
{
    cin>>l>>r;
    scanf("%d",&t);//其实应该都用cin 
    
    for(int i=1;i<=t;i++)
    {
        string tmp;
        cin>>tmp;


        check(tmp);
    }
    return 0;
}