ZISUOJ 2024算法基础公选课练习二

🕗 发布于 2024-11-11 13:52 算法 c++ 数据结构

一、前言

先把代码丢上来，后续再补上思路

二、题目总览

三、具体题目

3.1 问题 A: 成绩排序1

参考代码

简单排序

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

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

    int t = 1;
    std::cin >> t;
    while(t--) {
        int n;
        std::cin >> n;
        std::vector<int> v(n);
        for(auto &vi:v) std::cin >> vi;
        std::sort(v.begin(),v.end(),[&](const int &num1,const int &num2) {
            return num1>num2;
        });
        for(int i = 0;i<n;i++) std::cout << v[i] << " \n"[i==n-1];
    }
    
    return 0;
}

3.2 问题 B: 数字和排序

参考代码

简单排序

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

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

    int n = 1;
    while(std::cin >> n) {
        if(n==0) break;
        std::vector<pii> v(n);
        for(int i = 0;i<n;i++) {
            int num;std::cin >> num;
            int tmp = num,sum = 0;
            while(tmp!=0) {
                sum+=tmp%10;
                tmp/=10;
            }
            v.emplace_back(sum,num);
        }
        std::sort(v.begin(),v.end(),[&](const pii& p1,const pii& p2) {
            if(p1.first!=p2.first) return p1.first>p2.first;
            return p1.second > p2.second;
        });
        for(int i = 0;i<n;i++) {
            std::cout << v[i].second << " \n"[i==n-1];
        }

    }
    
    return 0;
}

3.3 问题 C: 帆帆的挂件

参考代码

简单模拟

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

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

    int n,x_0;
    std::cin >> n >> x_0;
    std::vector<int> a(n),b(n);
    for(auto &ai:a) std::cin >> ai;
    for(auto &bi:b) std::cin >> bi;
    int ans = 0;
    for(int i = 0;i<n;i++) {
        if(x_0>=a[i]) {
            x_0+=b[i];
            ++ans;
        }
    }
    std::cout << ans << '\n';
    
    return 0;
}

3.4 问题 D: 文件名排序

参考代码

stringstream很好处理这种读入情况

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

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

    std::string line;
    std::vector<pss> v;
    while(std::getline(std::cin,line)) {
        std::stringstream ss(line);
        std::string tmp1,tmp2;
        while(ss >> tmp1 >> tmp2) v.emplace_back(tmp2,tmp1);
    }
    std::sort(v.begin(),v.end());
    for(const auto &vi:v) {
        std::cout << vi.second << ' ' << vi.first << '\n';
    }
    
    return 0;
}

3.5 问题 E: 火星数排序

参考代码

可以用哈希表映射过去，写题的时候脑子犯昏，写了好多if

#include <bits/stdc++.h>
using namespace std;
struct number{
int en;
int mn;
}a[1000];

int earth(int n){
int temp=n;
int total = 0;
int sum[20];
int index = 0;
while(temp != 0){
if(temp%10==0){
sum[index] = 0;
}else if(temp%10==8){
sum[index] = 1;
}else if(temp%10==1){
sum[index] = 2;
}else if(temp%10==5){
sum[index] = 3;
}else if(temp%10==2){
sum[index] = 4;
}else if(temp%10==3){
sum[index] = 5;
}else if(temp%10==9){
sum[index] = 6;
}else if(temp%10==4){
sum[index] = 7;
}else if(temp%10==7){
sum[index] = 8;
}else if(temp%10==6){
sum[index] = 9;
}
index++;
temp /= 10;
}
for(int i = index-1;i>=0;i--) total = total*10+sum[i];
return total;
}


bool cmp1(number a,number b){
return a.en<b.en;
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);

int Case;
cin>>Case;
for(int i=0;i<Case;i++){
int j=0;
int n;cin >> n;
for(int j = 0;j<n;j++) cin >> a[j].mn;

for(int j = 0;j<n;j++) a[j].en = earth(a[j].mn);
sort(a,a+n,cmp1);

for(int j = 0;j<n;j++){
if(j==0) cout << a[j].mn;
else cout << ' ' << a[j].mn;
}
cout << '\n';
}


