ZISUOJ 2024算法基础公选课练习一（1）

🕗 发布于 2024-11-07 07:09 算法 数据结构

前言、

又是一年算法公选课，与去年不同的是今年学了一些纯C++（而不是带类的C）

一、我的C++模板

1.1 模板1

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    return 0;
}

1.2 模板2

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    
}
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    //如果有多组数据，则放开下一行的注释
    // std::cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

二、题目总览

三、具体题目

3.1 问题 A: 删数问题(Tan1)：

思路：

用贪心算法（属于不是很容易察觉的那种）。跑k次循环，每次循环找出第一个逆序对，此时需要删去的就是逆序对中的第一个数（较大的那个）；如果找不到逆序对，那么删除最后一个数。另外，特判出现前导零的情况，既可以用string的erase()方法，也可以用reverse()函数反转字符串，再使用pop_back()函数（主要是因为没有pop_front()函数，猜测string是拿vector实现的，而不是deque）。

参考代码1：

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::string a;int k;
    std::cin >> a >> k;
    for(int i = 0;i<k;i++) {
        int idx = 0;
        while(idx<a.size()-1&&a[idx]<=a[idx+1]) idx++;
        if(idx!=a.size()-1) {
            a.erase(idx,1);
        }else {
            a.erase(a.size()-1,1);
        }
    }
    while(a.front()=='0'&&a.size()>1) {
        a.erase(0,1);
    }
    std::cout << a << '\n';

    return 0;
}

参考代码2：

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::string a;int k;
    std::cin >> a >> k;
    for(int i = 0;i<k;i++) {
        int idx = 0;
        while(idx<a.size()-1&&a[idx]<=a[idx+1]) idx++;
        if(idx!=a.size()-1) {
            a.erase(idx,1);
        }else {
            a.erase(a.size()-1,1);
        }
    }
    std::string ans = a;
    std::reverse(ans.begin(),ans.end());
    while(ans.back()=='0'&&ans.size()>1){
        ans.pop_back();
    }
    std::reverse(ans.begin(),ans.end());
    std::cout << ans << '\n';

    return 0;
}

3.2 问题 B: 输出亲朋字符串：

思路：

没啥好说的，模拟一下就行，如果打算直接在原字符串上修改，那么需要暂存第一个字符

参考代码：

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::string s;
    std::getline(std::cin,s);
    char tmp = s[0];
    for(int i = 0;i<s.size();i++) {
        if(i!=s.size()-1) {
            s[i]+=s[i+1];
        }else {
            s[i]+=tmp;
        }
    }
    std::cout << s << '\n';

    return 0;
}

3.3 问题 C: 密钥加密：

思路：

注意题中的两个模运算，因为字符串可能存在空格，所以读数据用getline()来读

参考代码：

这里有两个小技巧

1.字符'0'到'9'转数字，我们可以直接异或48，同理，数字转字符'0'到'9'也可以直接异或48得到

2.string下标从0开始，我们可以让它的前面拼接一个字符（通常是空格），这样它有意义的字符下标就从1开始，当然输出的时候记得把第一个字符去掉再输出

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::string key,str;
    while(std::getline(std::cin,key)&&std::getline(std::cin,str)) {
        int len_key = key.size();
        int len_str = str.size();

        std::vector<int> real_key;
        real_key.emplace_back(key[len_key-1]^48);
        for(int i = 0;i<len_key-1;i++) {
            real_key.emplace_back(key[i]^48);
        }

        str = " "+str;
        for(int i = 1;i<=str.size();i++) {
            str[i] = str[i]+real_key[i%len_key];
            str[i] = str[i]>122?str[i]-91:str[i];
        }
        str.erase(0,1);

        std::cout << str << '\n';
    }

    return 0;
}

3.4 问题 D: 排列对称串：

思路：

如果一个字符串前后反转还等于反转前的值，那么它就是对称的字符串，把对称的字符串放进vector，然后排序一下，排序可以写cmp()函数，也可以用C++11的语法糖-匿名函数（我下面的代码是拿匿名函数写的），最后输出vector的内容即可

参考代码：

小技巧：

基于范围的for循环也是C++11的新语法糖，可以遍历一个容器，减少代码书写量

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::vector<std::string> v;
    std::string str;

    while(std::getline(std::cin,str)) {
        std::string reverse_str = str;
        std::reverse(reverse_str.begin(),reverse_str.end());
        if(reverse_str==str) {
            v.emplace_back(str);
        }
    }

    std::sort(v.begin(),v.end(),[&](const std::string &s1,const std::string &s2)->bool {
        if(s1.size()!=s2.size()) return s1.size()<s2.size();
        return s1<s2;
    });

    for(auto &vi:v) {
        std::cout << vi << '\n';
    }

    return 0;
}

