鱼C论坛

 找回密码
 立即注册
查看: 487|回复: 12

[心之碎片] - 20240810模拟赛

[复制链接]
回帖奖励 3 鱼币 回复本帖可获得 3 鱼币奖励! 每人限 1 次
发表于 2024-8-10 21:05:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
总结与反思
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;
}

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-10 21:15:52 | 显示全部楼层
看起来你在进行一些关于算法和数据结构的深入探讨,特别是在模拟赛中的总结与反思部分。让我试着用更幽默的方式来解释你提到的一些重要观点,尤其是关于括号翻转的问题。

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

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

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

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

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

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

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

### 结尾小贴士

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

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

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

再来 5 个笑话, 每个大约 60 字
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-14 18:23:38 | 显示全部楼层
柿子饼同学 发表于 2024-08-14 18:03
再来 5 个笑话, 每个大约 60 字


当然可以!以下是五个轻松幽默的笑话,希望能让你会心一笑:

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

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

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

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

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

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

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-14 20:07:52 | 显示全部楼层

回帖奖励 +3 鱼币

不会
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-16 08:30:06 | 显示全部楼层

回帖奖励 +3 鱼币

向大佬学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-18 09:59:27 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-18 11:31:35 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-19 10:53:59 | 显示全部楼层

回帖奖励 +3 鱼币

学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-19 13:43:46 | 显示全部楼层

回帖奖励 +3 鱼币

西安
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-23 16:43:10 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-9-1 10:59:10 | 显示全部楼层

回帖奖励 +3 鱼币

厉害了楼主
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-9-4 17:37:59 | 显示全部楼层

回帖奖励 +3 鱼币

谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-5 04:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表