[C++知识库]Educational Codeforces Round 118 (Rated for Div. 2) A-C

D的难度跨度太大了，先不写了。
A. Long Comparison
给出一个数字x1,后面添加p1个0，一个数字x2，后面添加p2个0。比较两个数字的大小，输出比较的情况。
x和p都是10的6次方的范围，直接乘肯定炸，那我们肯定是一边比一边乘，分情况讨论。
1.如果后面加0的个数相同，那么只要比较x1和x2的大小就可以了
2.如果加的0个数不同，我们要再分两种情况讨论，具体的看代码吧。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main()
{
    ll t,n,x1,x2,p1,p2;
    cin>>t;
    while(t--)
    {
        cin>>x1>>p1;
        cin>>x2>>p2;
        if(p1==p2)  //直接比较x1,x2就可以了
        {
            if(x1>x2) {cout<<">"<<endl;continue;}
            if(x1==x2) {cout<<"="<<endl;continue;}
            if(x1<x2) {cout<<"<"<<endl;continue;}
        }
        if(p1>p2)  //如果x1的0多
        {
            ll i;
            int f=0;
            i=p1-p2;
            if(x1>=x2) {cout<<">"<<endl;continue;} //x1比x2还大，x1后面的0也多
            else{
                while(i--) //如果x1比x2小，就开始乘0
                {    x1=x1*10;
                    if(x1>x2) {f=1;break;}  //乘到x1比x2大，输出就行
                }
                if(f==1) {cout<<">"<<endl;continue;} 
                if(f==0){  //到最后都乘完都没x2大
                    if(x1==x2) {cout<<"="<<endl;continue;}
                    if(x1<x2) {cout<<"<"<<endl;continue;}
                }
            }
        }
        if(p1<p2)  //和上面的道理一样
        {
            ll i;
            int f=0;
            i=p2-p1;
            if(x1<=x2) {cout<<"<"<<endl;continue;}
            else{
                while(i--)
                {    x2=x2*10;
                    if(x2>x1) {f=1;break;}
                }
                if(f==1) {cout<<"<"<<endl;continue;}
                if(f==0){
                    if(x1==x2) {cout<<"="<<endl;continue;}
                    if(x1>x2) {cout<<">"<<endl;continue;}
                }
            }
        }
    }
}

本来十分钟就可以ac的，手打太快了导致有个符号写成了”-“，wr了一次还花了一分钟检查，多了11的罚时…
B. Absent Remainder
给出几组大小为n的数组，要在其中找到x,y需满足三个条件1.x!=y。2.x,y都是数组中的元素。3.xmody的余数不存在于数组中，输出n/2组答案即可。
比赛的时候我并没有想到简单的方法，直接用二重循环暴力查找，用map来记录数组中的数，只要找到n/2组数据就打破循环，这样虽然复杂度很高，但是只要找到n/2组数据就行了，所以还是ac了。
后来闲的没事去看别人的视频，发现人家排序完用其他的数余第一个数直接就过了…

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int a[200001];
int main()
{
   int i,n,t,j;
   cin>>t;
   while(t--)
   {
       cin>>n;
       int ans=0,num=0;
       int k=0;
       ans=n/2;
       map<int,int>b;
       for(i=0;i<n;i++)
       {
           cin>>a[i];
           b[a[i]]=1;
       }
       sort(a,a+n);
       for(i=0;i<n;i++)
       {
           for(j=i+1;j<n;j++)
           {
               if(num==ans) {k=1;break;}
               int x=a[j];
               int y=a[i];
               if(b[x%y]==0) {cout<<x<<" "<<y<<endl;num++;}

           }
           if(k==1) break;
       }
   }
}

C. Poisoned Dagger
打一个杀龙的游戏，你可以给龙使毒。给出t组数据，每组数据包含一个数组的大小n和龙的血量h，这个数组表示在这些时间你可以毒一次龙，在龙中毒期间毒它就刷新毒素但并不叠加。输出毒死这只龙，这个毒药应该持续的最短时间。
血量h最大为10的18次方，肯定不能直接遍历。我首先想到了二分答案，但是t的大小有1000，n有100，还要二分10的18次方，我选择用贪心去做了（其实二分完全能过，我想多了）。
贪心的想法是，我们要找到毒药的最小持续时间，最小的情况是什么？肯定是每一段毒的持续时间都没有浪费（即最小区间大于血量h除毒的次数的这个平均值）。但是对于一些情况，并没有满足我们想要的这个平均值，该人物就又再次使毒了，这样我们就只能减去它，然后再次使用这样的贪心思想。这时我们已经用掉了一个区间，所以求平均值的时候分母要减1了。从小到大一直采用这种思想，直到找到这些区间的最小值都大于这个平均值，那么接下来我们就可以把这些毒平分给每个区间了。以前减掉的那些区间不用管，对于我们现在找到的最小值肯定比以前减去的那些区间要大，那些毒浪费了就浪费了，我们没有办法。
我这里说的浪费毒是一种平均的思想，前面如果你小于平均值来毒龙，后面你就要用更长持续时间的毒药来毒死它，这样毒持续的最短时间就要加大。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int main()
{
   int i,n,t,j;
   cin>>t;
   while(t--)
   {
       ll a[101];
       ll b[101];
       ll h;
       cin>>n>>h;
       for(i=0;i<n;i++)
       {
           cin>>a[i];
       }
       for(i=0;i<n;i++)
       {
           b[i]=a[i+1]-a[i]; //我们把这些使毒的时间之差取出来再排个序
       }
       b[n-1]=100000000000000000000; //和龙的战斗时间非常长，最后一个区间是非常大的
       sort(b,b+n);
       int k=n;
       ll aver;
       int q=0;
       for(i=0;i<n;i++)
       {
           aver=h/k;  
           if(h%k!=0) aver=aver+1; //如果平均值还有余数，那么平均值就要加一
           if(aver<=b[i]) {break;}//后面的区间毒不会被浪费了，平均分就可以了
           if(aver>b[i]) {
            h=h-b[i];  //我们想要平分的毒会被浪费掉，只能把它减去，继续分析下一次平分的情况
            k--;
           }
       }
       cout<<aver<<endl;//输出这个我们千辛万苦找到的平均分配的值
   }
}

我怀疑有同学偷看我cf的代码，咳咳。