Crysfly的博客

博客

Public CT* Round #2 Day 1 题解

2024-11-26 10:54:17 By Crysfly

赤橙黄绿

青与兰

考虑画一个十字形,把第 $1,3$ 象限和第 $2,4$ 象限分别匹配,红点是 $(0,0)$,如果蓝点和黄点的数量匹配就匹配成功。

如果确定了十字形的角度,那么两条分割线的位置是确定的(必须把点分成两半),因此可以 check 一个角度是不是可行的。

这样分点之后,第一象限点数 = 第三象限点数,第二象限点数 = 第四象限点数。

设差值 $c$ 为 第一象限蓝点数 - 第三象限黄点数。则 $-c$ 为 第二象限蓝点数 - 第四象限黄点数。

若 $c=0$ 则找到了能匹配成功的角度。

考虑角度从 $\alpha = 0$ 转到 $\alpha = \frac{\pi}{2}$,那差值会从 $c$ 变到 $-c$,并且在转动过程中每次只会 $\pm 1$,一定有一个角度差值为 $0$。

二分求这个角度即可。具体的,假设 $c_l > 0, c_r < 0$,我们求出 $c_{mid}$,不断取 $c_l \times c_r < 0$ 的区间。

算 $c_{\alpha}$ 需要排序,时间复杂度 $O(n\log n\log V)$。(也可以 nth_element,$O(n\log V)$)

黑与紫

鸽了,可以看 https://qoj.ac/blog/bulijiojiodibuliduo/blog/994

Public NOIP Round #8 题解

2024-11-26 10:25:45 By Crysfly
  • 组题人 & 搬题人:znstz, Crysfly

位集

来源:

最后 bitset 中为 $1$ 的点 $j$ 是在 $i \in [l,r]$ 中 $s_{i,j}$ 全为 $0$ / 全为 $1$ 的。

设 $len_{i,j}$ 表示从 $(i,j)$ 开始往右,相同的的最大长度。这个可以直接递推得出。

将每个 $i$ 的所有 $len_{i,j}$ 排序,查询时二分即可。

偷塔

来源:

$X_{max} - X_{min}$ 可以看作,选出 $k$ 个点后,在点集中任意选出一个点贡献 $+X$,再任意选一个点贡献 $-X$,得到的最大值。$Y_{max} - Y_{min}$ 也同理。

于是设 $f_{i,j,s}$ 表示前 $i$ 个点中,选了 $j$ 个点,$+X/-X/+Y/-Y$ 有哪些已经选择并产生贡献(状压为 $s$)。可以得到 $O(nk)$ 的做法。

进一步的,考虑贪心:若 $k\ge 5$,容易发现 $c$ 最大的点一定被选。如果不选 $c$ 最大的点,剩下 $5$ 个点中一定存在不对 $+X/-X/+Y/-Y$ 产生贡献的点,可以调整到 $c$ 更大。

这样就把问题降为了 $k\le 4$,DP 部分的复杂度降为 $O(n)$,只需要对 $c$ 排序。时间复杂度 $O(n\log n)$。

降雨

来源:

对于最终方案,积水的总体积为:

$$\sum_{k=1}^n\min\{\max_{1\le j\le k}h_j,\max_{k\le j\le n}h_k\}-h_k$$

注意到只与前缀、后缀最大值有关,因此可以 DP:

设 $f_{i,j,p,s,0/1}$ 表示前缀 $i$ 个格子中,选了 $j$ 个抹平,此时前缀最大高度为 $p$,后缀最大高度为 $s$,积水数量 $\bmod 2$ 为 $0/1$。

观察到 $p,s$ 都只有至多 $k+1$ 种取值,状态数为 $O(nk^3)$,转移为 $O(1)$。

考虑优化:注意到,最终最高的格子一定不会贡献任何积水,但是最高的格子可以当作边界来用。

假设枚举了最终最高的格子 $i$,那只需要前缀/后缀分别 DP,在这个位置合并即可。

那么状态降为 $f_{i,j,p,0/1}$(不需要记录后缀最大高度),时间复杂度 $O(nk^2)$。

矩阵

来源:

Public NOIP Round #8 公告

2024-11-20 23:09:42 By Crysfly

Public NOIP Round #8 将在 2024 年 11 月 23 日 - 2024 年 11 月 24 日 举行!

本次比赛只有提高组,进行 4.5 小时,有 4 道题,OI 赛制。题目难度约为 noip,所有题目都有部分分。

