Qingyu的博客

博客

Public NOIP Round #4 题解

2022-11-20 15:28:33 By Qingyu
  • 搬题人:
    • 咖啡, 画图:Qingyu
    • 治病, 拓扑序计数:feecle6418
    • 序列:Wu_Ren
    • 水果:p_b_p_b
  • 组题人:Qingyu
  • 题解:alpha1022, feecle6418, Wu_Ren, p_b_p_b

咖啡 (Div. 2 Only)

来源:

Tutorial by alpha1022.

不妨采用贪心策略:能喝则喝。

从左往右扫描,维护当前手中有几杯咖啡即可。

画图 (Div. 2 Only)

来源:

Tutorial by alpha1022.

采用深度优先搜索或广度优先搜索得出 $(x,y)$ 所在的连通块并染色即可,需要保证每个格子不被重复访问。

治病 (Div. 1 + Div. 2)

来源:

Tutorial by feecle6418.

首先我们要算出,如果不忽略任何医生,尼特花费的钱数。根据题意我们知道,对于某种药片,尼特吃这种药片的时间就是所有医生药方里的时间的并集,也就是给出一些区间让你求并。这是经典问题,按照左端点从小到大排序,维护当前最大的右端点即可。

如果忽略某个医生,只需要找到只被这一个医生覆盖的 (药片,时间) 二元组,把这些二元组的贡献减掉。对每种药片分开考虑,也就是对每个区间,求出只被这一个区间覆盖的位置的总长度。首先用差分求出每个位置被覆盖了多少次,找出只被覆盖一次的位置,把这些位置的权值赋值成 1,对权值做前缀和,然后求出每个区间内的位置的权值之和,就是只被这一个区间覆盖的位置的总长度。

所有差分、前缀和都需要在离散化之后的坐标上进行,瓶颈在于离散化,总时间复杂度为 $O((\sum K)\log (\sum K)+n+m)$。

拓扑序计数 (Div. 1 + Div. 2)

来源:

Tutorial by feecle6418.

设 $f(S)$ 表示按照拓扑序从前往后的顺序加点,初始为空集,到已经加入 $S$ 这个点集,这一段的加点方案数。设 $g(S)$ 表示按照拓扑序从后往前的顺序删点,初始为全集,到现在还剩下 $S$ 这个点集,此时删除顺序的方案数。$f,g$ 都可以在 $O(2^nn)$ 时间内简单地 dp 求出。

对于给定的 $u,v$,$u$ 在 $v$ 前,就是要,拓扑序加入 $v$ 那一刻,$u$ 已经在拓扑序里了。所以,$ans_{u,v}=\sum [u\in S,v\notin S]f(S)g(S\cup \{v\})$(枚举加入 $v$ 之前一刻,有哪些点加入了拓扑序)

直接实现该算法的时间复杂度为 $O(2^nn^2)$,但 $S$ 的枚举有 $1/4$ 的常数,已经可以过。

当然,上述算法还可以继续优化到 $O(2^nn)$:枚举 $S,v$,相当于 $\forall u\in S$,$ans_{u,v}$ 都加上一个定值。因此瓶颈在于:“给出 $a_{0}\sim a_{2^n-1}$,对所有 $u$ 求出 $\sum_{u\in S}a_S$”。可以用下面的方法:

for i from n-1 downto 0:
    for j from 2^i to (2^{i+1}-1):
        ans[i]+=a[j]
        a[j-2^i]+=a[j]

最后 $ans_u$ 就是答案。因此我们把 $O(2^nn)$ 的循环优化到了 $O(2^n)$。(但是实际上速度仅仅变快了不到一倍)

序列 (Div. 1 Only)

来源:

Tutorial by Wu_Ren.

由于答案有可二分性,直接获得 $O(nm\log n)$ 做法。

下面是正解:

考虑每次建出小根笛卡尔树,并且在笛卡尔树上 dp

我们对于每个节点,维护子树内 $a_i$ 最大值 $mx$,区间长度 $sz$,最长合法子段长度 $len$。

假设 $u$ 的两个儿子为 $lc,rc$,那么考虑合并 $lc,rc$ 的信息来得到 $u$ 的信息。

$mx,sz$ 的合并是显然的。考虑 $len$ 的合并,首先,假如合法子段不经过 $u$,那么就是 $len_u\leftarrow \max(len_{lc},len_{rc})$。假设存在 $u\in[l,r]$ 使得 $[l,r]$ 是合法子段,那么假设 $\max\limits_{i\in[l,u-1]} \{a_i\}\ge \max\limits_{i\in[u+1,r]} \{a_i\}$,此时我们可以发现,如果 $l>u-sz_{lc}\land r>u$,那么 $[l-1,r-1]$ 也是合法的。

那么就可以知道,我们可以认为跨越 $u$ 的合法子段要么一个端点是 $u$,要么一个端点是 $u-sz_{lc}$ 或 $u+sz_{rc}$。

