2022 年 CCPC 河南省赛 (A,E,F,G,H)

这篇具有很好参考价值的文章主要介绍了2022 年 CCPC 河南省赛 (A,E,F,G,H)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

更好的阅读体验 \color{red}{更好的阅读体验} 更好的阅读体验



A. Mocha 上小班啦


原题链接

题目大意

  • 一个数由互不相同的 n n n 位数组成。
  • 输出 n n n 位的满足上述条件的最小整数(不含前导零)。
  • 不存在则输出 − 1 -1 1

思想

  • 签到题。
  • n <= 10 时,最小的 n n n 位数的序列为 [1, 0, 2, 3, 4, 5, 6, 7, 8 ,9]
  • n > 10 时不存在可以满足条件的数。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int a[] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};

void solve(){

    int n; cin >> n;
    if(n > 10) cout << -1 << endl;  //大于10不存在满足条件的数
    else{
        for(int i = 0 ; i < n; i ++) cout << a[i];  //注意交换1和0的顺序
    }

    return ;

}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

E. Serval 的俳句


原题链接

题目大意

  • 给定一个长度为 n n n 的字符串 S S S
  • 求是否存在长度为 17 17 17 的子序列满足:
    • S ′ 1 , S ′ 2 , S ′ 3 , S ′ 4 , S ′ 5 S′_1 , S′_2 , S′_3 , S′_4 , S′_5 S1,S2,S3,S4,S5 为同一个字符;
    • S ′ 6 , S ′ 7 , . . . , S ′ 11 , S ′ 12 S′_6 , S′_7 , . . . , S′_{11}, S′_{12} S6,S7,...,S11,S12 为同一个字符;
    • S ′ 13 , S ′ 14 , S ′ 15 , S ′ 16 , S ′ 17 S′_{13}, S′_{14}, S′_{15}, S′_{16}, S′_{17} S13,S14,S15,S16,S17 为同一个字符。
  • 存在输出该子序列,不存在则输出 none

思想

  • 签到题。
  • 暴力枚举 S i S_i Si,统计满足的 S 1 ′ ∼ S 5 ′ S'_1 \sim S'_5 S1S5,若可以找到满足的子序列,标记该字符后进入下一层循环;
  • 暴力枚举 S j S_j Sj,统计满足的 S 6 ′ ∼ S 12 ′ S'_6 \sim S'_{12} S6S12,若可以找到满足的子序列,标记该字符后进入下一层循环;
  • 暴力枚举 S k S_k Sk,统计满足的 S 13 ′ ∼ S 17 ′ S'_{13} \sim S'_{17} S13S17,若可以找到满足的子序列,则将上面标记的直接输出即可。
  • n < 17 时或者没有找到存在可以满足条件的子序列,则输出 none
  • 由于每一段的子序列很短,最坏的情况是 2 6 3 × 5 2 × 7 = 3 , 075 , 800 26^3 \times 5^2 \times 7 = 3,075,800 263×52×7=3,075,800,实际上的情况会远小于该时间复杂度,所以完全 O K OK OK

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 200;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){

    int n; cin >> n;
    if(n < 17){  //长度不够,不可能找到
        cout << "none" << endl;
        return ;
    }

    string s; cin >> s;
    int vis1[N] = {0};  //统计相同的前5个字符
    for(int i = 0; i < s.size(); i ++){
        vis1[s[i]] ++;
        if(vis1[s[i]] == 5){
            char op1 = s[i];  //标记前5个字符
            int vis2[N] = {0};  //统计相同的中间7个字符
            for(int j = i + 1; j < s.size(); j ++){
                vis2[s[j]] ++;
                if(vis2[s[j]] == 7){
                    char op2 = s[j];  //标记中间7个字符
                    int vis3[N] = {0};  //统计相同的后5个字符
                    for(int k = j + 1; k < s.size(); k ++){
                        vis3[s[k]] ++;
                        if(vis3[s[k]] == 5){  //找到最后5个字符,直接输出
                            for(int u = 0; u < 5; u ++) cout << op1;
                            for(int u = 0; u < 7; u ++) cout << op2;
                            for(int u = 0; u < 5; u ++) cout << s[k];
                            return ;
                        }
                    }
                }
            }
        }
    }
	//找不到满足条件的序列
    cout << "none" << endl; 
    return ;

}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

F. 集合之和


原题链接

题目大意

  • 对于两个有限的数集 A , B A,B A,B,定义 A + B A+B A+B 为:
    • A + B = { x + y   ∣   x ∈ A , y ∈ B } A + B = \{x + y~|~ x \in A, y \in B \} A+B={x+y  xA,yB}
  • 记有限数集 A A A 的元素个数为 ∣ A ∣ |A| A
  • 给定 n n n,求满足 ∣ A + A ∣ = n |A + A| = n A+A=n ,且满足 ∀ x ∈ A , 0 ≤ x ≤ 5 × 1 0 5 \forall x \in A, 0\le x \le 5\times10^5 xA,0x5×105 的数集 A A A
  • 若存在 A A A 满足上述条件,输出内含元素的数量并输出所含元素(任意解均可),不存在则输出 − 1 -1 1

