版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: 题解 - 洛谷 10 月月赛 II & JROI R3 categories:

• 算法竞赛
• 题解 tags:
• 算法竞赛
• 题解
• 洛谷
• 洛谷月赛
• 交互题
• 数据结构
• 数学
• 树
• 容斥定理 date: 2021-10-04 18:26:00

比赛链接

• Div. 1
• Div. 2

题目概览

A - 『JROI-3』R.I.P

题目背景

Her Requeim

我想要肯定你的伦理 但是那是无法实现的

落幕 ......

"早上好, 早上了哟. "

声音 停滞

解去枷锁的双手 毫不犹豫地向前舒展

那片盛开的花 与放晴的此世都如此美丽 痛苦于此已再无痕迹

$$ \Large \text{R.I.P.} $$

$$ 1997.1.30\ -\ 2018.3.21 $$

$$ 1997.1.30\ -\ 2018.3.21 $$

{% mmedia "bilibili" "bvid:1fb411w7Qj" "quality:high" "danmaku" "allowfullscreen" %}

题目描述

你被曲师女性朋友的故事感动哭了, 于是你准备玩起 MC

你需要用栅栏框住一个长方形区域, 假设这个长方形区域大小为 $a \times b$ 个像素格, 则需要长为 $a+1$, 宽为 $b+1$ 规模的栅栏框住这个区域

现在你发现他的羊和牛需要恰好 $n$ 个像素格才够生存, 而你的背包里有 $m$ 个栅栏, 你想知道, 你用你所拥有的的栅栏是否能框出 $n$ 个像素格?

不需要用光所有栅栏, 只要框出区域大小为 $n$ 个像素格的长方形即可

注意, 上面的 $a,b,n,m$ 都应是整数

输入输出格式

输入格式

第一行一个整数 $T$, 表示测试组数

接下来 $T$ 行, 一行两个整数 $n,m$, 同题意

输出格式

一行一个字符串, 如果可行输出 Good, 如果不可行输出 Miss

输入输出样例

输入样例 #1

2
4 1
4 20

输出样例 #1

Miss
Good

说明

样例 1 解释

第一组数据: 实测可证, 无法用 $1$ 个栅栏围出 $4$ 个像素格

第二组数据: 可以考虑围出如下 $4=1 \times 4$ 的像素格

用下方的方式只需要用 $14$ 个栅栏即可

栅栏宽为 $1+1=2$, 长为 $4+1=5$, $(2+5) \times 2=14$. #### 数据规模与约定

本题采用捆绑测试

• Subtask 1 (30 pts) : $1\le n,m \le 10^4$, $T \leq 10^3$;
• Subtask 2 (70 pts) : $1\le n,m \le 10^{8}$, $T \leq 10^3$

在本题中栅栏是抽象化的而非具象化的, 即栅栏将会退化成一个点而非一个方格, 也就是我们可以通过求周长的方式求出一个栅栏框所需消耗的栅栏 (如果不理解可以看看样例 1 解释)

题意简述

对一个面积为 $n$ 的矩形, 求其最小周长+4

解题思路

由均值不等式可知从 $\sqrt n$ 向下找第一个能作为边的数即可

B - 『JROI-3』黑白棋

题目背景

赛时提醒: 如果您始终是 30pts, 且使用了题目给的快速读入, 请重新拷贝修改后的快速读入

赛时提醒: 本题如果解法正确, 快读可能无法起到优化作用

这个恐怕是将存在乃至于记忆切割成三十二颗的争夺黑白棋

双方剩下的棋子数字都很小——也就是重要性很高吧

            ......

——哥哥为什么会让自己落单呢?她原本对此感到疑惑

不过, 在得知答案之后, 那可以说是理所当然的做法

首先, 第一个理由极为单纯. 故意将记忆托付给对方, 暂时屈居败势的目的是——

「......那种事......白......做不到啊......」

想像了一下, 白露出悲伤的笑容, 做出这个结论

哥哥做的这些事, 如果由白执行......白不觉得自己的精神能够保持正常

自己仅仅因为哥哥从身旁消失, 就甚至一度怀疑哥哥的存在

——被忘掉的话还好. ——忘掉哥哥的话——白确信自己的精神会无法保持正常

            ......

(......这里......哥哥在......这里......)

即使是空无一物的空间, 但是白确信, 她感觉得到哥哥的位置

白顿时眼眶一热, 不过她强行忍住, 继续思考

