首页 > 其他分享 >2023 CCPC 秦皇岛

2023 CCPC 秦皇岛

时间：2024-09-16 22:46:59浏览次数：1  
标签：秦皇岛 int vi cin long CCPC i64 2023 using

A. Make SYSU Great Again I

因为\(k \ge 2n\)，所以可以顺序按照以阶梯形状摆放，这样可以保证每行每列两个，且\(\gcd\)都是 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>;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    int t = 1;
    for (int i = 1; i <= n and t <= k; i++) {
        cout << i << " " << i << "\n", t++;
        if (i == n)
            cout << i << " " << 1 << "\n", t++;
        else
            cout << i << " " << i + 1 << "\n", t++;
    }
    for (int i = 1; i <= n and t <= k; i++) {
        for (int j = 1 + ( i == n); j < i and t <= k; j++) {
            cout << i << " " << j << "\n", t++;
        }
        for (int j = i + 2; j <= n and t <= k; j++) {
            cout << i << " " << j << "\n", t++;
        }
    }
    return 0;
}

D. Yet Another Coffee

考虑一种贪心的情况，把所有的打折卡按照结束时间排序，然后我们逐个打折卡考虑，我们把打折卡给最便宜的咖啡使用一定最优，因为打折卡是使得价格为负数。操作完后，贪心的选择最便宜的即可。

#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>;

void solve() {
    int n, m;
    cin >> n >> m;
    vi a(n);
    for (auto &i: a) cin >> i;
    vector<pii> b(m);
    for (auto &[r, w]: b) cin >> r >> w;
    ranges::sort(b);
    multiset<int> pre;
    int t = 0;
    for (int x; auto [r, w]: b) {
        while (t < n and t < r) pre.insert(a[t++]);
        x = *pre.begin(), pre.erase(pre.begin()), pre.insert(x - w);
    }
    while (t < n) pre.insert(a[t++]);
    for (int i = 1, res = 0; i <= n; i++) {
        res += *pre.begin(), pre.erase(pre.begin());
        cout << res << " ";
    }
    cout << "\n";
    return;
}

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

F. Mystery of Prime

找规律发现对于两个奇偶相同的数\(x,y\)，存在一个数\(k\)可以使得\(x+k,y+k\)均为质数。然后相邻的两个数奇偶必须不同，除了一种特殊情况，就是两个\(1\)相邻。

因此我们可以设计状态\(f[i][0/1/2/3]\)表示前\(i\)个数，且第\(i\)个数的状态为\(0\)不改变、\(1\)修改为\(1\)、\(2\)修改为奇数、\(3\)修改为偶数。

然后转移就可以分为两类，一种相邻两个数，我们根据刚才说的奇偶不同和两个\(1\)的情况进行转移。还有一种是相邻三个数，两侧的数字就相同的情况。

#include<bits/stdc++.h>

using namespace std;

using vi = vector<int>;

const int inf = INT_MAX / 2;

bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    vi a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 2) {
        if (is_prime(a[1] + a[2])) cout << 0;
        else cout << 1;
        return 0;
    }

    vector f(n + 1, vi(4, inf));// 0 不变, 1 变1, 2 变奇, 3 变偶

    f[1][0] = 0;
    f[1][1] = (a[1] != 1);
    f[1][2] = f[1][3] = 1;

    for (int i = 2; i <= n; i++) {
        // 0
        if (is_prime(a[i] + a[i - 1])) f[i][0] = min(f[i][0], f[i - 1][0]);
        if (is_prime(a[i] + 1)) f[i][0] = min(f[i][0], f[i - 1][1]);
        if (a[i] % 2 == 1) f[i][0] = min(f[i][0], f[i - 1][3]);
        else f[i][0] = min(f[i][0], f[i - 1][2]);
        // 1
        if (is_prime(1 + a[i - 1])) f[i][1] = min(f[i][1], f[i - 1][0] + (a[i] != 1));
        f[i][1] = min(f[i][1], f[i - 1][1] + (a[i] != 1));
        f[i][1] = min(f[i][1], f[i - 1][3] + (a[i] != 1));
        // 2
        if (a[i - 1] % 2 == 0) f[i][2] = min(f[i][2], f[i - 1][0] + 1);
        f[i][2] = min(f[i][2], f[i - 1][3] + 1);
        // 3
        if (a[i - 1] % 2 == 1) f[i][3] = min(f[i][3], f[i - 1][0] + 1);
        f[i][3] = min(f[i][3], f[i - 1][1] + 1);
        f[i][3] = min(f[i][3], f[i - 1][2] + 1);
        // 改中间
        f[i][1] = min(f[i][1], f[i - 2][1] + 1 + (a[i] != 1)); // 1 x 1
        f[i][1] = min(f[i][1], f[i - 2][2] + 1 + (a[i] != 1)); // 奇 x 1
        f[i][2] = min(f[i][2], f[i - 2][2] + 2); // 奇 x 奇
        f[i][2] = min(f[i][2], f[i - 2][1] + 2); // 1 x 奇
        f[i][3] = min(f[i][3], f[i - 2][3] + 2); // 偶 x 偶
        if (a[i] % 2 == 1) { // ai 是 奇
            f[i][0] = min(f[i][0], f[i - 2][1] + 1); // 1 x ai
            f[i][0] = min(f[i][0], f[i - 2][2] + 1); // 奇 x ai
            if (a[i - 2] % 2 == 1) f[i][0] = min(f[i][0], f[i - 2][0] + 1); // ai-2 x ai
        } else { // ai 是 偶
            f[i][0] = min(f[i][0], f[i - 2][3] + 1);// 偶 x ai
            if (a[i - 2] % 2 == 0) f[i][0] = min(f[i][0], f[i - 2][0] + 1); // ai-2 x ai
        }
    }
    cout << ranges::min(f[n]);
    return 0;
}

