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

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

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

相关文章:

  • 表单 schema 配置化
  • L3-1 夺宝大赛
  • Manus 一码难求,MetaGPT、OpenManus、Camel AI 会是替代方案吗?
  • MESH网络技术解析
  • Ant Design Vue UI框架快速打造后台管理管理案例
  • K8S学习之基础三十:k8s中RBAC 的核心概念
  • 华为OD机考真题 Linux 发行版的数量(Java)
  • Android UI 组件系列(一):TextView 使用详解与常见属性
  • Fast dds 内存调优
  • 【前端实战】一文掌握响应式布局 - 多设备完美适配方案详解
  • 【DeepSeek】蓝耘智算 | 中国AI新范式:蓝耘智算云+DeepSeek R1部署实战教程
  • Spring @Bean注解使用场景二
  • 【PHP】获取PHP-FPM的状态信息
  • Python JSON模块详解:从入门到高级应用
  • C#—线程池详解
  • 健康养生:拥抱活力,畅享生活
  • Excel单元格中插入自定义超链接
  • 第5课 树莓派的Python IDE—Thonny
  • Python系列教程241——不要使用from *
  • Navicat for Snowflake 震撼首发,激活数据仓库管理全新动能