P7662

Shanganze · 2022-09-16 20:39:29 · 题解

题意：

给定一个数， 求离改数最近任意相邻两位奇偶性不同的数，若有多个，从小到大输出。

分析：

就分两种情况：

①找第一个比这个数大的 Handsome 数。

从高位往下找，找第一个奇偶性和前一位相同，若该位不为 9，将该位加一，后面的数就根据上一位变，若上一位为奇则该位为 0，反之则为 1。

②找第一个比这个数小的 Handsome 数。

从高位往下找，找第一个奇偶性和前一位相同，若该位不为 0，就将该位减一，后面的数就根据上一位变，若上一位为奇则该位为 8，反之则为 9。

然后，用高精减法判断两个数哪个更近。

然后就愉快 WA 了：72分 \;评测记录

同机房大佬给出了两组 hack 数据 ：

还是要修改第一个奇偶相同的数为 9 或 0 的情况。

如果为 9 时，加一时就把该位变为 0，上一位加 1，一直进位到上一位不为 9。

如果为 0 时，减一时就把该位变为 9，向上一位借位，一直借到不为零。

一天的奋斗终于 AC 了。

代码：

#include<bits/stdc++.h>
using namespace std;
struct a1
{
    int x[100001];
    a1()
    {
        memset(x,0,sizeof(x));
    }
}x,y,z;
a1 operator - (const a1 a,const a1 b)//高精减高精
{
    a1 c;
    for(int q=1;q<=1201;q++)
    {
        c.x[q]=a.x[q]-b.x[q];
    }
    for(int q=1;q<=1201;q++)
    {
        if(c.x[q]<0)
        {
            c.x[q+1]--;
            c.x[q]+=10;
        }
    }
    return c;
}
void read()//读入
{
    string a;
    cin>>a;
    for(int q=1;q<=a.size();q++)z.x[q]=y.x[q]=x.x[q]=a[a.size()-q]-'0';
}
void print(a1 a)//高精输出
{
    int p=1021;
    while(a.x[p]==0)p--;//去除前导零
    for(int q=p;q>=1;q--)cout<<a.x[q];
}
int bi(a1 a,a1 b)
{
    for(int q=1021;q>=1;q--)
    {
        if(a.x[q]>b.x[q])return 2;
        if(a.x[q]<b.x[q])return 1;
    }
    return 0;
}
int main()
{
    read();
    int p=1201,l=0,k=0;
    while(z.x[p]==0)p--;
    for(int q=p-1;q>=1;q--)
    {
        if(z.x[q]%2==z.x[q+1]%2)
        {
            if(z.x[q]!=0&&k!=1)
            {
                k=1;
                x.x[q]-=1;
                for(int w=q-1;w>=1;w--)
                {
                    if(x.x[w+1]%2==0)
                    {
                        x.x[w]=9;
                    }
                    else x.x[w]=8;
                }
            }
            else if(z.x[q]==0&&k!=1)//为0时特殊处理
            {
                k=1;
                int l=q+1;
                while(x.x[l]==0)l++;
                x.x[l]-=1;
                for(int w=l-1;w>=q;w--)x.x[w]=9;
//              x.x[q]=9;
                for(int w=q-1;w>=1;w--)
                {
                    if(x.x[w+1]%2==0)
                    {
                        x.x[w]=9;
                    }
                    else x.x[w]=8;
                }
            }
            if(z.x[q]!=9&&l!=2)
            {
                l=2;
                y.x[q]+=1;
                for(int w=q-1;w>=1;w--)
                {
                    if(y.x[w+1]%2==0)
                    {
                        y.x[w]=1;
                    }
                    else y.x[w]=0;
                }
            }
            else if(z.x[q]==9&&l!=2)//为9时特殊处理
            {
                l=2;
                y.x[q+1]+=1;
                y.x[q]=0;
                for(int w=q;w>=1;w--)
                {
                    if(y.x[w+1]%2==0)
                    {
                        y.x[w]=1;
                    }
                    else y.x[w]=0;
                }
            }
        }
        if(l==2&&k==1)break;
    }
    for(int q=p-1;q>=1;q--)//最后再扫一边处理进位，借位。
    {
        if(y.x[q]%2==y.x[q+1]%2)
        {
            y.x[q]--;
            for(int w=q;w>=1;w--)
            {
                if(y.x[w+1]%2==0)
                {
                  y.x[w]=1;
                }
                else y.x[w]=0;
            }
            break;
        }
    }
    for(int q=p-1;q>=1;q--)
    {
        if(x.x[q]%2==x.x[q+1]%2)
        {
            x.x[q]++;
            for(int w=q;w>=1;w--)
            {
                if(x.x[w+1]%2==0)
                {
                  x.x[w]=9;
                }
                else x.x[w]=8;
            }
            break;
        }
    }
    a1 x1=z-x,y1=y-z;
//  print(x1);
    if(bi(x1,y1)==1)print(x);
    else if(bi(x1,y1)==2)print(y);
    else if(bi(x,y)==0)print(x);
    else 
    {
        print(x);
        cout<<" ";
        print(y);
    }
//  cout<<endl;print(x);
//  cout<<endl;print(y);
    return 0;
}