这里可以发现,假如 $[l,u]$ 是合法子段且 $l>u-sz_{lc}$,那么 $[l-1,u-1]$ 也是合法子段,所以说一个端点是 $u$ 且另一个端点不是 $u-sz_{lc}$ 或 $u+sz_{rc}$ 的情况一定不优于 $\max(len_{lc},len_{rc})$。

那么我们只需要考虑一个端点在 $u-sz_{lc}$ 或 $u+sz_{rc}$,并且过 $u$ 的情况了(也就是说,我们只需要考虑至少把一颗子树完全包含的情况),这个转移是显然的。

复杂度 $O(nm)$。

水果 (Div. 1 Only)

来源:

Tutorial by p_b_p_b.

为了方便,先把 $a_i\ne -1$ 且无论如何都无法成为前缀最大值的水果删掉。

为了方便,再把水果的美味度修改一下,使得没有确定位置的水果的美味度是 $1,2,\cdots,m$ ,而确定位置的水果的美味度则是夹在中间的小数。

设 $a_1,\cdots,a_n$ 是读入的方案,$A_1,\cdots,A_n$ 是最终的方案。

放弃思考,直接设 $dp_{x,v}$ 表示确定了 $A_1,\cdots,A_x$ ,且其中最大值小于 $v+0.99$ ($v$ 是整数),考虑如何转移。

  • 如果 $a_x\ne -1$ ,那么有两种选择
    • 让 $a_x$ 成为最终的前缀最大值,那么从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移。
    • 扔掉 $a_x$ ,从 $dp_{x-1,v}$ 转移。
  • 如果 $a_x=-1$ ,再分两种
    • $a_1,\cdots,a_{x-1}$ 的最大值小于 $v$ ,那么这里肯定应该贪心放 $v$ ,从 $dp_{x-1,v-1}+c_v$ 转移。
    • 否则这里只能被迫开摆,随便放个以后不用的小的,从 $dp_{x-1,v}$ 转移。(注意因为我们做过预处理,所以这里总是可以保证不超过 $v$ 。)

于是就获得了一个非常垃圾 $O(n^2)$ 做法,下面考虑优化。

  • 对于 $a_x\ne -1$ ,注意到 $dp_{x,0},\cdots,dp_{x,m}$ 单调不降,因此一定是一个前缀从 $dp_{x-1,\lfloor a_x\rfloor}+c_{a_x}$ 转移,而其他地方直接把 $dp_{x-1,v}$ 拉过来。因此只要二分分界点就可以直接前缀赋值。
  • 对于 $a_x=-1$ ,显然只有一个合法状态会从 $dp_{x-1,v}$ 转移,剩下的都从 $dp_{x-1,v-1}+c_v$ 转移。不过这个怎么维护呢?

设 $S_i=\sum_{j=1}^i c_j$ 表示 $c$ 的前缀和。另外设 $pre_x$ 表示 $a_1,\cdots,a_x$ 有几个 $-1$ 。

对每个 $dp_{x,v}$ 维护一个二元组 $f_{x,v}=(x',y)$ ,表示 $dp_{x,v}=S_v-S_{v-(pre_x-x')}+y$ ,那么就做完了:从 $dp_{x-1,v-1}+c_v$ 转移,就等价于 $f_{x,v}=f_{x-1,v-1}$ 。而其他转移也都是简单的单点或区间赋值。

暴力线段树就能维护了。还可以再好看一点,用双端队列来维护二元组的连续段,但其实区别不大。

Public NOIP Round #4 公告

2022-11-13 02:21:21 By Qingyu

Public NOIP Round #4 将在 2022 年 11 月 20 日 8:30 举行!

比赛分为普及组和提高组,普及组进行 3.5 小时,提高组进行 4.5 小时。普及和提高分别有 4 道题,OI 赛制,其中普及组和提高组有两题相同。

与上一次比赛相同的是,本次比赛将与 MarsOJ 合作。pjudge 上仍然会有常规模式的比赛,而 MarsOJ 则可以提供仿真 csp/noip 考场环境的云电脑,具体可以加入用户群(915426363)。 选手可以根据自己的训练需要来自由选择在 pjudge 或 MarsOJ 参赛。两边都是免费的。

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

本次模拟赛的组题人为 Qingyu ,搬题人为 Qingyu, Wu_Ren, p_b_p_b, feecle6418。验题人待定。

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

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

Public NOIP Round #3 题解

2022-10-22 14:38:11 By Qingyu
  • 搬题人:
    • 数字:gyh20
    • 因子:Wu_Ren
    • 移除石子:feecle6418
    • 抓内鬼:p_b_p_b
    • 异或序列:feecle6418
    • 数圈圈:feecle6418
  • 组题人:hehezhou
  • 题解:gyh20, Wu_Ren, feecle6418, p_b_p_b

数字 (Div. 2 Only)

