Codeforces Round #667 (Div. 3)（A、B、C、D、E）

àì夳堔傛蜴生んèń 2022-12-04 04:29 158阅读 0赞

# Codeforces Round \#667 (Div. 3)（A、B、C、D、E） #

[**比赛地址**][Link 1]

补题补晚了，估计访问量没了

## A：Yet Another Two Integers Problem ##

#### 题意 ####

给定两整数a,b，每次可以选择\[1,10\]中任意一个数字k，使得a=a+k(或a=a-k)，问最少需要多少步使得a=b。

#### 题解 ####

当然每次选择10是最优的操作，于是只需要求：abs(a-b)/10向上取整即可。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    int main(){
        
        int t,a,b;
        scanf("%d",&t);
        while(t--){
        
            scanf("%d%d",&a,&b);
            int num=abs(a-b);
            int ans=num/10;
            if(num%10) ans++;
            printf("%d\n",ans);
        }
        return 0;
    }

## B：Minimum Product ##

#### 题意 ####

有两个整数a,b；分别存在相应的下界x,y。有一操作：每次可以将a(或b)减一，但是不能小于对应的下界。可以操作n次，最终使得a\*b最小

#### 题解 ####

1.  如果可以将a(或b)删除到对应的下界，则优先进行此操作，剩余的次数删除另一个数
2.  如果不能的话，则从删除a和删除b中取最小值

可以用四个变量（初始化都为题目意义上的无穷大值）表示上述操作的四个结果，从中取最小值。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    int main(){
        
        ll t,a,b,x,y,n;
        scanf("%lld",&t);
        while(t--){
        
            scanf("%lld%lld%lld%lld%lld",&a,&b,&x,&y,&n);
            if(n>(a-x)+(b-y)){
        
                printf("%lld\n",x*y);
                continue;
            }
            ll num1,num2,num3,num4;
            num1=num2=num3=num4=1e18;
            if(n>=(a-x)) num1=x*(b-(n-(a-x)));
            else num3=(a-n)*b;
            if(n>=(b-y)) num2=y*(a-(n-(b-y)));
            else num4=(b-n)*a;
            //cout<<num1<<' '<<num2<<' '<<num3<<' '<<num4<<endl;
            ll ans=min(num1,min(num2,min(num3,num4)));
            printf("%lld\n",ans);
        }
        return 0;
    }

## C：Yet Another Array Restoration ##

#### 题意 ####

每组数据给定n，x，y。需要你构造长度为n的等差数列，而且必须包括x，y，同时还得满足数列的最大值尽可能的小。

#### 题解 ####

看了下官方题解，感觉似乎没我的思路简单。  
直接枚举x到y之间相差多少个公差，从而可以计算出公差以及首项、末项，如果当前末项小于之前保存的最小末项值，则更新。只需O(n)的时间复杂度，最终按照首项到末项的顺序打印即可。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    int main(){
        
        int t,n,x,y;
        scanf("%d",&t);
        while(t--){
        
            scanf("%d%d%d",&n,&x,&y);
            int d,a1,an=inf,ad;
            for(int i=0;i<=n-2;i++){
        
                if((y-x)%(i+1)) continue;
                d=(y-x)/(i+1);
                a1=x,an;
                while(a1>=1&&(a1+(n-1)*d)>=y){
        
                    a1-=d;
                }
                a1+=d;
                //cout<<a1<<' '<<d<<endl;
                if(an>a1+(n-1)*d&&(a1+(n-1)*d)>=y){
        
                    an=a1+(n-1)*d;
                    ad=d;
                }
            }
            a1=an-(n-1)*d;
            printf("%d",a1);
            for(int i=2;i<=n;i++){
        
                printf(" %d",a1+(i-1)*d);
            }
            printf("\n");
        }
        return 0;
    }

## D：Decrease the Sum of Digits ##

#### 题意 ####

每组数据给定两整数n,s ，每次可以使n+1，最终需要使得n的位数和小于等于s，问最少需要多少步。

#### 题解 ####

zz了，这题居然没写出来。首先判断起始n是否满足条件，如果满足直接输出0，如果不满足，则从低位到高位分别使得当前遍历的位数的值为0。如果满足条件则结束遍历。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    const ll mod=1e9+7;
    ll t,n,s;
    ll sum(ll x){
        
        ll ans=0;
        while(x){
        
            ans+=x%10;
            x/=10;
        }
        return ans;
    }
    int main(){
        
        scanf("%lld",&t);
        while(t--){
        
            scanf("%lld%lld",&n,&s);
            //cout<<sum(n)<<endl;
            if(sum(n)<=s){
        
                printf("0\n");continue;
            }
            ll bit=1,ans=0;
            for(int i=0;i<18;i++){
        
                ll dig=(n/bit)%10;
                ll x=bit*((10-dig)%10);
                n+=x;
                ans+=x;
                if(sum(n)<=s){
        
                    break;
                }
                bit*=10;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

## E：Two Platforms ##

#### 题意 ####

给定n个点的坐标(xi,yi)从对应的位置下落，以及某一值k，需要你从中找出两条长度为k的板子，使得能接住最多的点，求能接住最多的点的个数。

#### 题解 ####

没做出来，看的官方题解。首先y可以无限小，于是不需要考虑y坐标，直接对x坐标从小到大排序，用两个数组l\[\],r\[\]（其中l\[i\]表示：以点i为板子的右端点能接住的点个数。r\[i\]表示：在点i为板子左端点能接住的点个数），对l\[\]求最大前缀，r\[\]求最大后缀。最终只需遍历1—n，从l\[i\]+r\[i+1\]中取最大值即可。

#### AC代码（cpp） ####

#include<bits/stdc++.h>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=2e5+5;
    const ll mod=1e9+7;
    int x[maxn],y[maxn];
    int l[maxn],r[maxn];
    int t,n,k;
    int main(){
        
        scanf("%d",&t);
        while(t--){
        
            scanf("%d%d",&n,&k);
            for(int i=1;i<=n;i++) scanf("%d",&x[i]);
            for(int i=1;i<=n;i++) scanf("%d",&y[i]);
            sort(x+1,x+n+1);
            int j=n;
            //后缀最大值
            for(int i=n;i>=1;i--){
        
                while(x[j]-x[i]>k) --j;
                r[i]=j-i+1;
                if(i<n) r[i]=max(r[i],r[i+1]);
            }
            //前缀最大值
            j=1;
            for(int i=1;i<=n;i++){
        
                while(x[i]-x[j]>k) ++j;
                l[i]=i-j+1;
                if(i>1) l[i]=max(l[i],l[i-1]);
            }
            int ans=1;
            for(int i=1;i<n;i++){
        
                ans=max(ans,r[i+1]+l[i]);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[Link 1]: https://codeforces.com/contest/1409