R0011. 「T1」积木高塔 Solution

返回题目

简要题意：

给定一个矩阵，以及其每一格中完全相同立方体的高度（即个数），求：

1. 这座高塔最高点的高度。
2. 这座高塔从第 $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

返回题目

简要题意：

给定一个区间的左边界和右边界，输出其中所有既是回文数也是质数的数。

题目分析：

先思考做法：

1. 暴力枚举 $[l,r]$ 的每一个数。

数据范围 $1$ 的后面有 $8$ 个 $0$ 啊，好好想想你在做什么。

2. 因为判断回文数较快且回文数较少，所以先判断回文数，再判断质数。

看起来比较合理了吧，但是复杂度 $\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}$。