R0011. 「T1」积木高塔 Solution
简要题意：
给定一个矩阵，以及其每一格中完全相同立方体的高度（即个数），求：
-
这座高塔最高点的高度。
-
这座高塔从第 \(1\) 层到最高层之间，每一层的立方体个数。
题目分析：
做法 \(1\):
期望得分：\(50\ pts\)
对于层数，我们可以在读入时使用 max 函数取得最高层，也就是求出了总层数。然后对于每一层，都扫描一遍，如果积木柱高度大于等于这一层的高度，就说明这个积木柱在这个层数有一格积木，故 cnt++。
时间复杂度：\(\mathcal{O}(nmk)\)
$ \mathrm{Code:} $
//Code by Polarie，略有修改
#include <bits/stdc++.h>
using namespace std;
int a[10001][10001];
int main () {
int n, m, maxn = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
maxn = max(maxn, a[i][j]);//取最大值
}
}
cout << maxn << endl;
for (int i = 1; i <= maxn; i++) {
int cnt = 0;//归零
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= m; k++) {
if (a[j][k] >= i)
cnt++;//扫描
}
}
cout << cnt << endl;
}
return 0;//好习惯
}
然鹅 \(\mathrm{Subtask\ 3}\) 全部 \(\mathrm{TLE}\)……
做法 \(2\):
期望得分：\(100\ pts\)
既然要统计积木个数，那我们就考虑计数排序，利用了桶排的思想，这样的好处是不用扫描，且不用存储矩阵，即少开了一个 \(5000 \times 5000\) 的二维数组。
时间复杂度：\(\mathcal{O}(nm)\)
$ \mathrm{Code:}$
//Code by __er
#include <bits/stdc++.h>
using namespace std;
int maxn = -1, n, m, i, j, ans[11]/*桶*/, tmp;
inline int read() {//快速读入
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
int main() {
n = read();
m = read();
int nm = n * m;
ans[1] = nm;//所有积木柱高度都大于1，故第一层必然全都有
for (i = 1; i <= nm; i++) {
tmp = read();
maxn = max(maxn, tmp);
while (tmp >= 2) {
ans[tmp]++;
tmp--;//统计
}
}
cout << maxn << endl;
for (i = 1; i <= maxn; i++) {
cout << ans[i] << endl;
}
return 0;
}
不开 \(O2\) 最慢一个点也在 \(600ms\) 以下，足以通过此题。
R0012. 「T2」回文质数 Solution
简要题意：
给定一个区间的左边界和右边界，输出其中所有既是回文数也是质数的数。
题目分析：
先思考做法：
- 暴力枚举 \([l,r]\) 的每一个数。
数据范围 \(1\) 的后面有 \(8\) 个 \(0\) 啊，好好想想你在做什么。
- 因为判断回文数较快且回文数较少，所以先判断回文数，再判断质数。
看起来比较合理了吧，但是复杂度 \(\mathcal{O}(\sum_{i=l}^{r} \dfrac{i}{2}+\sqrt{i})\)，或者说简单点：\(\mathrm{TLE}\)。
所以我们采用更快的方法，生成回文质数：
int reverse(int n) {
int a[10], i, sum = 0, t = n;
for (i = 0; n > 0; i++, n /= 10) {
a[i] = n % 10;
}
for (int j = 1; j < i; j++) {
sum = sum * 10 + a[j];
}
return sum + t * pow(10, i - 1);
}
bool prime(int n) {
if (n == 1) {
return false;
}
if (n == 2) {
return true;
}
if (n % 3 == 0) {
return false;
}
for (int i = 7; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
void dfs(int i) {
int x = reverse(i);
if (x > r) {
return;
}
if (prime(x) && x != 7 && x >= l) {
a[sum++] = x;
}
for (int j = 0; j < 10; j++) {
if (i * i < r) {
dfs(i * 10 + j);
} else {
return;
}
}
}
但是，你会惊讶的发现，这么写是会 \(\mathrm{WA}\) 滴！
因为它是无序生成的，所以要排序，这里用的是二分快排：
void qsort(int l, int r) {
int i = l, j = r, mid = a[(l + r) / 2];
while (i <= j) {
while (a[i] < mid)
i++;
while (a[j] > mid)
j--;
if (i <= j)
swap(a[i++], a[j--]);
}
if (i < r)
qsort(i, r);
if (l < j)
qsort(l, j);
}
注意 \(5,7,11\) 小于 \(3\) 位，需要特判。
\(\mathrm{Code:}\)
#include <bits/stdc++.h>
using namespace std;
int l, r, sum, a[1000000];
int reverse(int n) {
int a[10], i, sum = 0, t = n;
for (i = 0; n > 0; i++, n /= 10) {
a[i] = n % 10;
}
for (int j = 1; j < i; j++) {
sum = sum * 10 + a[j];
}
return sum + t * pow(10, i - 1);
}
bool prime(int n) {
if (n == 1) {
return false;
}
if (n == 2) {
return true;
}
if (n % 3 == 0) {
return false;
}
for (int i = 7; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
void qsort(int l, int r) {
int i = l, j = r, mid = a[(l + r) / 2];
while (i <= j) {
while (a[i] < mid)
i++;
while (a[j] > mid)
j--;
if (i <= j)
swap(a[i++], a[j--]);
}
if (i < r)
qsort(i, r);
if (l < j)
qsort(l, j);
}
void dfs(int i) {
int x = reverse(i);
if (x > r) {
return;
}
if (prime(x) && x != 7 && x >= l) {
a[sum++] = x;
}
for (int j = 0; j < 10; j++) {
if (i * i < r) {
dfs(i * 10 + j);
} else {
return;
}
}
}
int main() {
cin >> l >> r;
if (l == 5) {
a[0] = 5;
a[1] = 7;
a[2] = 11;
sum = 3;
} else if (l <= 7) {
a[0] = 7;
a[1] = 11;
sum = 2;
} else if (l <= 11) {
a[sum++] = 11;
}
dfs(1);
dfs(3);
dfs(7);
dfs(9);
qsort(0, sum - 1);
for (int i = 0; i < sum; i++) {
cout << a[i] << '\n';
}
return 0;
}
即可 \(\mathrm{AC}\)。
R0013. 「T3」街道赛跑 Solution
题目分析：
核心思想：有向图 Dfs遍历。
首先我们要存图。虽然邻接表的确功能和优点很强大，但是这道题目50个点，100条边还是邻接矩阵好写多了。在练习邻接表的时候别忘记练习下邻接矩阵。
这道题目分两问，第一问其实很好做，怎么去搜索“不可避免的点”呢，只要把从这个点出发的所有边都标记为不通，然后再去看是不是所有点都被遍历了就可以了。
第二问的答案一定都包含在第一问的答案里面。所以我们可以直接搜索第一问的答案。从第一问的答案的那个点开始遍历，看那个点之前的点有没有被遍历到就可以了。
\(\mathrm{Code:}\)
#pragma(3,"Ofast")
#include <iostream>
using namespace std;
bool m[51][51], vis[51], vis2[51];
int a[51], a2[51], p1, p2, p3 = 0;
#define int register int
bool dfs1(int x) {
if (vis[x]) {
return false;
}
if (x == p3) {
return true;
}
vis[x] = true;
for (int i = 0; i <= p3; i++) {
if (m[x][i] ) {
if (dfs1(i)) {
return true;
}
}
}
return false;
}
bool dfs2(int x) {
if (vis[x]) {
return true;
}
if (vis2[x]) {
return false;
}
vis2[x] = true;
for (int i = 0; i <= p3; i++) {
if (m[x][i]) {
if (dfs2(i)) {
return true;
}
}
}
return false;
}
#undef int
int main() {
#define int register int
ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
while (true) {
int t;
cin >> t;
if (t == -1) {
break;
}
if (t == -2) {
p3++;
} else {
m[p3][t] = true;
}
}
p3--;
for (int i = 1; i <= p3 - 1; i++) {
for (int j = 0; j <= p3; j++) {
vis[j] = false;
}
vis[i] = true;
for (int j = 0; j <= p3; j++) {
vis2[j] = false;
}
if (!dfs1(0)) {
a[p1++] = i;
vis[i] = false;
if (!dfs2(i)) {
a2[p2++] = i;
}
}
}
cout << p1;
for (int i = 0; i <= p1 - 1; i++) {
cout << " " << a[i];
}
cout << endl << p2;
for (int i = 0; i <= p2 - 1; i++) {
cout << " " << a2[i];
}
return 0;
}
我写题解的怎么可能给你 \(\mathrm{WA}\) 代码蛋子？这代码绝对保 \(\mathrm{AC}\)。
标签：10,return,OJ,Criss,int,题解,sum,++,mathrm From： https://www.cnblogs.com/ymxx-home/p/R001Solution.html