Codeforces Round #667 (Div. 3)A~D题解

发布于 2020-09-05  0 次阅读


A. Yet Another Two Integers Problem

思路:

两个数之间相差10的个数向上取整

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int mod=1e9 +7;
const int N=2e5 +9;
int a, b;
void solve(){
    cin>>a>>b;
    int c=fabs(a-b);
    cout<<(c+9)/10<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Minimum Product

题目大意:

您将得到四个整数a,b,x和y。 最初,a≥x和b≥y。 您最多可以执行n次以下操作:
选择a或b并将其减少一。 但是,作为该操作的结果,a的值不能小于xx,b的值不能小于yy。
您的任务是找到不超过n次的给定操作可以达到的a和b(a⋅b)的最小乘积。

思路:

两数相乘越接近越大
所以两值差越大,乘值越小,所以尽可能的使得连两个值相差大即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int a, b, x, y, n;

void solve(){
    cin>>a>>b>>x>>y>>n;

    int c1=a-x;
    if(c1>n)    c1=n;
    int ta=a-c1;
    int tb=max(b-n+c1,y);
    int ans=ta*tb;

    int c2=b-y;
    if(c2>n)    c2=n;
    tb=b-c2;
    ta=max(a-n+c2,x);
    ans=min(ans,ta*tb);
    cout<<ans<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

C. Yet Another Array Restoration

题目大意:

构造一个长度为n的等差数列,使得其中的最大值最小
给你长度n和等差数列其中的两个值a,b

思路:

枚举求公差即可,求得公差的大小后就贪心构造序列
贪心策略
首先构造x到y的部分,因为要使得最大值最小,所以先构造x前面的值再构造y后面的值即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int x, y, n;
void solve(){
    cin>>n>>x>>y;
    for(int i=1; i<=50; i++){
        if((y-x)%i==0 && (y-x)/i+1<=n){
            for(int j=x; j<=y; j+=i)    if(n>0)   cout<<j<<" ", n--;
            for(int j=x-i; j>=1; j-=i)  if(n>0)   cout<<j<<" ", n--;
            for(int j=1; j<=n; j++)     if(n>0)   cout<<y+j*i<<" ";
            cout<<endl;
            return ;
        }
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

D. Decrease the Sum of Digits

题目大意:

给你一个正整数n。每一步可以给n增加1(即使n=n+1)。
你的任务是找到你需要执行的最小移动数,以使n的数字和小于或等于s。

思路:

首先预处理一下a的每位和,如果等于s就可以直接输出0了
否则从最高位往后处理,当sum > = s 后将当前位往前进位即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=29;
int n, s;
int a[N], b[N];
int ans, len, sum;
void solve(){
    cin>>n>>s;
    int tmp=n;
    memset(a, 0, sizeof(a)); 
    memset(b, 0, sizeof(b));
    len=sum=0;
    while(n){
        a[++len]=n%10;
        sum+=n%10;
        n/=10;
    }
    if(sum==s)  {cout<<"0"<<endl; return ;}
    sum=0;
    for(int i=len; i>=1; i--){
        sum+=a[i];
        if(sum<s)   b[i]=a[i];
        else{
            b[i+1]++;
            for(int j=i; j>=1; j--) b[j]=0;
            break;
        }
    }
    ans=b[len+1];
    for(int i=len; i>=1; i--)   ans*=10, ans+=b[i];
    cout<<ans-tmp<<endl;
    return ;
}
 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

平平无奇的大学在读本科生