return 0;
}

3.6 问题 F: 帆帆的数位计算

参考代码

写个循环模拟就行，我当时想复杂了

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

void dfs(std::string num,int step) {
    if(num.size()==1) {
        std::cout << step << '\n';
        return;
    }
    int sum = 0;
    for(const auto &c:num) {
        sum+=c^48;
    }
    dfs(std::to_string(sum),step+1);
}
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::string num;
    std::cin >> num;
    dfs(num,0);
    
    return 0;
}

3.7 问题 G: 帆帆的数列

参考代码

前缀和+贪心

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

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

    int t = 1;
    std::cin >> t;
    while(t--) {
        int n,m;
        std::cin >> n;
        std::vector<int> a(n+1,0),preA(n+1,0);
        for(int i = 1;i<=n;i++) {
            std::cin >> a[i];
            preA[i] = preA[i-1]+a[i];
        }
        std::cin >> m;
        std::vector<int> b(m+1,0),preB(m+1,0);
        for(int i = 1;i<=m;i++) {
            std::cin >> b[i];
            preB[i] = preB[i-1]+b[i];
        }

        int ans = 0;
        for(int i = 0;i<=n;i++) {
            for(int j = 0;j<=m;j++) {
                ans = std::max(ans,preA[i]+preB[j]);
            }
        }
        std::cout << ans << '\n';
    }
    
    return 0;
}

3.8 问题 H: 帆帆的糖

参考代码

一开始当成dfs写了，没看到范围，真是蠢了。可以直接二分枚举答案，不能直接暴力，会TLE

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

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

    int n,k;
    std::cin >> n >> k;
    int ans = 0;
    int low = 1,high = n;
    
    while(low<high) {
        int mid = (low+high)>>1;
        if(1LL*(1+mid)*mid/2-(n-mid)>=k) {
            high = mid;
        }else {
            low = mid+1;
        }
    }
    std::cout << n-low << '\n';

    return 0;
}

3.9 问题 I: Determine the Photo Position

参考代码

前缀和

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

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

    int n,m;
    std::cin >> n >> m;
    std::vector<std::vector<char>> g(n+5,std::vector<char>(n+5));
    std::vector<std::vector<int>> pre(n+5,std::vector<int>(n+5,0));
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=n;j++) {
            std::cin >> g[i][j];
            pre[i][j]=pre[i][j-1]+(g[i][j]^48);
        }
    }

    std::string t;std::cin >> t;

    int ans = 0;
    for(int i = 1;i<=n;i++) {
        for(int j = m;j<=n;j++) {
            if(pre[i][j]-pre[i][j-m]==0) {
                ++ans;
            }
        }
    }
    std::cout << ans << '\n';

    return 0;
}

3.10 问题 J: Ball Dropping

参考代码

初中数学计算

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

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

    double r,a,b,h;
    std::cin >> r >> a >> b >> h;
    if(2*r<=b) {
        std::cout << "Drop\n";
        return 0;
    }
    double h0 = std::sqrt(h*h+((a-b)/2)*((a-b)/2));
    double sin = ((a-b)/2)/h0;
    double cos = h/h0;
    double tan = ((a-b)/2)/h;
    double x1 = r*sin,x2 = (r*cos-b/2)/tan;

    std::cout << "Stuck\n";
    std::cout << std::fixed << std::setprecision(10) << x1+x2 << '\n';

    return 0;
}

3.11 问题 K: Cut the Tree

参考代码

套了别人的两个模板，链式前向星和带权的线段树+dfs找树上LIS，注意数组不能开太大也不能开太小

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int N = 1e5+5,M = N,INF = 0x3f3f3f3f;

//链式前向星
int head[N];
int val[N];
int n;
int ans;

struct edge{
int next, to, w;
}e[N << 1];
int cnt;

