• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Educational Codeforces Round 108 (Rated for Div. 2) 题解

开发技术 开发技术 2周前 (04-29) 9次浏览

原题链接

A题 Red and Blue Beans

题意:给定(r)个红豆,(b)个蓝豆,将他们分到任意多个包中,要求每个包中红豆和蓝豆的差值不能超过(d),可以则输出(YES),否则输出(NO)
贪心即可,将较小的那个放到不能放为止,然后在将另外一个顺次放进去。

代码:

typedef long long LL;

const int N = 200010;

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- ) 
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        int res = abs(a - b);
        if (res == 0) puts("YES");
        else 
        {
            int l = min(a, b);
            int x = res / l;
            int y = res % l;
            if (y >= 1) x ++ ;
            if (x <= c) puts("YES");
            else puts("NO");
        }
    }

    return 0;
}

B题 The Cake Is a Lie

题意:给定一个棋盘,要求输出能否从((1, 1))走到((n, m))刚好花(k)步,能则输出(YES),否则输出(NO)
sb题,找规律找了半天发现只有一种情况,直接判断就行。

代码:

typedef long long LL;
 
const int N = 110;
 
int n, m, k;
 
int main()
{
    int T;
    scanf("%d", &T);
    while (T -- ) 
    {
        cin >> n >> m >> k;
        
        int res = n - 1 + (m - 1) * n;
        if (res == k) puts("YES");
        else puts("NO");
    }
 
    return 0;
}

C题 Berland Regional

题意:给定编号(1-n)的学校,每个学校有若干个人,要求对于(1 – n)内的每个值(k)都将这些人分成(k)个人的小组,按从大到小排序,不足(k)人则不分,要求将这些小组的值加起来输出。

对于朴素的做法肯定就是两层循环,但是题目给的范围太大(2e5),如果直接暴力会(TLE),所以我们就要对朴素做法进行优化

我们经过思考后不难发现我们所要加上的值一定是,每个学校内的人的总数(sum)所能包含的最大的k的倍数,而这个倍数就是(sum-sum%k),因此我们对每一个(k)值,就能找到能加的值得上限,这样我们只需要第一层循环(1-n),第二层循环(k)值即可,这里由于我们(k>=sum)的无法组成小队,可以不用循环。同时我们可以使用前缀和进行优化

代码:

typedef long long LL;
 
const int N = 200010;
 
int n, m, k;
int g[N], w[N];
vector<LL> s[N]; // 前缀和数组
LL res[N]; 
 
bool cmp(LL a, LL b) // 重载比较函数
{
    return a > b;
}
 
int main()
{
    int T;
    scanf("%d", &T);
    while (T -- ) 
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) res[i] = 0, s[i].clear();
        for (int i = 1; i <= n; i ++ ) scanf("%d", &g[i]);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
 
        for (int i = 1; i <= n; i ++ ) s[g[i]].push_back((LL)w[i]);
        for (int i = 1; i <= n; i ++ ) sort(s[i].begin(), s[i].end(), cmp);
 
        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j < s[i].size(); j ++ ) 
                s[i][j] = s[i][j - 1] + s[i][j];
        
        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j <= s[i].size(); j ++ ) 
            {
                int t = s[i].size();
                res[j] += s[i][t - t % j - 1]; // 下标从0开始
            }
 
        for (int i = 1; i <= n; i ++ ) printf("%lld ", res[i]);
        printf("n");
    }
 
    return 0;
}

D题 Maximum Sum of Products

题意:给定两个序列(a)(b),要求翻转(a)的一段子序列使得(sum_{i=1}^n a_i*b_i)最大。
区间(dp)(好像还可以暴力做),(f[l][r])表示翻转(l-r)区间之后(sum_{i=l}^r a_i*b_i)的值,之后再枚举一遍区间对(res)取一个(max)即可。
状态转移方程为:(f[i][j]=f[i+1][j-1]+a[i]*b[j]+a[j]*b[i])
需要注意的是第一层循环必须是从大到小循环,因为我们会使用到(i+1)

代码:

const int N = 5010;
 
int n, m, k;
LL a[N], b[N];
LL f[N][N]; // f[l][r] 表示将l-r区间反转之后的值是多少
LL s[N];    
 
int main()
{
    cin >> n;
 
    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 i = 1; i <= n; i ++ ) f[i][i] = a[i] * b[i]; // 初始化,只翻转一个数
 
    for (int i = n - 1; i >= 1; i -- ) 
        for (int j = i + 1; j <= n; j ++ )
            f[i][j] = f[i + 1][j - 1] + a[i] * b[j] + a[j] * b[i];
 
    LL res = s[n];
    for (int i = 1; i <= n; i ++ ) 
        for (int j = i + 1; j <= n; j ++ ) 
            res = max(res, f[i][j] + s[i - 1] + s[n] - s[j]);
 
    cout << res << endl;
 
    return 0;
}

程序员灯塔
转载请注明原文链接:Educational Codeforces Round 108 (Rated for Div. 2) 题解
喜欢 (0)