思想

  • 思维,规律,构造。

  • 构造简单数集 A = { 0 , 1 , 2 , … , k } , ∣ A ∣ = k A = \{0,1,2,\dots,k\}, |A| = k A={0,1,2,,k},A=k,则 A + A = { 0 , 1 , 2 , … , 2 k } , ∣ A + A ∣ = 2 k + 1 A + A = \{0,1,2,\dots,2k\},|A+A| = 2k + 1 A+A={0,1,2,,2k},A+A=2k+1

  • 通过上述构造,显然当 n n n 为奇数时一定有解,我们只需要构造满足如上规则的数集即可。

  • 接下来讨论 n n n 为偶数的情况:

    • ∣ A ∣ = 2 , ∣ A + A ∣ = 3 |A| = 2, |A+A| = 3 A=2,A+A=3,当 n = 2 n = 2 n=2 时无解;
    • ∣ A ∣ = 3 , 5 ≤ ∣ A + A ∣ ≤ 6 |A| =3,5\le |A+A|\le 6 A=3,5A+A6,当 n = 4 n = 4 n=4 时无解;
    • 其他情况下,构造数集 A = { 0 , 2 , 3 , … , k } A = \{0,2,3,\dots,k\} A={0,2,3,,k},则 A + A = { 0 , 2 , 3 , … , 2 k } , ∣ A + A ∣ = 2 k A+A =\{0,2,3,\dots,2k\},|A+A| = 2k A+A={0,2,3,,2k},A+A=2k
  • 综上所述,根据 n n n 的奇偶性按照上述规则构造即可。


代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, string> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int n;

void solve(){

    cin >> n;

    if(n == 2 || n == 4){
        cout << -1 << endl; 
        return ;
    }

    if(n % 2 != 0){  //奇数构造0, 1, 2, 3,...,(n - 1) / 2
        cout << (n - 1) / 2 + 1 << endl;  
        for(int i = 0; i <= (n - 1) / 2; i ++) cout << i << ' ';
    }
    else{  //偶数构造 0, 2, 3,..., n / 2
        cout << n / 2 << endl;
        cout << 0 << ' ';
        for(int i = 2; i <= n / 2; i ++) cout << i << ' ';
    }

}

int main(){

    IOS;

    int _ = 1;

    while(_ --){
        solve();
    }

    return 0;

}

G. Mocha 上大班啦


原题链接

题目大意

  • 给定 n n n 01 01 01 串以及 q q q 次操作,每次操作会把第 i i i 个串的 l − r l − r lr 位替换为和第 j j j 个串的 l − r l − r lr 位分别进行与运算的结果。
  • i i i 次操作有概率 p i p_i pi 成功。
  • 询问最后 n n n 个串与运算得到的串中 1 1 1 的个数。

思想

  • 思维题。
  • 概率期望套皮,其实无需处理。
  • 只要一列中出现过 0 0 0,由于进行的是“与”位运算,操作多少次都不会影响任何一个 01 01 01 串第 i i i 位的值,结果一定是 0 0 0
  • 故直接计算初始 01 01 01 串与操作后的 1 1 1 的个数即为答案。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, string> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

const int N = 1010;

char a[N][4 * N];

int n, m;

void solve(){

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

    int q; cin >> q;
    while(q --){
        for(int i = 0; i < 5; i ++){
            int op; cin >> op;
        }
    }

    for(int i = 0; i < m; i ++){
        int cnt = 1;
        for(int j = 0; j < n; j ++){
            if(a[j][i] == '0') cnt = 0;  //存在某一列为0时
        }
        res += cnt;
    }

    cout << res << endl;

}

int main(){

    IOS;

    int _ = 1;

    while(_ --){
        solve();
    }

    return 0;

}

H. 旋转水管


原题链接

题目大意

  • 给定 2 × m 2 \times m 2×m 的水管图,水管有 I,L 两种,且两种水管均可以旋转。
  • 问是否可以通过旋转水管,使得水从 x x x 列流入后从 y y y 列流出。

思想

  • DFS 搜索。
  • 水管出水状态和进入状态相关,故需要记录上一个格子流入下一个格子时的状态。
  • 分析状态可知:
    • 对于 I 形的水管,流出状态和流入状态相同。
    • 对于 L 形的水管,当流入状态是 ↑ \uparrow ↓ \downarrow 时,流出时都有两种状态 ← \leftarrow → \rightarrow ;当流入状态是 ← \leftarrow → \rightarrow 时,流出时都有两种状态 ↑ \uparrow ↓ \downarrow
  • 根据上述分析,我们可以得到相应状态的偏移量,在搜索时通过加上该偏移量达到坐标的转移。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

