Codeforces Round #667 (Div. 3)

A.Yet Another Two Integers Problem

题解:签到题
代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
void solve(){
	int a,b;cin>>a>>b;
	int ans=abs(b-a)/10;
	if(abs(b-a)%10) ans++;
	cout<<ans<<endl;
}
int main(){
	int T;cin>>T;
	while(T--) solve();
}


B.Minimum Product

题意:签到
题解:分类讨论即可
代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
void solve(){
	ll a,b,x,y,n;cin>>a>>b>>x>>y>>n;
	ll ans=1e18;
	if((a-x)>=n&&(b-y)>=n) ans=min({ans,(a-n)*b,(b-n)*a});
	else if((a-x)>=n) ans=min({ans,(a-n)*b,y*max(x,a-(n-b+y))});
	else if((b-y)>=n) ans=min({ans,(b-n)*a,x*max(y,b-(n-a+x))});
	else if(a-x+b-y<=n) ans=min(ans,x*y);
	else ans=min({ans,y*(a-(n-b+y)),x*(b-(n-a+x))});
	cout<<ans<<"\n";
}
int main(){
	int T;cin>>T;
	while(T--) solve();
}


C.Yet Another Array Restoration

题意:构造一个相邻元素之差相同且包含x和y的序列,要求最大值最小
题解:枚举增量即可
代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
void solve(){
	int n,x,y;cin>>n>>x>>y;
	int c=y-x;
	rep(a,1,c) if(c%a==0){
		int mn=y-(n-1)*a;
		if(mn>0&&mn<=x){
			rep(i,0,n-1) printf("%d ",y-i*a); 
			puts("");return;
		}
	}
	int cc=c,top=mod;
	rep(a,1,c) if(c%a==0){
		int mn=y-(n-1)*a,tot=0;
		while(mn<=0) tot++,mn+=a;
		int mx=y+a*tot;
		if(mx<top&&mn<=x) top=mx,cc=a;
	}
	int mn=y-(n-1)*cc;
	while(mn<=0) mn+=cc;
	rep(i,0,n-1) printf("%d ",mn+i*cc);
	puts("");
}
int main(){
	int T;cin>>T;
	while(T--) solve();
}


D.Decrease the Sum of Digits

题意:略
题解:不难发现答案肯定是10…00减去n的连续后几位
代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int cal(ll x){
	int ans=0;
	while(x) ans+=x%10,x/=10;
	return ans;
}
void solve(){
	ll n,s;cin>>n>>s;
	if(cal(n)<=s) return (void)puts("0");
	ll ans=1e18;
	rep(i,1,18){
		ll x=1;
		rep(j,1,i) x*=10;
		ll tmp=x-(n%x),now=n+tmp;
		if(cal(now)<=s) ans=min(ans,tmp);
	}cout<<ans<<"\n";
}
int main(){
	int T;cin>>T;
	while(T--) solve();
}


E.Two Platforms

题意:略
题解:二分练习题
代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,k,x[maxn],pre[maxn],sub[maxn];
void solve(){
	scanf("%d%d",&n,&k);
	rep(i,1,n) scanf("%d",&x[i]);
	rep(i,1,n) scanf("%d",&x[0]);
	sort(x+1,x+1+n);
	rep(i,1,n){
		int st=lower_bound(x+1,x+1+n,x[i]-k)-x-1;
		int ed=upper_bound(x+1,x+1+n,x[i]+k)-x;
		pre[i]=i-st;sub[i]=ed-i;
	}
	rep(i,2,n) pre[i]=max(pre[i],pre[i-1]);
	dep(i,n-1,1) sub[i]=max(sub[i],sub[i+1]);
	int ans=0;
	rep(i,0,n-1) ans=max(ans,pre[i]+sub[i+1]);
	printf("%d\n",ans);
}
int main(){
	int T;cin>>T;
	while(T--) solve();
}


F.Subsequences of Length Two

题意:略
题解:\(dp[i][j][k]\) 表示前 \(i\) 个位置,更改 \(j\) 次,包含 \(k\) 个\(t_1\) 时的最大值。
代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,k,dp[220][220][220];
char s[220],t[3];
void Max(int &a,int b){a=max(a,b);}
int main(){
    scanf("%d%d%s%s",&n,&k,s+1,t+1);
    if(t[1]==t[2]){
    	int mx=0;
    	rep(i,1,n) mx+=s[i]==t[1];
    	mx=min(mx+k,n);
    	return printf("%d\n",mx*(mx-1)/2),0;
    }int ans=0;
    memset(dp,0x9f,sizeof dp);
    dp[0][0][0]=0;
    rep(i,1,n) rep(j,0,k) rep(c,0,i){
    	int &x=dp[i][j][c];
    	if(s[i]==t[1]){if(c) Max(x,dp[i-1][j][c-1]);}
    	else if(s[i]==t[2]) Max(x,dp[i-1][j][c]+c);
    	Max(x,dp[i-1][j][c]);
    	if(j&&c) Max(x,dp[i-1][j-1][c-1]);
    	if(j) Max(x,dp[i-1][j-1][c]+c);
    	Max(ans,dp[n][j][c]);
    }printf("%d\n",ans);
}

发表评论,支持MarkDown语法