Codeforces Round 886 (Div. 4)记录

A - To My Critics

代码：

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string.h>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<queue>
#include<unordered_set>
#include<stdlib.h>
#include<sstream>
#include<iomanip>
typedef long long ll;
using namespace std;
const int Mod=1e9+7;
const int N=1e5+7;
int T;
ll ans=0;
int n,k,m,q;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a+b>=10)
        {
            cout<<"YES"<<endl;
        }
        else if(a+c>=10)
        {
            cout<<"YES"<<endl;
        }
        else if(b+c>=10)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    system("pause");
    return 0;
}

B - Ten Words of Wisdom

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string.h>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<queue>
#include<unordered_set>
#include<stdlib.h>
#include<sstream>
#include<iomanip>
typedef long long ll;
using namespace std;
const int Mod=1e9+7;
const int N=1e5+7;
int T;
ll ans=0;
int n,k,m,q;
struct Node
{
    int A,B;
    int num;
}node[55];
bool cmp(Node a, Node b)
{
    return a.B>b.B;
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>node[i].A>>node[i].B;
            node[i].num=i;
        }   
        sort(node+1,node+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            if(node[i].A<=10)
            {
                //cout<<node[i].A<<" "<<node[i].B<<endl;
                cout<<node[i].num<<endl;
                break;
            }
            //cout<<node[i].A<<" "<<node[i].B<<endl;
        }
    }
    system("pause");
    return 0;
}

C - Word on the Paper

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string.h>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<queue>
#include<unordered_set>
#include<stdlib.h>
#include<sstream>
#include<iomanip>
typedef long long ll;
using namespace std;
const int Mod=1e9+7;
const int N=1e5+7;
int T;
ll ans=0;
int n,k,m,q;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        char c[10][10];
        for(int j=0;j<8;j++)
        {
            for(int k=0;k<8;k++)
            {
                cin>>c[j][k];
            }
        }
        for(int k=0;k<8;k++)
        {
            for(int j=0;j<8;j++)
            {
                if(c[j][k]!='.')
                {
                    cout<<c[j][k];
                }
            }
        }
        cout<<endl; 
    }
    system("pause");
    return 0;
}

D - Balanced Round

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string.h>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<queue>
#include<unordered_set>
#include<stdlib.h>
#include<sstream>
#include<iomanip>
typedef long long ll;
using namespace std;
const int Mod=1e9+7;
const int N=1e5+7;
int T;
int n,k,m,q;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>k;
        int a[200010];
        for(int i=0;i<n;i++)
        {
            cin>>a[i];

        }
        sort(a,a+n);
        int cnt=1,ans=1;
        for(int i=0;i<n-1;i++)
        {
            //cout<<a[i]<<" ";
            if(a[i+1]-a[i]<=k)
            {
                cnt++;
                ans=max(ans,cnt);
            }
            else
            {
                cnt=1;
            }
        }
       
         cout<<n-ans<<endl;
       
    }
    system("pause");
    return 0;
}

E - Cardboard for Pictures

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string.h>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<queue>
#include<unordered_set>
#include<stdlib.h>
#include<sstream>
#include<iomanip>
typedef long long ll;
using namespace std;
const int Mod=1e9+7;
const int N=1e5+7;
int T;
int n,q;
int main()
{
    cin>>T;
    while(T--)
    {
        ll m;
        ll a[200010];
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];  
        }
        int t=a[0];
        ll l=1,r=1000000000;
        ll mid;
        while(l<=r)
        {
            long double tt=0,t=0;
            mid=(l+r)/2;
            for(int i=0;i<n;i++)
            {
                tt=(a[i]+2*mid)*(a[i]+2*mid);
                t+=tt;
            }
            ll ttt=t;
            //cout<<t<<"================================"<<endl;
            if(t>m)
            {
                r=mid-1;
            }
            else if(t<m)
            {
                l=mid+1;
            }
            else
            {
                break;
            }
        }
        cout<<mid<<endl;
    }
    system("pause");
    return 0;
}

F - We Were Both Children

思路：我们忽略任何大于 $n$的 $a_i$，因为无论如何我们都抓不到它们。我们在 $cnt_i$中记录每次跳跃距离有多少只青蛙。我们从$1$到$n$的每一个$i$，并在$i$的每一个小于或等于$n$的倍数上加上$cnt_i$。这个动作是一个调和数列，需要 $O(nlogn)$ 时间。我们从 $1$到 $n$依次取最大值。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string.h>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<queue>
#include<unordered_set>
#include<stdlib.h>
#include<sstream>
#include<iomanip>
typedef long long ll;
using namespace std;
const int Mod=1e9+7;
const int N=1e5+7;
int T;
int n,q,m;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        vector<ll> cnt(n + 1, 0), mx(n + 1, 0);
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            if(x<=n)
            {
                cnt[x]++;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j+=i)
            {
                mx[j]+=cnt[i];
            }
        }
        cout<<*max_element(mx.begin(),mx.end())<<endl;
    }
    system("pause");
    return 0;
}