OJ刷题 第十二篇

21308 - 特殊的三角形

时间限制 : 1 秒

内存限制 : 128 MB

有这样一种特殊的N阶的三角形，当N等于3和4时，矩阵如下：

请输出当为N时的三角形。

输入

输入有多组数据，每行输入一个正整数N，1<=N<=100

输出

按照给出的样例进行输出

样例

输入

3

输出

1 2 6
3 5
4

 答案：

#include<iostream>
#include<stdio.h>
using namespace std;
int main() {int a[101][101] = { 0 };int ret = 1;//给每个元素赋值的变量bool direction = false;//true表示往下走，false表示往上走int i = 1,N;while (scanf("%d",&N)==1) {ret = 1;direction = false;//计算三角形的值for (int i = 1; i <= N; i++) {if (direction) {//当前往下走int col = i;for (int k = 1; k <= i; k++) {a[k][col--] = ret++;}direction = !direction;//改变方向}else {//往上走int col = i;for (int k = 1; k <= i; k++) {a[col--][k] = ret++;}direction = !direction;//改变方向}}//打印for (int i = 1; i <= N; i++) {for (int j = 1; j <= N - i + 1; j++) {//每行元素有N-i+1个元素cout << a[i][j] << ' ';}cout << endl;}}return 0;
}

分析：这个题难度还是比较大的，之前我们在前面刷到过那个蛇形矩阵，那个题在前面也挺难的，但是我们理解整个代码逻辑后其实也没那么难，初次遇到这个题那肯定挺难的。这个题就是类似于这种：如图：

就是像一个蛇一样来回走。因此我们可以设置一个标记用来表示蛇是往下走还是往上走。每次走完后改变当前方向。至于每个方向是怎么走的，这个就自己去琢磨了。

 另外这个题输入的数据个数是任意的，最开始我写的是这样：