char mp[2][N];
bool vis[2][N];

int m, sl, el;

bool flag = 0;

void dfs(int l, int r, int st){

    if(flag == 1) return ;  //满足条件直接返回

    if(l == 2 && r == el - 1){  //越界只有到达出口的情况合法
        flag = 1;  //标记答案
        return ;
    }

    if(l < 0 || l >= 2 || r < 0 || r >= m) return ;  //越界直接返回

    if(vis[l][r]) return ;  //走过该点返回

    vis[l][r] = 1;  //标记走过

    if(l >= 0 && l < 2 && r >= 0 && r < m){
        if(mp[l][r] == 'I'){  //进入状态和流出状态相同
            if(st == 0) dfs(l + 1, r, 0); 
            if(st == 1) dfs(l, r + 1, 1);
            if(st == 2) dfs(l - 1, r, 2);
            if(st == 3) dfs(l, r - 1, 3);
        }
        else{
            if(st == 0 || st == 2){  //从下面或上面流入的状态
                dfs(l, r + 1, 1);
                dfs(l, r - 1, 3);
            }
            if(st == 1 || st == 3){  //从左边或右边流入的状态
                dfs(l + 1, r, 0);
                dfs(l - 1, r, 2);
            }
        }
    }

    vis[l][r] = 0;  //搜过返回恢复现场

    return ;
}

bool solve(){
    cin >> m >> sl >> el;
    for(int i = 0; i < 2; i ++) cin >> mp[i];

    flag = 0;  //多实例,初始化
    for(int i = 0; i < 2; i ++){
        for(int j = 0; j <= m; j ++) vis[i][j] = 0;
    }

    dfs(0, sl - 1, 0);

    return flag;

}

