1019 | 千姿百态
据说正儿八经应该用卡塔兰数。然鹅，不会。
-
可能的二叉树形态数 == 可能的二叉搜索树形态数
任何一棵二叉树，按中序遍历的顺序给结点赋值（有序的），都可以形成二叉搜索树。 -
递归也可，一棵🌲，n个结点，左右子树结点共 nn-1 个。
可以拆成左0右nn-1，左1右nn-2， ……，到左nn-1右0。
累加：左*右
注意乘取模，加也取模。 -
注意保存结果，不要重复计算。
-
初始：结点数0，形态1种；结点数1，形态1种。
-
卡塔兰数
递推h(n) = h(n-1)*(4n-2)/(n+1)不能用来取模，因为(4n-2)/(n+1)可能是小数。
可以用另一个公式：(n+1)!(2n)!/n!
#include <cstdio>
#include <algorithm>
#define MOD 1000000007
using namespace std;
typedef long long LL;
LL type_cnt[1001] = {0};
LL dfs(int num) {
if (num == 1 || num == 0) return type_cnt[num];
for (int i = 0; i < num; ++i) {
if (type_cnt[i] == 0) type_cnt[i] = dfs(i);
if (type_cnt[num - i - 1] == 0) type_cnt[num - i - 1] = dfs(num - i - 1);
type_cnt[num] = (type_cnt[num] + type_cnt[i] * type_cnt[num - i - 1] % MOD) % MOD;
}
return type_cnt[num];
}
int main() {
int ign, n;
scanf("%d%d", &ign, &n);
type_cnt[0] = 1, type_cnt[1] = 1;
printf("%lld\n", dfs(n));
return 0;
}
1023 | 缺失数
像PAT里那道找缺失的最小正数一样写的，然后TLE。看了题解。
- 首先，n个数中缺失的最小正数不可能比n+1大。若记下正数排序，大于n+1的数不用记。
- 标准解法
让每个数回到自己的位置
遍历i从1到nn，若arr[arr[i]]中存的不是arr[i]，循环并swap。
⚠️循环，下标不要越界
#include <cstdio>
#include <algorithm>
using namespace std;
int vec[10000001];
int main() {
int nn;
long long temp;
scanf("%d", &nn);
for (int i = 1; i <= nn; ++i) {
scanf("%lld", &temp);
vec[i] = int(temp);
}
for (int i = 1; i <= nn; ++i) {
while (vec[i] <= nn && vec[i] > 0 && vec[vec[i]] != vec[i])
swap(vec[i], vec[vec[i]]);
}
for (int i = 1; i <= nn; ++i) {
if (vec[i] != i) {
printf("%d\n", i);
return 0;
}
}
printf("%d\n", nn + 1);
return 0;
}
1024 | 宇宙树
有点综合。
-
可能有多个连通分量（输入边时，用并查集，标号大的合并到标号小的）。
-
从每个集合的老大开始DFS，注意维护路径的值。
-
DFS的return条件
- 自己就是老大。
- 没有孩子了。
只有一条边，且另一段结点在这条路径上（访问过，是父亲）。
-
路径值的加法需要用大整数加法（猝不及防……）
- 大整数加法长度取两者中，不够就补0，注意最后的进位。
- 注意前导0的处理，注意去除前导0之后为空再补一个0。
- 注意算完reverse。
-
DFS时路径的维护
visited true/false，push_back/pop_back成对用。
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int nn, mm, uf[10001];
string path_val, tree_val;
char types[10001];
vector<int> graph[10001];
bool visited[10001] = {false};
int _find(int a) {
return uf[a] < 0 ? a : uf[a] = _find(uf[a]);
}
void _union(int a, int b) {
a = _find(a);
b = _find(b);
if (a != b) {
int ta = min(a, b), tb = max(a, b);
uf[ta] += uf[tb];
uf[tb] = ta;
}
}
string str_plus(string &sa, string &sb) {
int la = sa.length(), lb = sb.length();
int extra = 0, temp;
string res;
int i = la - 1, j = lb - 1;
for (; i >= 0 || j >= 0; i--, j--) {
int a = i >= 0 ? sa[i] - '0' : 0, b = j >= 0 ? sb[j] - '0' : 0;
temp = extra + a + b;
extra = temp / 10;
temp %= 10;
res += char(temp + '0');
}
if (extra) res += char(extra + '0');
while (res.back() == '0') res.pop_back();
if (res.empty()) res = "0";
reverse(res.begin(), res.end());
return res;
}
void DFS(int curr) {
if (graph[curr].empty()) {
string temp;
temp += types[curr];
tree_val = str_plus(tree_val, temp);
return;
}
if (graph[curr].size() == 1 && visited[graph[curr][0]]) { // leaf
path_val += types[curr];
tree_val = str_plus(tree_val, path_val);
path_val.pop_back();
return;
}
visited[curr] = true;
path_val += types[curr];
for (auto item:graph[curr]) {
if (!visited[item])DFS(item);
}
visited[curr] = false;
path_val.pop_back();
}
int main() {
scanf("%d%d\n", &nn, &mm);
fill(uf, uf + nn, -1);
int v1, v2;
for (int i = 0; i < nn; ++i)
scanf("%c ", &types[i]);
for (int i = 0; i < mm; ++i) {
scanf("%d%d", &v1, &v2);
graph[v1].push_back(v2);
graph[v2].push_back(v1);
_union(v1, v2);
}
vector<int> roots;
int cnt = 0;
for (int i = 0; i < nn; ++i) {
_find(i);
if (uf[i] < 0) {
roots.push_back(i);
cnt++;
}
}
printf("%d\n", cnt);
for (int i = 0; i < cnt; i++) {
tree_val = "0";
DFS(roots[i]);
printf("%s", tree_val.data());
printf(i + 1 == cnt ? "\n" : " ");
fill(visited, visited + nn, false);
}
return 0;
}
网友评论