Educational Codeforces Round 108 (Rated for Div. 2)

2021.4.29

A

题意：有r个红豆角，b个蓝豆角，将这些豆角分组，要求每组两种豆角至少各有一个，并且每组豆角数量相差不超过d，判断分组是否可以成立。

题解：先取出k1=max(r,b)和k2=min(r,b)，这样最多可以分成k2组，每组放一个，这样比它大的豆角最多可以取(d+1)*k2个，只需判断k1是否小于等于最大值就可以了。

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int main(void)
{
    std::ios::sync_with_stdio(false);
    ll t,r,b,d;
    cin>>t;
    while(t--)
    {
        cin>>r>>b>>d;
        ll k=min(r,b);
        ll maxx=(d+1)*k;
        if(max(r,b)>maxx)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
    return 0;
}

B

题意：走格子，每次只能向下走或者向右走一格，向下一步需要花费y，向右走需要花费x，就是走一步的花费就是横坐标或者纵坐标不变的那个，从点(1,1)花费k走到(n,m)是否成立？

题解：只需确定两个极值点，从点(1,1)走到(n,m)的最多花费和最小花费，最多花费就是横坐标或者纵坐标小的走到底，然后再往终点走去，最小花费则相反，最后判断k是否在这区间。

#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
    std::ios::sync_with_stdio(false);
    int t,flag,n,m,k;
    cin>>t;
    while(t--)
    {
        flag=0;
        cin>>n>>m>>k;
        int maxx=max(n-1,m-1);
        int minx=min(n-1,m-1);
        int sum1=maxx+max(n,m)*(min(n,m)-1);
        int sum2=minx+min(n,m)*(max(n,m)-1);
        if(k>=sum2&&k<=sum1)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

C

题意：有编号1-n的学校，有n个选手，每个选手都有各自的能力值和其各自的学校，假设以k个人为一组，每个学校用能力值从大到小排组队，剩下组不成一队的就忽略掉，k[1,n]，输出所有学校队伍的能力值。

题解：将每个学校的队员进行排序，遍历1-n，将该学校所有以k人为一组的队员能力值加到对应的数组中，用前缀和比较快，最后输出所有加的数。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200005];
int main()
{
    std::ios::sync_with_stdio(false);
    ll t,n,x;
    cin>>t;
    while(t--)
    {
        cin>>n;
        vector<ll>vis(n+1);
        vector<ll>vc[n+1];
        vector<ll>ans(n+1);
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            vc[a[i]].push_back(x);
            vis[a[i]]++;
        }
        for(int i=1;i<=n;i++)
        {
            sort(vc[i].begin(),vc[i].end());
            for(int j=vis[i]-2;j>=0;j--)
                vc[i][j]+=vc[i][j+1];
            for(int j=1;j<=vis[i];j++)
                ans[j-1]+=vc[i][vis[i]%j];
        }
        for(int i=0;i<n;i++)
            cout<<ans[i]<<' ';
        cout<<endl;
    }
}

D

题意：输入两个长度为n的序列a，b，可以选择序列a中最多一个长度小于等于n的子序列，将其顺序调换，求调换后最大为多少？

题解：遍历每个点和以这个点为中心子序列的长度（子序列长度偶数另外看），依次往外扩展，若转换的子序列为[l,r]，那么转换的子序列和就是转换子序列[l+1,r-1]的和加上，然后加上前l-1和后r+1个未转换的和，这个操作用前缀和比较快，这样遍历点和长度向外扩展时就可以比较转换后的最大值，然后取出最大值。

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
int main(void)
{
    std::ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    vector<ll>a(n+1),b(n+1),sum(n+1);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i]*b[i];
    ll maxx=sum[n],ans;
    for(int i=1;i<=n;i++)
    {
        ans=a[i]*b[i];
        for(int l=i-1,r=i+1;l>=1&&r<=n;l--,r++)
        {
            ans+=a[l]*b[r];
            ans+=a[r]*b[l];
            maxx=max(maxx,ans+sum[n]-sum[r]+sum[l-1]);
        }
        ans=0;
        for(int l=i,r=i+1;l>=1&&r<=n;l--,r++)
        {
            ans+=a[l]*b[r];
            ans+=a[r]*b[l];
            maxx=max(maxx,ans+sum[n]-sum[r]+sum[l-1]);
        }
    }
    cout<<maxx<<endl;
    return 0;
}