[心之碎片] - 20240814模拟赛

柿子饼同学

总结与反思

B - 要反过来考虑贡献

C - 换根题通常想分类, 然后对于每个点求一个子树的答案, 一个子树外的答案, 树上问题一定要画图, 分类

D - dfs填数独实际上是对于一个点的队列来填, 只需要安排好搜索顺序,
带着全局变量的搜索搜到答案一定要给下一个赋值为现在这个, 因为回溯不一定是从头开始
警惕排序等会让位置变化的东西, 位置会变化导致无法按照原来的编号查询

B - 加号
给定一个长度为 n 的数字字符串，每个字符是'0'~'9'。
现在有k个加号，可以插入到字符串中，每个加号只能在两个数字之间。
每一种插入方案，都对应一个表达式，可以计算出一个值。
求所有方案的值之和。

插入加号的具体不好算, 考虑计算每个数字作为个位/十位...的总贡献, 这样就使得她后面的几个位置不能填 + , 其他位置随便
所以预处理组合数, 上前缀和

// sum[i] 表示 1 为第 i 位的贡献
// 垒前缀和即可 O(1) 计算
for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1];
    sum[i] = sum[i] + math.p10[i - 1] % P * math.C(n - i - 1, k - 1) % P;
}
// 注意考虑 i 这个位置后面不放 +, 要单独算
for (int i = 1; i <= n; i++) {
    ans = (ans + (s[i] * (math.p10[n - i] * math.C(i - 1, k) % P + sum[n - i]) % 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[N];

// up, dn 分别代表除了子树, 子树内的节点到 x 的距离和
int siz[N], up[N], dn[N], dep[N], dfn[N], tot;
int f[N][18];

void dfs1(int u, int pa) {
    dfn[u] = ++tot;
    siz[u] = 1;
    f[u][0] = pa;
    dep[u] = dep[pa] + 1;

    for (int i = 1; i < 18; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }

    for (auto v : e[u]) {
        if (v == pa)
            continue;

        dfs1(v, u);
        siz[u] += siz[v];
        dn[u] += siz[v] + dn[v];
    }
}

void dfs2(int u, int pa) {
    // pa 头顶上的 up[pa] 每个点都要走 pa-> u 一次, 总共 n - siz[pa] 次
    // pa 先去掉 u 子树的答案, 再加上除了 u 子树的点从 pa -> u 的次数, 即
    // up[u] = (up[pa] + (n - siz[pa])) + (dn[pa] - dn[u] - siz[u] + siz[pa] - siz[u]);

    if (u != 1)
        up[u] = (n - siz[u]) + up[pa] + dn[pa] - dn[u] - siz[u];

    for (auto v : e[u]) {
        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[x][i];
    }
    return x;
}

int lca(int u, int v) {
    if (dep[u] < dep[v])
        swap(u, v);

    u = Up(u, dep[u] - dep[v]);

    if (u == v)
        return u;

    for (int i = 17; i >= 0; i--) {
        if (f[u][i] == f[v][i])
            continue;
        u = f[u][i];
        v = f[v][i];
    }

    return f[u][0];
}

int dist(int u, int v) { return (dep[u] + dep[v] - dep[lca(u, v)] * 2); }

int sigma(int x) { return ((1 + x) * x / 2); }

bool issub(int x, int y) { return (dfn[y] >= dfn[x] && dfn[y] < dfn[x] + siz[x]); }

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[u] + dn[u]);
    }

    if (issub(u, rt)) {
        int c = Up(rt, dep[rt] - dep[u] - 1);
        return (up[u] + dn[u] - dn[c] - siz[c] + dist(rt, u) * (n - siz[c]));
    }

    return (dn[u] + dist(rt, u) * siz[u]);
}

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[u].emplace_back(v);
        e[v].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][N], n;

// 首先给连通块排序, 重新分配每个点的搜索顺序, 确定每个点属于的连通块编号
struct Block {
    int siz, facs;
    vector<pii> node;
} blk[N * N];

int cnt_blk, id[N][N];
// 注意 blk 是要排序的, 后面没法直接查询 siz, 所以这里记录一下
int siz[N * N];

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[x][y]); }

void Explore(int x, int y) {
    id[x][y] = cnt_blk;
    blk[cnt_blk].siz++;
    blk[cnt_blk].node.emplace_back(x, y);

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (Check(nx, ny) && mp[x][y] == mp[nx][ny]) {
            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[i][j]) {
                cnt_blk++;
                blk[cnt_blk].facs = Factors(mp[i][j]);
                Explore(i, j);
                siz[cnt_blk] = blk[cnt_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[i].node) {
            q.emplace_back(x);
        }
    }

    m = q.size();
}

// 现在开始 dfs 填数, 记录答案编号方便回答字典序的要求
bitset<N> visx[N], visy[N];
int cnt[N * N], mul[N * N];
int ans[M][N][N], sum = 0;
set<int> st;

bool Check(int x, int y, int a) { return (!visx[x][a] && !visy[y][a] && !((mp[x][y] / mul[id[x][y]]) % 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[sum][i][j] = ans[sum - 1][i][j];
            }
        }
        return;
    }

    int x = q[pos].first, y = q[pos].second;
    int c = id[x][y];

    cnt[c]++;
    for (int i = 1; i <= n; i++) {
        // 能取吗?
        if (Check(x, y, i)) {
            mul[c] *= i;
            // 真能取吗?
            if (cnt[c] < siz[c] || (cnt[c] == siz[c] && mul[c] == mp[x][y])) {
                ans[sum][x][y] = i;
                visx[x][i] = 1, visy[y][i] = 1;

                dfs(pos + 1);

                visx[x][i] = 0, visy[y][i] = 0;
            }
            mul[c] /= i;
        }
    }
    cnt[c]--;
}

void Solve() {
    for (int i = 0; i <= n * n; i++) {
        mul[i] = 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[v][i][j]);
            }

            for (auto it = st.begin(); it != st.end();) {
                if (ans[*it][i][j] > 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[i][j];
        }
    }

    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[best][i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

FishC

鱼油你好，以下是你提到的四道题目的总结与思路解析:

### 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[i] = prefix_sum[i - 1] * 10 + (s[i - 1] - '0');
    }
    
    // 计算每个位置的贡献
    for (int i = 0; i < n; ++i) {
        long long place_value = 1;
        for (int j = i; j < n; ++j) {
            total_value += (s[j] - '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[u] + dep[v] - 2 * dep[lca(u, v)];
}

// 处理每次查询的主函数
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 小助理，如未能正确解答您的问题，请继续追问。

简柠啦

harryhan123

666

简柠啦

很cool的阳

磷酸

ooio

曾热爱这世界

👌

zsy0226

/orz/orz

trinityee

厉害了楼主

森林格格屋

谢谢

XiaoMengXin-1

谢谢鱼币