526互联

Codeforces Round 880 (Div. 2) C. k-th equality

发布时间 2023-06-20 10:52:09作者: 突破铁皮

看好久题目了，题目大意是给定三个位数A,B,C和一个k，要求求所有满足要求的a+b=c等式中的第k个等式

等式按字典序由小到大枚举，例如1+9=10和2+6=8中1+9=10比2+6=8小

思路我们首先求出a,b,c的取值范围，然后先确定a，对于每一个确定的a都有一个确定的b和c区间与之对应，并且a+b=c,c=a-b,当a和b确定时，c也就确定了

，所以主要考虑在a确定的情况下的b区间的长度，最后找到第k个式子的区间

k个式子=区间1的等式个数+区间2+....包含第k个式子的区间中为第j个式子

然后k不断减去前面的区间最后k=j，求出为包含第k个式子区间的第j个等式得结果

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int a,b,c;
ll k;
void solve(){
		cin>>a>>b>>c>>k;
		//注意最大取值为max-1
		int max_a=pow(10,a),min_a=pow(10,a-1);//a的范围 
		int max_b=pow(10,b),min_b=pow(10,b-1);//b的范围 
		int max_c=pow(10,c),min_c=pow(10,c-1);//c的范围 
		for(int i=min_a;i<max_a;i++){//将a按字典序枚举 
			ll x=max(min_b,min_c-i);//求出b的最小取值，不能小于b的最小值也不能加a小于c的最小值 
			ll y=min(max_b,max_c-i);//求出b的最大取值，不能大于b的最大取值加a也不能大于c的最大取值，又因为a，b，c均为正整数，因此c-i一定小于pow(10,c) 
			if(x>y) continue;//如果区间小于1就跳过 
			if(y-x>=k){//如果该区间数大于k说明第k个等式就在该区间中 
				cout<<i<<" + "<<x+k-1<<" = "<<x+k-1+i<<endl;//注意从x开始算第k个为x+k-1 
				return;
			}
			k-=y-x;//如果该区间小于k，k减去该区间等式个数 
		}
		cout<<-1<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	
}