(......然后这就是......第二个......同时也是......最大的......理由. )

白将写着【参】的棋子白色面朝上, 用手指夹住

哥哥是『白色还是黑色』, 这个问题也不需要犹豫

因为既然他将最后的棋局托付给『白』——那他当然是持白棋

这个现在看不见, 甚至无法认知的棋局

既没有开始的记忆, 也不知道盘面的经过如何. 不过哥哥故意下输, 并且为了让白能获胜所可能下的棋步......

而对方看到之后, 完全中了哥哥的计谋, 被诱导而下的棋步......

然后, 为了逆转, 哥哥可能选择的所有位置分布. 将这些全部推测分析——仅用三步棋反败为胜

            ......

然后——原先失去一天半的记忆——逆流了回来——

题目描述

白在和森精种玩黑白棋, 但黑白棋的规则有所改变

有 $n$ 个黑白棋子, 第 $i$ 个棋子编号为 $i$. 棋子初始全为黑, 游戏中, 仅由白一人操作, 白希望尽可能多的把棋子变成白色

白要求第 $k$ 个棋子和第 $k \times p$ 个不能同时变成白色

白共玩了 $T$ 次, 每次白想知道最多能把多少棋子变成白色. 每次游戏独立

为避免混淆, 加粗的白是人名

输入输出格式

输入格式

第一行一个正整数 $T$, 表示数据组数

下面 $T$ 行每行两个整数 $n,p$, 同题意

输出格式

共 $T$ 行, 每行一个正整数, 表示白最多能把多少枚棋子变为白色

输入输出样例

输入样例 #1

1
3 2

输出样例 #1

2

输入样例 #2

1
100 5

输出样例 #2

84

说明

样例 1 解释

可以选择第 $2,3$ 个棋子变色

数据规模与约定

本题采用捆绑测试

• Subtask 1 (5 pts) : $T \le 5$, $n \le 2$;
• Subtask 2 (5 pts) : $T \le 5$, $n \le 10$;
• Subtask 3 (20 pts) : $T \le 5$, $n \le 10^6$;
• Subtask 4 (70 pts) : 无特殊限制

对于 $100\%$ 的数据满足, $1 \le T \le 10^6$, $0 \le n \le 10^{18}$, $1 \le p \le 10^{9}$

{% icodeweb blog lang:cpp lgr-094/B1.cpp %}

题意简述

$$ S:={x\in 1..n\mid px\notin S} $$

求 $|S|$

解题思路

容斥一下易得答案为

$$ \sum_{i=0}^{\infin}(-1)^i\left\lfloor n\left(\frac{1}{p}\right)^i\right\rfloor $$

C - 『JROI-3』1÷0

题目背景

1÷0=梦恋

在距离遥远的山丘上, 看得见彼方宛如天地崩毁的光景
「——『设计体』传来报告——以功率《七二·八％》重现设计成功——开始同步. 」
  一机机凯种的女性体这么告知里克, 然后举起手
「【典开】——Org.0000——『真典·弑星者』——拜托您了. 」
  ——出现在虚空中的是, 外形有如小型的塔, 刺在地上的一把枪
方才目睹的, 有如让世界终结的暴力漩涡

题目描述

空想用跳棋模拟「圣战」中机凯种的移动方式

一条无限长的数轴上有 $n$ 个不能动的跳棋, 空会询问把一颗可以动的跳棋放在一个位置可以最多进行几次跳跃. 空会问很多次, 每次询问互相独立

设第 $i$ 颗不能动的棋子的坐标为 $x_i\left(\forall i\in\left[1,n\right]\right)$

则跳棋移动的规则如下:

• 这颗跳棋必须是允许移动的

• 若这颗棋子位于 $a$, 目标位置为 $b$, 则应仅有一颗棋子位于二个位置之间且中间棋子到 $a,b$ 的距离相等

  形式化的讲应有:

$$ \sum_{k=1}^n \left[x_k\in\left[b,a\right]\right]=1 $$

且 $\exists k\ x_k=\dfrac{a+b}{2}$

• 出题人过于良心 (, 你只能向左边跳

输入输出格式

输入格式

第一行两个整数 $n,q$, 同题意

接下来一行 $n$ 个整数, 第 $i$ 个表示 $x_i$

接下来一行 $q$ 个数 $x_0$, 表示放置可以动的棋子的位置

输出格式

$q$ 行, 每行一个整数, 第 $i$ 行表示第 $i$ 次询问的结果

输入输出样例

输入样例 #1

3 3
3 5 8
4 6 7

输出样例 #1

1
2
0

说明

样例解释 1

$$ \Huge\Box\Box\blacksquare{\color{red}{\Box}}\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}\blacksquare\Box\Box $$

