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

The 3rd UCUP Stage 29: Metropolis(QOJ contest 1913) 总结

附:出题组题解(繁中)。

A(不可做)

B

递归贪心地构造,若当前点有未走的相邻点,且没有 \(p_{i+1}\),那么当前点就要连 \(p_{i+1}\),递归 \(p_{i+1}\)。否则我们可以先回溯。

C

发现其中有一个人每次都只能选偶数。

  • \(l\) 为奇数时:
    • \(r<2l\) 则怎么选都不会影响另一个人,判断 \(r-l\) 的奇偶性即可。
    • 否则先手可以开始选 \(2l\) 必胜。
  • \(l\) 为偶数时:
    • \(r<2(l+1)\) 则怎么选都不会影响另一个人。
    • 否则后手可以开始选 \(2(l+1)\) 而获胜。

D

目标是把 \(a_{n-1}\)\(a_n\) 都变成 \(0\)。同时发现连续的一段 1111000 可以变成 1010101,这意味着可以把前面的 1 往后移。

需要细致地分类讨论。

  • \(a_{n-1}=1\)
    • 要使 \(a_{n-3}=1\)。也可以使 \(a_{n-4}=1\)\(a_{n-2}=1\)
  • \(a_{n-1}=0\)\(a_n=1\)
    • 要使 \(a_{n-4}=1\land a_{n-3}=1\)\(a_{n-4}=1\land a_{n-2}=1\)\(a_{n-3}=1\land a_{n-2}=1\)

把前面的 1 往后移时,要限制移到的位置,然后才能 check 以上条件。移的时候要一位一位移。

E(未过)

在点双上考虑合法的图长什么样。

F(未过)

分治 FFT。

G

二分答案。每条直线可以贡献一个前缀或后缀,贪心地选即可。

H

\(n=2,3,4\) 的玩出来,然后每次消掉最后三行归约成 \(n-3\) 的问题,具体构造看题解。

I

每次合并相当于连 \(k-1\) 条边,那么 \(p\) 从后一定是 \(p(k-1)+1\) 个点的乘积。找到最大的 \(p\) 使得乘积非 \(0\) 即可。注意 \(p=0\) 要对 \(a_1\) 取模。

J

首先建树,可以扫描线后用线段树加底层 set 维护。

然后每次修改,考虑与两个 DFS 序相邻的关键点 LCA 的最深哪个,那么 \(x\) 到这个 LCA 上所有点贡献都会改变。用 BIT 维护 \(s_i\) 表示深度为 \(i\) 的合法点数,每次修改都是区间加。

K

对于每个左部点,保留最大 \(K\) 条边,然后再在此基础上每个右部点保留最多 \(K\) 条边。这是因为如果匹配了被一条扔掉的边 \((u,v)\),那么 \(u\) 还有权值更优的至少 \(K\) 条边,此时一定能替换使得更优。

然后在这 \(O(nK)\) 条边保留最大的 \((2k-1)(k-1)+1\) 条边即可,这是因为每匹配一条边,就会阻挡 \(2k-1\) 条边,\(k-1\) 轮都是如此,最后一轮还需一条边。

对这 \(O(K^2)\) 条边用 SPFA 跑费用流,复杂度 \(O(K^4)\)

L(未过)

DP 题。

M(未过)

\(Z\) 最大和 \(Z=0\) 的点一定在圆内,记组成集合 \(S\)。而其他点就没有区分了,它们都在圆上,记组成集合 \(P\)

  • \(|P|=0\),找一个无限大的圆即可。
  • \(|P|=1\),要求存在一条直线,使得 \(S\) 中所有点都在直线的一侧。
  • \(|P|\ge3\),圆是确定的。
  • \(|P|=2\),假设 \(P=\{X,Y\}\),线段 \(XY\) 一定是一条弦,找到弦两侧分别使得圆周角最小的 \(S\) 中的点,此时圆会最大,对这两个圆分别 check 即可。
http://www.hskmm.com/?act=detail&tid=18628

相关文章:

  • 空白金兰契的多维解构与实践路径:从价值表征困境到人机共生伦理
  • 2025中国制造企业500强榜单发布
  • 读 WPF 源代码 了解获取 GlyphTypeface 的 CharacterToGlyphMap 的数量耗时原因
  • 张江,首个万亿市值巨头诞生!
  • Java 与智慧交通:车联网与自动驾驶支持
  • 9月26号
  • 初衷的澄明:空白金兰契的深意
  • Aidoku - 专为iOS/iPadOS打造的免费开源漫画阅读器
  • windos的hyper-v安装的宝塔面板,在面板里面点击重启服务器后再也无法启动面板。
  • Obsidia Git同步方法(偏安卓)
  • 什么是 FullGC
  • Unity渲染时的排序规则
  • AI智慧的三重跃升:从「数理魔兽」到「悬荡悟空」的文明协作者
  • 新学期每日总结(第 5天)
  • codeforces round 1054(e.f)
  • 【SimpleFOC-小项目】驱动电机正转3周
  • 联合体union的基本用法
  • 弱结构光三维扫描重建
  • 9.27 git与pycharm
  • PCA降维
  • docker复制文件到宿主机
  • 【SimpleFOC】SimpleFOC的运动规划器(Motion Planner)和梯形速度规划
  • Day22多态详解
  • rad/s RPM之间的换算
  • 再见Playwright!谷歌官方Chrome DevTools MCP正式发布,AI编程效率再翻倍
  • Markdown 之——清单の语法
  • “计算理论之美”课程笔记一:概率
  • “计算理论之美”课程笔记四:高维空间组合优化
  • git分支从dev迁移到maser
  • Centos7安装ffmpeg