首页 > 其他分享 >Refact.ai Match 1 (Codeforces Round 985)

Refact.ai Match 1 (Codeforces Round 985)

时间：2024-11-10 21:19:25浏览次数：1  
标签：cnt ai vi -- Codeforces long 985 int using

A. Set

二分出最大数满足至少有\(k\)个倍数的数。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const i32 inf = INT_MAX / 2;

const int mod = 1e9 + 7;


void solve() { 
    int l, r, k;
    cin >> l >> r >> k;

    int L = l, R = r, res = -1;
    while(L <= R) {
        int mid = (L + R) / 2;
        int cnt = r / mid - (l - 1) / mid;
        if(cnt >= k) res = mid, L = mid + 1;
        else R = mid - 1;
    }
    if(res < l) cout << 0 << "\n";
    else cout << res - l + 1 << "\n";

    return ;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while(T --)
        solve();
    return 0;
}
 

有一个结论，这个数实际上就是\(\left\lfloor \frac {r}{k} \right\rfloor\)

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;


using vi = vector<int>;
using pii = pair<int,int>;

void solve(){
    int l, r, k;
    cin >> l >> r >> k;
    cout << max(0, r / k - l + 1) << "\n";
    return ;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int T;
    cin >> T;
    while(T --)
        solve();

    return 0;
}

B. Replacement

这题，相当于每次选择两个相邻且不同数字，然后删掉\(r_i\oplus 1\)。所以只要当前\(0,1\)的个数都大于\(0\)就一定有解。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const i32 inf = INT_MAX / 2;

const int mod = 1e9 + 7;