从左到右的三个红色方块是询问的位置

• 对于第一个询问, 可以跳 $1$ 步, 从 4 跳到 2
• 对于第二个询问, 可以跳 $2$ 步, 从 6 跳到 4 跳到 2
• 对于第三个询问, 棋子不能向左移动, 因为左边同距离位置有一颗不能动的棋子

对于 $100\%$ 的数据满足 $1\le n\leq 3\times 10^6$, $1\le q\leq3\times 10^5$, $1\le x\le 10^{18}$, $xi+1\lt x{i+1}(\forall i \in [1,n-1])$

• 限制 $\text{A}$: $x_n\le2\times 10^5$
• 限制 $\text{B}$: 有不超过 $50$ 个 $i$ 不满足 $xi-x{i-1}\le 100$ , 其余 $i$ 满足 $\sum_{i}{xi-x{i-1}} \le 2\times 10^5$

题意简述

解题思路

复杂度

代码参考

D - 『JROI-3』删树

题目背景

你在 2021 年 7 月 10 日在洛谷打了一场比赛叫做 EZEC Round 10, 其中里面有一道造树题你觉得特别水, 随手就切了它. (所以没做过链接里题的人快来做啊!!!)

现在你在打 JROI-3 的月赛, 你觉得造树太水了想删掉树, 于是良心的出题人给了你一个机会. 但是, 在删除树之前, djy 想先知道树的边权和

题目描述

这是一道交互题

有一个 $n$ 个节点的带边权的树, 编号为 $1-n$. 每个点的度数是已知的. djy 想知道树上所有边的权值和, 但他太菜了, 不会去算如此简单的问题, 因此把这个题扔给了您

由于您很强, 所以您可以对这棵树进行一些改变: 删除所有度数为 $1$ 的节点, 得到剩下点的个数和每个点的度数

您可以向交互库进行三种类型的提问:

• 对于当前树上存在的一个点, 询问它的 dfs 序 $^1$
• 对于当前树上存在的一对节点, 询问它们之间的距离 $^2$
• 删除当前树上所有度数为 $1$ 的节点, 同时删除与这些节点相邻的边, 并且将所有未被删除的节点进行重新编号. 保证剩下的节点的编号分别为 $1-k$, 其中 $k$ 是剩下的节点个数

你需要操作不超过 142 次 (包括提交答案), 并在树删空之前求出当前树上所有边的权值和

注:

• dfs 序 $^1$: dfs 序指从当前的 $1$ 号节点进行 深度优先搜索 , 每个节点被第一次访问的顺序. 一棵树的 dfs 序不唯一. 每次删除操作后 dfs 序会被重置. 保证 dfs 序不随着其他操作而改变, 即两次询问同一节点的 dfs 序的询问中间如果没有删除操作, 保证回答相同的值
• 距离 $^2$: 指在树上两点路径上的边权和. 特别地, 两个相同节点的距离为 $0$

输入输出格式

输入格式

「交互模式」

本题采用 IO 交互模式

在开始交互前, 您需要先读入 $n$, 表示树中点的个数

接下来一行 $n$ 个数, 表示每个点的度数

您可以进行三种类型的询问:

• dfn u: 询问交互库编号为 $u$ 的节点的 dfs 序. 交互库返回一行一个整数, 表示 $u$ 的 dfs 序
• dis u v: 询问交互库编号为 $u$ 和 $v$ 的两个节点的距离. 交互库返回一行一个整数, 表示 $u$ 和 $v$ 的距离
• del: 要求交互库删除度数为 1 的点以及与之相连的边. 交互库将对点进行重编号, 并重新跑一个 dfs 序, 交互库返回第一行一个整数为树的大小 $m$, 第二行 $m$ 个整数, 第 $i$ 个表示编号为 $i$ 的点的度数

如果您求出了当前树上所有边的边权和, 按照 ! x 的格式输出答案 $x$, 并立刻结束程序

请保证作为询问参数的节点未被删除且 del 操作后树不为空

如果您的操作不合法或次数大于 142 次, 交互库会立刻终止程序, 并将结果判定为 WA/RE/TLE/MLE.

