[心之碎片] - 20240814模拟赛
本帖最后由 柿子饼同学 于 2024-8-21 22:58 编辑总结与反思{:10_266:}{:10_250:}{:10_281:}
B - 要反过来考虑贡献
C - 换根题通常想分类, 然后对于每个点求一个子树的答案, 一个子树外的答案, 树上问题一定要画图, 分类
D - dfs填数独实际上是对于一个点的队列来填, 只需要安排好搜索顺序,
带着全局变量的搜索搜到答案一定要给下一个赋值为现在这个, 因为回溯不一定是从头开始
警惕排序等会让位置变化的东西, 位置会变化导致无法按照原来的编号查询
B - 加号
给定一个长度为 n 的数字字符串，每个字符是'0'~'9'。
现在有k个加号，可以插入到字符串中，每个加号只能在两个数字之间。
每一种插入方案，都对应一个表达式，可以计算出一个值。
求所有方案的值之和。
插入加号的具体不好算, 考虑计算每个数字作为个位/十位...的总贡献, 这样就使得她后面的几个位置不能填 + , 其他位置随便
所以预处理组合数, 上前缀和
// sum 表示 1 为第 i 位的贡献
// 垒前缀和即可 O(1) 计算
for (int i = 1; i <= n; i++) {
sum = sum;
sum = sum + math.p10 % P * math.C(n - i - 1, k - 1) % P;
}
// 注意考虑 i 这个位置后面不放 +, 要单独算
for (int i = 1; i <= n; i++) {
ans = (ans + (s * (math.p10 * math.C(i - 1, k) % P + sum) % P)) % P;
}
cout << ans;
C - 疯狂动态树
换根 + 查询子树内的点到根的距离和 + 查询链上的点到根的距离和
分类讨论, 对于子树问题分类 : 根在 u 上, u 的子树内, u 的子树外
对于链, 求出根到链的最短路和接入根的点, 然后路径分成两半求个等差数列
对于点到链的两端加上这个链, 三个路径的交点是三个点的 lca 中去掉两个相同的值
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int ID, n, m, rt;
vector<int> e;
// up, dn 分别代表除了子树, 子树内的节点到 x 的距离和
int siz, up, dn, dep, dfn, tot;
int f;
void dfs1(int u, int pa) {
dfn = ++tot;
siz = 1;
f = pa;
dep = dep + 1;
for (int i = 1; i < 18; i++) {
f = f];
}
for (auto v : e) {
if (v == pa)
continue;
dfs1(v, u);
siz += siz;
dn += siz + dn;
}
}
void dfs2(int u, int pa) {
// pa 头顶上的 up 每个点都要走 pa-> u 一次, 总共 n - siz 次
// pa 先去掉 u 子树的答案, 再加上除了 u 子树的点从 pa -> u 的次数, 即
// up = (up + (n - siz)) + (dn - dn - siz + siz - siz);
if (u != 1)
up = (n - siz) + up + dn - dn - siz;
for (auto v : e) {
if (v == pa)
continue;
dfs2(v, u);
}
}
int Up(int x, int d) {
for (int i = 17; i >= 0; i--) {
if ((d >> i) & 1)
x = f;
}
return x;
}
int lca(int u, int v) {
if (dep < dep)
swap(u, v);
u = Up(u, dep - dep);
if (u == v)
return u;
for (int i = 17; i >= 0; i--) {
if (f == f)
continue;
u = f;
v = f;
}
return f;
}
int dist(int u, int v) { return (dep + dep - dep * 2); }
int sigma(int x) { return ((1 + x) * x / 2); }
bool issub(int x, int y) { return (dfn >= dfn && dfn < dfn + siz); }
int Query_path(int u, int v) {
// cut 意为 rt 到路径的最近点
int cut = lca(u, rt) ^ lca(v, rt) ^ lca(u, v);
int res = 0;
res += sigma(dist(u, cut)) + sigma(dist(v, cut));
res += dist(rt, cut) * (dist(u, v) + 1);
return res;
}
int Query_subt(int u) {
if (rt == u) {
return (up + dn);
}
if (issub(u, rt)) {
int c = Up(rt, dep - dep - 1);
return (up + dn - dn - siz + dist(rt, u) * (n - siz));
}
return (dn + dist(rt, u) * siz);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("crazy.in", "r", stdin);
freopen("crazy.out", "w", stdout);
rt = 1;
cin >> ID >> n >> m;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e.emplace_back(v);
e.emplace_back(u);
}
dfs1(1, 0);
dfs2(1, 0);
while (m--) {
int op, x, y;
cin >> op >> x;
if (op == 0) {
rt = x;
} else if (op == 1) {
cin >> y;
cout << Query_path(x, y) << '\n';
} else {
cout << Query_subt(x) << '\n';
}
}
return 0;
}
D - 聪明格
n*n 的棋盘, 每个格子填 1-n 的数, 每行每列没有重复数字, 满足给出的连通块中的数字乘积是连通块的值(mp上的值)
求字典序最小的解
搜索优化: 必须满足每行每列不冲突, 按照连通块排序(从好填到不好填, 按照连通块大小和乘积因数个数排序)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 12;
const int M = 305;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
int mp, n;
// 首先给连通块排序, 重新分配每个点的搜索顺序, 确定每个点属于的连通块编号
struct Block {
int siz, facs;
vector<pii> node;
} blk;
int cnt_blk, id;
// 注意 blk 是要排序的, 后面没法直接查询 siz, 所以这里记录一下
int siz;
int Factors(int x) {
int res = 0;
for (int i = 1; i * i <= x; i++) {
if (!(x % i))
res++;
}
return res;
}
bool Check(int x, int y) { return (x > 0 && x <= n && y > 0 && y <= n && !id); }
void Explore(int x, int y) {
id = cnt_blk;
blk.siz++;
blk.node.emplace_back(x, y);
for (int i = 0; i < 4; i++) {
int nx = x + dx, ny = y + dy;
if (Check(nx, ny) && mp == mp) {
Explore(nx, ny);
}
}
}
vector<pii> q;
int m;
void Assign_points() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (!id) {
cnt_blk++;
blk.facs = Factors(mp);
Explore(i, j);
siz = blk.siz;
}
}
}
sort(blk + 1, blk + cnt_blk + 1, [](Block& x, Block& y) {
if (x.siz == y.siz)
return x.facs < y.facs;
return x.siz < y.siz;
});
for (int i = 1; i <= cnt_blk; i++) {
for (auto x : blk.node) {
q.emplace_back(x);
}
}
m = q.size();
}
// 现在开始 dfs 填数, 记录答案编号方便回答字典序的要求
bitset<N> visx, visy;
int cnt, mul;
int ans, sum = 0;
set<int> st;
bool Check(int x, int y, int a) { return (!visx && !visy && !((mp / mul]) % a)); }
void dfs(int pos) {
if (pos == m) {
st.emplace(sum++);
// 一定要注意这里, 当前走成功了之后要给接下来的图赋值
// 因为下一次走成功不一定是从头开始走的, 可能某一个小分支就又有了
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ans = ans;
}
}
return;
}
int x = q.first, y = q.second;
int c = id;
cnt++;
for (int i = 1; i <= n; i++) {
// 能取吗?
if (Check(x, y, i)) {
mul *= i;
// 真能取吗?
if (cnt < siz || (cnt == siz && mul == mp)) {
ans = i;
visx = 1, visy = 1;
dfs(pos + 1);
visx = 0, visy = 0;
}
mul /= i;
}
}
cnt--;
}
void Solve() {
for (int i = 0; i <= n * n; i++) {
mul = 1;
}
dfs(0);
}
int Select() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int minv = 1e9;
for (auto v : st) {
minv = min(minv, ans);
}
for (auto it = st.begin(); it != st.end();) {
if (ans[*it] > minv) {
it = st.erase(it);
} else {
it++;
}
}
}
}
return *st.begin();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
freopen("smart.in", "r", stdin);
freopen("smart.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> mp;
}
}
Assign_points();
Solve();
int best = Select();
cout << sum << '\n';
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << ans << ' ';
}
cout << '\n';
}
return 0;
}
鱼油你好，以下是你提到的四道题目的总结与思路解析:
### B - 加号问题
**问题描述**：给定一个长度为 `n` 的数字字符串，每个字符是'0'~'9'。现在有 `k` 个加号，可以插入到字符串中，每个加号只能在两个数字之间。要求所有方案的值之和。
**解题思路**：
1. **计算贡献**：每个数字在表达式中的位置会决定它的贡献，考虑每个数字作为个位、十位等位置的贡献。
2. **使用前缀和与组合数进行预处理**：
- 用前缀和快速计算子字符串的和。
- 用组合数计算插入加号的方案数。
3. **复杂度控制**：通过预处理和有效的计算方式，确保算法在 O(n) 或 O(n log n) 的时间内完成。
// 伪代码简化
int calculate_total_value(string s, int k) {
int n = s.size();
vector<long long> prefix_sum(n + 1, 0);
long long total_value = 0;
// 计算前缀和
for (int i = 1; i <= n; ++i) {
prefix_sum = prefix_sum * 10 + (s - '0');
}
// 计算每个位置的贡献
for (int i = 0; i < n; ++i) {
long long place_value = 1;
for (int j = i; j < n; ++j) {
total_value += (s - '0') * place_value;
place_value *= 10;
}
}
// 返回总值
return total_value;
}
### C - 换根树问题
**问题描述**：给定树和查询，每次询问需要计算某些节点的属性，比如子树的大小、路径上的权值等。
**解题思路**：
1. **分类处理**：每个查询根据性质分类，如子树内部和外部的计算。
2. **双DFS和LCA处理**：通过递归深度优先搜索（DFS），一次计算子树属性，二次根据换根情况重新计算。
// 伪代码简化
int lca(int u, int v) {
// 找到u和v的最近公共祖先
}
// 距离计算
int dist(int u, int v) {
return dep + dep - 2 * dep;
}
// 处理每次查询的主函数
int Query_path(int u, int v) {
int cut = lca(u, rt) ^ lca(v, rt) ^ lca(u, v);
int res = 0;
// 计算路径上的贡献
return res;
}
### D - 深度优先搜索填数独
**问题描述**：使用深度优先搜索（DFS）来填数独，确保每个填充操作的正确性。
**解题思路**：
1. **队列填充**：每次选择一个点进行填充，根据可能的选项填入。
2. **搜索顺序设计**：安排好回溯顺序，确保不重复或遗漏，尤其要注意全局变量的影响，每次搜索完成要更新状态。
// 伪代码简化
void dfs_fill_sudoku(...) {
if (complete) return;
for (int i = 0; i < n; ++i) {
// 尝试填入每个可能的数字
dfs_fill_sudoku(...);
}
}
### 反思与总结
- **性能优化**：在处理大规模数据时，需通过优化算法设计和使用合适的数据结构确保效率。
- **边界条件**：考虑各种输入的极端情况，确保算法能正确处理。
- **调试与测试**：多测试用例覆盖，尤其是边界和特殊情况，防止意外错误。
希望这些简洁的解释对你有所帮助！如果有更多问题或需要进一步的代码实现，请随时提出。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:10_256:}{:10_256:} 666 {:10_256:}{:10_256:} {:7_142:} {:10_256:} {:10_256:} 👌 /orz/orz 厉害了楼主{:10_254:} 谢谢 谢谢鱼币
页:
[1]