3.5 问题 E: 《庆余年》之四大宗师：

思路：

利用哈希表先把每个人的积分算出来，然后拷贝到vector中排序（因为哈希表不支持排序），然后根据要求排序，排序好后输出即可

参考代码：

小技巧：

拷贝可以用copy()函数实现，也可以写一个for循环，然后把数据emplace_back进vector

#include <bits/stdc++.h>
using i64 = long long;
using psi = std::pair<std::string,int>;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::unordered_map<std::string,int> mp;
    std::string player1,player2,result;

    for(int t = 0;t<6;t++) {
        std::cin >> player1 >> player2 >> result;
        if(result=="S") {
            mp[player1]+=3;
        }else if(result=="F") {
            mp[player2]+=3;
        }else {
            mp[player1]+=1;
            mp[player2]+=1;
        }
    }

    std::vector<psi> v(mp.size());
    std::copy(mp.begin(),mp.end(),v.begin());

    std::sort(v.begin(),v.end(),[&](const psi &p1,const psi &p2)->bool {
        if(p1.second!=p2.second) return p1.second>p2.second;
        return p1.first<p2.first;
    });

    for(auto &player:v) {
        std::cout << player.first << '\n';
    }

    return 0;
}

后记：

我写了很多C++11的语法糖，C++新版本出了越来越多的语法糖，存在即合理。新语法糖肯定有优秀的地方，我们在书写代码的时候应该尽可能多地使用新语法

原文地址：https://blog.csdn.net/Beau_Will/article/details/143581098

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：创维E900-S_华为EC6108V9_v9u_海思hi3798mv100华为系统优盘刷机固件包
下一篇：vue3+vite搭建脚手架项目本地运行electron桌面应用

【原创】java+ssm+mysql收纳培训网系统设计与实现
使用java+ssm+mysql开发的收纳视频培训网，系统包含超级管理员，系统管理员、培训师、用户角色，功能如下：超级管理员：管理员管理；用户管理（培训师、用户）；课程管理（课程、课程视频、评论）；预
阅读更多2024-11-07
C# 内存管理与对象生命周期在面向对象设计中的重要性
C# 通过 CLR 提供了自动的内存管理，使用堆（Heap）和栈（Stack）两种不同的内存区域来管理程序中的内存。栈（Stack）：用于存储局部变量和方法调用相关的数据。栈是一种后进先出（LIFO）
阅读更多2024-11-07
Swift 开发教程系列 - 第2章：Swift 基础语法
在这个章节中，我们将介绍 Swift 的基础语法，包括变量与常量的定义、数据类型、类型转换和操作符的使用。掌握这些基础知识能帮助你更熟练地理解和编写 Swift 代码。
阅读更多2024-11-07
【k8s】ClusterIP能http访问，但是不能ping 的原因
ClusterIP是一个虚拟 IP 地址，无法响应ping请求。你可以使用curltelnet或nc等工具来测试ClusterIP服务的连通性。kube-proxy通过iptables或ipvs规则来
阅读更多2024-11-07
代码随想录 | Day38 | 动态规划：01背包应用目标和&&一和零
代码都不难写，这真的不能怪笔者拖更，这两道题真给我整麻了。
阅读更多2024-11-07
[vulnhub]Empire: Breakout
vulnhub - Empire: Breakout
阅读更多2024-11-07
PPO(Proximal Policy Optimization)算法介绍
PPO通过引入剪辑损失函数，有效地限制了策略更新的幅度，兼顾了学习效率和更新稳定性。在RLHF中，PPO作为微调预训练语言模型的关键算法，发挥了重要作用，使得模型能够从人类反馈中高效学习，生成更符合人
阅读更多2024-11-07
Ionic Range: Building Dynamic Range Sliders for Mobile Apps
ion-range。
阅读更多2024-11-07
Flink滑动窗口（Sliding）中window和windowAll的区别
#滑动窗口的window和windowall的区别
阅读更多2024-11-07
jmeter结合ansible分布式压测--3压测执行
1、执行命令： ./jmeter-5.4.1/bin/jmeter.sh -n -t streamgwInfer/streamgw_pushUrls.jmx -R 11.xxx.xxx.48,11.x
阅读更多2024-11-07

ZISUOJ 2024算法基础公选课练习一（1）

前言、

一、我的C++模板

1.1 模板1

1.2 模板2

二、题目总览

三、具体题目

3.1 问题 A: 删数问题(Tan1)：

思路：

参考代码1：

参考代码2：

3.2 问题 B: 输出亲朋字符串：

思路：

参考代码：

3.3 问题 C: 密钥加密：

思路：

参考代码：

3.4 问题 D: 排列对称串：

思路：

参考代码：

3.5 问题 E: 《庆余年》之四大宗师：

思路：

参考代码：

后记：

相关文章