2024算法基础公选课练习四(综合2)

server/2024/11/26 9:05:35/

一、前言

最后几个题确实有难度,这次有两题没整出来

二、题目总览

三、具体题目

3.1 问题 A: 水题系列1-B(班级排位)

思路

最暴力的思路是写线段树,然后暴力枚举两个端点,总体时间复杂度为O(n^2*logn)最坏会到1e9的数量级,可能会TLE,我没试过。我用的贪心枚举,具体思路见代码

我的代码

#include <bits/stdc++.h>
using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n+5,0);for(int i = 1;i<=n;++i) std::cin >> a[i];std::vector<std::vector<int>> v(n+5,std::vector<int>(2,0));for(int i = 1;i<=n-1;++i) {for(int j = i+1;j<=n;++j) {int d = std::abs(a[i]-a[j]);// if(d>v[i][0]) {//     v[i][0] = d;if(d>=j-i+1) {std::cout << "YES\n";return;}// }}}std::cout << "No\n";
}
int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int tt = 1;std::cin >> tt;while(tt--) {solve();}return 0;
}

3.2 问题 B: 一锐语言

思路

真·水题

我的代码

#include <bits/stdc++.h>
using i64 = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n;std::cin >> n;// while(std::cin >> n) {std::string line;std::getline(std::cin,line);int ans = 0;for(int i = 1;i<=n;++i) {std::getline(std::cin,line);if(line.find('+')!=std::string::npos) {++ans;}else {--ans;}}std::cout << ans << '\n';// }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,v;std::cin >> n >> v;int now_n = 1,now_v = 0,ans = 0;while(now_n+now_v<n) {if(n-now_n<v-now_v) ans+=now_n*(n-now_n),now_v+=n-now_n;else ans+=now_n*(v-now_v),now_v+=v-now_v;++now_n;--now_v;}std::cout << ans << '\n';return 0;
}

3.4 问题 D: 虎哥学乐器

思路

直接贪心即可,一开始给当成求01背包了,WA了好几次(后面有个题思路是01背包,我一开始反而当成贪心做了[裂开])

我的代码

#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,k;std::cin >> n >> k;// std::vector<int> a(n+5,0);std::vector<pii> a(n+5);for(int i = 1;i<=n;++i) std::cin >> a[i].first,a[i].second = i;std::sort(a.begin()+1,a.begin()+1+n);std::vector<int> ans;int now_k = 0,cnt = 0;for(int i = 1;i<=n;++i) {if(now_k+a[i].first<=k) {++cnt;now_k+=a[i].first;ans.emplace_back(a[i].second);}}std::sort(ans.begin(),ans.end());std::cout << cnt << '\n';for(const auto i:ans) std::cout << i << " \n"[i==ans.back()];return 0;
}

3.5 问题 E: 回文串游戏

思路

简单博弈论,跟所有字母出现次数的奇偶有关

我的代码

#include <bits/stdc++.h>
using i64 = long long;int main() {std::cin.tie(nullptr)->sync_with_stdio(false);std::string s;std::cin >> s;std::unordered_map<char,int> map;for(const auto &c:s) ++map[c];int cnt = 0;for(const auto &p:map) {if(p.second&1) ++cnt;}std::cout << (cnt==0||cnt&1?"First\n":"Second\n");return 0;
}

3.6 问题 F: 拆解玩具

思路

看似是图论题,不过仔细看了提示就知道这也是个简单的贪心题

我的代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
int a[1005];
int sum;
int main(){cin >> n >> m;for (int i = 1; i <= n;i++){cin >> a[i];}for (int i = 1; i <= m;i++) {cin >> x >> y;if (a[x] >= a[y]) {sum += a[y];}else {sum += a[x];}}cout << sum << endl;return 0;
}

3.7 问题 G: 搜索——魔法卷轴

思路

dfs每次确认一行,dfs中循环判断列是否已经被标记(有其他手印在同一行或者同一列,这里实际上只需要判断同一列是否有其他手印即可)了,如果找到了一种结果,那么++ans,ans就是最后的答案

我的代码

#include <bits/stdc++.h>
using i64 = long long;
int n,m,res;
char a[15][15];
bool b[15];
void dfs(int k,int s){if(s>=m){res+=1;return;}if(k>n){return;}for(int i=1;i<=n;i++){if(a[k][i] == '@' && b[i]==0){b[i]=1;dfs(k+1,s+1);b[i]=0;}}dfs(k+1,s);
}
int main(){std::cin.tie(nullptr)->sync_with_stdio(false);std::cin>>n>>m;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){std::cin>>a[i][j];}}res=0;dfs(1,0);std::cout << res<< '\n';return 0;
}

3.8 问题 H: 虎哥的书架

思路

一开始怎么看怎么都是模拟和贪心,但是后来才发现是一个01背包的套壳题,对于每本书,只有两种状态,要么放在竖着放下面,要么横着放上面

我的代码

#include <bits/stdc++.h>
using i64 = long long;
using pii = std::pair<int,int>;
constexpr int INF = 0x3f3f3f3f;void solve() {int n;std::cin >> n;std::vector<pii> v(n+5);for(int i = 1;i<=n;++i) std::cin >> v[i].first >> v[i].second;std::vector<int> pre(n+5,0);for(int i = 1;i<=n;++i) pre[i] = pre[i-1]+v[i].first;std::vector<int> dp(2*n+5,INF);dp[0] = 0;for(int i = 1;i<=n;++i) {for(int j = pre[n];j>=v[i].first;--j) {dp[j] = std::min(dp[j],dp[j-v[i].first]+v[i].second);}}int ans = 0;for(int i = pre[n];i>=0;--i) {if(pre[n]-i>=dp[i]) {ans = pre[n]-i;break;}}std::cout << ans << '\n';
}int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int T = 1;// std::cin >> T;while (T--) {solve();}return 0;
}

