当前位置: 首页 > news >正文

251005

cf1046 div3 and 2024 ICPC Hongkong

div3

E

因为每个数只能被操作一次,所有被操作之后必须要是目标值。于是对于一个数,如果它当前不和目标值符合,就要尝试异或一个后面一个数,而且后面一个数也只有两种情况:目标值和原来的值。

所以直接特判一下最后一个数然后遍历一遍就好了。鉴定为中杯。

    bool ok = true;if (a[n] != b[n]) {ok = false;}for (int i = 1; i < n && ok; ++i) {if ((a[i] ^ b[i + 1]) != b[i] && (a[i] ^ a[i + 1]) != b[i] && a[i] != b[i]) {ok = false;}}

F

实际上若有一条从 \((1, 1)\)\((x, y)\) 路径且路径上的值都为 0,则 \(a\) 的前 \(x\) 个数都相等且等于 \(b\) 的前 \(y\) 个数。具体是 0 或者是 1 就决定了需要操作多少次。

对两个序列分别维护出将前 \(i\) 个数修改成 1 / 0 的最小操作次数是容易的:

std::vector<std::array<int, 3>> work(const std::string &s) {std::vector f(n + 1, std::array<int, 3>{ 0, 0, 0 });for (int i = 1; i <= n; ++i) {int d = s[i] - '0';f[i][d] = f[i - 1][d];f[i][d ^ 1] = f[i - 1][d ^ 1] + 1;}return f;
}

假设对于 \(a\) 我们用以上函数算出了 \(p\),对于 \(b\) 我们用以上函数算出了 \(q\)。我们基于此考虑如何算价值,假设我们到 \((x, y)\) 是设为 0 更优,则必然满足:

\[p[x][0] + q[y][0] \leq p[x][1] + q[y][1] \]

移项可得:

\[p[x][0] - p[x][1] \leq q[y][1] - q[y][0] \]

于是我们对 \(p\) 每一项按照 \(p[x][0] - p[x][1]\) 升序排序,对 \(q\) 的每一项按照 \(q[y][1] - q[y][0]\) 升序排序,同时算一下 \(q\) 的前后缀。遍历 \(x\) 二分一下取 0 和取 1 的分界点就好了。

auto p = work(a);for (int i = 1; i <= n; ++i) {p[i][2] = p[i][0] - p[i][1];}auto q = work(b);for (int i = 1; i <= n; ++i) {q[i][2] = q[i][1] - q[i][0];}std::sort(p.begin() + 1, p.end(), cmp);std::sort(q.begin() + 1, q.end(), cmp);std::vector pre(n + 1, 0ll), suf(n + 2, 0ll);for (int i = 1; i <= n; ++i) {pre[i] = pre[i - 1] + q[i][1];}for (int i = n; i >= 1; --i) {suf[i] = suf[i + 1] + q[i][0];}i64 ans = 0;for (int i = 1; i <= n; ++i) {int idx = std::upper_bound(q.begin() + 1, q.end(), p[i], cmp) - q.begin();ans += 1ll * (idx - 1) * p[i][1] + pre[idx - 1] + 1ll * (n - idx + 1) * p[i][0] + suf[idx];}

鉴定为排序题

G

这题观察不难,主要是要时间复杂度正确的实现。

    // 预处理部分val[0] = 1;pre[0] = 1ll;for (int i = 1; i <= N; ++i) {val[i] = (i * pre[i - 1]) % Mod;pre[i] = (pre[i - 1] * val[i]) % Mod;}// 计算部分for (auto &ele : s) {num = ele;if (num <= 31 && ope(num) <= k) {k -= ope(num);(ans *= val[num]) %= Mod;}else {break;}}while (k > 0) {int MSB = std::__lg(k);k -= (1 << MSB);(ans *= num) %= Mod;(ans *= pre[MSB]) %= Mod;num = MSB + 1;}std::cout << ans << '\n';

ICPC Hongkong

做之前:什么叫去年香港2铜3题银5题金

做之后:太过困难

K

可以逆着考虑,即对于 \(t_i\) 可以在 R 右边添加任意字符,在 L 左边添加任意字符,看能否凑成 \(s\)

深入的去想会发现 \(t_i\) 中的组合 LR 必须放在一起,但实际上我们并不用特意去考虑这个问题,因为当你确定了 L 的位置后,你在这个位置后找的 R 的位置可能并不与之前 L 的位置相邻,但是我们一定可以把 L 的位置向后移知道和 R 相邻。大概就是当 s 是 LLLLLR \(t_i\) 是 LR 时,我们去找 L 的位置会找到第一个位置,我们去找 R 的位置会找到最后一个位置,此时虽然不相邻,但是一定可以将 L 移动到与 R 相邻的位置。所以只用考虑一点特殊情况:\(t_i\) 开头是 R 时,由于不能往左边添加任何字符,所以 \(s\) 的开头也必须时 R,结尾同理考虑。

L

看题解写出来的构造……

此题最重要的观察就是,对于任意一条题目中描述的路径,一定会经过所有的反对角线(即“ / ”这样的)一次且仅一次。如果考虑每条反对角线上与目标颜色相异(枚举目标颜色)的颜色数量,结合上面的观察就能得到这些数量必须有相同的奇偶性。

