Qingyu的博客

博客

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$ 的值,然后先把这些物品选掉之后再贪心即可。
  • 放弃分析,直接先按照性价比排序贪心选,然后在每种价值物品的边界附近进行小背包。大概和前一种是等价的。

评论

boat
@
  • 2023-09-17 21:58:06
  • Reply
songdashe
找零 这题是不是 $a_i \leq 10^9$啊?我看数据(每个数据的前面一些)还有原题都没有 $a_i$ 大于 $10^9$ 的
  • 2024-04-26 19:02:00
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。