C++学习笔记3

A. 求出那个数

题目描述

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

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

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

$$a_n=\{\begin{array}{ll}1& n\le 2\\ a_{n-a_{n-1}}+a_{n-1-a_{n-2}}& n>2\end{array}$$

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

输入格式

多组输入。

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

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

• $1\le n\le 10^6$

输出格式

每组输入在一行中输出 $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$，$A$ 标号就是 $1$，$\dots$，$Z$ 编号就是 $26$，然后再将每个编号转为长度为 $5$ 的二进制数以后，按照螺旋方阵的方式填入一个 $R\times C$ 的矩阵中，若二进制串不够长就在后面补 $0$。

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

0001
0100
0010
1010

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

输入格式

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

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

$S$ 中可能含有空格！

输出格式

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

样例

输入 #1

4 4 BEE

输出 #1

0001010000101010

1. 注意输入有空格
2. 转二进制之后不足五位前面要补零
3. 整个二进制串长度不足 $R\times 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$ 行。

第一行表示要付的价格。

第二行有 $5$ 个数字 $p_1,p_5,p_{10},p_{20},p_{50}$，分别是东东钱包里面一元、五元、十元、二十元和五十元硬币的个数。

第三行有 $5$ 个数字 $p_1,p_5,p_{10},p_{20},p_{50}$，是老板所拥有的一元、五元、十元、二十元和五十元硬币的个数。

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

输出格式

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

样例

输入 #1

25
0 3 2 2 3 
1 1 1 1 1

输出 #1

4

提示

付 $3$ 个 $5$ 元，$2$ 个 $10$ 元，$2$ 个 $20$ 元，老板找回 $1$ 个 $50$ 元，最后手里有 $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$，没有排水装备的格子只需要等水流到有排水装备的格子，水能往相邻且较低的格子流动，流动到相邻一格的时间为 $1$。若某个格子的水能流到不止一个具有排水装备的格子，则让其流向最近的一个。

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

假设安装了 $3$ 个排水设备在地图上，为了尽快排完所有的水，其中一种方案是装在三维图中的灰色格子上，这样各个格子所需要的排水时间下：

输入格式

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

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

• $1\le n\le 500,1\le m\le 1000$
• $0<d<2^{31}$

输出格式

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

若需要超过 $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$ 就是 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$ 的正整数 $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$，那我们相当于是有抽象的杯子 $k_1\times (x-y)$，也有抽象的杯子 $k_2\times y-x$，$k_1,k_2$ 都是任意常数
2. 所以题目相当于是求 $k_1\times (x-y)+k_2\times y-x=z$ 的解
3. 合并可得 $k_3\times x-k_4\times y=z$，$k_3,k_4$ 是任意常数
4. 上面这个方程有解的条件就是 $z\mathrm{mod}\gcd (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;
}