7-4 奇葩楼层 (15 point(s))

几乎每个国家都有自己忌讳的数字,有的大楼在给楼层编号的时候,会刻意跳过含有不吉利数字的编号。比如中国人比较忌讳 4,有的大楼就没有第 4 层、第 14 层 等等,这样楼层的编号就会是 1、2、3、5、…… 即编号为 5 的楼层实际是第 4 层。那么在去掉了忌讳数字之后最高楼层编号为 n 的大楼,实际上有多少层呢?

输入格式:

输入在一行中给出 2 个整数,依次为大楼最高层的编号 n(1<n≤1000),和某国人民忌讳的数字 d(0≤d≤9)。题目保证 n 中不包含 d。注意楼层编号从 1 开始。

输出格式:

在一行中输出该大楼的实际楼层数。

输入样例:

1
50 4

输出样例:

1
36
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int main()
{
int n, d, t = 0;
cin >> n >> d;
for (int i = 1; i <= n; i++)
{
if (i < 10) (i!=d?t++:t);
else if (i >= 10 && i < 100) (i % 10 != d && i / 10 != d)?t++:t;
else if (i >= 100 && i < 1000) (i % 10 != d && (i % 100 - i % 10) / 10 != d && i / 100 != d)?t++:t;
else if (i = 1000) (d!=1&&d!=0) ? t++:t;
}
cout << t << endl;
return 0;
}

7-5 大勾股定理 (15 point(s))

大勾股定理是勾股定理的推广:对任何正整数 n 存在 2n+1 个连续正整数,满足前 n+1 个数的平方和等于后 n 个数的平方和。例如对于 n=1 有 32+42=52;n=2 有 102+112+122=132+142 等。给定 n,本题就请你找出对应的解。

输入格式:

输入在一行中给出正整数 n(≤104)。

输出格式:

分两行输出满足大勾股定理的解,格式如下:

1
2
a[0]^2 + a[1]^2 + ... + a[n]^2 =
a[n+1]^2 + ... + a[2n]^2

其中解的数列 a[0] ... a[2n] 按递增序输出。注意行首尾不得有多余空格。

输入样例:

1
3

输出样例:

1
2
21^2 + 22^2 + 23^2 + 24^2 =
25^2 + 26^2 + 27^2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int b = n*(2*n+1);
for (int i = 1;i<=(n+1);i++)
{
cout<<n*(2*n+1)+i-1<<"^2";
if(!(i==n+1)) cout<<" + ";
}
cout<<" ="<<endl;
for (int i = n+2;i<=(2*n+1);i++)
{
cout<<n*(2*n+1)+i-1<<"^2";
if(!(i==2*n+1)) cout<<" + ";
}
cout<<endl;
return 0;
}

7-6 矩阵列平移 (20 point(s))

给定一个 n×n 的整数矩阵。对任一给定的正整数 k<n,我们将矩阵的偶数列的元素整体向下依次平移 1、……、k、1、……、k、…… 个位置,平移空出的位置用整数 x 补。你需要计算出结果矩阵的每一行元素的和。

输入格式:

输入第一行给出 3 个正整数:n(<100)、k(<n)、x(<100),分别如题面所述。

接下来 n 行,每行给出 n 个不超过 100 的正整数,为矩阵元素的值。数字间以空格分隔。

输出格式:

在一行中输出平移后第 1 到 n 行元素的和。数字间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

1
2
3
4
5
6
7
8
7 2 99
11 87 23 67 20 75 89
37 94 27 91 63 50 11
44 38 50 26 40 26 24
73 85 63 28 62 18 68
15 83 27 97 88 25 43
23 78 98 20 30 81 99
77 36 48 59 25 34 22

输出样例:

1
440 399 369 421 302 386 428

样例解读

需要平移的是第 2、4、6 列。给定 k=2,应该将这三列顺次整体向下平移 1、2、1 位(如果有更多列,就应该按照 1、2、1、2 …… 这个规律顺次向下平移),顶端的空位用 99 来填充。平移后的矩阵变成:

