p_b_p_b的博客

博客

Public Round #12 题解

2024-02-25 16:08:26 By p_b_p_b
  • 搬题人
    • 电塔:Wu_Ren
    • 并查集:p_b_p_b, Lynkcat
    • 划分序列:Crysfly
  • 组题人
    • p_b_p_b
  • 题解:部分题解可以见验题人题解

电塔

来源:

首先把 $x_i$ 从小到大排序,不妨假设 $x_i$ 相对大小关系不变,那么只需满足 $x^\prime_{i+1}-x^\prime_i\ge d$。

设 $y_i=x_i-id$,那么只需保证最终 $y_{i+1}\ge y_i$。同时,在这个过程中我们需要保证 $y_i\ge -id$。

由于我们需要保证 $y_i\ge y_1\ge -d$,所以我们先把比 $-d$ 小的 $y_i$ 先提升到 $-d$,然后就不需要考虑下界的限制了。

那么接下来就是有一个数组,每次给某个数加减一,使得最终单调不降,求最小操作数。

考虑设 $f_{i,j}$ 为 $y^\prime_i\le j$ 且前 $i$ 个数已经单调不降的最小花费,$g_{i,j}$ 为 $y^\prime_i=j$ 且前 $i$ 个数已经单调不降的最小花费,那么有 $g_{i,j}=f_{i-1,j}+|y_i-j|$,容易发现我们的 $j$ 只需要取在 $\{y_i\}$ 里出现过的即可,复杂度 $O(n^2)$。

然后发现假如 $(j,g_{i-1,j})$ 这些点是下凸的,$f\leftarrow g$ 相当于前缀最小值,所以 $(j,f_{i-1,j})$ 这些点也是下凸的,然后 $(j,|y_i-j|)$ 也是下凸的,所以 $(j,g_{i,j})$ 也是下凸的。

同时 $(j,f_{i,j})$ 是呈现分段线性函数的样式,具体的,存在 $0=a_0\le a_1\le a_2\le \dots\le a_i$,使得 $f(x)=f_{i,x}$ 在 $[a_j,a_{j+1}]$ 上斜率为 $j-i$,且 $\forall x\ge a_i,f(x)=f(a_i)$。我们尝试用堆维护 $a_1,a_2,\dots,a_i$ 以及 $w=f_{i,a_i}$。那么从 $f_{i-1}$ 转移到 $f_{i}$ 时,假如 $y_i \ge a_{i-1}$,那么直接令 $a_i=y_i$ 即可;假如 $y_i < a_{i-1}$,那么令 $w:=w+a_{i-1}-y_i$,并设置 $a_{i-1}:=y_i,a_i=y_i$ 即可。

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

并查集

来源:

考虑每条边对答案的贡献。合并 $A_i,B_i$ 时,如果令 $A_i$ 为 $B_i$ 的父亲,则这条边被走的次数是 $B_i$ 当前连通块向外连的边数。

因此只要确定了边的顺序,那么一定是让度数小的连通块成为度数大的连通块的父亲。

进一步可以发现,如果 $B_i$ 的连通块度数非零,那么把加边的顺序修改为先合并 $B_i$ 的连通块,再连接 $(A_i,B_i)$ ,再按照原顺序合并 $A_i$ 的连通块,一定不劣。

因此不难证明,最优加边顺序一定满足加入的边在任意时刻都是连通的。即存在一个根,每次加边是把儿子和父亲合并,且父亲此时一定已经与根连通。

感性理解一下,最优加边顺序里,儿子的度数应该不会比上面一整个连通块的度数要大。事实上,如若不然,把儿子选为根一定更优。

于是加入一个儿子就是给答案加上总度数,然后给总度数加上儿子的度数减一。

最后只需要把加入儿子的顺序定下来,满足父亲比儿子早加入。这是一个经典的贪心题,可以用并查集加优先队列实现。

复杂度 $O(n^2\log n)$ 。

划分序列

来源:

咕了,见验题人题解

Public Round #12 公告

2024-02-18 10:32:11 By p_b_p_b

省选即将来临,Public Round #12 将在 2024 年 2 月 25 日的早上 8:30 举行!比赛将进行 4.5 小时,共 3 道题,OI 赛制。

本次比赛的题目难度可能略低于省选,方便选手整理状态,提振信心。所有题目都有部分分。

本次模拟赛的搬题人为 Wu_Ren, Crysfly, p_b_p_b, Lynkcat ,组题人为 p_b_p_b ,验题人为 znstz, flower, yzc2005, Lynkcat 。

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

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

Public NOIP Round #6 题解

2023-10-15 13:04:18 By p_b_p_b
  • 搬题人
    • 倒腾:p_b_p_b
    • 探索:p_b_p_b
    • 抉择:feecle6418
    • 重生:p_b_p_b
    • 遍历:Crysfly
    • 排序:Wu_Ren
  • 组题人
    • p_b_p_b
  • 题解:部分题解可以见验题人题解

倒腾

来源:

直接模拟即可。

探索

来源:

深度优先搜索每一步是否有碰到障碍,并且不能与之前已经定下来的状态冲突,即可 $O(2^n)$ 搜出所有可能的路径。

抉择

来源:

