C/C++教程

Educational Codeforces Round 118 (Rated for Div. 2)

本文主要是介绍Educational Codeforces Round 118 (Rated for Div. 2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

蒟蒻的题解QAQ~
比赛连接

目录
  • A. Long Comparison (长的比较)
  • B. Absent Remainder (缺席剩余)
  • C. Poisoned Dagger (毒匕首)

A. Long Comparison (长的比较)

题意

给定两个数x1和x2,分别在其末尾添加p1和p2个零,比较它们的大小

思路
由于给定的数字范围较大,所以我们用字符串来存数据,先比较两个字符串长度,如果长度相同在比较数字大小。

代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        bool flag=true;  
        string x1,x2;

        int p1,p2;
        cin>>x1>>p1;
        cin>>x2>>p2;

        int len1=x1.length()+p1;
        int len2=x2.length()+p2;

        if(len1>len2) cout<<">"<<endl;
        else if(len1<len2) cout<<"<"<<endl;
        else{

                if(x1.length()<x2.length())    //补零
                {
                    x1+=string(x2.length()-x1.length(),'0');
                }
                else
                    x2+=string(x1.length()-x2.length(),'0'); 
            for(int i=0;i<x1.length();i++)  //逐位比较大小
            {
                if(x1[i]>x2[i])
                {
                    flag=false;
                    cout<<">"<<endl;
                    break;
                }
                else if(x1[i]<x2[i]){
                    flag=false;
                    cout<<"<"<<endl;
                    break;
                }
            }

            if(flag)   //如果长度相同且大小相同
                cout<<"="<<endl;
        }
    }

    return 0;
}

B. Absent Remainder (缺席剩余)

题意

找出\(\lfloor n/2\rfloor\) 对不同数x,y满足:
1.x\(\neq\)y
2.x和y都出现在序列a中
3.x%y不出现在序列a中

思路
前两个条件都是非常容易满足的,而对于第三个条件,我们只需要将数组排序,对于每一个大于最小值n的数字m,都会有m%n<n,答案便显而易见了

代码

#include<bits/stdc++.h>

using namespace std;

#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=2e5+10;

int a[N];


int main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++) {
            cin>>a[i];
        }

        sort(a,a+n);
        for(int i=0;i<n/2;i++)    
            cout<<a[i+1]<<' '<<a[0]<<endl;
    }
    return 0;
}

C. Poisoned Dagger (毒匕首)

题意

给定攻击次数n和龙血量h,在给出n个攻击时间点,求最小攻击伤害值k

思路
每次造成的上海为min(k,a[i]-a[i-1),最后一次造成的伤害为k,所以总共造成的伤害为k+\(\sum_{i=1}^{i=n-1}min(k,a[i]-a[i-1])\),由于数据较大,所以我们二分得出k的值

代码

#include<bits/stdc++.h>

using namespace std;

#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N=110;

typedef long long LL;

LL a[N],c[N];


int main()
{
    IOS;
    int t;
    cin>>t;
    while(t--)
    {
        LL n,h;
        cin>>n>>h;
        for(int i=0;i<n;i++)  cin>>a[i];

        LL l=1,r=1e18;  
        while(l<=r)
        {
            LL mid=l+r+1>>1;
            LL sum=mid;
            for(int i=1;i<n;i++)
                sum+=min(mid,a[i]-a[i-1]);
            if(sum<h) l=mid+1;
            else r=mid-1;
        }

        cout<<l<<endl;
    }
    return 0;
}

这篇关于Educational Codeforces Round 118 (Rated for Div. 2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!