Educational Codeforces Round 121 1626B Minor Reduction

68 阅读 0 评论 45 点赞

我是靠谱客的博主负责小甜瓜，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 121 1626B Minor Reduction，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述（传送门）

在这里插入图片描述

题目翻译：

给你一个十进制数x，高位没有多余的0。你需要对其执行一次操作：将x中两个相邻的数替换成它们的和（它们的和的高位也不能有多余的0，比如如果和是9，就用9来替换，而不是09；如果和是0，则用0来替换，而不是00）
比如，如果x = 10057，则可能的结果是：

选择第一位数1和第二位数0，用1+0=1来替换，则结果是1057；
选择第二位数0和第三位数0，用0+0=0来替换，则结果也是1057；
选择第三位数0和第四位数5，用0+5=5来替换，则结果仍然是1057；
选择第四位数5和第五位数7，用5+7=12来替换，则结果是10012；

问能得到的最大的数是几？

解题思路：

令取得的两位数为a(允许a的高位有多余的0，比如a = 09，a = 00)，a的个位数和十位数相加等于b 。
首先可以发现， a ≥ b。证明如下：

不管a取何值，b ≤ 18（b最大的情况是：当a = 99时，b = 18）。
因此，当18＜a ≤ 99时，a＞b，命题成立；
当10 ≤ a ≤ 18时，b ≤ 9，而a ≥ 10，故a＞b，命题成立；
当0 ≤ a ≤ 9时，a = b，命题成立。

从上面的证明也可以发现，当a ≥ 10时，a > b（而非a ≥ b）

对两位数进行上面的操作，其位数变化会有两种情况：①位数减一（如11->2）；②位数不变（如56->11）。为了使结果尽可能地大，显然第②种情况得到的结果比第①种情况得到的结果要大。然后对这两种情况进行分类讨论：1、根据上面的证明可以知道，当位数不变时，说明取得的a ≥ 10，而当a ≥ 10时，a > b，这说明操作过后，a会变小。而如果a在x的高位，其变小会使得x的值降得更多，所以我们应当选择处于x的低位的a。2、当位数减一时，b ≥ a的十位，若a在x的高位，a的变化会使得x的值增得更多，所以这时要优先选择处于x的高位的a。若此时a的十位=b，我们应当继续遍历，还是直接选择该位置的a呢？这种情况下，a只能是10，以x=1000011来举例，若继续向后遍历，试图找到一个a的十位<b，则结果是100002，此时首位1后连续的0的个数没有减少；若直接选择该位置的a，则结果是100011，此时首位1后连续的0的个数减少了一个，根据首位1后连续的0的个数来判断两个结果的大小，可以知道当a的十位=b时，我们应该直接选择该位置的a。
总得来说，先从x的低位向高位遍历，若找到一个位数不变的情况，直接输出结果；若遍历完后未发现位数不变的情况，则直接对高位的两位进行上述操作，得出结果。

代码：

#include<iostream>
#include<cstring>
using namespace std;
string operate(string s,int i) { //对数中第i位和第i+1位进行操作
	int a,b,c,d;
	string add="";
	a=s[i]-'0',b=s[i+1]-'0',c=(a+b)/10,d=(a+b)%10;
	if(c!=0) add=add+char('0'+c);
	add=add+char('0'+d);
	if(i<=s.size()-3) return s.substr(0,i)+add+s.substr(i+2,s.size()-(i+2));
	else return s.substr(0,i)+add;
}
int main() {
//	freopen("1.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,a,b;
	string s;
	cin>>n;
	while(n--) {
		cin>>s;
		bool flag=false;
		for(int i=s.size()-2;i>=0;i--){
			a=s[i]-'0',b=s[i+1]-'0';
			if(a+b>=10){
				cout<<operate(s,i)<<endl;
				flag=true;
				break;
			}
		}
		if(!flag) cout<<operate(s,0)<<endl;
	}
}