专栏文章

题解:P9080 [PA 2018] Nowy kontrakt

P9080题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miob7jpk
此快照首次捕获于
2025/12/02 16:21
3 个月前
此快照最后确认于
2025/12/02 16:21
3 个月前
查看原文
吐槽:我居然是第一篇题解,并且这道题好像还不难。

P9080 [PA 2018] Nowy kontrakt

题目大意

这题我们需要对序列 aa 通过末尾添加数字的方式使其严格单调递增,要求最小化操作次数。难点在于处理不同位数数字间的比较和进位问题。

分析

  1. 位数多的数字肯定大于位数少的。
  2. 如果位数相同,那么比较字典序,如果小于前一个数,就在末尾填 00
  3. 若位数比前一个数少:
  • 前导部分更大:补零到相同位数 +1+1
  • 前导部分相同:检查剩余位是否需要进位。
  • 前导部分更小:补零到相同位数。

上代码!!!

CPP
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
string a,b;
int main() {
//	freopen("a.in","r",stdin);
	scanf("%d",&n);
	cin>>a;
	for(int i=2; i<=n; a=b,i++) {
		cin>>b;
		if(a.size()<b.size()||(a.size()==b.size()&&a<b))continue;
		if(a==b) {
			ans++;
			b+='0';
			continue;
		}
		if(a.size()>b.size()) {
			if(a.substr(0,b.size())>b) {
				ans+=a.size()-b.size()+1;
				b+=string(a.size()-b.size()+1,'0');
			} else if(a.substr(0,b.size())==b) {
				string t=a.substr(b.size());
				if(t.find_first_not_of('9')==string::npos) {
					ans+=a.size()-b.size()+1;
					b+=string(a.size()-b.size()+1,'0');
				} else {
					ans+=a.size()-b.size();
					b=a;
					for(int j=b.size()-1; j>=0; j--) {
						if(b[j]=='9')b[j]='0';
						else {
							b[j]++;
							break;
						}
					}
				}
			} else {
				ans+=a.size()-b.size();
				b+=string(a.size()-b.size(),'0');
			}
			continue;
		}
		ans+=a.size()-b.size()+1;
		b+=string(b.size()+1-b.size(),'0');
	}
	printf("%lld",ans);
	return 0;
}
你不点赞,晚上我就去你家偷马桶盖!

评论

3 条评论,欢迎与作者交流。

正在加载评论...