int main(){

    IOS;

    int _ = 1;

    cin >> _;

    while(_ --){
        if(solve()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;

}

赛后回顾与总结


生涯第一次参加 C C P C CCPC CCPC,先贴一张战绩:

2022 年 CCPC 河南省赛 (A,E,F,G,H)

铜尾巴是 188 188 188,我们队伍 191 191 191 喜提铁牌 (bushi) 啊吧啊吧。。。

赛程回顾

  • 两个大三的队友还是很给力的,上来就切掉了 A A A 题,拿下了一个漂亮的 AC
  • 我之后粗略地计算了一下 E E E 题的时间复杂度,于是直接三个循环暴力切掉了,虽然因为统计字母数量的 vis 数组开小了,白白吃了一发 WA为全队奠定了打铁的基础。
  • 然后我发现 H H H 题是个搜索貌似能行?从此队伍少了一个人。。。
  • 队友开搞 F F F ,上机打表,我在纸上手撕 H H H
  • 队友开搞 G G G ,最后发现是道沙笔套皮期望的诈骗题,光速写完不测样例直接冲,小 WA 一下就过了,没有一开始切掉就很可惜。
  • 然后 zhgg 开始帮我调我的沙笔 H H H 题,因为觉得 BFS 的思路完全没问题,死磕到底,最后头晕脑胀坐标都搞混了,剩半小时重写一次最后都没搞出来,直接大寄 (。_。)。
  • 最后绝望看榜 200 + 200+ 200+ 的名次去掉大星的队伍粗略算一下能拿铜尾巴~~(赛后发现还是太天真)~~,不过维他柠檬茶是真的好喝,逃。

赛后总结

  • 打铁的根本的原因还是自己能力太弱小了。
  • 其本质就是我的懒惰,在本该出成绩的时期思想上懈怠、行动上松懈了。训练量达不到还妄想着出成绩。
  • 这次参赛也明显感受到了经验的不足,两个大三的队友异常地镇定和发挥稳定,相较而言,没有大赛经验的我在比赛时手忙脚乱拖累了团队。
  • 最后是比赛题目的分配和合作,团队协同参赛的我们互相没有磨合好,队友在讨论时我独自去切没有把握的题,最后还没有解出来,也错过了讨论和看其他题目的机会和时间。

PS文章来源地址https://www.toymoban.com/news/detail-453635.html

  • 今后的计划:
    • 加训;
    • 加训;
    • 还是 TMD 加训。
  • 和队友抽空多打几场 VP,训练团队合作。
  • 卧薪尝胆,下次 I C P C ICPC ICPC 必将胜利。

到了这里,关于2022 年 CCPC 河南省赛 (A,E,F,G,H)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【附源码】基于flask框架基于微信小程序的河南省美食分享平台 后台(python+mysql+论文)

    本系统(程序+源码)带文档lw万字以上   文末可获取本课题的源码和程序 选题背景: 随着移动互联网的飞速发展,微信小程序以其无需下载安装、使用方便的特点,逐渐成为人们日常生活中获取信息和进行交流的重要工具。特别是在美食分享领域,人们对各地特色美食的了

    2024年04月27日
    浏览(44)
  • “卓见杯”郑州轻工业大学第十五届程序设计大赛暨河南省高校邀请赛题解

    C 最大的数 — 贪心 首先n个点有n条边必然有环,因此可以无限制的加数,又因为题目要求最大不超过1e9,所以答案一定是9位数 如果把形成的环缩点的话就会变成拓扑序列,首先要找到数字最大的那几个点,把他们入队,然后遍历他们的下一个点,找到下一个点里的最大值,

    2023年04月13日
    浏览(60)
  • 【超好懂的比赛题解】2022CCPC四川省赛 个人题解

    title : “海康威视杯“ 2022年第十四届四川省大学生程序设计大赛 tags : ACM,练习记录 date : 2022-10-18 author : Linno 题目链接:https://ac.nowcoder.com/acm/contest/42105 出题数量:5/11 (顺序:K-F-B-H-A) A-Adjacent Swapping 显然可以先贪心移动(直接扫一遍)字符使前后两半在字符数量上是一样的

    2024年02月08日
    浏览(58)
  • QOJ 6504. CCPC Final 2022 D Flower's Land 2题解

    给你一个只含 (0,1,2) 的序列,相邻两个相同的数字可以直接消掉。 询问包含两种 区间所有数 (+1) 并对 (3) 取模。 求一段区间能否用上述消除方式消完。 在我们做相邻两个能被消掉,判断一段区间能否被消掉时,常常用矩阵来考虑。 把每一种颜色用一种矩阵来表示,若当

    2024年02月15日
    浏览(45)
  • Qt 物联网系统界面开发 “ 2022湖南省大学生物联网应用创新设计竞赛技能赛 ——应用物联网的共享电动自行车 ”

    本篇源于 “ 2022 湖南省大学生物联网应用创新设计竞赛技能赛参考样题 ” ——应用物联网的共享电动自行车 针对共享电动自行车应用场景,设计实现共享电动自行车、用户、管理等相关人、物互联的物联网系统。假设系统由电动自行车、后端服务器、前端应用终端、以及电

    2024年02月11日
    浏览(35)
  • 论文阅读:GamutMLP A Lightweight MLP for Color Loss Recovery

    这篇文章是关于色彩恢复的一项工作,发表在 CVPR2023,其中之一的作者是 Michael S. Brown,这个老师是加拿大 York 大学的,也是 ISP 领域的大牛,现在好像也在三星研究院担任兼职,这个老师做了很多这种类似的工作,通过一些轻量模型,将一些数据转换过程中的变换关系进行拟

    2024年02月19日
    浏览(36)
  • 图像色彩增强相关论文阅读-Representative Color Transform for Image Enhancement(ICCV2021)

    作者:Hanul Kim1, Su-Min Choi2, Chang-Su Kim3, Yeong Jun Koh 单位:Seoul National University of Science and Technology 2Chungnam National University 3Korea University 前人方法都是encode-decode方式,丢失细节;密集转化也限制颜色空间的迁移效果; 本文使用颜色迁移表征(RCT)表征颜色变化,根据输入和表征颜

    2024年02月11日
    浏览(45)
  • 体验百度文心一言AI大模型生产生成河南大学、太原理工大学、哈尔滨工程大学和青岛大学简介

    河南大学(Henan University),简称“河大”,坐落于中国河南省,是河南省人民政府与中华人民共和国教育部共建高校,国家“双一流”建设高校,入选国家“111计划”、中西部高校基础能力建设工程、卓越医生教育培养计划、卓越法律人才教育培养计划、卓越教师培养计划、

    2024年02月11日
    浏览(49)
  • Latent Diffusion(CVPR2022 oral)-论文阅读

    论文: 《High-Resolution Image Synthesis with Latent Diffusion Models》 github: https://github.com/CompVis/latent-diffusion 为了使得DM在有限计算资源下训练,同时保留其生成质量及灵活性,作者将其应用于预训练编解码器的隐空间。基于表征训练扩散模型达到降低计算量及细节保留的最优点。作者

    2024年02月11日
    浏览(45)
  • HumanNeRF(CVPR2022 oral)-人体重建论文阅读

    论文: 《HumanNeRF: Free-viewpoint Rendering of Moving People from Monocular Video》 github: https://github.com/chungyiweng/humannerf 作者提出HumanNeRF,给出复杂动作人体单视角视频,暂停任一帧渲染出任意视角下该人体,甚至360度视角下该人体; HumanNeRF优化了人在标准T姿势下的表征,与运动场相一致,

    2024年02月15日
    浏览(97)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包