在每一次询问之后, 请不要忘记输出换行符以及清空缓存区, 否则将会出现未知的错误. 为了避免这种情况, 您可以使用:

• 对于 C++, 使用 fflush(stdout) 或 cout.flush()
• 对于 Java, 使用 System.out.flush()
• 对于 Python, 使用 stdout.flush()
• 对于其他语言, 请阅读相关文献

输出格式

见 「交互模式」

输入输出样例

输入样例 #1

6
3 1 2 1 1 2

1

5

输出样例 #1

dfn 1

dis 6 2

! 17

说明

样例仅供理解交互过程, 可能不符合逻辑

【样例解释】

树的形态如上

第一次询问节点 $1$ 的 dfs 序, 为 $1$

第二次询问节点 $2$ 与节点 $6$ 的距离, 为 $5$

当前树上所有边的边权和为 $17$

【数据范围】

「本题采用捆绑测试」

• Subtask 1 (1pts) : $n \le 2$
• Subtask 2 (4pts) : $n \le 4$
• Subtask 3 (20pts) : $n\le 150$
• Subtask 4 (10pts) : 树是一条链
• Subtask 5 (30pts) : 保证度数为 $1$ 的点不超过 $50$ 个
• Subtask 6 (20pts) : $n\le 2000$
• Subtask 7 (15pts) : 无特殊限制

对于 $100\%$ 的数据, $1\le n\le 5000$, 每条边的边权不大于 $10^5$ 且为正整数

解题思路

• 如果树是一条链, 那么直接查询两端距离输出即可
• 如果树的叶子结点很少 (具体来说就是叶子结点个数的 2 倍小于当前可执行操作数), 那么我们可以先把各叶子结点的编号按结点 DFS 序排序, 然后查询相邻两结点的距离, 那么答案便是这些距离和的一半
• 由于树的性质, 我们执行删除操作后, 叶子结点不会变多, 所以如果树的叶子结点很多, 则执行删除操作后回到上两步即可

代码参考

E - 『JROI-3』Moke 的游戏

题目描述

Moke 是一个喜欢玩游戏的男孩子

众所周知, 游戏应当有血量. 血量永远是非负整数, 如果在某个时刻血量将要变为负数, 那么游戏会崩溃, 这就不算作一种游戏局面. 这里允许血量是 $0$

一般来说, 友好的游戏都会具有一定的初始血量. 但是 Moke 是一个喜欢在游戏里受虐的男孩子. 所以他把自己的初始血量设成了 $0$

不过, 这个游戏的难度并不高

它一共进行 $n+1$ 个时刻. 初始是第 $0$ 个时刻, 最终是第 $n$ 个时刻. 每个时刻 Moke 会遇到以下三种事件, 然后进入下一时刻:

1. 空地. 它使得 Moke 的血量不变. 一共有 $a_0$ 种不同的空地
2. 怪兽. 它使得 Moke 的血量减一. 一共有 $a_{-1}$ 种不同的怪兽
3. 道具. 它使得 Moke 的血量增加一个正整数. 具体地, 一共有 $a_p$ 种使 Moke 血量加 $p$ 的道具, 其中 $p \in \mathbb Z^+$

为了不让游戏太复杂, 游戏的开发者保证 $\big|{p \mid p \in \mathbb Z^+ \land a_p > 0}\big|=k$. 即, 所有道具总共只造成恰好 $k$ 种不同的血量变化量

当然, Moke 还是给自己进一步增加了难度. 他要求结束时自己的血量为 $0$, 且给出一个正整数 $m$, 表示限制这 $n+1$ 个时刻中, 他恰好有 $m$ 次血量为 $0$ (包括初始时刻)

请求出所有不同的, 符合 Moke 限制的游戏局面个数. 两个局面不同当且仅当每个时刻遇到的事件的种类不同 (包括不同的空地、不同的怪兽和不同的道具)

Moke 不希望你面对太困难的问题. 所以他给出一个质数 $P=10^9+7$ 并只要求你给出取模 $P$ 后的答案

输入输出格式

输入格式

第一行, 三个正整数 $n,m,k$

第二行, 两个正整数 $a0,a{-1}$

以下 $k$ 行, 其中第 $i$ 行两个正整数 $pi,a{p_i}$. 表示存在道具造成的血量变化量为 $pi$, 且这样的道具有 $a{p_i}$ 种

输出格式