来源:AtCoder Beginner Contest 182 (https://atcoder.jp/contests/abc182/tasks/abc182_c)

Tutorial by gyh20.

做法 $1$:

直接搜索每一位是否删掉,时间复杂度可以做到 $2^{\log n}\log n$ 或者 $2^{\log n}$,这里的 $\log$ 是以 $10$ 为底的,可以通过。

Submission #56492 - Public Judge (pjudge.ac)

做法 $2$:

我们知道,一个数字能被 $3$ 整除,当且仅当其所有数位之和是 $3$ 的倍数,所以我们一定不会删数位是 $3$ 的倍数的这些位,同时也不会删三个 $\bmod 3$ 相同的位,同时也不会同时删 $\bmod 3=1$ 的和 $\bmod 3=2$ 的,这样我们就知道答案不超过 $2$。

于是求出所有数位上有多少个 $\bmod 3=1$,多少个 $\bmod 3=2$,分类讨论一下即可。

Submission #56801 - Public Judge (pjudge.ac)

因子 (Div. 2 Only)

来源:

  • Petrozavodsk Summer 2020. Day 5: JAG Summer+ Opening Contest. Problem B. Non-Trivial Common Divisor
  • ACM-ICPC Japan Alumni Group Summer Camp 2019. Problem B. Non-Trivial Common Divisor
  • https://qoj.ac/contest/505/problem/1336

Tutorial by Wu_Ren.

容易知道 $k$ 取某个质数最优,开个桶统计每个质数的答案即可,复杂度 $O(\sum \sqrt{a_i}+\omega (a_i))$。

移除石子 (Div. 1 + Div. 2)

来源:

Tutorial by feecle6418.

算法一

对于前三个测试点,可以从左往右删,第 $i$ 次输出 $(4i,4i,4i-2,4i-2)$。

对于第四、五个测试点,可以从下往上删,按照纵坐标顺序,第 $i$ 次删掉排在第 $2i-1$ 位、第 $2i$ 位的点即可。

结合起来期望得分 $50$。

算法二

大胆猜想一定有解。

算法一中的讨论指引我们从边上开始删。

将所有点按照横坐标从小到大排序,相同的按照纵坐标从小到大排序。不妨在该顺序中从后往前删。设在该顺序下,最后一个点为 $X$,倒数第二个点为 $Y$,倒数第三个点为 $Z$。

但是不一定合法,我们分类讨论几种情况:

  1. $X,Y$ 都是横坐标最大的点,这时靠右放个正方形,可以删掉 $X,Y$。

  2. 横坐标最大的点只有 $X$。

    1. $Y$ 的纵坐标小于或等于 $X$ 的纵坐标,则放一个以 $Y$ 为左下顶点的很大的正方形。

    2. $Y$ 的纵坐标大于 $X$ 的纵坐标。

      1. $Z$ 的横坐标等于 $Y$ 的横坐标,$Z$ 的纵坐标大于 $X$ 的纵坐标。

        这时以 $YZ$ 为一边放一个正方形就可以删掉 $Y,Z$:

      2. $Z$ 的横坐标等于 $Y$ 的横坐标,$Z$ 的纵坐标恰好等于 $X$ 的横坐标。

        这时以 $YZ,ZX$ 中短的一边作为正方形的一条边,比如下图中 $YZ\le ZX$,就这样画:

        注意,为了防止 $YZ=ZX$ 时把 $XYZ$ 三个点恰好都框住,需要把正方形偏移 0.5 个单位,这也是题目允许输出小数的原因。

      3. 不是以上两种情况,则以 $(x_Y,y_X)$ 为左下角作一个很大的正方形即可:

瓶颈在于排序,时间复杂度为 $O(n\log n)$,期望得分 $100$。

如果某些情况讨论漏了,可以得到 $90$ 分,因为数据随机时很难覆盖所有情况。

抓内鬼 (Div. 1 + Div. 2)

来源:

  • Noric Collegiate Programming Contest 2021. Problem C. Customs Control
  • Petrozavodsk Winter 2022. Day 4: Almost Northern Contest. Problem C. Customs Control
  • https://qoj.ac/contest/822/problem/1774

Tutorial by p_b_p_b.

算法一

$k=1$ 。

不难想到一个简单策略是只在点 $1$ 处放一个 uoj 壮丁,其他地方都放 pjudge 壮丁。这种策略只会在 $1$ 和 $n$ 有边时失败,但此时唯一的最短路就是从 $1$ 一步走到 $n$ ,因此只要 $n\ge 3$ 就可以在 $1,n$ 都放 pjudge 壮丁,就解决了。

算法二

$u_i\in \{1,n\}$ 或 $v_i\in \{1,n\}$ 。

同样先特判掉 $1,n$ 有边的情况,然后不难发现只要给 $1$ 和 $n$ 分配不同来源的壮丁,剩下的点随便分,就一定可以掐断所有路线。或者如果 $k=0$ 或 $k=n$ 也是显然有解的。

算法三

一般情况。

沿用算法二,先给 $1,n$ 分配不同来源的壮丁,不妨假设 $1$ 的壮丁是 P 而 $n$ 的壮丁是 U 。

可以发现,如果存在边 $(1,x)$ ,并且 $x$ 的壮丁也是 P ,那就相当于把 $x$ 从图里删掉了。这是因为从 $1$ 不能一步走到 $x$ ,而其他拐一个弯再到 $x$ 的走法不可能是最短路。存在边 $(y,n)$ 且 $y$ 的壮丁是 U 的情况同理。

因此只需要把 pjudge 壮丁贪心分配给 $1$ 旁边的点。那么要么是把 $1$ 旁边的点都删完了,要么是剩下的 uoj 壮丁可以把 $n$ 旁边的点删完。总之 $1$ 和 $n$ 肯定有一个是周围的点被删完了。

异或序列 (Div. 1 Only)

来源:

  • Petrozavodsk Winter 2021. Day 8: Belarusian SU Contest, Yandex Cup 2021. Problem C. Brave Seekers of Unicorns
  • XXI Open Cup named after E.V. Pankratiev, Grand Prix of Belarus. Problem C. Brave Seekers of Unicorns
  • https://qoj.ac/contest/536/problem/1085

Tutorial by feecle6418.

算法一

从小到大加入数来 dp。暴力一点,既然要求连续三个的异或和不为 $0$,就记录序列的最后两个位置 $x,y$ 分别是什么,加入 $z$ 的时候要求 $x,y,z$ 异或和不为 $0$。

时间复杂度 $O(n^3)$,期望得分 $40$ 分。

算法二

注意到性质:如果连续三个位置 $a_i,a_{i+1},a_{i+2}$ 违反了题目的限制,那 $(a_{i-1},a_i,a_{i+1})$ 就不可能违反限制了。

设 $f(n)$ 表示以 $n$ 结尾有多少个合法的序列。使用容斥:$f(n)=1+\sum _{i < n}f(i)-C$,$C$ 是在 $n$ 处第一次违反限制的序列数。$C$ 怎么算?如果一个序列 $[\dots,x,y,n]$ 在 $(x,y,n)$ 第一次违反限制,枚举 $y$,如果 $x=(y\operatorname{xor}n) < y$,$C$ 就应该加上 $f(x)$。

时间复杂度 $O(n^2)$,期望得分 $60$ 分。

算法三

对于 $\sum_{i < n}f(i)$ 这部分,可以用前缀和优化。

对于 $C=\sum_{y < n}[(y\operatorname{xor}n) < y]f(y\operatorname{xor}n)$,考虑满足条件的 $y$ 有何性质:实际上只要 $y$ 的二进制最高位和 $n$ 相同就有 $(y\operatorname{xor}n) < y$ 了。此时,枚举最高在哪一位 $y$ 和 $n$ 不同,则比这一位低的位可以任取,这样 $(y\operatorname{xor}n)$ 就属于一段特定的区间。因此我们把上述求和拆成了 $O(\log n)$ 段区间求和,同样可以前缀和。

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

数圈圈 (Div. 1 Only)

来源:

  • Petrozavodsk Winter 2021. Day 8: Belarusian SU Contest, Yandex Cup 2021. Problem F. Border Similarity Undertaking
  • XXI Open Cup named after E.V. Pankratiev, Grand Prix of Belarus. Problem F. Border Similarity Undertaking
  • https://qoj.ac/contest/536/problem/1088

Tutorial by feecle6418.

算法一

枚举每种情况,再暴力判断条件是否满足。

可通过子任务 $1$,期望得分 $5$。

算法二

预处理从 $x$ 开始往右、往下最长的一段连续相同字符,再暴力枚举,这时可以 $O(1)$ 判断了。

时间复杂度 $O(n^2m^2)$,可通过子任务 $1,2$,期望得分 $15$。

算法三

子任务 $3$ 中,只需要求有多少个矩形,这很容易 $O(1)$ 计算。

子任务 $4$ 中,注意圈的大小肯定不大,因此小范围内枚举即可。结合前述期望得分 $40$。

算法四

考虑对矩阵分治,每次选择长的一边割开,然后计算经过中线(中线长度等于短的一边长度)的“圈”数量。不妨假设是竖着切的。

在下图中,我们对每一对 $(u,v)$ 求出左边的 匚 和右边对称的形状数量,最终乘起来即可。因为两边是对称的,下面就只描述怎么求 匚 数量了。

设 $L_u$ 表示 $u$ 往左,相同字符至多能延伸到第几列;$D_{x,y}$ 表示 $(x,y)$ 往下,相同字符至多能延伸到第几行。则我们要求的是 $$ \sum_{i=\max(L_u,L_v)}^{mid} [D_{i,u}\ge v] $$ 若 $L_u\ge L_v$,就是求: $$ \sum_{i=L_u}^{mid} [D_{i,u}\ge v] $$ 因为 $L_u$ 是固定的,所以这里可以用一个桶存下所有的 $D_{i,u}$,做个后缀和就可以 $O(1)$ 求出了。

否则,我们发现 $[D_{i,u}\ge v]$ 等价于 $[U_{i,v}\le u]$($U$ 表示向上延伸最远能到第几行),所以做法是一样的。

时间复杂度 $O(nm\log nm)$,因为递归有 $\log nm$ 层,设短边长 $x$ 长边长 $y$,每层用 $x^2+xy\le 2xy$ 也即 $O(xy)$ 的时间处理了询问,加起来每层是 $O(nm)$。可以通过本题得到 $100$ 分。

当然,如果固定 $u$ 将 $\{D_{i,u}\}$ 看成一个序列,上面就是问序列的某个后缀里有几个数 $\ge x$,用树状数组容易优化到 $O(\log n)$ 单次询问。时间复杂度 $O(nm(\log nm)^2)$。也可以通过本题得到 $100$ 分。

Public NOIP Round #2 题解

2022-10-04 13:34:02 By Qingyu
  • 搬题人:
    • 就这:Y25t
    • 保序回归问题:Y25t
    • 恰钱:skip2004
    • 排序:Wu_Ren
    • 图同构:hehezhou
    • 找零:p_b_p_b
  • 组题人:p_b_p_b
  • 题解:p_b_p_b, Wu_Ren, Y25t, nantf

就这 (Div. 2 Only)

来源:

  • 2021-2022 ICPC Northern Eurasia - Belarus Regional Contest. Problem A. Constructiveforces
  • Кубок Трёх Четвертьфиналов 2021. Problem A. Constructiveforces

Tutorial by Y25t

其实只用保证每个长为 $m$ 的子串中恰好有 $k$ 个 1 就合法了,一种简单的构造是:

for(int i=0;i<n;i++) std::cout<<(i%m<k);

保序回归问题 (Div. 2 Only)

来源:

  • 2021-2022 ICPC Northern Eurasia - Belarus Regional Contest. Problem E. Positive Thinking
  • Кубок Трёх Четвертьфиналов 2021. Problem E. Positive Thinking

Tutorial by Y25t

当 $\prod y_i> 0$ 时,取 $x_i=y_i$,答案为 $0$。

当 $\prod y_i= 0$ 时,设 $\{y_i\}$ 中 $0$ 的个数为 $c$,那么至少要 $c$ 的代价才能使乘积非 $0$。而先把 $c-1$ 个 $0$ 变成 $1$,然后剩下那个 $0$ 根据情况变为 $1$ 或 $-1$ 即可取到这个下界。

当 $\prod y_i< 0$ 时,考虑 $\{y_i\}$ 中绝对值最小的位置,不妨设为 $j$。当 $y_j> 0$ 时将其变为 $-1$,否则将其变为 $1$,这样能使 $\prod y_i$ 反号,花费代价为 $|y_j|+1$,容易证明这是下界。

这些情况均可线性判断。

恰钱:(Div. 1 + Div. 2)

来源:

  • The 2022 ICPC Asia Regionals Online Contest (I)

Tutorial by p_b_p_b

如果你会数位 dp 那么可以直接往里套,显然是能做的。

否则,你也可以毛估估一下:

  • 当 $\text{ctz}(x)\le 5$ 时 $\text{ppc}(x)$ 也很小,这样只会有 $O((\log r)^4)$ 个合法的 $x$ 。
  • 否则这样的 $x$ 只有 $r/2^5$ 个,也不会太多,把合法的留下就更少了。

所以可以写个爆搜得到所有合法的 $x$ ,然后每次询问时二分。爆搜只需要 dfs+剪枝 即可。

最后,你也可以每次询问时枚举 $\text{ctz}(x)$ ,然后进行一些神秘贪心或调整,也可以通过此题。

排序:(Div. 1 + Div. 2)

来源:

  • Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest. Problem C. StalinSort Algorithm

链接:https://qoj.ac/problem/1456

tutorial by Wu_Ren

考虑 dp,设 $f_i$ 为当前子序列结尾为 $a_i$ 并且保证最终子序列包含 $a_i$ 的情况下,当前子序列长度的最大值。

那么考虑 $f_i+1$ 贡献到 $f_j$ 的条件,设 $nx_i$ 为 $\min\{j\mid j>i\land a_j>a_i\}$,那么就是 $j\in[nx_i,nx_{nx_i})\land a_j>a_i$。

为了干掉 $a_j>a_i$ 这个条件,我们可以按 $a_i$ 从小到大枚举 $i$ 进行转移,这样就可以忽略这个条件。具体的,按 $a_i$ 从小到大枚举 $i$,用 $f_i$ 更新答案,然后用 $f_i+1$ 更新在 $[nx_i,nx_{nx_i})$ 中的 $f_j$。

注意,假如 $a_0=0$,那么 $f_i$ 的初值是 $[i\in[nx_0,nx_{nx_0})]$。

用线段树辅助转移,复杂度 $O(n\log n)$。

图同构:(Div. 1 Only)

来源:

  • 2021“MINIEYE杯”中国大学生算法设计超级联赛(6). Problem 1007. Power Station of Art
  • Petrozavodsk Summer 2021. Day 6. Xi'an JTU Contest 1, Grand Prix of Xi'an. Problem G. Power Station of Art
  • XXII Open Cup named after E.V. Pankratiev, Grand Prix of Xi'an. Problem G. Power Station of Art

链接:https://qoj.ac/problem/1869

Tutorial by nantf

对相邻两个点 $u,v$ 操作时,相当于将两点同时反色,然后交换颜色。于是可以看成每个点的颜色跟着点权形成的二元组在移动,从起点到终点如果经过了偶数条边(经过多次算多次)则最终颜色不变,否则最终颜色需要反色。

每个连通块独立,以下分别考虑每个连通块,有两种情况。

1. 该连通块为二分图

则无论如何移动,只要确定了每个二元组的起点和终点,则颜色是否被反色只与起点与终点是否在二分图的同一部有关。

分别考虑每种点权,则要求 $A$ 图和 $B$ 图的 左部黑点+右部红点 数量相等、右部黑点+左部红点 数量相等。这是一个必要条件。构造说明这也是充分条件。

任取这个连通块的一棵生成树,任取一个叶子,不妨设其在 $B$ 图中为左部黑点或右部红点,则任取 $A$ 图中一个点权相同的左部黑点或右部红点(由和相等一定存在),将其一路交换过来,以后的过程就可以在两张图中都忽略这个叶子。最后所有点都可以归位。

2. 该连通块不为二分图

也即该连通块一定存在奇环。

此时在确定每个二元组的起点和终点后,颜色是否被反色还不好确定。

再注意到,所有二元组经过的边数之和为偶数。则要求两图黑点奇偶性相同,红点奇偶性相同,且对于每种点权,两图的总点数相等。这是一个必要条件。构造说明这也是充分条件。

首先若整个连通块就是一个奇环,可以用下述的方法使得点权不变的前提下,相邻两个点 $x,y$ 的颜色反转。

  • 将 $x$ 上的二元组沿反方向交换一圈到 $y$ 点,然后将原本 $y$ 上的二元组沿反方向交换一圈到 $x$ 点。

那么先任意交换至点权对应,由黑点红点奇偶性不变,容易用该操作使得颜色也对应。

然后对于任意一个连通块,固定一个奇环,任取这个连通块的一棵生成树(要求奇环上至多一条边不属于该生成树),任取一个不在奇环上的叶子。任取 $A$ 图中一个点权相同的点一路交换过来,若仅沿树边交换会导致颜色不对,则交换到该叶子后再一路交换到奇环,绕奇环交换一圈,再原路返回,颜色就是正确的。最后只会剩下这个奇环的点没有归位,用上一种情况的做法即可。

直接按上述过程判断即可,时间复杂度 $O(n+m)$。

找零:(Div. 1 Only)

来源:

  • 京都大学プログラミングProgrammingコンテストContest 2021. Problem F. One Yen Coin
  • Petrozavodsk Winter 2022. Day 1. Kyoto U Contest 2. Problem F. Flatland Currency.
  • XXII Open Cup named after E.V. Pankratiev, Grand Prix of Kyoto. Flatland Currency.

链接:https://qoj.ac/problem/2544

Tutorial by p_b_p_b

可以发现,虽然纸币有不同面额,但我们其实只关心面额为 $1$ 的纸币数。剩余的钱具体是用哪些纸币表示出来,对后续操作没有影响。

因此也不难发现每次只会购买一个物品,不会出现打包购买的情况。

所以一个价格为 $a_i$ 的物品的价值就是 $5\lceil a_i/5\rceil-a_i$ ,我们需要做一个背包问题。但是价格实在是太高了。

注意到价值很小,所以可以把价值放进状态里。设 $dp_{i,j}$ 表示考虑了前 $i$ 个物品,获得的价值为 $j$ ,所需的最小代价,这样就可以把复杂度优化到 $O(n^2)$ 。

然后有多种继续优化的方法:

  • 注意到如果价值相同,那么一定是按价格从小到大选。所以可以设 $dp_{i,j}$ 表示考虑了所有价值 $\le i$ 的物品,获得的价值为 $j$ ,所需的最小代价,然后利用决策单调性在 $O(n\log n)$ 的时间内从 $dp_i$ 转移到 $dp_{i+1}$ 。
  • 注意到价值的 $\text{lcm}$ 是 $12$ ,所以可以把每种价值的物品分别先打包成价值为 $12$ 的包裹,然后按照价格从小到大选包裹。这样的一个问题是最优解的价值并不一定是 $12$ 的倍数,但是可以枚举价值为 $1,2,3,4$ 的物品选的个数模 $12,6,4,3$ 的值,然后先把这些物品选掉之后再贪心即可。
  • 放弃分析,直接先按照性价比排序贪心选,然后在每种价值物品的边界附近进行小背包。大概和前一种是等价的。

Public Easy Round #3 题解

2022-09-22 16:44:28 By Qingyu
  • 搬题人:
    • DNA 匹配 2:Qingyu
    • 情报传递 3:Qingyu
    • 别急 2:Qingyu
    • 旅程:flower
    • 染色:Qingyu
    • 运算符 2:feecle6418
    • 匹配求和:Qingyu
  • 组题人:Qingyu
  • 验题人:feecle6418, flower, gyh20, test12345
    UOJ 缺投!

DNA 匹配 2(50 Points)

来源:

  • infO(1) Cup 2017 National Round. Problem 2, DNA

链接:https://qoj.ac/contest/998/problem/4713

算法 1

题目好难啊,不太会做,干脆输出随机数吧!

期望得分 $1 \sim 2$ 分。

算法 2

我们接着输出随机数,由于是 bitand,所以我们考虑随机的时候让每个数的 popcount 大一些,例如要求每个数 popcount 至少为 $14$。

期望得分 $10 \sim 30$ 分。

算法 3

考虑将 $2000$ 个数分成两组 $A, B$,每组包含 $1000$ 个数。将第一组的二进制表示下 $0 \sim 9$ 位钦定为 $1$,$10 \sim 19$ 位设为随机数。将第一组的二进制表示下 $0 \sim 9$ 位设为随机数,$10 \sim 19$ 位钦定为 $1$。并假设任意两个数两两不同。

此时,注意到任取一对 $x \in A, y\in B$,$x \operatorname{and} y$ 恰好包含了 $y$ 的前 $10$ 位与 $x$ 的后 $10$ 位,这至少包含了 $1000\times 1000 = 10^6$ 种不同的结果。

期望得分 $50$ 分(满分)。

情报传递 3(50 Points)

来源:

  • ByteDance-Moscow Workshops Camp 2022. Shuffle Contest. Problem M, Multiple Communications

链接:https://qoj.ac/contest/997/problem/4675

算法 1

题目好难啊,不太会做,那就干脆把所有数都发过去吧!

需要 $NL$ 个 bit,可以通过子任务 1,获得 $5$ 分。

算法 2

如果 $x, y$ 均均匀独立随机生成,那么其前 $\ell$ 位相等的概率为 $2^{-\ell}$。因此,对于子任务 $3$,在数据随机的情形下,我们可以给每个串直接截取前 $30$ 位发送过去,并在询问时只使用 $C$ 的前 $30$ 位。

需要使用 $30N$ 个 bit,可以通过子任务 1 与子任务 3,获得 $10$ 分。

算法 3

算法 2 存在的问题是,我们可以刻意钦定一些位,使得每个串在这些位上均相等。为了避免攻击,我们可以给每个位 $i$ 附上一个 $[0,2^{30})$ 内的随机权值 $w_i$。根据 Schwartz–Zippel lemma,发生碰撞的概率即为 $\Pr[P(r_1,r_2,\ldots,r_n)=0]\leq\frac{d}{|S|}$。

需要使用 $30N$ 个 bit,期望得分 $50$ 分(满分)。

别急 2(75 Points)

来源:

  • ByteDance-Moscow Workshops Camp 2022. Shuffle Contest. Problem B, Broken Connection

链接:https://qoj.ac/contest/997/problem/4664

观察

注意到我们发送过去后顺序会被随机打乱,因此我们可以认为我们只能传递每种数的数量。

问题可以转化为我们可以发送 $10$ 个非负整数变量 $x_0,x_1,\cdots, x_9$,且需要保证 $\sum_{i=0}^9 x_i \le L$。

算法 1

注意到我们要传递一个 $10$ 位 $10$ 进制数,我们不妨考虑用 $x_i$ 来表示第 $i+1$ 位的值。这样在最坏情况下需要使用长为 $100$ 的字符串,得分 $7.5$ 分。

在此基础上可以进行一些常数优化,例如给每一位随机一个排列 $p_{0\cdots 9}$,转而使用 $p_i$ 来表示,这样期望情况下每一位只会用到长为一半的字符串,可以获得更多的分数。

算法 2

注意到对于方程 $x_1+\cdots+x_n = m$,我们可以使用隔板法来计数其非负整数解的数量 $f(n,m) = \binom{m+n-1}{n-1}$。因此,我们可以快速的求出一个局面的字典序。注意到当 $L=50$ 时,$\binom{50+10-1}{10-1} = 12565671261 > 10^{10}$,因此我们直接使用解的字典序来编码 $X$ 即可。

期望得分 $75$ 分(满分)。

旅程(75 Points)

来源:

  • Natjecanje timova studenata informatičara hrvatskih sveučilišta 2012. Problem G. Restorani

链接:https://qoj.ac/contest/433/problem/4852

算法 1

可以把题意中 $u$ 对 $v$ 喜欢,建成 $u$ 到 $v$ 的有向边。那么 $u$ 推荐 $v$ 就等价于,可以从 $u$ 走到 $v$。

先缩点后,对于每个scc考虑决策。

  1. 不经过这个 scc,代价是 0。
  2. 经过 $k$ 个此 scc 的点,其中 $1$ 个点的代价 $y_u$,剩下 $k-1$ 个点的代价是 $x_u$。

因此考虑预处理 $f_{u,i}$ 表示在第 $u$ 个 scc 经过 $i$ 个点的最代价。

令 $g_{u,i}$ 表示从第 $u$ 个 scc 开始走,经过 $i$ 个点的最小代价,转移是枚举 $u$ 的出边,和 $u$ 里走过了多少点,时间复杂度 $O(n^3)$

染色(75 Points)

来源:

本题修改自 Hong Kong Olympiad in Informatics 2014 Senior Group(香港電腦奧林匹克 2014 高級組)中的 Dividing the Cities(城市分配)一题。

算法 1

题目好难啊,不太会做,直接把整个方案给发送过去吧。

每个颜色需要占用 $3$ 个 bit,共需 $3N$ 个 bit,期望得分 $2$ 分。

算法 2A

如果 Bob 自力更生,自己寻找染色方案,那么是非常困难的。但是对一张图 $2$ - 染色非常简单:我们只需要 DFS 一遍即可。

我们不妨将颜色两两配对,对于颜色 $c$ 我们发送颜色 $\left\lfloor c/2\right \rfloor$。此时,我们需要将每一种颜色 $c'$,区分为 $2c'$ 与 $2c'+1$。这相当于我们要将这种颜色的点进行 $2$ - 染色,我们只需要 DFS 整张图即可线性完成。

这样,每个颜色只需要占用 $2$ 个 bit,共需 $2N$ 个 bit,期望得分 $24.85$ 分。

算法 2B

我们考虑另一个角度。如果这张图中,某个点的度数小于 $8$,那么我们可以直接删去这个点:将其余部分的染色方案复原后,他至多只有 $7$ 个邻居,因此总有一种颜色它可以直接使用。

这样,我们可以不断地删去图中度数小于 $8$ 的点,直到所有点的度数都至少为 $8$。由于一条边至多对度数之和贡献 $2$,因此剩余的点数不可能超过 $M/4$ 个。

这样,我们只需要发送 $M/4$ 个点的信息,共需 $3M/4$ 个 bit,期望得分 $30.92$ 分。

算法 3

同时使用算法 2A 与算法 2B,共需 $M/2$ 个 bit,期望得分 $75$ 分(满分)。

运算符 2(125 Points)

来源:

  • Petrozavodsk Winter 2021. Day 8. Belarusian SU Contest, Yandex Cup. Problem A. Belarusian State University
  • XXI Open Cup named after E.V. Pankratiev, Grand Prix of Belarus. Problem A. Belarusian State University

链接:https://qoj.ac/contest/536/problem/1083

算法 1

可以发现,二元 01 运算一共只有以下几种:

  • 恒 0 / 恒 1。这时可以通过重新对下标赋值,将其转为 AND 运算。
  • $f(x,y)=x$ 或 $f(x,y)=y$,或 $f(x,y)$ 等于 $x$ 或 $y$ 取反。这时可以通过重新对无关一边的下标赋值 1,将其转为 AND 运算。
  • 等价于,或把 $x$ 取反后等价,或把 $y$ 取反后等价,或均取反后等价 AND/XOR。

进行适当操作后,直接在每位上分别运用通常的 AND/XOR 卷积的处理方式即可。可以证明,AND 与 XOR 运算在每一位上不会互相干扰。

时间复杂度 $O(2^nn)$。

匹配求和(200 Points)

来源:

  • Petrozavodsk Winter 2020. Day 9. Yuhao Du Contest 7. Problem F. Fast as Ryser
  • XX Open Cup named after E.V. Pankratiev, Grand Prix of Zhejiang. Problem F. Fast as Ryser

链接:https://qoj.ac/contest/449/problem/2068

算法 1

设 $E_0 = \{ (1, 2), (3, 4), \cdots \}$,则注意到对任意 $E' \subseteq E$,$E'$ 是匹配当且仅当 $E' \cup E_0$ 是若干环与链的并。

image-per-3.jpg

注意到由于 $2i-1$ 与 $2i$ 必须在同一个集合内,因此集合总数只有 $O(2^{n/2})$ 种。因此我们可以在 $O(2^{n/2} \cdot n^2)$ 的时间复杂度内计算出对所有 $S$ 将其划分成环/链的方案数。例如,对于链,我们可以记 $dp[mask][i]$ 表示已经经过的 block 的集合为 $mask$,现在位于点 $i$ 的贡献之和。对于环,我们可以直接枚举最大的点当作环的起点,由于 $\sum_{i\le n} 2^i = 2^{n+1}-1$,因此复杂度仍为 $O(2^{n/2} \cdot n^2)$。

划分完成后,我们可以使用 SOS DP(时间复杂度 $O(n \cdot 3^{n/2})$)或子集 exp(时间复杂度 $O(n^2 \cdot 2^{n/2})$)来计算最终将图划分成若干环/链的方案数。

总的时间复杂度为 $O(n \cdot 3^{n/2})$ 或 $O(n^2 \cdot 2^{n/2})$。由于常数上的差异,两种算法实际上均可通过。

UOJ 缺投!
Qingyu Avatar