QOJ #8047. DFS Order 4 题解
Description 小青鱼（Little Cyan Fish），又名青羽小（Qingyu Xiao），非常喜欢 DFS 序的概念。今天，他手中有一棵有 nnn 个节点的有根树 TTT，节点编号从 111 到 nnn。这棵树的根是节点 111，而对于每个节点 iii（2≤i≤n2 \le i \le n2≤i≤n），其父节点为 fif_ifi，满足 1≤fi<i1 \le f_i &l
QOJ #5573. Holiday Regifting 题解
Description 有一个 nnn 个点的图，有 mmm 条有向边 u→vu \to vu→v，保证 u<vu<vu<v，每个点有一个 cic_ici。 一开始每个点有一个点权 aia_iai。每次操作可以给 111 号点的点权加上 111。如果一个点的 ai=cia_i = c_iai=ci，那么 ai←0a_i \gets 0ai←0，并且所有 iii 指向的
[AGC047F] Rooks 题解
Description 有 NNN 个车在一张无限大的棋盘上，第 iii 个在 (Xi,Yi)(X_i,Y_i)(Xi,Yi)。每行每列最多一个车。 有一个卒，会替换第 sss 个车，可以走八连通，但是不能走到被车攻击的地方。吃车的时候可以走对角，否则只能走上下左右。 对于 s=1…Ns=1\ldots Ns=1…N，求出吃掉最多的车时的最小步数。 2≤N≤2×105,1≤Xi,Yi≤106
[ARC196B] Torus Loop 题解
Description 问题陈述 有一个由 HHH 行和 WWW 列组成的网格。行的编号从上到下为 0,1,…,H−10,1,\ldots,H-10,1,…,H−1 ，列的编号从左到右为 0,1,…,W−10,1,\ldots,W-10,1,…,W−1 。让 (i,j)(i,j)(i,j) 表示位于第 iii 行和第 jjj 列的单元格。 给你 HHH 个字符串 S0,S1,…,Sn−1S_0
[ARC150E] Weathercock 题解
Description 有 n×kn\times kn×k 个人排成一行，从左往右按 0,1,…nk−10,1,\ldots nk−10,1,…nk−1 编号。每个人初始都面对着一个方向 L 或 R。给出一个字符串 s0…n−1s_{0\dots n-1}s0…n−1，则第 iii 个人的方向为 si mod ns_{i\bmod n}simodn。 接下来进行若干轮操作，每一轮所有人同时进
QOJ #964. Excluded Min 题解
Description 设 SSS 为一个包含非负整数的多重集。你可以对 SSS 进行任意次（可能为零次）以下操作：选择一个在 SSS 中至少出现两次的数 xxx，删除其中一个 xxx，但插入一个 (x−1)(x-1)(x−1) 或 (x+1)(x+1)(x+1) 代替（仅当 x−1x-1x−1 非负时才能插入 x−1x-1x−1）。定义 F(S)F(S)F(S) 为通过这些操作能达到的最大 m
P9528 [JOISC 2022] 蚂蚁与方糖 题解
Description JOI 君是一个生物学家。他准备对蚂蚁和方糖做一些实验。 JOI 君的实验在一个长度为 10910^9109 的木条上进行。这根木条被从左往右放置。木条上距离左端点 xxx 的点被称作坐标为 xxx 的点。 现在，木条上什么都没有。JOI 君将会进行 QQQ 次操作。第 iii 个操作 (1≤i≤Q)(1 \le i \le Q)(1≤i≤Q) 由三个整数 Ti,Xi,A
P9531 [JOISC 2022] 复兴计划 题解
Description 给定一个 nnn 个点 mmm 条边的连通图，带边权。 有 qqq 次询问，每次给定一个 xxx，并将所有边的边权 www 变为 ∣w−x∣|w-x|∣w−x∣，问新图的最小生成树大小。 询问之间独立。 n≤500,m≤105,q≤106n\leq 500,m\leq 10^5,q\leq 10^6n≤500,m≤105,q≤106。 Solution 首先对于一条边