99_wood's blog

NEUACM 2025 Winter Training 6 题解 D 和平委员会 & E Riddle 第一次接触 2-SAT 问题，感觉网上的很多博客讲的都不是很清楚，搞了半天没搞懂，好在最后搞懂了。 SAT 问题是指有若干个变元，和一个谓词，要求找出一个指派使得谓词为真，或者说明无解。 2-SAT 问题指的是把这个谓词写成合取范式后，每个大项中最多有两个变元情形。只有 2-SAT 可以

NEUACM 2025 Winter Training 5 题解 D 丝之割 题意 形式化题意：有 mmm 条弦，一条弦可以抽象为一个二元组 (u,v)(u,v)(u,v)，你可以进行任意次切割操作，一次切割操作你将选择两个下标 iii 和 jjj 满足 i,j∈[1,n]i,j \in [1,n]i,j∈[1,n]，然后所有满足 u>i,v<ju>i,v<ju>i,

NEUACM 2025 Winter Training 4 题解 D 运输计划 题意 一个 nnn 个点的树，每条边的边权，给出 mmm 条路径。要求只改变一条边的边权，使得所有路径中长度最大的路径的长度最小。 n,m≤3×105n, m \le 3 \times 10^5n,m≤3×105。 分析 “最大值最小”提示我们要二分答案。假设我们当前要求最大路径长度不能超过 ddd。那么所有长度大于

NEUACM 2025 Winter Training 3 题解 B「TAOI-3」终有一天，飞向水平线的彼方 题意 原题链接：https://oier.team/problems/X8C。 Mio 有一个长度为 nnn 的正整数数列 a1,…,ana_1, \ldots, a_na1​,…,an​。她会对这个序列进行若干次操作，每次她会选择一对正整数 l,rl,rl,r，满足 1≤l≤r≤n1

NEUACM 2025 Winter Training 2 题解 D 松鼠聚会 题意 二维平面上 nnn 个点。求其中一个点使得其他点到该点的切比雪夫距离之和最小。 0≤n≤1050 \le n \le 10^50≤n≤105。 分析 切比雪夫距离含有 max⁡\maxmax，难以维护。考虑通过坐标变换 [x′y′]=12[111−1][xy]\left[ \begin{matrix} x

NEUACM 2025 Winter Training 1 题解 F 炸弹 题意 在一条直线上有 nnn 个炸弹，每个炸弹的坐标是 xix_ixi​，爆炸半径是 rir_iri​，当一个炸弹爆炸时，如果另一个炸弹所在位置 xjx_jxj​ 满足： ∣xj−xi∣≤ri|x_j-x_i| \le r_i∣xj​−xi​∣≤ri​，那么，该炸弹也会被引爆。 现在，请你帮忙计算一下，先把第 iii 个炸

2024 下半年回忆录 前言 又到了半年一度的回忆录总结，2024 下半年对我真是不平凡的半年，但也有可能每个半年对我来说都不是平淡的。人生到处知何似，应似飞鸿踏雪泥。下半年借着打 XCPC 赛事的机会，去了很多之前没有去过的城市，在能力和眼界等方面都有不小提升。 虽说是 2024 年的回忆录，但当我真的开始码字，已经是大年初九，一方面是因为想要把一整个学期和寒假都包括在回忆录中，另一方面也是时间

2024 上半年回忆录 前言 又到了一年一度的总结时间。话说“回忆录”这一系列不过是源于去年一时兴起想把美好的时光记录下来所写的一点文字，没想到反响不错，从此便成为我的博客的固定栏目。 不过写回忆录也不光是为了读者的反馈和阅读量。若真以此为目的，怕不是博客都没必要写了😂。回忆录更多的是为了让我铭记过去半年的经历，总结过往，规划未来。 现在呢是 2024 年的 8 月 27 日。去年的 8 月 2

CCPC2022威海站 B题 Recruitment 题解 题目大意 原题链接 初始有一个由 nnn 个正整数组成的形如 a1+a2+⋯+ana_1 + a_2 + \cdots + a_na1​+a2​+⋯+an​ 的式子, n−1n - 1n−1 个操作每次将其中一个加号改为乘号. 现给出初始的式子和每次修改后的式子的值 sis_isi​, 求原来的 nnn 个正整数以及每次操作的符号的位置.

CF1970E3 Trails (Hard) 题解 题目 题目大意: 给定 mmm 个点. 每个点都和一个共同的中心点有若干条路径. 对于第 iii 个点, 有 sis_isi​ 条短路径, lil_ili​ 条长路径. 一个小人开始在 111 号点, 每天他要走两条路径到达一个点(可以和出发点相同), 要求每天走过的路径至少有一条长路径. 问走 nnn 天后, 所有合法路径的方案数. 1≤m≤1