当所有的反对角线都具有相同的颜色,我们就一定可以构造出合法的路径组合。具体的,我们考虑依次满足所有主对角线(实现上我是从右向左依次满足每条主对角线的),对于每条主对角线(除了左下角那个),我们每次先走到下一条主对角线的最上面一个点,然后看右边的点是否是目标颜色,是就先下后右,否则先右后下将它变成目标颜色,直到不能再下了就一直往右走到终点。

bool find(std::vector<std::vector<bool>> g) {ans.clear();std::vector anti_cnt(n + m, 0);for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (g[i][j]) {anti_cnt[i + j] += 1;}}}for (int i = 1; i <= n + m - 2; ++i) {if ((anti_cnt[i] - anti_cnt[i - 1]) % 2 != 0) {return false;}}std::string path;int x, y;auto down = [&]() -> void {x += 1;g[x][y] = !g[x][y];path.push_back('D');};auto right = [&]() -> void {y += 1;g[x][y] = !g[x][y];path.push_back('R');};for (int k = 1 - m; k + 1 < n; ++k) {x = 0, y = 0;int tx = 0, ty = 0;path.clear();if (k < 0) {tx = 0, ty = -k - 1;}else {tx = k + 1, ty = 0;}g[0][0] = !g[0][0];for (int i = 0; i < tx; ++i) {down();}for (int i = 0; i < ty; ++i) {right();}while (x < n - 1 && y < m - 1) {if (g[x][y + 1]) {right();down();}else {down();right();}}while (x + 1 < n) {down();}while (y + 1 < m) {right();}ans.push_back(path);}if (g[0][0]) {path.clear();x = 0, y = 0;for (int i = 0; i < n - 1; ++i) {down();}for (int i = 0; i < m - 1; ++i) {right();}ans.push_back(path);}return true;
}

G

nmd 不会啊。

一开始考虑公式去了,想着能化成什么易于维护的东西,实际上只需要考虑 \(f(i, j)\) 的变化规律就好了。

此题关键的观察就是 \(f(i, j)\) 计算。

想到用字典树去实现新增的操作是容易的,但困难的是,如何用字典树上的信息来计算更新 \(f(i, j)\)。单独考虑字典树上每个节点对答案的贡献,对于一个字典树节点 \(x\),假设有 \(sz_x\) 个字符串经过了该节点,则该节点就能对 \(f(i, j)\) 贡献 \(\lfloor {sz_x \over j } \rfloor\) 的贡献。计算所有节点对 \(f(i, j)\) 的贡献就能得到其值。

我们再来考虑插入一个字符串后的更新。什么时候由\(\lfloor {sz_x \over j } \rfloor\) 变到 \(\lfloor {sz_x + 1 \over j } \rfloor\) 会让值增加 1 呢,即 \(j \mid sz_x + 1\) 时,于是我们找到所有的 \(sz_x + 1\) 的因数 \(k\) 然后让 \(f(i, k)\) 加一更新值并更新答案就好了。

void upd(int val) {for (auto &p : fac[val]) {ans ^= 1ll * p * f[p];f[p] += 1;ans ^= 1ll * p * f[p];}return;
}void insert(std::string s) {int cur = 0;for (auto &c : s) {int idx = c - 'a';if (trie[cur].to[idx] == 0) {trie[cur].to[idx] = ++tot;trie[tot] = Node();}cur = trie[cur].to[idx];trie[cur].siz += 1;upd(trie[cur].siz);}return;
}
http://www.hskmm.com/?act=detail&tid=25185

相关文章:

  • Java基础 Day26 - 详解
  • 14_mklink创建符号链接
  • 7_如何构建知识图谱
  • 点双连通分量例题:矿场搭建
  • MTK oppoR9m Smart Phone flash Tool 提示 ERROR: STATUS_UNSUPPORT_CTRL_CODE (0xC0010004)
  • 我开发的 Chrome 插件 SEO Tools Extension 今天上线了
  • Windows Server部署Vue3+Spring Boot项目 - 实践
  • 深入解析:阿里云无影云桌面深度测评
  • 2025.10.5模拟赛
  • C++/CLI
  • uboot 2020版本下gpio命令的使用
  • 盛世华诞 举国同庆|热烈庆祝 LEWISAK 英勇重创消火栓 1 周年!
  • 完整教程:<el-table>构建树形结构
  • 如何在markdown中插入折叠框
  • wqs二分
  • markdown语法详解
  • CF2115 VP 记录
  • 2-SAT模板
  • lab5
  • lab4
  • NumPy广播:12个技巧替代循环,让数组计算快40倍
  • 某中心2026年推出1111个技术实习岗位
  • 川土微变频器应用分享
  • POLIR-Society-Philosophy- Hegels 形而上学System Philosophy Dialectics 系统化哲学辩证法: 自由意志+封闭的绝对精神
  • 解决VLC 无法解码格式“h264” (H264 - MPEG-4 AVC (part 10))
  • CF2115 总结
  • luogu P8816 [CSP-J 2022] 上升点列 题解
  • CF558C Amr and Chemistry BFS解
  • Atbash密码和摩斯密码
  • Redis 中如何保证缓存与数据库的内容一致性?