Codeforces 108

A题
题意：r个红豆和b个绿豆，要求跟他们分组，每组至少有1个红豆和1个绿豆，且红豆的绿豆的个数相差不能超过d
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll t,a,b,c;

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>c;
        if(min(a,b) * (c + 1) >= max(a,b)) cout<<"YES\n";
            else cout<<"NO\n";
    }
    return 0;
}

B题
题意：问能否花费k从（1,1）移动到（n,m）
(x,y)花费y到达(x+1,y)，花费x到达(x,y+1)
解：暴力可知所有到（n,m）的花费都相同，为nm-1
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int t,a,b,c,s;


void dfs(int x,int y)
{
    if(x == a && y == b)
    {
        cout<<s<<endl;
        return;
    }
    if(x + 1 <= a)
    {
        s += y;
        dfs(x + 1,y);
        s -= y;
    }
    if(y + 1 <= b)
    {
        s += x;
        dfs(x,y + 1);
        s -= x;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>c;
        if(c != (a * b - 1)) cout<<"NO\n";
            else cout<<"YES\n";
        //s = 0;
        //dfs(1,1);
    }
    return 0;
}

C题
题意：每个学校有若干个学生，他们都有各自的代码能力ai，每个学校派出若干组，每组k个人，问所有学校能派出的人的代码能力之和最大是多少

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long ll;
ll n,t,a[maxn],s[maxn],x;
vector<ll>v[maxn];

void solve()
{
    cin>>n;
    for(int i = 1;i <= n; ++i)
        v[i].clear(),s[i] = 0;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    for(int i = 1;i <= n; ++i)
    {
        cin>>x;
        v[a[i]].push_back(x);
    }
    for(int i = 1;i <= n; ++i)
    {
        sort(v[i].begin(),v[i].end());
        reverse(v[i].begin(),v[i].end());
        int k = v[i].size();
        for(int j = 1;j < k; ++j)
            v[i][j] += v[i][j - 1];
        for(int j = 1;j <= k; ++j)  ///枚举k
            s[j] += v[i][k - 1 - k % j];///k % j
    }
    for(int i = 1;i <= n; ++i)
        cout<<s[i]<<((i == n)?'\n':' ');
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--) solve();
    return 0;
}

D题
题意：给出a和b，要求翻转一次a的子串，使得∑（ai*bi）最大
解：DP求解

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e3 + 10;
typedef long long ll;
ll n,t,a[maxn],b[maxn],s[maxn],ans,f[maxn][maxn];

void solve()
{
    cin>>n;
    ans = 0;
    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) s[i] = s[i - 1] + a[i] * b[i];
    for(int l = n;l >= 1; --l)
        for(int r = l;r <= n; ++r)
        {
            if(l == r) f[l][r] = a[l] * b[l];
            else if(l + 1 == r) f[l][r] = a[l] * b[r] + a[r] * b[l];
            else f[l][r] = f[l + 1][r - 1] + a[l] * b[r] + a[r] * b[l];
        }
    for(int i = 1;i <= n; ++i)
        for(int j = i;j <= n; ++j)
            ans = max(ans,s[i - 1] + f[i][j] + s[n] - s[j]);
    cout<<ans<<endl;
}


int main()
{
    std::ios::sync_with_stdio(false);
    t = 1;
    while(t--) solve();
    return 0;
}