G. Path

手推一下发现，其实答案就是\(\sum|a_i - a_{i-1}| + \sum |b_i - b_{i-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>;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vi a(n), b(m);
    for (auto &i: a) cin >> i;
    for (auto &i: b) cin >> i;
    int res = 0;
    for (int i = 1; i < n; i++)
        res += abs(a[i] - a[i - 1]);
    for (int i = 1; i < m; i++)
        res += abs(b[i] - b[i - 1]);
    cout << res;
    return 0;
}

J. Keyi LIkes Reading

其实只有13个物品，然后我们可以设计状态\(f[i][j]\)表示前\(i\)天选了\(j\)是否成立。其中\(j\)是二进制表示那些被选了。

因此我们可以用\(O(13\times (2^{13})^2)\)的代价转移出来。

#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>;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    vi cnt(13);
    int n, w;
    cin >> n >> w;

    for (int i = 1, x; i <= n; i++)
        cin >> x, cnt[x - 1]++;
    ranges::sort(cnt, greater<>());
    n = 0;
    while (n < 13 and cnt[n] != 0) n++;
    cnt.resize(n);
    vi can;
    int N = 1 << n;
    for (int i = 1, sum; i < N; i++) {
        sum = 0;
        for (int j = 0; j < n; j++)
            if ((i >> j) & 1) sum += cnt[j];
        if (sum <= w) can.push_back(i);
    }
    vi f(N);
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        auto g = f;
        for (int t = 1; t < N; t++) {
            for (auto p: can) {
                if ((t | p) != t) continue;
                g[t] |= f[t ^ p];
            }
        }
        f = move(g);
        if (f[N - 1]) {
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}

然后赛时因为写错了一点，导致越界进而导致 TLE。我按头写了一个优化，首先我们倒序枚举，这样可以优化空间，然后对于状态\(j\)，我强制要求当前学习的单词中包含了\(j\)的\(msg\)，这样的话可以把复杂度减小\(\frac{1}{13}\)。\(msg\)是最高有效位。

#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>;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    vi cnt(13);
    int n, w;
    cin >> n >> w;

    for (int i = 1, x; i <= n; i++)
        cin >> x, cnt[x - 1]++;
    ranges::sort(cnt, greater<>());
    n = 0;
    while (n <= 13 and cnt[n] != 0) n++;
    cnt.resize(n);

    auto msg = [&](int x) {
        for (int i = n - 1; i >= 0; i--) {
            if ((x >> i) & 1) return i;
        }
    };

    vector<vi> can(n);

    int N = 1 << n;
    for (int i = 1, sum; i < N; i++) {
        sum = 0;
        for (int j = 0; j < n; j++)
            if ((i >> j) & 1) sum += cnt[j];
        if (sum <= w) can[msg(i)].push_back(i);
    }
    vi f(N);
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int t = N - 1; t >= 1; t--) {
            if (f[t]) continue;
            for (auto p: can[msg(t)]) {
                if ((t | p) != t) continue;
                if (f[t ^ p] == 0)continue;
                f[t] = 1;
                break;
            }
        }
        if (f[N - 1]) {
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}

