自动搬运

查看原文

来自洛谷，原作者为

	Shanganze **

搬运于2025-08-24 22:31:57，当前版本为作者最后更新于2022-09-16 20:39:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

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

分析：

就分两种情况：

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

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

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

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

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

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

同机房大佬给出了两组 hack 数据 ： $1001$ $\;$ $999$

还是要修改第一个奇偶相同的数为 $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;
}