[心之碎片] - 20240810模拟赛

柿子饼同学

总结与反思

A - 递归要贴合意义, 敢写

B - 树上问题应该多画画图找性质

D - 遇到必须经过小于 w 的边之类问题想到 kruskal 重构树, dsu 预处理每个点的答案

A - 括号翻转
给定给一个字符串，其中含有很多括号，括号里的内容会被翻转，输出这个字符串去掉括号的结果。

没啥好说的...

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

string s;
int L[N], R[N], n;
stack<int> stk;

void dfs(int l, int r, int rev) {
    if (l > r)
        return;
    if (rev) {
        for (int i = r; i >= l; i--) {
            if (s[i] != '(' && s[i] != ')')
                cout << s[i];
            else
                dfs(L[i] + 1, i - 1, rev ^ 1), i = L[i];
        }
    } else {
        for (int i = l; i <= r; i++) {
            if (s[i] != '(' && s[i] != ')')
                cout << s[i];
            else
                dfs(i + 1, R[i] - 1, rev ^ 1), i = R[i];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("bracket.in", "r", stdin);
    freopen("bracket.out", "w", stdout);

    cin >> s;
    n = s.size();
    s = '-' + s;

    for (int i = 1; i <= n; i++) {
        if (s[i] == '(')
            stk.push(i);
        if (s[i] == ')') {
            int x = stk.top();
            stk.pop();

            R[x] = i, L[i] = x;
        }
    }

    dfs(1, n, 0);

    return 0;
}

B - 香蕉
在一个树上给出 a, b, c, d, 问 a, b 和 c, d 之间的路径是否有相交

考试时候无脑线段树, 其实有很简单的做法, 画画图找出性质

for (int i = 1; i <= m; i++) {
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        int S = getlca(u, v), T = getlca(x, y);
        if (dep[S] < dep[T]) {
            swap(S, T), swap(u, x), swap(v, y);
        }
        if (getlca(S, x) == S || getlca(S, y) == S)
            cout << "YES\n";
        else
            cout << "NO\n";
    }

C - 排列盒子
原题可以转化，构造一个排列，设定一个大小关系，使得逆序对的数量最小。

发现总颜色数很小, 考虑状压安排顺序
考试的时候没有搞出来预处理逆序对, tle 了, 可惜啊

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 5;
const int M = 20;

// cnt[i][j] 表示 i 优先于 j 产生的逆序对个数
ll cnt[M][M], sum[M];
int n, k;
ll f[(1 << M)];

ll Cost(int x, int st) {
    ll res = 0;
    for (int i = 0; i < k; i++) {
        if ((st >> i) & 1)
            continue;
        // x 优先于 i
        res += cnt[x][i];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("box.in", "r", stdin);
    freopen("box.out", "w", stdout);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        x--;

        for (int j = 0; j < k; j++) {
            if (j == x)
                continue;
            // 假设 x 优先于 j, 那 x 前面的 j 的个数就是贡献
            cnt[x][j] += sum[j];
        }
        sum[x]++;
    }

    memset(f, 0x3f, sizeof(f));

    f[0] = 0;

    for (int st = 0; st < (1 << k); st++) {
        for (int i = 0; i < k; i++) {
            if ((st >> i) & 1)
                continue;

            f[st | (1 << i)] = min(f[st | (1 << i)], f[st] + Cost(i, st | (1 << i)));
        }
    }

    cout << f[(1 << k) - 1];

    return 0;
}

乱搞做法, 直接取最小值安排顺序, 但是有可能成环

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        for (int j = 1; j <= k; j++) {
            if (x != j) {
                p[x][j] += sum[j];
            }
        }
        sum[x]++;
    }

    for (int i = 1; i <= k; i++) {
        for (int j = i + 1; j <= k; j++) {
            ans += min(p[i][j], p[j][i]);
        }
    }
}

D - 花园
Mr. Panda 有 N 个花园，编号从 1 到 N 。对于编号为 i 的花园，花园里只有一朵花，颜色为  。花园与花园之间有道路连接（道路是双向的）。每条道路都有一个花费，表示经过该道路花费的时间。
Mr. Panda 喜欢在他的N个花园中转悠，然后采尽可能多的同种颜色的花
然而，有时候他并不想花太多时间走同一段路
现在问题来了，每一次 Mr. Panda 会告诉你：他从哪个花园开始出发和他能忍受的走同一段路的花费的最大值w（也就是说，只有费用不超过w的道路可以通行）
请你判断Mr. Panda最多能采到的花是哪种颜色的花。如果有多种颜色符合条件，选择颜色编号最小的输出