标签：秦皇岛,int,vi,cin,long,CCPC,i64,2023,using
From： https://www.cnblogs.com/PHarr/p/18416717

相关文章

  • 基于django+vue分类学科竞赛管理系统-后台2023【开题报告+程序+论文】-计算机毕设
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容研究背景随着教育改革的深入和对学生综合素质培养重视程度的提升，学科竞赛作为提升学生创新能力、实践能力和团队协作精神的重要途径，其规模和影响力......
  • 202312-2 因子化简ccfcsp
    常规质数因子带相关资料抄写稍加修改指数的筛选部分includeinclude<math.h>typedeflonglongll;usingnamespacestd;boolisprime(lln){inti;if(n<=1)returnfalse;intsq=(int)sqrt(1.0n);for(i=2;i<=sq;i++){if(n%i==0)returnfalse;}returntrue;}cons......
  • 信息学奥赛初赛天天练-90-CSP-S2023基础题2-离散数学、染色、完全三叉树、平面图、边
    PDF文档公众号回复关键字:202409152023CSP-S选择题1单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）6以下连通无向图中，()一定可以用不超过两种颜色进行染色A完全三叉树B平面图C边双连通图D欧拉图7最长公共子序列长度常常用来衡量两个序列的相......
  • 二分图 by LFRED2023
    本文由LFRED2023撰写，由本人帮忙代发二分图二分图的定义二分图又叫二部图，是图论的一种特殊模型假设$S=(V,E)$是一个无向图。如果顶点$V$可分割为两个互不相交的子集$(A,B)$，并且图中的每条边$(i,j)$所关联的两个顶点$i$和$j$分别属于这两个不同的顶点......
  • 2023年全国高中数学联合竞赛A卷加试P3：组合极值、染色
    题目求具有下述性质的最小正整数$k$：若将$1,2,\cdots,k$中的每个数任意染为红色或者蓝色,则或者存在$9$个不同的红色的数$x_1,x_2,\cdots,x_9$满足$x_1+x_2+\cdots+x_8<x_9,$或者存在$10$个互不相同的蓝色的数$y_1,y_2,\cdots,y_{10}$满足$y_1+y_2+\cdots+y_9<y_{10}.$解......
  • 基于django+vue电脑DIY微信小程序演示录像22023【开题报告+程序+论文】-计算机毕设
    本系统（程序+源码+数据库+调试部署+开发环境）带论文文档1万字以上，文末可获取，系统界面在最后面。系统程序文件列表开题报告内容研究背景随着科技的飞速发展，个人电脑（PC）已成为人们日常生活与工作中不可或缺的一部分。然而，在市场上琳琅满目的电脑配件和复杂多变的配置选项中，许多......
  • 信息学奥赛初赛天天练-89-CSP-S2023基础题1-linux常用命令、完全平方数、稀疏图、队列
    PDF文档公众号回复关键字:202409142023CSP-S选择题单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）1在Linux系统终端中，以下哪个命令用于创建一个新的目录?()AnewdirBmkdirCcreateDmkfold2从0,1,2,3,4中选取4个数字，能组成(......
  • 2024 CCPC Online
    A(军训I)大分类讨论#pragmaGCCoptimize("O3,unroll-loops")#pragmaGCCtarget("avx2,bmi,bmi2,lzcnt,popcnt")//如果在不支持avx2的平台上将avx2换成avx或SSE之一#include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedef......
  • springboot+vue在线考试系统的设计与演示录像220239【程序+论文+开题】计算机毕业设计
    系统程序文件列表开题报告内容研究背景随着互联网技术的飞速发展，教育领域正经历着前所未有的变革。传统的考试方式，如纸质试卷考试，不仅效率低下、成本高昂，而且在组织、阅卷及反馈等环节上存在诸多不便。尤其是在大规模考试或远程教育中，这些问题尤为突出。因此，开发一种高效、......
  • 时序必读论文05｜PatchTST : 时序数据Patch已成趋势【ICLR 2023】
    书接上回，我们在之前的文章已经分析了直接把transformer应用到时间序列预测问题的不足，其中我们总结了4个不足：分别是：注意力机制的计算复杂度高，为O(N^2)，并且计算得出的权重仅有少部分有用；注意力机制仅建立单时间点位之间的关系，实际能提取到的信息非常有限；对时序或者说位......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99