while (true) {cin >> N;

就陷入死循环，代码不通过，提示输出超限！后面还是借助C语言的scanf函数的输入来输入，后面就能通过了。这个题这样出，用C/C++还是不好实现的，因为这种任意数据的输入，而且还不知道输入什么表示结尾，这种输入用C/C++实现比较困难！。

最后是否通过：

21204 - 图书管理员(NOIP2017PJT2)

时间限制 : 1 秒

内存限制 : 128 MB

图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。 每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。

小D刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他需要的书，请输出-1。

输入

输入文件的第一行，包含两个正整数 n 和 q，以一个空格分开，分别代表图书馆里书的数量和读者的数量。 接下来的 n 行，每行包含一个正整数，代表图书馆里某本书的图书编码。 接下来的 q 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆里读者的需求码的长度，第二个正整数代表读者的需求码。 数据范围：1 ≤ n ≤ 1,000，1 ≤ q ≤ 1,000，所有的图书编码和需求码均不超过 10,000,000。

输出

输出文件有 q 行，每行包含一个整数。 如果存在第 i 个读者所需要的书，则在第 i 行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码；否则输出-1。

样例

输入

5 5 
2123 
1123 
23 
24 
24 
2 23 
3 123 
3 124 
2 12 
2 12

输出

23 
1123 
-1 
-1 
-1

答案：

#include<iostream>
typedef struct reader {//读者信息，包括所需编号长度和末尾的编号int length;int code;
}reader;int calcute(int length, int book) {//计算某本书末尾长度为length的值，如2232末尾长度为2的值是32int sum = 0;int r = 1,mul=1;for (int i = 1; i <= length; i++) {r = book % 10;;sum = sum + mul*r;mul *= 10;book /= 10;}return sum;
}
using namespace std;
int main() {int n_book, q_read;//分别表示书的数量和读者的数量cin >> n_book >> q_read;int book[1000];//存放书的编号reader people[1000];//存放读者信息//输入书的编码for (int i = 0; i < n_book; i++) {cin >> book[i];}//输入读者的数据for (int i = 0; i < q_read; i++) {cin >> people[i].length >> people[i].code;}//求最大编号的书int max=book[0];//求最大编号是为了找最小编号，仔细琢磨for (int i = 1; i < n_book; i++) {max = max > book[i] ? max : book[i];}//对每一位读者找编号最小的那本书for (int i = 0; i < q_read; i++) {int min=max;bool flag = false;for (int j = 0; j < n_book; j++) {if (calcute(people[i].length, book[j])==people[i].code) {min = min > book[j] ? book[j] : min;flag = true;}}if (flag) {cout << min << endl;}else {cout << -1 << endl;}}return 0;
}

 分析：这个题给的信息有点多，要仔细梳理，文字多不要害怕，往往文字多，题目逻辑是很简单的。这到题的意思就是对每一个读者，每一位读者给出了编号得长度和指定得编号，现在就是要去和每本书作比较，取出每本书指定长度的末尾，然后和读者给出的编号比较，如果一样，就保存当前书的编号，继续对比，直到所有书对比完，找到最小那个编号即可，如果没有符合条件的编号，打印-1即可。

这道题难点：

1、在存读者的信息用到了结构体，当然你也可以用两个数组存储，但是为了体现出读者信息的整体性，用结构体还是比较好。这是难的一个点。

2、其次就是这道题我们要通过最大编号找最小编号。这个可能不好理解。当然用两个数组存读者信息的话也用不到这个。

是否通过：

21401 - 进制转换

时间限制 : 1 秒

内存限制 : 128 MB

给定一个十进制正整数N（1 ≤ N ≤ 30000），求其对应的二进制数。

输入

仅一行，包含一个正整数N。

输出

共一行，包含一个正整数，表示N对应的二进制数。

样例

输入

10

输出

1010

 答案：

#include<iostream>
using namespace std;
int main() {int N;cin >> N;int num = N;int a[16];//题目说N最大为30000，故二进制数最多不超过16位int i = 0,count = 0;while (num) {int r = num % 2;a[i++] = r;count++;num /= 2;}if (N == 0) {cout << N << endl;}else {for (int i = count - 1; i >= 0; i--) {cout << a[i];}}return 0;
}

分析：当N为0时到单独处理，我们用短除法把十进制数获得余数，采取倒取余数的方式获得它的二进制数。其实也可以可以采用栈来实现。栈的一个应用可以用来实现进制转换。

是否通过：

21403 - 间谍

时间限制 : 1 秒

内存限制 : 128 MB

现在有9个科学家正在一起研究机密问题，但据可靠消息，其中有两人是间谍，只有7个人是真正的科学家。cyh同学想将这两个间谍揪出来。当然，这9人都声称自己不是间谍。幸运的是，每个人都戴着一顶帽子，帽子上有一个小于100的正整数。根据最新的准确消息，真正的7位科学家戴着的帽子上的数字之和刚好等于100。由于cyh同学要准备期终考试，请你编写一个程序，找出真正的7个科学家。

输入

输入共9行。

每行一个整数，第i行的整数表示第i个科学家戴的帽子上的正整数。

输出

输出共7行（因为只有7个科学家）。

每行一个整数，第i行的整数表示第i个科学家戴的帽子上的正整数，注意输出的顺序是按去掉两个间谍后的顺序。

样例

输入

1
5
6 
7 
10 
12 
19 
29 
33

输出

1
5
6 
7 
19 
29 
33

答案：

#include<iostream>
using namespace std;
int main() {int a[9];int sum = 0;for (int i = 0; i < 9; i++) {cin >> a[i];sum += a[i];}sum -= 100;//则sum的值为不是科学家的两个人帽子之和//找出符合条件的两个人for (int i = 0; i < 9; i++) {for (int j = 1; j < 9; j++) {if (a[i] + a[j] == sum) {a[i] = 0;a[j] = 0;break;}}}//打印for (int i = 0; i < 9; i++) {if (a[i]) {cout << a[i] << endl;}}return 0;
}

 分析：这个题意思就是在9个数中找出7个数，使得它们的和为100，剩下的两个数字肯定就是间谍。但是现在怎么把所有的7种组合找出来呢？用9重循环？？？我想这不好办吧。这道题我们反其道而行之。既然是求求7个等于100的数字，我们可以把9个数字加起来然后减去100，得到的结果就是间谍之和，间谍就两个，只需两个循环即可。

是否通过：

 

21405 - 哪种苹果最多

时间限制 : 1 秒

内存限制 : 128 MB

陶陶家的院子里有许多苹果树，每到秋天树上就会结出许多苹果。苹果成熟的时候，陶陶就会跑去摘苹果。经过估算，每个苹果都有一个甜度，第i个苹果的甜度为di。

输入

输入共有两行：

第一行，包含一个整数n，表示有n个苹果；

第二行，包含n个用空格隔开的正整数，分别表示n个苹果的甜度。

对于100%的数据，1≤di≤1000;1≤n≤100。

输出

输出共一行，包含两个用空格隔开的整数，分别表示最多的那种苹果的甜度及有几个这样的苹果。

样例

输入

10
100 200 200 140 129 134 167 198 200 110

输出

200 3

答案：

#include<iostream>
using namespace std;
int main() {int n;cin >> n;int di[100];for (int i = 0; i < n; i++) {cin >> di[i];}//找出甜度不同的苹果的有多少个int kind[100] = { 0 };for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (di[i] == di[j]) {kind[i]++;}}}//求出不同甜度的苹果的个数，求出最大的那个个数int max = kind[0];int maxDI = di[0];//求出甜度最大的苹果for (int i = 0; i < n; i++) {if (max <= kind[i]) {max = kind[i];}maxDI = maxDI > di[i] ? maxDI : di[i];}//甜度个数相同的苹果，求出甜度小的那个int min = maxDI;for (int i = 0; i < n; i++) {if (max == kind[i]) {min = min < di[i] ? min : di[i];}}cout << min << ' ' << max << endl;return 0;
}

分析：这道题和前面那道21404-最好吃的苹果相比，难度大了一些。另外这个题有一个条件它没说清楚，当不同的甜度有相同的的苹果个数且都是最多时，要选出甜度最小的那个，这是题目没有说明的地方，我也是通过它的测试案例才知道题目少了这个条件。

是否通过：