[心之碎片] - 20240810模拟赛,综合交流区,技术交流,鱼C论坛

柿子饼同学 发表于 2024-8-10 21:05:32

[心之碎片] - 20240810模拟赛

总结与反思{:10_266:}{:10_277:}
A - 递归要贴合意义, 敢写
B - 树上问题应该多画画图找性质
D - 遇到必须经过小于 w 的边之类问题想到 kruskal 重构树, dsu 预处理每个点的答案

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

没啥好说的...
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

string s;
int L, R, 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 != '(' && s != ')')
            cout << s;
         else
            dfs(L + 1, i - 1, rev ^ 1), i = L;
   }
} else {
   for (int i = l; i <= r; i++) {
         if (s != '(' && s != ')')
            cout << s;
         else
            dfs(i + 1, R - 1, rev ^ 1), i = R;
   }
}
}

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 == '(')
         stk.push(i);
   if (s == ')') {
         int x = stk.top();
         stk.pop();

         R = i, L = 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 < dep) {
         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 产生的逆序对个数
ll cnt, sum;
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;
}
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 += sum;
   }
   sum++;
}

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

f = 0;

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

         f = min(f, f + 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 += sum;
         }
   }
   sum++;
}

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

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;

// Kruskal tree
vector<int> e;
int val;

struct Kru {
int u, v, w;
} edges;

struct DSU {
int f, tot;

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

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

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

   if (x == y)
         return 0;

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

void Kruskal() {
dsu.Init();
val = 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.u, edges.v);
   if (cur)
         val = edges.w;
}
}

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

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

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

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

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

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

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

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

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

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

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

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

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

ans = 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;
}
for (int i = 1; i <= m; i++) {
   int u, v, w;
   cin >> u >> v >> w;
   edges = { u, v, w };
}

Kruskal();
for (int i = dsu.tot; i; i--) {
   if (!dfn) {
         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] <= w)
            x = f;
   }
   last = ans;

   cout << ans << '\n';
}

return 0;
}

FishC 发表于 2024-8-10 21:15:52

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

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

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

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

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

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

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

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

### 结尾小贴士

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

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

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

柿子饼同学 发表于 2024-8-14 18:03:45

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

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

FishC 发表于 2024-8-14 18:23:38

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

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

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

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

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

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

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

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

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

芜湖666 发表于 2024-8-14 20:07:52

不会

18408238295 发表于 2024-8-16 08:30:06

向大佬学习学习{:10_254:}

很cool的阳 发表于 2024-8-18 09:59:27

{:7_115:}

lwh0602 发表于 2024-8-18 11:31:35

{:7_146:}

1101378861 发表于 2024-8-19 10:53:59

学习一下

shuaijun 发表于 2024-8-19 13:43:46

西安

磷酸发表于 2024-8-23 16:43:10

{:10_281:}

trinityee 发表于 2024-9-1 10:59:10

厉害了楼主{:10_254:}

森林格格屋 发表于 2024-9-4 17:37:59

谢谢

页: [1]

鱼C论坛's Archiver

[心之碎片] - 20240810模拟赛