算法一

设 $dp(i)$ 表示 $a[1\dots i]$,其中 $i$ 必须处于子序列中,的答案。转移为 $dp(i)=\max_{j\lt i}dp(j)+(a_j\&a_i)$,时间复杂度 $O(n^2)$,期望得分 $45$。

算法二

对于 $a_i\le 511$ 的数据,可以设 $f(i,j)$ 表示 $a[1\dots i]$,选择一个子序列,子序列最后一个数是 $j$ 的答案。转移为 $f(i,j)=f(i-1,j),f(i,a_i)=\max_{j}f(i-1,j)+(a_i\&j)$。期望得分 $20$。

算法三

如果 $a_i$ 随机,大部分 $a_i$ 肯定都要选。在算法一中强制 $j\ge i-500$ 就可以了。

算法四

考虑如何用类似算法三的思路(大部分时候多选都比少选优)优化算法一。

注意到如果 $i$ 之前选的最后一个数是 $a_x=y$,而存在 $x\lt j\lt i$ 满足 $a_{j}$ 和 $a_x$ 的最高位都是 $2^w$,但是最优解在 $i$ 之前没有选 $j$ 而是选了 $x$,则 $(a_x\&a_i)\ge (a_x\&a_j)\ge 2^w$,说明 $a_i$ 也有 $2^w$ 这一位。那 $(a_x,a_j,a_i)$ 一定比 $(a_x,a_i)$ 优,矛盾了(前者权值至少是 $2^w\times 2$,后者权值至多是 $a_x\lt 2^{w}\times 2$)。

所以可能转移到 $i$ 的 $x$ 只可能是每种最高位出现的最后一个位置。

时间复杂度 $O(n\log V)$。期望得分 $100$。

解法不唯一,本题还有很多形式类似的结论都是对的。

重生

来源:

在路上了!

遍历

来源:

在路上了!

排序

来源:

solution by Wu_Ren

考虑操作变成,把序列 $A$ 划分成 $D_1+D_2+\dots+D_m$,把 $A$ 变为 $rev(rev(D_1)+rev(D_2)+\dots+rev(D_n))$。

因为可以用两步进行一次相邻元素的交换,有一个 $n(n-1)$ 的做法。同时有很多简单的 $n-1$ 的做法。

还有一个分治排序的做法,归并两段有序的 $a_{1,\dots,p},b_{1,\dots,q}$ 时,找到这些数的中位数 $w$,进行一次 reverse 把比 $w$ 小的数放在左边,大的放在右边,显然两个部分还是分别能分成两个有序的段,可以分治并行,总操作数精细实现可以做到 $1+\sum\limits_{j=1} \lceil\log_2(\lceil\frac{n}{2^j}\rceil)\rceil$。当然,也有很多其他 $O(\log n)$ 归并的方法。

正解考虑排序 01 序列,那么把相邻的 0 和相邻的 1 合并,最后有 ...0101...,那么我们划分为 ...|01|0|10|1|01|0 或者 ...01|0|10|1|01,那么操作一次后,段数都会变为原来的 $1/3$ 上取整。

我们从高到低考虑每个位,假设我们对于高的位都排序完了,那对于这一位我们把高位相同的数看作一个序列,相当于对若干个序列进行上面的过程,可以并行,所以对于每个位我们的操作数都是 $\lceil\log_3n\rceil$。

精细实现的话总操作数为 $1+\sum\limits_{j=0} \lceil\log_3(\lceil\frac{n}{2^j}\rceil)\rceil$,在 $n=20000$ 时为 $78$,能过。

Public NOIP Round #6 公告

2023-10-14 23:12:13 By p_b_p_b

Public NOIP Round #6 将在 2023 年 10 月 15 日 8:30 举行!

比赛分为普及组和提高组,普及组进行 3.5 小时,提高组进行 4 小时。普及和提高分别有 4 道题,OI 赛制,组别之间可能存在题目重合。

本次比赛将与 MarsOJ 合作。pjudge 上仍然会有常规模式的比赛,而 MarsOJ 则可以提供仿真 csp / noip 考场环境的云电脑,具体可以加入用户群(915426363)。

选手可以根据训练需求自由选择在 pjudge 或 MarsOJ 参赛。两边都是免费的。

本次比赛的题目难度约为 CSP-J/S ,所有题目都有部分分。

本次模拟赛的组题人为 p_b_p_b ,搬题人为 Wu_Ren, p_b_p_b, feecle6418, Rainbow 。验题人 znstz, namespace_std, Lynkcat 。

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

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

Public Round #10, #11 公告

2023-07-15 10:03:53 By p_b_p_b

Public Judge 也来蹭 NOI 热度了!

为了帮大家备战 NOI ,Public Round #10, #11 将分别在 2023 年 7 月 18 日和 7 月 19 日的早上 8:00 举行!比赛将进行 5 小时,共 3 道题,OI 赛制。

本次比赛的题目难度分别为 NOI Day1 Day2,所有题目都有部分分。

本次模拟赛的搬题人为 Qingyu, Wu_Ren, feecle6418, p_b_p_b ,组题人为 p_b_p_b ,验题人为 znstz, TBD

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

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

p_b_p_b Avatar