当前位置：首页 > article >正文

【CF】Day7——Codeforces Round 919 (Div. 2) BC

article 2025/3/17 11:16:51

B. Summation Game

题目：

思路：

千万别想的太难了，想难你就输了

鲍勃想最小化数组的话肯定是把x个最大的全乘以-1，爱丽丝想最大化就要删去k个最大值，但是不一定要删k个

观察数据，n是2e5，那么我们暴力枚举删后i个元素然后取最大值即可，同时要注意先排序

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"

void solve()
{
    int n, k, x;
    cin >> n >> k >> x;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin()+1, a.end());
    int res = -1e18;
    for (int i = 1; i <= n; i++)
    {
        a[i] += a[i - 1];
    }
    int sum = a[n];
    //删i个元素
    for (int i = 0; i <= k; i++)
    {
        int j = n - i;
        int minus = sum - a[j];
        int bobnum = a[j] - a[max(j - x,0LL)];
        int chage = sum - minus - 2*bobnum;
        //cout << sum << " " << minus << " " << bobnum << " " << chage << endl;
        res = max(res, chage);
    }
    cout << res << endl;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C. Partitioning the Array

题目：

思路：

首先，我们把问题分成两个部分

①.分成n/k个子数组

②.找出一个m满足题意

问题①肯定是没问题的，我们可以暴力枚举1~ $\sqrt{n}$ 快速直到哪些树是n的因数

那么问题②该如何解决呢，首先我们要明白题意的意思，既然是要每个子数组全相等，也就是说对于任意一个ai，要满足 $(a \equiv b)modm$ ，其中a = a[i]，b = a[i+k]，根据同余的减法，也就是说有

(abs(a[i] - a[i+k]) $\equiv$ 0 mod m)，即 $\left |a[i] - a[i+k] \right | \equiv 0 mod m$

那我们只需要暴力枚举即可，我们求出gcd(a[i] - a[i+k],a[i+1],a[i+1+k],....) = g

至于为什么要求gcd也很明显，因为每个a[i] - a[i+k]都要能被m整除，所以肯定要求所有a[i] - a[i+1]的最大公因数

因为m大于等于2，所以只要g大于一就能增加答案

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"

int n;

int gcd(int a,int b)
{
    return (!b) ? a : gcd(b, a % b);
}

int fuc(const vector<int>&a, int k)
{
    if (k == n)
    {
        return 1;
    }
    int g = abs(a[1] - a[1 + k]);
    for (int i = 1; i <= n-k; i++)
    {
        g = gcd(g, abs(a[i] - a[i + k]));
        if (g == 1)
        {
            return 0;
        }
    }
    return 1;
}

void solve()
{
    cin >> n;
    vector<int> a(n+1,0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int ans = 0;
    for (int k = 1; k*k <= n; k++)
    {
        if (n % k == 0)
        {
            ans += fuc(a, k);
            if (k * k != n)
                ans += fuc(a, n / k);
        }
    }
    cout << ans << endl;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

查看全文

http://www.kler.cn/a/586536.html