1
2
3
4
5
6
7
11 99 23 99 20 99 89
37 87 27 99 63 75 11
44 94 50 67 40 50 24
73 38 63 91 62 26 68
15 85 27 26 88 18 43
23 83 98 28 30 25 99
77 78 48 97 25 81 22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
int main()
{
int n, k, x;
cin >> n >> k >> x;
int matrix[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> matrix[i][j];

for (int j = 2; j / 2 <= n / 2; j += 2)
{
for (int i = 0; i < n - (k - (j / 2) % k); i++)
{
matrix[n - 1 - i][j - 1] = matrix[n - 1 - i - (k - (j / 2) % k)][j - 1];
}
for (int i = 0; i < (k - (j / 2) % k); i++)
{
matrix[i][j - 1] = x;
}
}
for (int i = 0; i < n; i++)
{
int num=0;
for (int j = 0; j < n; j++)
{
num+=matrix[i][j];
}
cout<<num<<(i!=(n-1)?" ":"");
}
return 0;
}

7-7 约会大作战 (20 point(s))

某社团开展了一个“快闪”相亲活动,活动规则如下:

  1. 社团负责人将所有人分为两组,并收集了每个人对另外一组的所有人的好感度;
  2. 然后社团负责人会随机地在两组各抽取一个人,询问他们是否愿意一起去约会;
  3. 所有人对一开始的两次询问一定会拒绝;
  4. 从第三次询问开始,如果询问的人的好感度大于这个人之前的两个没能牵手的人,则接受,否则拒绝;
  5. 只有两个人同时接受,约会才成立。
  6. 约会成立后,后面的询问一律拒绝。

现在给出好感度和每次询问的两个人,请你帮忙计算一下最终有哪些人可以去约会了。

输入格式:

输入第一行是三个数字 N,M,Q (1 ≤ N,M ≤ 100, 1 ≤ Q ≤ 500), 表示分成的两组里,第一组有 N 个人,第二组有 M 个人,共有 Q 次询问。

接下来 N 行,每行 M 个数,第 i 行的第 j 个数表示第一组的第 i 个人对第二组的第 j 个人的好感度数值。数字的绝对值不超过 100。

再接下来的 M 行,每行 N 个数,第 i 行的第 j 个数表示第二组的第 i 个人对第一组的第 j 个人的好感度数值。数字的绝对值同样不超过 100。

最后有 Q 行,每行两个数字 x,y,表示主持人询问第一组的第 x 个人和第 y 个人去不去约会。

每一组内人的编号从 1 开始。

注意: 如果同一对人被询问两次,会被当成两对人处理。

输出格式:

输出若干行,每行两个数 a,b,表示第一组的第 a 个人和第二组的第 b 个人约会成功。顺序按照询问顺序的先后。如果没有一对能约会成功,则输出一行 PTA is my only love

输入样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
3 4 12
8 9 1 2
3 4 8 5
1 8 2 9
8 6 2
8 4 1
5 8 7
7 2 8
3 1
2 3
3 3
1 3
2 1
1 4
1 1
2 4
3 2
2 2
1 2
3 4

输出样例:

1
2
1 1
3 4

7-8 浪漫侧影 (25 point(s))

v.JPG

“侧影”就是从左侧或者右侧去观察物体所看到的内容。例如上图中男生的侧影是从他右侧看过去的样子,叫“右视图”;女生的侧影是从她左侧看过去的样子,叫“左视图”。

520 这个日子还在打比赛的你,也就抱着一棵二叉树左看看右看看了……

我们将二叉树的“侧影”定义为从一侧能看到的所有结点从上到下形成的序列。例如下图这棵二叉树,其右视图就是 { 1, 2, 3, 4, 5 },左视图就是 { 1, 6, 7, 8, 5 }。

fig.JPG

于是让我们首先通过一棵二叉树的中序遍历序列和后序遍历序列构建出一棵树,然后你要输出这棵树的左视图和右视图。

输入格式:

输入第一行给出一个正整数 N (≤20),为树中的结点个数。随后在两行中先后给出树的中序遍历和后序遍历序列。树中所有键值都不相同,其数值大小无关紧要,都不超过 int 的范围。

输出格式:

第一行输出右视图,第二行输出左视图,格式如样例所示。

输入样例:

1
2
3
8
6 8 7 4 5 1 3 2
8 5 4 7 6 3 2 1

输出样例:

1
2
R: 1 2 3 4 5
L: 1 6 7 8 5