选手可以在以下时间窗口中自由选择 4.5 小时参加(UTC +8):

  • 2024-11-23 08:30:00 - 2024-11-23 13:00:00
  • 2024-11-23 10:00:00 - 2024-11-23 14:30:00
  • 2024-11-23 13:30:00 - 2024-11-23 18:00:00
  • 2024-11-23 19:00:00 - 2024-11-23 23:30:00
  • 2024-11-24 08:30:00 - 2024-11-24 13:00:00
  • 2024-11-24 10:00:00 - 2024-11-24 14:30:00
  • 2024-11-24 13:30:00 - 2024-11-24 18:00:00

本次比赛的组题人为 Crysfly, znstz,搬题人为 Crysfly, znstz,验题人为 gqh, qiuzx, pp_orange

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Public NOIP Round #7 题解

2024-10-21 23:23:46 By Crysfly
  • 组题人:znstz, Crysfly

填写数字

来源:

排列计数

来源:

黑白棋子

来源:

不妨假设 $w\ge b$。

记 $mx_i$ 为删去 $i$ 之后剩下的连通块的大小最大值,那么假如 $w>mx_i$,则 $i$ 任意时刻必须是白色。

考虑当有点必须是白色时,答案就是把这些必须是白色的点删去后,剩下的大小超过 $b$ 的连通块个数。

否则,答案是 $1$ 或 $2$,而且为 $1$ 当且仅当存在某个点 $u$,删去 $u$ 之后存在两个连通块大小超过 $w$ 且存在另一个连通块大小超过 $b$。

我们记 $m=\min\{mx_i\}$,显然这个式子在重心处取到最小,所以我们以重心为根(有两个的时候就以那条边为根)。

当 $w\le m$ 时,没有点必须是白色,割掉一个点后最大的连通块一定是父亲的那个,所以记 $se_i$ 为儿子子树中的次大值,那么当 $b\le \max\{se_i\}$,答案是 $1$,否则答案是 $2$。

当 $w>m$ 时,必须是白色点的那些点形成了一个包含根的连通块,那么我们知道删去白色的点之后剩下的连通块一定是某个子树,那么一个子树是剩下来的连通块的条件就是 $mx_{fa_i}< w\le mx_i$,然后会所有 $b\le \min(w,sz_i)$ 有 $1$ 的贡献。

复杂度 $O(n)$。

冒泡排序

来源:

考虑枚举一个值 $V$,将序列中 $\ge V$ 的值看作 $1$,$< V$ 的值看作 $0$,将序列变成 $01$ 的形式。

对于所有的 $V$,求出对 $01$ 序列做完后区间内 $1$ 的个数,把这些答案相加就是总和。

发现对于一段后缀,它的每个 $0$ 每轮会向前移一格。一段前缀,如果有 $1$ 的话,一定会有 $1$ 交换到交界处。

那么对于一个值 $V$,我们询问的后缀 $[p,r]$ 新增的 $1$ 的个数其实是 $[p,p+k-1]$ 中的 $0$ 数与 $[l,p-1]$ 中的 $1$ 数取 $\text{min}$。

把暴力写出来,发现 $\text{min}$ 两边的贡献都是简单的主席树查询,取 $\text{min}$ 的情况也是简单的主席树二分,直接维护就好了。

时间复杂度 $O(n \log n)$。

Public NOIP Round #7 公告

2024-10-16 22:43:25 By Crysfly

Public NOIP Round #7 将在 2024 年 10 月 19 日 8:30 - 2024 年 10 月 20 日 18:00 举行!

本次比赛只有提高组,进行 4 小时,有 4 道题,OI 赛制。题目难度约为 noip,所有题目都有部分分。

选手可以在以下时间窗口中自由选择 4 小时参加(UTC +8):

  • 2024-10-19 08:30:00 - 2024-10-19 12:30:00
  • 2024-10-19 10:00:00 - 2024-10-19 14:00:00
  • 2024-10-19 14:00:00 - 2024-10-19 18:00:00
  • 2024-10-19 19:00:00 - 2024-10-19 23:00:00
  • 2024-10-20 08:30:00 - 2024-10-20 12:30:00
  • 2024-10-20 10:00:00 - 2024-10-20 14:00:00
  • 2024-10-20 14:00:00 - 2024-10-20 18:00:00

如果已经报名的选手想要修改比赛时间,可以在此处取消报名。

本次比赛的组题人为 Crysfly, znstz,搬题人为 Crysfly, znstz,验题人为 gqh, qiuzx, pp_orange

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

Crysfly Avatar