void init(){
for(int i = 0; i <= n; i++)
head[i] = -1;
cnt = 0;
}

void add(int u, int v, int w = 0){
e[cnt].w = w;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt++;
}

//带权线段树+dfs找LIS
int tot;
struct Tree{
int l, r;
int lis, lds;
}tree[N * 100];
int rt[N];
int sz[N];
int root, maxPart;
int res;
int vis[N];
void getrt(int S, int u, int f){
sz[u] = 1;
int maxx = 0;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].to;
if(vis[v] || f == v)
continue;
getrt(S, v, u);
sz[u] += sz[v];
maxx = std::max(maxx, sz[v]);
}
maxx = std::max(maxx, S - sz[u]);
if(maxx < maxPart){
maxPart = maxx;
root = u;
}
}
int build(){
tot++;
tree[tot].l = tree[tot].r = tree[tot].lis = tree[tot].lds = 0;
return tot;
}
void update(int &p, int l, int r, int pos, int vlis, int vlds){
if(p == 0)
p = build();
tree[p].lis = std::max(tree[p].lis, vlis);
tree[p].lds = std::max(tree[p].lds, vlds);
if(l == r)
return ;
int m = (l + r) >> 1;
if(pos <= m)
update(tree[p].l, l, m, pos, vlis, vlds);
else
update(tree[p].r, m+1, r, pos, vlis, vlds);
}
int merge(int p, int q){
if(!p || !q)
return p + q;
tree[p].lis = std::max(tree[p].lis, tree[q].lis);
tree[p].lds = std::max(tree[p].lds, tree[q].lds);
// 最大上升子序列长度
res = std::max(res, std::max(tree[tree[p].l].lis + tree[tree[q].r].lds,
tree[tree[p].r].lds + tree[tree[q].l].lis));
tree[p].l = merge(tree[p].l, tree[q].l);
tree[p].r = merge(tree[p].r, tree[q].r);
return p;
}
pii query(int p, int l, int r, int L, int R){ // L R 询问
if(!p || l > r)
return {0, 0};
if(L <= l && r <= R)
return {tree[p].lis, tree[p].lds};
int m = (l + r) >> 1;
pii ret = {-INF, -INF};
pii tr, tl;
if(L <= m)
tl = query(tree[p].l, l, m, L, R);
if(m < R)
tr = query(tree[p].r, m+1, r, L, R);
ret.first = std::max(tl.first, tr.first);
ret.second = std::max(tl.second, tr.second);
return ret;
}
void dfs(int u, int f){
rt[u] = 0;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].to;
if(v == f)
continue;
dfs(v, u);
}
int nlis = 0, nlds = 0;
for(int i = head[u]; ~i; i = e[i].next){
int v = e[i].to;
if(v == f)
continue;
int lis = query(rt[v], 1, n, 1, val[u]-1).first;
int lds = query(rt[v], 1, n, val[u]+1, n).second;
rt[u] = merge(rt[u], rt[v]);
res = std::max(res, lis + 1 + nlds);
res = std::max(res, nlis + 1 + lds);
nlis = std::max(nlis, lis);
nlds = std::max(nlds, lds);
}
update(rt[u], 1, n, val[u], nlis + 1, nlds + 1);
}
void calc(int S, int u){
maxPart = S;
getrt(S, u, 0);
vis[root] = 1;
int maxx = 0, pos = -1;
for(int i = head[root]; ~i; i = e[i].next){
int v = e[i].to;
res = 0;
dfs(v, root);
if(res > maxx){
maxx = res;
pos = v;
}
}
ans = std::min(ans, maxx);
if(pos == -1 || vis[pos])
return ;
calc(sz[pos], pos);
}
void solve(){
std::cin >> n;
init();
for(int i = 1; i < n; i++){
int u, v;
std::cin >> u >> v;
add(u, v);
add(v, u);
}
for(int i = 1; i <= n; i++)
std::cin >> val[i];
ans = INF;
calc(n, 1);
std::cout << ans << '\n';
}

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

    int T;
    // std::cin >> T;
    T = 1;
    while(T--){
        solve();
    }