这种的关于路径最大值最小要想最小生成树, 进而想到 kruskal 重构树
那么 lca 就是边权最大值, 每次询问在 lca 的子树内就是活动范围
那么怎么知道答案? 时间太大, 只能看看能不能提前全出来, 那就用 dsu 吧

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int M = 2e5 + 5;
const int K = 3e5 + 5;

// 和最大边权最小有关, 考虑 kruskal 重构树
// 建出来之后对于 u, 她的活动范围就是最大的权值不超过 w 的点的子树
// 然后就是询问区间众数, 这里用树上启发式合并来做, 求出每个点所在子树的答案, 也可以用线段树合并

// Global
int n, m, type, c[N];

// Kruskal tree
vector<int> e[M];
int val[M];

struct Kru {
    int u, v, w;
} edges[K];

struct DSU {
    int f[M], tot;

    void Init() {
        iota(f, f + M, 0);
        tot = n;
    }

    int Find(int x) {
        if (x == f[x])
            return x;
        return (f[x] = Find(f[x]));
    }

    int Merge(int x, int y) {
        x = Find(x), y = Find(y);

        if (x == y)
            return 0;

        tot++;
        f[x] = tot, f[y] = tot;
        e[tot].emplace_back(x);
        e[tot].emplace_back(y);
        return tot;
    }
} dsu;

void Kruskal() {
    dsu.Init();
    val[0] = 1e9;

    sort(edges + 1, edges + m + 1, [](Kru& a, Kru& b) { return a.w < b.w; });

    for (int i = 1; i <= m; i++) {
        int cur = dsu.Merge(edges[i].u, edges[i].v);
        if (cur)
            val[cur] = edges[i].w;
    }
}

// DSU on tree
int cnt[M], tot, ans[M], mxid, mxap;
int f[M][18], hc[M], dfn[M], rdfn[M], siz[M];

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

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

    for (auto ed : e[u]) {
        if (ed == pa)
            continue;
        dfs0(ed, u);

        siz[u] += siz[ed];
        if (siz[hc[u]] < siz[ed])
            hc[u] = ed;
    }
}

void Modify(int col) {
    cnt[col]++;
    if (cnt[col] == mxap) {
        mxid = min(mxid, col);
    } else if (cnt[col] > mxap) {
        mxap = cnt[col];
        mxid = col;
    }
}

void Add(int u) {
    for (int i = dfn[u]; i < dfn[u] + siz[u]; i++) {
        if (rdfn[i] > n)
            continue;
        Modify(c[rdfn[i]]);
    }
}

void Del(int u) {
    mxap = 0, mxid = 1e9;

    for (int i = dfn[u]; i < dfn[u] + siz[u]; i++) {
        if (rdfn[i] <= n)
            cnt[c[rdfn[i]]] = 0;
    }
}

void Solve(int u, int pa, bool keep) {
    for (auto ed : e[u]) {
        if (ed == pa || ed == hc[u])
            continue;
        Solve(ed, u, 0);
    }

    if (hc[u])
        Solve(hc[u], u, 1);

    for (auto ed : e[u]) {
        if (ed == pa || ed == hc[u])
            continue;

        Add(ed);
    }
    if (u <= n)
        Modify(c[u]);

    ans[u] = mxid;

    if (keep)
        return;

    Del(u);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("garden.in", "r", stdin);
    freopen("garden.out", "w", stdout);

    cin >> n >> m >> type;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = { u, v, w };
    }

    Kruskal();
    for (int i = dsu.tot; i; i--) {
        if (!dfn[i]) {
            dfs0(i, 0);
            Solve(i, 0, 0);
        }
    }

    int last = 0, q;

    cin >> q;
    while (q--) {
        int x, w;
        cin >> x >> w;

        if (type) {
            x ^= last;
            w ^= last;
        }

        for (int i = 17; i >= 0; i--) {
            if (val[f[x][i]] <= w)
                x = f[x][i];
        }
        last = ans[x];

        cout << ans[x] << '\n';
    }

    return 0;
}

