C++学习笔记3

A. 求出那个数

题目描述

喵喵是一个爱睡懒觉的姑娘,所以每天早上喵喵的妈妈都花费很大的力气才能把喵喵叫起来去上学。

在放学的路上,喵喵看到有一家店在打折卖闹钟,她就准备买个闹钟回家叫自己早晨起床,以便不让妈妈这么的辛苦。但是想到自己睡觉睡的太死了,一个闹钟可能并不能够把自己叫醒,所以她决定买一些闹钟回家一起用。

但是 n n n 个闹钟的音量并不是一个闹钟音量的 n n n 倍,而是存在一个很奇怪的数学关系:

a n = { 1 n ≤ 2 a n − a n − 1 + a n − 1 − a n − 2 n > 2 a_n=\begin{cases} 1 & n\le2 \\ a_{n-a_{n-1}}+a_{n-1-a_{n-2}} & n>2 \end{cases} an={1anan1+an1an2n2n>2

现在喵喵想请你帮忙计算 n n n 个闹钟的音量会有多大,请你写个程序帮忙计算。

输入格式

多组输入。

每组输入在一行中给出一个正整数 n n n

n = 0 n=0 n=0 时表示输入结束。

  • 1 ≤ n ≤ 1 0 6 1\le n\le10^6 1n106

输出格式

每组输入在一行中输出 n n n 个闹钟的音量总和。

样例

输入 #1

1
2
3
5
10
0

输出 #1

1
1
2
3
6
  1. 按照题目的要求递推过去即可。
#include <bits/stdc++.h>
using namespace std;int a[1000010];void solve()
{int _;cin >> _;while (_){cout << a[_] << '\n';cin >> _;}
}signed main()
{a[1] = a[2] = 1;for (int i = 3;i <= 1000000;i++){a[i] = a[i-a[i-1]]+a[i-1-a[i-2]];}int TTT;
//	cin >> TTT;TTT = 1;while (TTT--) solve();return 0;
}

B. 加密通话

题目描述

在这个信息十分发达的时代,喵喵十分担心自己发送的消息被黑客拦截,因此他决定将内容加密。她和同学一起发明了一种加密方法,因为他们要加密的文字只有大写字母和空格,所以她们一起约定空格编号就是 0 0 0 A A A 标号就是 1 1 1 … \dots Z Z Z 编号就是 26 26 26,然后再将每个编号转为长度为 5 5 5 的二进制数以后,按照螺旋方阵的方式填入一个 R × C R\times C R×C 的矩阵中,若二进制串不够长就在后面补 0 0 0

例如 R = 4 , C = 4 R=4,C=4 R=4,C=4 时,加密 BEE B = 00010 , E = 00101 , E = 00101 B=00010,E=00101,E=00101 B=00010,E=00101,E=00101。末尾补零填进矩阵后是这样:

0001
0100
0010
1010

然后我们再将矩阵中的元素一行一行的取出来,得到加密后的信息就是
0001010000101010 0001010000101010 0001010000101010。如果通信全靠手算的话,那就急死人了,现在先请你来实现一个加密程序来将信息进行加密。

输入格式

输入仅在一行中给出 R , C R,C R,C,以及要加密的字符串 S S S

保证 R , C R,C R,C 不会超过 20 20 20,且 R × C R\times C R×C 不会小于五倍的字符串的长度。

S S S 中可能含有空格!

输出格式

在一行中输出加密后的结果。

样例

输入 #1

4 4 BEE

输出 #1

0001010000101010
  1. 注意输入有空格
  2. 转二进制之后不足五位前面要补零
  3. 整个二进制串长度不足 R × C R\times C R×C 末尾要补零
  4. 最后填进矩阵遍历即可
#include <bits/stdc++.h>
//#define int long long
using namespace std;int n,m;
string s;
map <char,string> mp;
string str;const int fx[4] = {0,1,0,-1},fy[4] = {1,0,-1,0};
char ans[100][100];void solve()
{cin >> n >> m;getchar(); //别忘了把 n,m 之后的空格读入进来 getline(cin,s);mp[' '] = "00000";mp['a'] = "00001";mp['b'] = "00010";mp['c'] = "00011";mp['d'] = "00100";mp['e'] = "00101";mp['f'] = "00110";mp['g'] = "00111";mp['h'] = "01000";mp['i'] = "01001";mp['j'] = "01010";mp['k'] = "01011";mp['l'] = "01100";mp['m'] = "01101";mp['n'] = "01110";mp['o'] = "01111";mp['p'] = "10000";mp['q'] = "10001";mp['r'] = "10010";mp['s'] = "10011";mp['t'] = "10100";mp['u'] = "10101";mp['v'] = "10110";mp['w'] = "10111";mp['x'] = "11000";mp['y'] = "11001";mp['z'] = "11010";for (int i = 0;i < s.size();i++) str += mp[tolower(s[i])];for (int i = 0;i < 100;i++) for (int j = 0;j < 100;j++) ans[i][j] = '.';while (str.size() < n*m) str = str + '0';int x = 0,y = 0;int d = 0;for (int i = 0;i < n*m;i++){ans[x][y] = str[i];int xx = x + fx[d];int yy = y + fy[d];if (xx < 0 || xx >= n || yy < 0 || yy >= m || ans[xx][yy] != '.'){d = (d+1) % 4;xx = x + fx[d];yy = y + fy[d];}x = xx;y = yy;}for (int i = 0;i < n;i++) for (int j = 0;j < m;j++) cout << ans[i][j];
}signed main()
{int TTT;
//	cin >> TTT;TTT = 1;while (TTT--) solve();return 0;
}

C. 换零钱

题目描述

喵喵现在有一堆硬币,这么多的硬币带在身上沉甸甸的,所以她不想要这么多硬币,于是乎她在想怎么在付款的时候一次性付出更多个数的硬币。这天喵喵在柜台结账的时候,她突然想到如果自己多付一些钱让老板找零,可能会让自己硬币的个数更少。老板为了更好的给客人找零,他一定会用最少的硬币数量找零给客人。

这样,喵喵开始思考该付给老板多少钱,才能在付完钱之后手里的硬币数量最少。可惜的是,喵喵在计算这方面一直不太擅长,就请你来帮助喵喵解决这个烦恼吧。

输入格式

输入一共有 3 3 3 行。

第一行表示要付的价格。

第二行有 5 5 5 个数字 p 1 , p 5 , p 10 , p 20 , p 50 p_1,p_5,p_{10},p_{20},p_{50} p1,p5,p10,p20,p50,分别是东东钱包里面一元、五元、十元、二十元和五十元硬币的个数。

第三行有 5 5 5 个数字 p 1 , p 5 , p 10 , p 20 , p 50 p_1,p_5,p_{10},p_{20},p_{50} p1,p5,p10,p20,p50,是老板所拥有的一元、五元、十元、二十元和五十元硬币的个数。

你可以假设喵喵身上的钱足够来付账,而且至少有一种付钱的方法使得老板可以找得开(如果需要找零的话)。

输出格式

在一行中输出一个正整数表示付完钱剩余的硬币个数。

样例

输入 #1

25
0 3 2 2 3 
1 1 1 1 1

输出 #1

4

提示

3 3 3 5 5 5 元, 2 2 2 10 10 10 元, 2 2 2 20 20 20 元,老板找回 1 1 1 50 50 50 元,最后手里有 4 4 4 个硬币。

直接把所有的钱付给老板,然后让老板往回找。

#include <bits/stdc++.h>
//#define int long long
using namespace std;const int inf = 1e9;int n;
int a[10];
int b[10];const int coin[6] = {0,1,5,10,20,50};
int ans,dp[1000010];int sum; //现有的钱 void solve()
{cin >> n;for (int i = 1;i <= 5;i++) cin >> a[i],sum += a[i] * coin[i];for (int i = 1;i <= 5;i++) cin >> b[i],b[i] += a[i]; //先付钱sum -= n; //付完前后还剩 sum 元for (int i = 1;i <= sum;i++) dp[i] = inf;for (int i = 5;i >= 1;i--) //尽量取大的 {//理论上能拿到的最多的 和 老板有的int num = min(sum/coin[i],b[i]);for (int k = 1;num > 0;k *= 2){if (k > num) k = num; //取最多num -= k; //还剩的for (int j = sum;j >= coin[i] * k;j--)dp[j] = min(dp[j],dp[j-coin[i]*k]+k);}}cout << dp[sum];
}signed main()
{int TTT;
//	cin >> TTT;TTT = 1;while (TTT--) solve();return 0;
}

D. 紧急排水

题目描述

由于气候变暖,许多地方都出现了历史上从未有过的大暴雨,造成了巨大的损失。为了排出各个地区的积水,国家紧急召集了有相关经验的科学家和工程师们组成了救灾小队,小队成员经过讨论后决定利用地形优势来制定排水方案。经过勘测,可以得到地表各区域的高度,如下高度表和三维图。

在这里插入图片描述

高度表中的数字代表高低,相邻(有边相接)的格子不会有相同的高度。为了尽快消除积水,得最大限度的利用排水设备进行作业。若一个格子有排水装备,则该格子排水所需时间为 0 0 0,没有排水装备的格子只需要等水流到有排水装备的格子,水能往相邻且较低的格子流动,流动到相邻一格的时间为 1 1 1。若某个格子的水能流到不止一个具有排水装备的格子,则让其流向最近的一个。

为了避免排水装备的不合理安置,任两个排水装备所在的格子之间的水不能流通,也就是说任何有排水装备的格子的水不可能流到另一个有装备的格子。

假设安装了 3 3 3 个排水设备在地图上,为了尽快排完所有的水,其中一种方案是装在三维图中的灰色格子上,这样各个格子所需要的排水时间下:
在这里插入图片描述

输入格式

第一行输入两个正整数 n , m n,m n,m 代表地图为 n × n n\times n n×n,最多安装 m m m 个排水设备。

接下来 n n n 行,每行有 n n n 个数字表示格子的高度 d d d

  • 1 ≤ n ≤ 500 , 1 ≤ m ≤ 1000 1\le n\le500,1\le m\le1000 1n500,1m1000
  • 0 < d < 2 31 0<d<2^{31} 0<d<231

输出格式

在一行中输出排水所需最短时间。

若需要超过 m m m 个排水装备才能将所有格子都排水,输出 Impossible

样例

输入 #1

3 9
3 2 3
2 1 2
3 2 3

输出 #1

2

输入 #2

4 3
5 3 2 3
4 2 1 2
5 3 2 3
4 2 3 2

输出 #2

3

输入 #3

3 1
1 2 3
2 1 2
3 2 3

输出 #3

Impossible
  1. 安装排水设备的个数等于坑的个数,多少个坑多少个设备,如果坑数大于 m m m 就是 Impossible
  2. 坑是指比周围格子都低的格子
  3. 然后从坑往外一圈一圈的搜,取最大值就行了
#include <bits/stdc++.h>
#define int long long
using namespace std;int a[510][510];
int f[510][510];
int mx,cnt;
int n,m;const int fx[4] = {-1,0,0,1},fy[4] = {0,-1,1,0};int low(int x,int y)
{for (int i = 0;i < 4;i++){int xx = x + fx[i],yy = y + fy[i];if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[x][y] > a[xx][yy])return 0;}return 1;
}struct node {int x,y,d;};
queue <node> q;void bfs()
{while (!q.empty()){int x = q.front().x,y = q.front().y,d = q.front().d;q.pop();for (int i = 0;i < 4;i++){int xx = x + fx[i],yy = y + fy[i];if (xx >= 0 && xx < n && yy >= 0 && yy < n && !f[xx][yy] && a[x][y] < a[xx][yy]){q.push({xx,yy,d+1});f[xx][yy] = 1;mx = max(mx,d+1);}}}
}void solve()
{cin >> n >> m;for (int i = 0;i < n;i++)for (int j = 0;j < n;j++)cin >> a[i][j];for (int i = 0;i < n;i++)for (int j = 0;j < n;j++)if (low(i,j))cnt++,f[i][j] = 1,q.push({i,j,0}); //坑if (cnt > m) cout << "Impossible";else bfs(),cout << mx;
}signed main()
{int TTT = 1;
//	cin >> TTT;while (TTT--) solve();return 0;
}

E. 倒酒

题目描述

喵喵是一个商人,主营业务是卖酒,做生意初期,一切以节省开支为第一要务,所以她除了装酒的大桶外只买了两个杯子,这两个杯子除了标注了装满时是装了多少,并没有其它刻度。

每当有客人光顾的时候,客人会告诉喵喵他想要买多少酒。虽然没有正常的容器,但是聪明的喵喵会利用这两个杯子的差异,经过若干次倒空与注满的操作,准确的凑出客人所需要的量。

经过多日经营,喵喵也发现了一个问题,有些客人的需求,喵喵是无论如何也凑不出来的,这个时候她就会提议让客人多买一点或者少买一点到恰好能凑出的量。

每次到最后才发现凑不出来所需要的量真的是让喵喵有点头疼,所以喵喵求助于你让你能不能最开始的时候就判断出客人的量能不能被准确凑出。

输入格式

多组输入。

每组输入给出三个不超过 100 100 100 的正整数 x , y , z x,y,z x,y,z,分别表示喵喵的两个杯子和客人需要的量。

一行中 0 0 0 的时候表示输入结束。

输出格式

对每组测试资料,你应该输出一行。如果客人要求的量凑得出来,请输出 Yes,否则请输出 No

样例 #1

样例输入 #1

1 2 1
1 2 9
3 5 4
3 6 8
0 0 0

样例输出 #1

Yes
Yes
Yes
No
  1. 两个杯子的容量 x , y x,y x,y,假设 x > y x>y x>y,那我们相当于是有抽象的杯子 k 1 × ( x − y ) k_1\times(x-y) k1×(xy),也有抽象的杯子 k 2 × y − x k_2\times y-x k2×yx k 1 , k 2 k_1,k_2 k1,k2 都是任意常数
  2. 所以题目相当于是求 k 1 × ( x − y ) + k 2 × y − x = z k_1\times(x-y)+k_2\times y-x=z k1×(xy)+k2×yx=z 的解
  3. 合并可得 k 3 × x − k 4 × y = z k_3\times x-k_4\times y=z k3×xk4×y=z k 3 , k 4 k_3,k_4 k3,k4 是任意常数
  4. 上面这个方程有解的条件就是 z m o d gcd ⁡ ( x , y ) = 0 z\bmod\gcd(x,y)=0 zmodgcd(x,y)=0
#include <bits/stdc++.h>
#define int long long
using namespace std;void solve()
{int a,b,c;while (cin >> a >> b >> c){if (a + b + c == 0) return ;if (c % __gcd(a,b) == 0) cout << "Yes\n";else cout << "No\n";}
}signed main()
{solve();return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1420521.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

【博士生必看】论文润色大揭秘!

&#x1f4dd; 投稿拒稿&#xff1f;语言不过关&#xff1f;别怕&#xff0c;我来支招&#xff01;&#x1f469;‍&#x1f393; &#x1f31f; 我的论文润色经历&#xff0c;从拒稿到接收的逆袭之路&#xff01;✨ &#x1f449; 【论文润色&#xff0c;我选了它】 我选择了…

嵌入式C语言高级教程:实现基于STM32的环境监测系统

⬇帮大家整理了单片机的资料 包括stm32的项目合集【源码开发文档】 点击下方蓝字即可领取&#xff0c;感谢支持&#xff01;⬇ 点击领取更多嵌入式详细资料 问题讨论&#xff0c;stm32的资料领取可以私信&#xff01; 环境监测系统通过实时收集和分析环境数据&#xff0c;如温度…

水面垃圾监测识别摄像机

随着城市化进程的加快和旅游业的兴起&#xff0c;水域环境污染问题日益突出&#xff0c;水面垃圾成为环境保护的重要问题。为有效监测和清理水面垃圾&#xff0c;水面垃圾监测识别摄像机应运而生。水面垃圾监测识别摄像机利用高清晰度摄像头和智能识别算法&#xff0c;能够实时…

【LeetCode:2391. 收集垃圾的最少总时间 + 二分】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

如何远程操作服务器中的Python编译器并将运行结果返回到Pycharm

文章目录 一、前期准备1. 检查IDE版本是否支持2. 服务器需要开通SSH服务 二、Pycharm本地链接服务器测试1. 配置服务器python解释器 三、使用内网穿透实现异地链接服务器开发1. 服务器安装Cpolar2. 创建远程连接公网地址 四、使用固定TCP地址远程开发 本文主要介绍如何使用Pych…

Scoop国内安装、国内源配置

安装配置源可参考gitee上的大佬仓库&#xff0c;里面的步骤、代码都很详细&#xff0c;实测速度也很好 glsnames/scoop-installer 也可以结合其它bucket使用 使用Github加速网站&#xff0c;也可以换做其他代理方式&#xff0c;自行测试 例如&#xff1a;https://mirror.ghprox…

法语语式与时态总结,柯桥零基础学法语

常用语式 法语中的常用语式分为&#xff1a;直陈式、条件式、虚拟式、命令式、不定式与分词式。 直陈式&#xff08;lindicatif&#xff09;初学法语时首先就要学直陈式&#xff0c;也是最常用的语式&#xff0c;表示确实发生的动作。 条件式&#xff08;le conditionnel&am…

操作系统原理与系统——实验十三多道批处理作业调度(作业可移动)

关键代码 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct data{int hour;//当前小时int min;//当前分钟 }time; struct node{char name[20];//进程名time arrive;//到达就绪队列时间int zx;//执行时间(预期时间)int size;int ta…

zookeeper安装集群模式

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了就去分享给你的码吧。 ZooKeeper是一个分…

Spring >> Spring AOP

AOP 与 Spring AOP AOP&#xff1a;面向切面编程。是一种思想&#xff0c;对某一类事情的集中处理。 例如现在大多数平台的用户登录都是有权限效验的&#xff0c;而对于平台页面的操作&#xff0c;除过登录&#xff0c;注册或者一些简单的&#xff0c;大多都是需要验证用户有没…

体验GM CHM Reader Pro,享受高效阅读

还在为CHM文档的阅读而烦恼吗&#xff1f;试试GM CHM Reader Pro for Mac吧&#xff01;它拥有强大的功能和出色的性能&#xff0c;能够让你轻松打开和阅读CHM文件&#xff0c;享受高效、舒适的阅读体验。无论是学习、工作还是娱乐&#xff0c;GM CHM Reader Pro都能成为你的得…

打印图案(金字塔)头歌作业

题目: 任务描述 本关任务&#xff1a;编写一个程序&#xff0c;输出堆叠式的金字塔图案。 输入n个字符&#xff0c;按以下原则输出&#xff1a;【参考样例】 1)第1个字符为一层金字塔图案&#xff0c;第2个字符为两层金字塔图案&#xff0c;第3个字符为三层金字塔图案&#x…

Redis经典问题:数据不一致

大家好,我是小米,今天我想和大家聊一聊Redis的一个经典问题——数据不一致。在使用Redis的过程中,你是否曾遇到过这样的问题?缓存和数据库中的数据不一致,可能导致应用程序的功能异常。下面,我将详细介绍数据不一致的原因,以及一些有效的解决方案。 什么是数据不一致 …

网络基础-Telnet协议

Telnet&#xff08;Telecommunication Network&#xff09;是一种基于文本的远程终端协议&#xff0c;允许用户通过网络连接到远程计算机&#xff0c;并在远程计算机上执行命令&#xff1b;它使用TCP作为传输层协议&#xff0c;并依赖于网络连接在客户端和服务器之间进行通信&a…

GDPU unity游戏开发 角色控制器与射线检测

在你的生活中&#xff0c;你一直扮演着你的角色&#xff0c;别被谁控制了。 小试 1. 创建一个角色控制器&#xff0c;通过键盘控制角色控制器的移动&#xff0c;角色控制器与家具发生碰撞后&#xff0c;通过Debug语句打印出被碰撞物体的信息(搜索OnControllerColliderHit的使用…

【吊打面试官系列】Java高并发篇 - 同步方法和同步块,哪个是更好的选择?

大家好&#xff0c;我是锋哥。今天分享关于 【同步方法和同步块&#xff0c;哪个是更好的选择&#xff1f;】面试题&#xff0c;希望对大家有帮助&#xff1b; 同步方法和同步块&#xff0c;哪个是更好的选择&#xff1f; 同步块是更好的选择&#xff0c;因为它不会锁住整个对象…

计算机的存储体系与性能,存储黑科技大揭秘

计算机体系结构&#xff0c;其中存储分为内存与硬盘。内存&#xff0c;非持久化存储&#xff0c;临时存数&#xff0c;断电即失&#xff1b;硬盘&#xff0c;持久化存储&#xff0c;数据长存&#xff0c;即使断电也无忧。 计算机存储种类繁多&#xff0c;分为内部与外部两类。…

走进开源,拥抱开源

走进开源&#xff0c;拥抱开源 一、开源文化1.1 什么是开源1.2 为什么要开源1.3 有哪些开源协议 二、选择开源2.1 开源社区的类型与特点2.2 如何选择开源社区2.3 如何选择开源项目 三、参与开源3.1 开源社区的参与方式3.2 开源项目的参与方式 四、Apache Doris 参与示例4.1 Dor…

如何将Git仓库中的文件打包成zip文件?

要将Git仓库中的文件打包成zip文件&#xff0c;您可以使用git archive命令。这个命令允许您将任何git可访问的树或提交导出成一个归档文件。以下是一些基本的步骤&#xff1a; 打开命令行或终端。切换到您的Git仓库的目录。执行git archive命令。 git archive --formatzip --o…

第13节 第二种shellcode编写实战(2)

在第二种shellcode编写实战(1)的基础上&#xff0c;新增加一个CAPI类&#xff0c;将所有用到的函数都在这个类中做动态调用的处理&#xff0c;这样使得整个shellcode功能结构更加清晰。 1. 新建类CAPI&#xff08;即api.h和api.cpp两个文件&#xff09;&#xff1a; api.h&…