return 0;
}

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

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

上一篇：政务培训｜LLM大模型在政府/公共卫生系统的应用
下一篇：docker网络配置：bridge模式、host模式、container模式、none模式

git怎么切换分支
这些命令会创建一个新的分支并立即切换到它。记得在切换分支之前，确保你的工作目录是干净的，即所有更改都已提交，否则 Git 可能会阻止你切换分支。如果你不想提交当前的更改，可以使用。命令，或者如果你使用
阅读更多2024-11-13
如何基于redis记录调用大模型问答的统一注册服务
在做各种大模型chat和应用后台服务过程中，需要记录不同应用、不同类型问题的调用情况，同时要求这种记录要快速便捷，因此就想到用redis来做统一记录，目前是同步调用方式，后续有空提供异步调用方式，从而
阅读更多2024-11-13
LLM大模型微调入门Lora（LlamaFactory）
是一个开源框架，旨在简化大型语言模型的定制化微调流程。该框架整合了多样化的训练策略与监控工具，支持通过命令行界面（CLI）和网页用户界面（WebUI）等多种方式进行交互，显著降低了进行模型微调所需的技
阅读更多2024-11-13
CMDB平台（进阶篇）：CMDB的构建指南（一）
获取CMDB知识：在定义项目之前，团队成员需要深入了解CMDB的概念、功能、以及在企业IT服务管理中的作用。定义项目及目标：明确项目的目标、范围、预期成果等，确保所有团队成员对项目有共同的理解。回顾及
阅读更多2024-11-13
【每日 C/C++ 问题】
namespace + 命名空间名称 + { 命名空间成员 }namespace N1 // N1为命名空间的名称// 命名空间中的内容，既可以定义变量，也可以定义函数int a;可以通过作用域解析运
阅读更多2024-11-13
《菲菲办公助手》简介及下载
每一个功能都是解决一类问题的，通用性很强，比如说智能数据查询，你要学会这一个功能，你就会你就可以解决这一类问题，如果你用函数来解决的话，那可能至少需要学习一周的时间才能熟练掌握，而且不太容易理解，非常
阅读更多2024-11-13
c# HttpClient,WebClient常用请求
方法来添加表单数据，其中第一个参数是表单项的内容，第二个参数是表单项的名称。
阅读更多2024-11-13
在JPA和EJB中用乐观锁解决并发问题
super();super(ex);将这个类继承于EJBException，可以被Backing Bean捕获。
阅读更多2024-11-13
什么是 Real-Time Factor (RTF)
RTF 表示生成语音所需的处理时间与语音时长的比值
阅读更多2024-11-13
计算机毕业设计必看必学35755flask旅游景区热度可视化平台原创定制程序,java、PHP、python、小程序、文案全套、毕设成品等
flask旅游景点热度可视化平台摘要信息化社会内需要与之针对性的信息获取途径，但是途径的扩展基本上为人们所努力的方向，由于站在的角度存在偏差，人们经常能够获得不同类型信息，这也是技术最为难以攻克的课
阅读更多2024-11-13

ZISUOJ 2024算法基础公选课练习二

一、前言

二、题目总览

三、具体题目

3.1 问题 A: 成绩排序1

参考代码

3.2 问题 B: 数字和排序

参考代码

3.3 问题 C: 帆帆的挂件

参考代码

3.4 问题 D: 文件名排序

参考代码

3.5 问题 E: 火星数排序

参考代码

3.6 问题 F: 帆帆的数位计算

参考代码

3.7 问题 G: 帆帆的数列

参考代码

3.8 问题 H: 帆帆的糖

参考代码

3.9 问题 I: Determine the Photo Position

参考代码

3.10 问题 J: Ball Dropping

参考代码

3.11 问题 K: Cut the Tree

参考代码

相关文章