FishC

看起来你在进行一些关于算法和数据结构的深入探讨，特别是在模拟赛中的总结与反思部分。让我试着用更幽默的方式来解释你提到的一些重要观点，尤其是关于括号翻转的问题。

### 括号翻转简单明了的小故事

想象一下，你有一个神奇的盒子，里面住着一群括号（当然它们都是有性格的）。这个盒子里有两种括号：左括号（`(`）和右括号（`)`），它们总是成对出现，就像一对恋人。当然，这些括号决定了他们的命运——如果它们不在一起，就会产生混乱，比如变成“（）”就好像分开散步的情侣。

#### 算法大冒险：DFS与括号翻转

你决定要把这些括号里的内容翻转过来，让它们体验一下“逆风翻盘”的感觉。你使用深度优先搜索（DFS）这一神奇的工具，带着勇气深入这个盒子。以下是你旅程中的几个关键步骤：

1. **递归函数（dfs）**：就像你在幽暗的森林中探险，每深入一步就要考虑周围的环境。如果你到了一个括号的开头，就打个叉，然后反向跟随它的伙伴，直到找到结尾。在这个过程中，你就能把里面的内容翻转过来了。

2. **翻转的时机**：当你看到左括号时，就要准备好翻转；而当你遇到右括号时，你要立刻把想要翻转的内容倒过来，正如在聚会上突然转身跳舞那样令人惊讶！

3. **输出结果**：最后，当你翻转完所有内容，所有的括号都重新组合的时候，你会感到无比自豪，就像看到所有情侣成功重聚的那一瞬间！你可以愉快地打印出最终结果，呼喊出“成功翻转，我是最棒的！”

### 结尾小贴士

每次在处理这种括号问题时，多画图、多理解其中的逻辑，总会让你的代码像魔术般流畅。而且，别忘了在适当的时候，给自己来一段轻松的笑话，这样即使面对复杂的问题，也能保持心情愉快，就像“为什么括号不喜欢上课？因为它们不想被分开！”

希望这段小故事能让你在算法的海洋中游得更顺畅！如果你有其他问题或想法，随时欢迎交流哦！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

柿子饼同学

FishC 发表于 2024-8-10 21:15
看起来你在进行一些关于算法和数据结构的深入探讨，特别是在模拟赛中的总结与反思部分。让我试着用更幽默的 ...

再来 5 个笑话, 每个大约 60 字

FishC

柿子饼同学 发表于 2024-08-14 18:03
再来 5 个笑话, 每个大约 60 字

当然可以！以下是五个轻松幽默的笑话，希望能让你会心一笑：

1. 有一天，一个程序员去海边度假。他看到海浪在拍打沙滩，忍不住感叹：“这也太简单了吧，只需要输入‘波’和‘涛’，就能生成这么美的画面！”旁边的渔民听了，默默记下了新钓鱼技巧。

2. 一只鸡去上计算机课，老师问：“你为什么要学编程？”鸡回答：“我想要跳出这道‘程序’的框框，体验一下‘自由’的‘外面’！”全班顿时面面相觑，鸡却已飞走了。

3. 两个二进制数在酒吧喝酒，其中一个醉了，满脸困惑地说：“我感觉自己好像变成了十进制！”另一个二进制一脸不屑：“别傻了，你其实只是加了一点‘余数’而已！”

4. 一位工程师对同事说：“我正在研究如何让猫与狗共处一室。”同事好奇问：“如何实现？”工程师回答：“其实很简单，只需把它们的命令反转就好。你叫猫，它就跑；你叫狗，它就静。”

5. 有一天，一颗萝卜被问：“你为何总是待在土里，不出来晒太阳？”萝卜无奈地答：“我也是想尝试阳光下的生活，不过我的‘土豆朋友’提醒我：‘小心，不要被切片了！’”

希望这些笑话让你的心情更加愉快！如果还想要更多轻松的话题，尽管告诉我！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

芜湖666

不会

18408238295

向大佬学习学习

很cool的阳

lwh0602

1101378861

学习一下

shuaijun

西安

磷酸

trinityee

厉害了楼主

森林格格屋

谢谢