3.9 问题 I: 躲避火墙

思路

没写出来,直接看老师给的题解思路:

设向右移动x步时,最少向上移动f(x)步。。

对于每一对(ai,bi),(ci,di)需满足对于任意x∈[0,cj-ai],有f(x)>=dj-bi+1。

逐个枚举每条限制,更新f[cj-ai]=max(f[cj-ai],dj-bi+1),再倒序做后缀max即可。

答案为max{x+f(x)},时间复杂度O(nm+max(a,b,c,d))。

参考代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T &x){static char ch;x = 0;ch = getchar();while(!isdigit(ch)) ch = getchar();while(isdigit(ch)) x = x*10+ch-'0',ch = getchar();
}
inline void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}
const int N = 2005,M = 2005;
int n,m,ax[N],ay[N],bx[M],by[M],ans = 2000000,mx[1000005];
int main(){int i,j;read(n),read(m);for(int i = 1;i<=n;++i) read(ax[i]),read(ay[i]);for(int i = 1;i<=m;++i) read(bx[i]),read(by[i]);for(int i = 1;i<=n;++i){for(int j = 1;j<=m;++j){if(ax[i]<=bx[j]&&ay[i]<=by[j]){mx[bx[j]-ax[i]] = max(mx[bx[j]-ax[i]],by[j]-ay[i]+1);}}}for(int i = 1000000;i;--i) mx[i-1] = max(mx[i-1],mx[i]);for(int i = 0;i<=1000000;++i) ans = min(ans,i+mx[i]);cout << ans << '\n';return 0;
}

3.10 问题 J: 削弱闪电链

思路

参考代码

#include <bits/stdc++.h>
using namespace std;const int N = 5e6+10;int a[5000100],n,k,l[5000100],sum,s[5000100],ans=-1;int main(){scanf("%d%d",&n,&k);for(int i = 1;i<=n;i++){scanf("%d",&l[i]);}sort(l+1,l+n+1);reverse(l+1,l+n+1);s[0]=1;s[1]=-1;for(int i=0,j=1;i<N;i++){sum+=s[i];s[i+1]+=s[i];if(sum+s[i+1]>=k){ans=i+1;break;}while(j<=n&&s[i]){s[i+2]+=2;s[i+2+((l[j]-1)/2)]--;s[i+2+(l[j]-1-((l[j]-1)/2))]--;s[i]--;sum--;j++;}}printf("%d",ans);return 0;
}


http://www.ppmy.cn/server/145013.html

相关文章

【Java 学习】详细讲解---包和导包、Scanner类、输入源

1. 包 1.1 什么是包&#xff1f; 举个例子&#xff0c;你和你的同学有不同的家庭&#xff0c;你们都有自己的爸爸妈妈&#xff0c;都有自己的家。在自己的家中你们可以按照自己爱好摆放东西&#xff0c;都互不干扰。但是&#xff0c;假如你们的家都在一起&#xff0c;你们就不…

未来可期:保研后的人工智能研究生活

哈喽&#xff0c;大家好&#xff01;好久没有更新博客了&#xff0c;今天想和大家分享一个好消息&#xff5e; 我已经成功保研至 南昌大学数学与计算机学院&#xff0c;研究方向是 人工智能 -- 人体行为识别。 回顾大学三年的时光&#xff0c;虽然谈不上轰轰烈烈&#xff0c;但…

鸿蒙HarmonyOS学习笔记(4)

自定义构建函数&#xff1a;Builder装饰器 ArkUI提供了一种轻量的UI元素复用机制Builder&#xff0c;该自定义组件内部UI结构固定&#xff0c;仅与使用方进行数据传递&#xff0c;开发者可以将重复使用的UI元素抽象成一个方法&#xff0c;在build方法里调用。 为了简化语言&a…

理解clickhouse 里的分区和分片键区别

文章目录 分片分区两分片&#xff0c;0副本的cluster 分片 CREATE TABLE logs_distributed AS logs_local ENGINE Distributed(cluster_name, -- 集群名称database_name, -- 数据库名称logs_local, -- 本地表名cityHash64(user_id) -- 分片键&#xf…

在Docker中部署osrm-backend

使用 Docker 安装和运行 OSRM-backend 是一个非常方便的方法&#xff0c;因为 Docker 可以提供一致的环境&#xff0c;避免了许多依赖性和配置问题。以下是如何使用 Docker 安装和运行 OSRM-backend 的步骤&#xff1a; 1. 安装 Docker 确保系统上已经安装了 Docker。如果没有…

以思维链为线索推理隐含情感

❀ 以思维链为线索推理隐含情感 简介摘要引言THORTHOR核心代码实验结果代码运行总结 简介 本文主要对2023ACL论文《Reasoning Implicit Sentiment with Chain-of-Thought Prompting》主要内容进行介绍。 摘要 尽管情绪分析任务常依据文本中的直接意见表达来判定目标的情绪倾向…

vulnhub靶场之breakout

empire靶场2 前言 靶机&#xff1a;breakout 攻击&#xff1a;kali 续接上个靶场empire1的继续学习 主机发现 使用arp-scan扫描或者直接查看虚拟机的ip地址 信息收集 使用nmap扫描 端口80apache 2.4.51开启smb服务的两个端口139、445&#xff0c;版本4.6.2两个http服务采…

day23|leetCode 39. 组合总和 , 40.组合总和II , 131.分割回文串

5.组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被…