void solve() { 
    int n;
    string s, r;
    cin >> n >> s >> r;

    vi cnt(2);
    for(auto i : s)
        cnt[i - '0'] ++;
    
    for(int x; auto i : r){
        x = (i - '0') ^ 1;
        if(cnt[0] > 0 and cnt[1] > 0)
            cnt[x] --;
        else {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    return; 
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while(T --)
        solve();
    return 0;
}
 

C. New Rating

一个比较神秘的 dp 题。

\(f[i][0]\)表示到\(i\)为止前缀全部都选的得分。

\(f[i][1]\)表示\(f[i][0]\)的前缀最大值。

\(f[i][2]\)表示到\(i\)且已经舍弃一个区间的最大值。

对于\(f[i][2]\)有两种转移，一种是从之前已经\(f[i-1][2]\)转移，这种是直接接在之前已经舍弃过区间的情况。还有一种是从\(f[i-1][1]\)转移，也就是当前就要舍弃区间的情况。

有一种情况是一个区间都不用舍弃的情况，此时随便舍弃一个也就是答案为\(n-1\)。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const i32 inf = INT_MAX / 2;

const int mod = 1e9 + 7;


void solve() { 
    int n;
    cin >> n;

    vi cnt(3);

    for(int i = 1, x, p; i <= n; i++) {
        cin >> x;
        if(x > cnt[0]) cnt[0] ++;
        else if(x < cnt[0]) cnt[0] --;

        if(x > cnt[2]) cnt[2] ++;
        else if(x < cnt[2]) cnt[2] --;

        p = cnt[1];
        if(x > p) p ++;
        else if(x < p) p --;

        cnt[2] = max(cnt[2], p);
        cnt[1] = max(cnt[1], cnt[0]);
    }
    cout << min(n - 1, ranges::max(cnt)) << "\n";
    return; 
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while(T --)
        solve();
    return 0;
}
 

D. Cool Graph

只要一个点\(x\)的度数大于二，我们任选两个与\(x\)相邻的点\(y,z\)。执行一次操作，至少会使得边的的数量减\(1\)，因此这个操作至多执行\(m\)次。

这个操作执行完后，会有两种情况。如果没有边了，则符合条件直接结束。

否则剩下的情况一定是一些孤立的边和孤立的点。我们可以任意选择一条边\((a,b)\)，然后对于剩下的孤立边\((x,y)\)，我们对\((a,x,y)\)进行一次操作，则会把边\((x,y)\)断掉，并插到\(a\)上，最终会形成一个以\(a\)为中心的菊花图。对于孤立的点\(x\)，我们可以执行一次操作\((a,b,x)\)，这样就会把\(x\)插到\(a,b\)中间，如果还有孤立点，就插到\(a,x\)中间。最终图就会变成以\(a\)为中心的菊花图插着一条链。

总体操作次数上限是\((m - 1) + (n -1)\)

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

using vi = vector<int>;
using pii = pair<int, int>;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> f(n + 1, -1);
    vector<array<int, 3>> res;

    auto add = [&](auto &&self, int x, int y) -> void {
        if (f[x] == y and f[y] == x) {
            f[x] = f[y] = -1;
        } else if (f[x] != -1) {
            int z = f[x];
            res.push_back({x, y, z});
            f[x] = f[z] = -1;
            self(self, y, z);
        } else if (f[y] != -1) {
            int z = f[y];
            res.push_back({x, y, z});
            f[y] = f[z] = -1;
            self(self, x, z);
        } else {
            f[x] = y, f[y] = x;
        }
        return;
    };

    for (int x, y; m; m--) {
        cin >> x >> y;
        add(add, x, y);
    }

    vector<pii> edge;
    for (int i = 1; i <= n; i++) {
        if (f[i] == -1) continue;
        if (f[i] < i) continue;
        edge.emplace_back(i, f[i]);
    }

    if (not edge.empty()) {
        auto [a, b] = edge[0];
        for (int i = 1; i < edge.size(); i++) {
            auto [x, y] = edge[i];
            res.push_back({a, x, y});
        }
        for (int i = 1; i <= n; i++) {
            if (f[i] != -1) continue;
            res.push_back({a, b, i});
            b = i;
        }
    }

    cout << res.size() << "\n";
    for(auto [x, y, z] : res)
        cout << x << " " << y << " " << z << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
        solve();

    return 0;
}

E. Common Generator

我们首先求出每个数\(a_i\)最小质因子\(b_i\)。

如果每一个数的最小质因子都不是本身，换句话说每一个数都不是质数，则每个数的次小质因子一定是大于等于\(2\)。也就是说对于每个数都存在\(2b_i \le a_i\)。并且

\[(2\times 1) \rightarrow (2 \times 2) \rightarrow \dots \rightarrow 2b_i \rightarrow 3b_i\rightarrow \dots \rightarrow a_i \]

这样的路径一定存在，所以\(2\)一定是答案。

剩下的情况就是存在一些数是质数。

首先我们要知道，任何一个质数一定不能按照题目的方法被构造。我们可以反证法，如果一个数\(a\)加上自己的因子\(b\)等于一个质数\(p\)，则一定有

\[p = a + b = kb + b = (k + 1) b \]

则\(p\)会有\((k+1)\)和\(b\)这两个因子，不符合质数定义。

因此如果存在两种质数则一定无解。

那么，我们就必须要选择唯一出现的质数\(p\)作为答案，剩下就是我们要判断这个答案是否合法。

  1. 如果这个数是\(p\)的倍数，一定可以被构造

  2. 如果这个数小于\(2p\)，一定不能被构造，无解。

  3. 如果这个数是偶数，则一定可以被构造，令\(a_i = 2k\)，并且\(a_i \ge 2p\)，则一定存在如下构造方法

    \[p \rightarrow 2p \rightarrow 2(p+1) \rightarrow 2(p+2) \rightarrow 2k = a_i \]

  4. 如果这个数减最小质因子大于等于\(2p\)，则一定可以被构造。首先这个数奇数，且最小质因子一定是奇数，则这个数减最小质因子一定是这个偶数，并且是这个数一个因数，记为\(x\)。因为满足了\(x\ge 2p\)，则一定可以用 3 的方法构造出\(x\)，再构造出\(a_i\)。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const i32 inf = INT_MAX / 2;

const int mod = 1e9 + 7;

const int N = 4e5;

vi minp;

void init() {
    minp = vi(N + 1, inf);
    for (int i = 2; i <= N; i++) {
        if (minp[i] != inf) continue;
        for (int j = i; j <= N; j += i)
            minp[j] = min(minp[j], i);
    }
    return;
}


void solve() {
    int n;
    cin >> n;

    vi a(n);

    for (int i = 0; i < n; i++) cin >> a[i];

    int must = -1;

    for (int i = 0; i < n; i++) {
        if (a[i] != minp[a[i]]) continue;
        if (must == -1) must = a[i];
        else if (must != a[i]) {
            cout << "-1\n";
            return;
        }
    }

    if (must == -1) {
        cout << "2\n";
        return;
    }

    for (int i = 0; i < n; i++) {
        if (a[i] % must == 0) continue;

        if (a[i] < must * 2) {
            cout << "-1\n";
            return;
        }

        if (a[i] % 2 == 0) continue;

        if (a[i] - minp[a[i]] < must * 2) {
            cout << "-1\n";
            return;
        }

    }
    cout << must << "\n";
    return;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    init();

    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

标签：cnt,ai,vi,--,Codeforces,long,985,int,using
From： https://www.cnblogs.com/PHarr/p/18538526

相关文章

  • 小北的字节跳动青训营与LangChain实战课：深入探索Chain的奥秘（上）写一篇完美鲜花推文？用Se
     前言    最近，字节跳动的青训营再次扬帆起航，作为第二次参与其中的小北，深感荣幸能借此机会为那些尚未了解青训营的友友们带来一些详细介绍。青训营不仅是一个技术学习与成长的摇篮，更是一个连接未来与梦想的桥梁~小北的青训营XMarsCode技术训练营——AI加码，字节跳......
  • P2123 皇后游戏 / [USACO12JAN] Mountain Climbing S / P1248 加工生产调度 题解
    P2123皇后游戏/[USACO12JAN]MountainClimbingS/P1248加工生产调度先来看P2123。我们把这个特别重要的公式打出来：\[c_{i}=\begin{cases}a_{1}+b_{1}&,i=1\\\displaystyle\max\left\{c_{i-1},\sum_{j=1}^{i}a_{j}\right\}+b_{i}&,2\leqi\leqn\end{......
  • C++中的RAII与内存管理
    C++中的RAII与内存管理引言资源获取即初始化（ResourceAcquisitionIsInitialization，简称RAII）是C++编程中一种重要的编程范式，它通过对象生命周期来管理资源，确保资源在不再需要时能够被正确释放。本文将从C++的内存布局入手，逐步深入到栈区、堆区的概念，new和delete的操作原理，最终......
  • 大模型携手AI原生应用融入全产业场景
    前言10月17日，百度世界2023在北京首钢园召开。百度集团执行副总裁、百度智能云事业群总裁沈抖宣布，对“云智一体”的战略内涵全面升级，即云智一体，深入产业，生态繁荣，AI普惠。重磅发布“千帆AI原生应用开发工作台”，加速企业AI原生应用落地；发布了国内首个AI原生应用商店；面向企业落......
  • POLIR-Society-Organization-Management: “How”-关系网络+组织建设+目标: 计划：管人:
    POLIR-Society-Organization-Management:“How”沟通+关系网络Object的Role:Internalboss/上级:Outcome,平级:Team/Organization员工:RoleExternalCustomer:7P+RelationshipSupplierCompetetorIndividualGovernment组织建设分辨好坏对错是非目......
  • roomGPT - 用 AI 打造专属你的梦幻房间
    更多AI开源软件：AI开源-小众AIhttps://www.aiinn.cn/sourcesroomGPT使用了ML模型以及ControlNet来生成各式各样的房间，他会根据你上传的房间照片，自动生成一张你“梦幻房间”的图片。​​主要功能上传房间图片：用户可以通过上传实际拍摄的房间照片或3D渲染图，RoomGPT......
  • B. Replacement （python解）-codeforces
    B.Replacement（python解）-codeforces原题链接：B.Replacement问题分析：我们有两个二进制字符串：s（长度为n）和r（长度为n-1）。根据游戏规则，我们需要在s上执行n-1次操作。在每次操作中，我们选择一个索引k，使得s[k]和s[k+1]不相同并将这两个字符替换为r[i]（第i次操作中r的......
  • 【大模型应用开发 动手做AI Agent】Agent的感知力：语言交互能力和多模态能力
    AIAgent,语言交互,多模态感知,大模型应用,自然语言处理,计算机视觉1.背景介绍在人工智能领域，AIAgent（智能代理）作为一种能够感知环境、做出决策并与环境交互的智能体，扮演着越来越重要的角色。一个强大的AIAgent需要具备敏锐的感知能力，才能有效地理解和响应周围世......
  • 【大模型应用开发 动手做AI Agent】Agent带来新的商业模式和变革
    大模型、AIAgent、应用开发、商业模式、变革、智能化、自动化1.背景介绍近年来，人工智能（AI）技术取得了飞速发展，特别是大模型的涌现，为AI应用带来了前所未有的机遇。大模型，是指参数规模庞大、训练数据海量的人工智能模型，具备强大的泛化能力和学习能力，能够在自然语言处理、......
  • 2024最新AI绘画系统软件（Midjourney）+GPT4文档分析总结，多模态识图理解，AI文生图/图生图/
    一、前言人工智能的快速发展已成为全球关注的焦点，其应用领域广泛，涵盖绘图、语言处理、视频编辑等。前沿技术不仅推动科技创新，还在艺术创作、内容生产和商业实践等方面展示出巨大潜力。例如，AI语言模型显著提升了内容自动生成、智能客服和文本翻译的效率及用户体验；AI绘图技术为......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99