一行, 一个非负整数. 表示答案取模 $P$ 的结果

输入输出样例

输入样例 #1

5 3 1
1 1
1 1

输出样例 #1

6

输入样例 #2

5 3 1
1 2
3 4

输出样例 #2

64

说明

• 对于 $30\%$ 的数据, $n \le 15$, $k \le 1$
• 对于 $50\%$ 的数据, $n \le 100$
• 对于 $70\%$ 的数据, $n \le 2.5 \times 10^3$
• 对于 $100\%$ 的数据, $1 \le n \le 5 \times 10^6$, $1 \le m \le n + 1$, $1 \le k \le 10$, $1 \le p_i \le n$, $0 < a0,a{-1},a_{p_i} < P$, 保证 $p_i$ 从小到大给出且互不相同

题意简述

解题思路

复杂度

代码参考

F - [Ynoi2006] wcirq

题目描述

这是一道交互题

你需要进行 $n$ 个原始操作, 对一个序列进行维护. 初始序列为空

第 $i$ 个原始操作给出整数 $x_i,\;l_i,\;r_i$, 表示在序列的第 $x_i$ 个位置前插入元素 $i$ (若 $x_i=i$ 则表示在序列末尾插入) , 然后查询序列中第 $li,\;l{i+1},\;\dots,\;r_i$ 个元素构成的集合

为了回答这些查询, 你可以操作若干个集合. 这些集合初始为空, 编号为 $1$ 到 $2\times 10^7$ 的整数

你可以花费 $1$ 个单位的第一类代价进行插入操作: 在编号为 $x$ 的集合中插入元素 $y$, 在回答第 $i$ 个原始操作的查询前, 需要保证 $1\le y\le i$

你可以花费 $k$ 个单位的第二类代价回答查询: 选取编号为 $a_1,\;a_2,\;\dots,\;a_k$ 的集合, 要求这些集合互不相交, 且并集是查询的答案

每次原始操作后, 插入操作和回答查询的第一类/第二类代价不能超过当前子任务的代价上限 $m_1,\;m_2$. 每次原始操作的代价分别计算

输入输出格式

输入格式

你需要实现函数:

void solve(int x,int l,int r);

对于每次原始操作, 这个函数被调用一次, 参数 x l r 对应 $x_i,\;l_i,\;r_i$

输出格式

你可以调用函数:

void op1(int x,int y);
void op2(int k);

调用 op1 表示执行一次插入操作;

对 $a_1,\dots,a_k$ 依次调用 op2 表示回答查询

在提交的代码中, 你需要声明这两个函数

输入输出样例

输入样例 #1

假设交互库调用了 3 次 solve 函数如下:

solve(1,1,1);
solve(1,2,2);
solve(2,1,3);

输出样例 #1

以下给出了一种符合要求的对 op1 和 op2 的调用:

op1(1,1);
op2(1);

此时序列为 $(1)$, 编号 1 的集合为 ${1}$, 第 1 次 solve 函数调用返回;

op2(1);

此时序列为 $(2,1)$, 编号 1 的集合为 ${1}$, 第 2 次 solve 函数调用返回;

op1(1,2);
op1(2,3);
op2(2);
op2(1);

此时序列为 $(2,3,1)$, 编号 1 的集合为 ${1,2}$, 编号 2 的集合为 ${3}$, 第 3 次 solve 函数调用返回

说明

$1\le n\le 10^6$;

$1\le x_i\le i$;

$1\le l_i\le r_i\le i$;

你输出的插入操作或回答查询中, 集合编号在范围 $1$ 到 $2\times 10^7$ 内, 插入操作的 $y$ 必须是序列中已有的元素

子任务 1 (10 分) : 保证 $1\le n\le 10^3$;

子任务 2 (10 分) : 保证 $l_i=1,\;r_i=i$;

子任务 3 (10 分) : 保证 $x_i=i$;

子任务 4 (20 分) : 保证 $1\le n\le 10^4$;

子任务 5 (10 分) : 保证 $1\le n\le 10^5$;

子任务 6 (20 分) : 数据随机生成, 其中 $n=10^6$, $(l_i,r_i)$ 和 $x_i$ 分别在所有可能的情况中随机选取

子任务 7 (20 分) : 无特殊限制

对子任务 6, $(m_1,m_2)=(64,64)$;

对其余子任务, $(m_1,m_2)=(64,256)$

题意简述

解题思路

复杂度

代码参考