交互和提交答案¶
交互和提交答案是信息学竞赛中的少数特殊题型。
[NOI2019] I 君的探险¶
题目背景¶
附加文件可在页面底部「附件」中下载。
特别提示¶
在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：
-
与原题不同的是，你不需要，也不应该在程序开头包含
explore.h头文件。 -
为了确保程序正常编译，你需要在你提交的程序开头加上如下函数声明语句：
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);
- 本题仅支持 C++ 语言（包括
C++，C++11，C++14，C++17）提交。
题目描述¶
时隔半年，I 君的商店终于开不下去了，他决定转让商店，做一名探险家去探索未知的广阔世界。
根据古书记载，他在一个大荒漠的腹地找到了未知文明创造的地下宫殿，宫殿由 \(N\) 个大型洞穴和 \(M\) 条连接这些洞穴的双向通路构成。I 君能借助古书分辨所处的洞穴，但书中并没有记录 \(M\) 条通路的连接结构，因此他难以搜寻传说中藏在宫殿里的无尽财宝。
不过现在 I 君发现了一个神秘机关，通过它可以获知宫殿的信息，I 君决定利用这个机关来得到宫殿的连接结构，请你来协助他。
地下宫殿可以抽象成一张 \(N\) 个点、\(M\) 条边的无向简单图（简单图满足任意两点之间至多存在一条直接相连的边），洞穴从 \(0 \sim n - 1\) 编号。目前你并不知道边有哪些。
每个洞穴都拥有一个光源，光源有开启、关闭两种状态，只有当光源处于开启状态时它所在的洞穴才会被照亮。初始时所有的光源都处于关闭状态，而光源的状态只能用I 君发现的神秘机关改变。更具体的，使用神秘机关可以进行如下四种操作：
-
向机关给定一个编号 \(x\)，机关将会改变\(x\) 号洞穴，以及与\(x\) 号洞穴有通路直接相连的洞穴的光源状态。即原来开启的光源将会关闭；原来关闭的光源将会开启。
-
向机关给定一个编号 \(x\)，机关将会显示当前\(x\) 号洞穴光源的状态。
-
向机关给定两个编号 \(x, y\)，表示你确定有一条连接 \(x\) 号洞穴与 \(y\) 号洞穴的通路，并让机关记录。
-
向机关给定一个编号 \(x\)，机关将会判断与 \(x\) 号洞穴相连的通路是否都已被记录。
机关在完成上一次操作后才能进行下一次操作。机关不能随意使用，因此每种操作的使用次数都有限制，分别为 \(L_m, L_q, M, L_c\)。你的任务是，编写一个程序，帮助 I 君决定如何合理利用神秘机关，从而正确地找到这 \(M\) 条通路。
实现细节¶
你不需要，也不应该实现主函数，你只需要实现函数 explore(N, M)，这里的 \(N\)和 \(M\) 分别表示洞穴和通路的个数。你可以通过调用如下四个函数来和交互库进行交互：
-
modify(x) -
这个函数可以令机关执行操作 \(1\)，给定的编号为 \(x\)。
-
你需要保证 \(0 \leq x < N\)，这个函数没有返回值。
-
query(x) -
这个函数可以令机关执行操作 \(2\)，给定的编号为 \(x\)。
-
你需要保证 \(0 \leq x < N\)，这个函数返回 \(0\) 或 \(1\)，表示目前 \(x\) 号洞穴的光源为关闭（\(0\) 表示）或开启（\(1\) 表示）状态。
-
report(x, y) -
这个函数可以令机关执行操作 \(3\)，给定的编号为 \(x, y\)。
-
你需要保证 \(0 \leq x, y < N\) 且 \(x \neq y\)，这个函数没有返回值。
-
check(x) -
这个函数可以令机关执行操作 \(4\)，给定的编号为 \(x\)。
-
你需要保证 \(0 \leq x < N\)，这个函数返回 \(0\) 或 \(1\)，其中返回 \(1\) 当且仅当与 \(x\) 号洞穴相连的所有通路都已通过操作 3 被记录。
评测时，交互库会恰好调用 explore 一次。
本题保证所使用的图在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。
数据保证在调用次数限制下，交互库运行所需的时间不超过1s；交互库使用的内存大小固定，且不超过128MB。
实现方法¶
选手工作目录下已经提供了一个 template_explore.cpp/c/pas，请将这个文件拷贝一份，重命名为 explore.cpp/c/pas，然后在其基础上答题。
-
对 C++ / C 语言选手
-
请确保你的程序开头有
#include "explore.h"。
- 你需要实现的函数
explore的接口信息如下：
void explore(int N, int M);
- 你可以调用的交互函数的接口如下：
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);
-
对 Pascal 语言选手
-
注意：Pascal 的代码中实现接口的语法较为复杂，请选手直接在下发的.
template_explore.pas的基础上进行答题，而不是自己从头实现代码。 -
你需要实现的函数
explore的接口信息如下：
procedure _explore(N, M : longint);
-
注意：这里的函数名称是
_explore而非explore，如果使用explore将导致编译失败。 -
你可以调用的交互函数的接口如下：
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;
试题目录下的 grader.cpp/c 以及 graderhelperlib.pas 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。
-
对
C/C++语言的选手： -
你需要在本题目录下使用如下命令编译得到可执行程序：
-
对于 C 语言：
gcc grader.c explore.c -o explore -O2 -lm
- 对于 C++ 语言：
g++ grader.cpp explore.cpp -o explore -O2 -lm
-
对于
Pascal语言的选手： -
你需要在本题目录下使用如下命令编译得到可执行程序：
fpc grader.pas -o"explore" -O2
-
对于编译得到的可执行程序：
-
可执行文件将从标准输入读入以下格式的数据：
第一行包含三个整数 \(L_m, L_q, L_c\) ，第二行包含两个整数 \(N, M\)，意义如题面描述。
接下来 \(M\) 行，每行两个整数 \(x, y\)，描述一条连接 \(x\) 号洞穴与 \(y\) 号洞穴的通路。
- 读入完成之后，交互库将调用恰好一次函数
explore，用输入的数据测试你的函数。你的函数正确返回后，交互库会判断你的计算是否正确，若正确则会输出Correct和交互函数调用次数相关信息，否则会输出相应的错误信息。
输入格式¶
输出格式¶
样例 #1¶
样例输入 #1¶
100 200 300
3 2
0 1
1 2
样例输出 #1¶
见“提示与说明”
提示¶
数据第一行的三个整数分别表示三种操作的调用次数限制，即 modify(x) 调用次数不能超过 \(100\)，query(x) 调用次数不能超过 \(200\)，check(x) 调用次数不能超过 \(300\)。
数据第二行的两个整数分别表示洞穴数和通路条数，即 \(N = 3 , M = 2\)。
report(x, y) 调用次数不能超过 \(M\)，该例子中即不超过 \(2\) 次。
下面是一个正确的交互过程：
| 选手程序 | 交互库 | 说明 |
|---|---|---|
| 调用 \(\text{explore}(3,2)\) | 开始测试 | |
| 调用 \(\text{modify}(0)\) | 对 \(0\) 号洞穴做操作 \(1\) | |
| 调用 \(\text{query}(2)\) | 返回 \(0\) | 目前 \(2\) 号洞穴的光源状态是关闭 |
| 调用 \(\text{report}(0,1)\) | 发现了道路 \((0,1)\) 并记录 | |
| 调用 \(\text{check}(0)\) | 返回 \(1\) | 与 \(0\) 号洞穴相关的道路都已被记录 |
| 调用 \(\text{report}(2,1)\) | 发现了道路 \((2,1)\) 并记录 | |
| 运行结束并返回 | 向屏幕打印 \(\text{Correct}\) | 交互结束，结果正确 |
下发文件说明¶
在本试题目录下：
-
grader.cpp/c以及graderhelperlib.pas是我们提供的交互库参考实现。 -
explore.h和grader.pas是头文件，选手不用关心具体内容。 -
template_explore.cpp/c/pas是我们提供的样例解题源代码。 -
explore1.in、explore2.in、explore3.in是样例输入，可供测试。
选手注意对所有下发文件做好备份。评测只收取本试题目录下的explore.c/cpp/pas，并且对该程序以外的文件的修改无效。
最终评测只会收取 explore.cpp/c/pas，修改选手目录下其他文件对评测无效。
本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 \(0\) 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 \(0\) 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。
在上述条件基础上，在一个测试点中，你得到满分，当且仅当：
-
你的每次函数调用均合法，且调用
modify、query和check的次数分别不超过\(L_m, L_q, L_c\)。 -
由于
report的调用次数限制为 \(M\)，你的每次调用都必须记录一条新的且存在的边；即每次调用report(x, y)时，应满足：有一条连接 \(x\) 号洞穴和 \(y\) 号洞穴的通路，且在这次调用之前从未调用过report(x, y)或report(y, x)。 -
你实现的函数
explore正常返回。 -
在
explore函数返回时，你已经通过调用report记录了全部 \(M\) 条通路。
本题共 \(25\) 个测试点，每个测试点 \(4\) 分。每个测试点的数据规模和相关限制见下表。
| 测试点编号 | \(N=\) | \(M=\) | \(L_m=\) | \(L_q=\) | \(L_c=\) | 特殊性质 |
|---|---|---|---|---|---|---|
| \(1\) | \(3\) | \(2\) | \(100\) | \(100\) | \(100\) | 无 |
| \(2\) | \(100\) | \(10\times N\) | \(200\) | \(10^4\) | \(2\times M\) | 无 |
| \(3\) | \(200\) | \(10\times N\) | \(200\) | \(4\times 10^4\) | \(2\times M\) | 无 |
| \(4\) | \(300\) | \(10\times N\) | \(299\) | \(9\times 10^4\) | \(2\times M\) | 无 |
| \(5\) | \(500\) | \(10\times N\) | \(499\) | \(1.5\times 10^5\) | \(2\times M\) | 无 |
| \(6\) | \(59998\) | \(\frac{N}{2}\) | \(17\times N\) | \(17\times N\) | \(0\) | \(A\) |
| \(7\) | \(99998\) | \(\frac{N}{2}\) | \(18\times N\) | \(18\times N\) | \(0\) | \(A\) |
| \(8\) | \(199998\) | \(\frac{N}{2}\) | \(19\times N\) | \(19\times N\) | \(0\) | \(A\) |
| \(9\) | \(199998\) | \(\frac{N}{2}\) | \(19\times N\) | \(19\times N\) | \(0\) | \(A\) |
| \(10\) | \(99997\) | \(N-1\) | \(18\times N\) | \(18\times N\) | \(0\) | \(B\) |
| \(11\) | \(199997\) | \(N-1\) | \(19\times N\) | \(19\times N\) | \(0\) | \(B\) |
| \(12\) | \(99996\) | \(N-1\) | \(10^7\) | \(10^7\) | \(2\times M\) | \(C\) |
| \(13\) | \(199996\) | \(N-1\) | \(10^7\) | \(10^7\) | \(2\times M\) | \(C\) |
| \(14\) | \(199996\) | \(N-1\) | \(10^7\) | \(10^7\) | \(2\times M\) | \(C\) |
| \(15\) | \(99995\) | \(N-1\) | \(10^7\) | \(10^7\) | \(2\times M\) | \(D\) |
| \(16\) | \(99995\) | \(N-1\) | \(10^7\) | \(10^7\) | \(2\times M\) | \(D\) |
| \(17\) | \(199995\) | \(N-1\) | \(10^7\) | \(10^7\) | \(2\times M\) | \(D\) |
| \(18\) | \(1004\) | \(2\times 10^3\) | \(10^7\) | \(5\times 10^4\) | \(2\times M\) | 无 |
| \(19\) | \(1004\) | \(3\times 10^3\) | \(10^7\) | \(5\times 10^4\) | \(2\times M\) | 无 |
| \(20\) | \(1004\) | \(3\times 10^3\) | \(10^7\) | \(5\times 10^4\) | \(2\times M\) | 无 |
| \(21\) | \(5\times 10^4\) | \(2\times N\) | \(10^7\) | \(10^7\) | \(2\times M\) | 无 |
| \(22\) | \(10^5\) | \(2\times N\) | \(10^7\) | \(10^7\) | \(2\times M\) | 无 |
| \(23\) | \(1.5\times 10^5\) | \(2\times 10^5\) | \(10^7\) | \(10^7\) | \(2\times M\) | 无 |
| \(24\) | \(2\times 10^5\) | \(2.5\times 10^5\) | \(10^7\) | \(10^7\) | \(2\times M\) | 无 |
| \(25\) | \(2\times 10^5\) | \(3\times 10^5\) | \(10^7\) | \(10^7\) | \(2\times M\) | 无 |
再次提醒，题目保证测试所使用的图在交互开始之前已经完全确定，而不会根据和你的程序的交互动态构造。
表中特殊性质栏中变量的含义如下：
A：保证每个点的度数恰好为 \(1\)。
B：保证对于每个 \(x > 0\)，存在恰好一个 \(y < x\) 的 \(y\) 使得 \(x\) 号洞穴与 \(y\) 号洞穴有通路直接相连。
C：存在 \(0 \sim N - 1\) 的一个排列 \(p_0, p_1, \cdots , p_{N-1}\)，使得对任意 \(1 \leq i < N\)，存在一条连接洞穴编号分别为 \(p_{i-1}\) 与 \(p_i\) 的通路。
D：保证图连通。
- 提示：你的程序可以通过判断传入的 \(N\) 的个位来区分上述不同的数据类型。
[NOI2004] 沙丘¶
题目背景¶
特别提示¶
在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：
- 提交时请在程序开头加入如下函数声明语句：
void init();
void look(int&, bool&);
void put_sign();
void take_sign();
void walk(int);
void report(int, int);
- 本题仅支持 C++ 语言（包括
C++，C++11，C++14，C++17）提交。
题目描述¶
根据新出土的一批史料记载，在塔克拉玛干沙漠中的一座沙丘下面，埋藏着一个神秘的地下迷宫。由著名探险家阿强率领的探险队经过不懈的挖掘，终于发现了通往地下迷宫的入口！队员们兴奋不已，急忙钻下去，去寻找那个埋藏已久的秘密。
他们刚钻进迷宫，只听“轰隆”一声巨响，回头一看，入口已与石墙融为一体，无法辨认。他们意识到自己被困在迷宫里了！环顾周围，似乎是一个洞穴。
这座迷宫由很多洞穴组成，某些洞穴之间有道路连接。每个洞穴都有一盏灯，凭借着微弱的灯光，可以看清有多少条道路与这个洞穴相连。每个洞穴的内部是完全相同的，且无法做标记。每条道路也是完全相同的，也无法做标记。
阿强凭借着微弱的灯光，发现了墙壁上的一段文字（事实上，每个洞穴的墙壁上都有这段文字），翻译成现代汉语就是：“陌生人，请把这个迷宫的洞穴数和道路数告诉我，我就会指引你走出迷宫。”
阿强很快镇定了下来，他拿出一个路标，对队员们说：“这个迷宫的危险程度远超出我们的想象，为了安全起见，大家一定要集体行动。我这儿有一个路标，有了它，我们一定能探明迷宫的结构。大家跟我走！”
现在，轮到你扮演阿强了。路标只有一个，可以随身携带，也可以暂时放在某个洞穴中（把路标放在道路上是毫无意义的，因为那里一片漆黑，什么都看不见）。你的任务很简单：用尽量少的步数探明这个迷宫共有多少个洞穴和多少条道路。“一步”是指从一个洞穴走到另一个相邻的洞穴。
交互方法¶
本题是一道交互式题目，你的程序应当和测试库进行交互，而不得访问任何文件（包括临时文件）。测试库提供了若干函数，它们的用法和作用如下：
-
init必须先调用，但只能调用一次，用作初始化测试库； -
look(d,sign)的作用是查看当前洞穴的情况，测试库将从整型变量 \(d\) 中返回与该洞穴相连的道路的数目，从布尔变量sign中返回该洞穴内是否有路标，sign为true表示有路标，为false表示无路标。 -
put_sign的作用是在当前洞穴放上路标。只有当路标随身携带着的时候，才可以调用这个函数。 -
take_sign的作用是把当前洞穴的路标拿走。只有当路标在当前洞穴时，才可以调用这个函数。 -
walk(i)的作用是沿着编号为 \(i\) 的道路走到相邻的洞穴中。这里的编号是相对于当前所在洞穴而言的，并且是暂时的。假设与某洞穴相连的道路有 \(d\) 条，这些道路按照逆时针顺序依次编号为 \(0\)，\(1\)，\(2\)，\(\ldots\)，\(d-1\)。走第一步时，编号为 \(0\) 的道路由库确定。以后的过程，阿强会将他走进这个洞穴的道路编号为 \(0\)。 -
report(n,m)的作用是向测试库报告结果。\(n\) 表示洞穴的数目，\(m\) 表示道路的数目。当这个函数被调用后，测试库会自动中止你的程序。
注意与其他交互题不同的是，您需要直接在 main() 函数内实现你的程序。
在 C/C++ 中，布尔型变量用整型变量代替，\(0\) 表示 false，\(1\) 表示 true。
思路¶
这交互题怎么写呢？
声明：本题解部分参考 Aly_ 大佬，orz。
我们从题目给定的操作入手，看看可以实现那些操作。
-
我们可以获取当前点的出边数量和路标情况。
-
我们可以在一个点放置或者收回路标，但是我们只有一个路标
-
我们可以沿着当前点按某种特定规律排序后的第i条边找到另外一个点去。当某个点的边的排序被确定后，那么就不会再改变了。即对于点 \(u\)，第一次访问其第 \(i\) 条出边到达的点和下一次回到点 \(u\) 后访问其第 \(i\) 条出边到达的点是一样的。
为了得到这幅图的信息，我们肯定要遍历这幅图，并且使用唯一一个路标确定我们访问到的这个点之前是否被访问过，并且确定我们访问的这条边是否之前被访问过。
为了遍历这幅图，我们需要一个遍历方法，最常见的就是深搜 dfs 了。但是因为这是一幅图，所以我们把边划分为**树边和非树边（即反祖边）**。
判定边貌似不太简单，我们先考虑点的情况。那么假设从点i走到点 j。
- 确定 \(i\) 到 $j $ 经过的边是非树边还是树边（下方加粗点），即从 \(1\) 号点到 \(3\) 号点就是我们要确定的前者。这种情况我们一定通过 \(i\) 访问过 \(j\) 了，以下图举例，我们从 \(1\) 直接访问 \(3\) 前已经通过 \(2\) 访问了 \(3\) 了。为什么我们不会先走非树边呢？因为我们的定义就是从当前点 \(u\) 走到一个没有到达的点 \(v\)，那么 \(u,v\) 间的边就是树边。如果先走了 \(1\) 号边，那么 \(1\) 号边就是树边了。
所以我们可以记 \(vis_{i,j}\) 表示从点 \(i\) 出发已经遍历了点 \(j\) 了（这里点 \(j\) 的编号是相对的，但是确定的，即我们把点 \(i\) 的祖先在 \(i\) 的邻点中编号为 \(0\) 号点并且以此为首按特定顺序编号）
但是在上面 \(1,3\) 号点的情况，我们并不是通过 \(vis_{1,3}=1\) 来判定我们当前要走的 \(1\) 号边是一条非树边的，而是通过 \(vis_{3,1}\) 来判定的。为什么？因为如果按第一种方法，那么我们在回溯统计时将需要转移合并很多信息，复杂度不允许。那么为什么第二种方法可以？因为我们发现非树边 \(1-3\) 时，可以确定的是我们之前也从 \(3\) 到达过 \(1\)（即通过树边到达 \(3\) 时遍历 \(3\) 的边造成的），因此我们的 \(vis_{3,1}\) 会标记为 \(1\)。
那么当我们发现了一条非树边时应该怎么样修改 \(vis\) 数组的值呢？把路标放在 $j $，回到 $i $，依次看 $i $ 的每个邻点上是否有路标，找到了之后就取回路标，修改 \(vis\) 为 \(1\) 并返回 $j $。在回到 $i $ 时如果发现当前边 $vis $ 为 $1 $ 就跳过。
- 确定 \(j\) 是 \(i\) 的祖先（以下 \(i\) 的祖先都指的是在树上 \(i\) 的父亲，我们要开数组记录）还是一个新点：我们先把路标放在 \(j\) 上，然后返回 \(i\) 并不断回溯 \(i\) 的祖先。最后如果回溯到根了都没看到路标，就说明 \(j\) 是一个新点，回到 \(j\) 修改答案，给 \(j\) 分配编号并且在图中标记方便下次我们再来到j时知道这是哪个点，并从 \(j\) 继续遍历，否则说明 \(j\) 是 \(i\) 的祖先，我们取走路标再返回 \(i\)，继续遍历。
上面我们其实已经无意中把边一起处理了，回顾看看。这里再提一句，为了实时确定我们当前的路径（这里的**路径**应该很好理解，我们把我们访问的路径看出一个个向量相加，消去相反的向量就得到我们当前从根节点到当前点的路径了）上每个点 \(u\)，我们走了它的第几个邻点，我们就记录数组 \(nxt_u\) 表示从 \(u\) 我们走了其第几个邻点。如果要从 \(u\) 往之前的点回溯，那么就把 \(nxt_u\) 改为 \(d-nxt_u\)（注意我们对于点 \(u\) 的邻点的编号是相对的，因此我们假设从正向访问 \(u\) 时经过的路径为 \(x→u→v\)，从 \(x→u\) 时 \(x\) 是 \(u\) 的 \(0\) 号邻点，\(v\) 是 \(u\) 的 \(k\) 号节点；那么再从 \(v→u\) 时 \(x\) 不是 \(u\) 的 $0 $ 号节点，而 \(v\) 是其 \(0\) 号邻点，\(x\) 是其 \(d-k\) 号节点，\(d\) 为我们使用 look(d, sign); 获取到的）。可以发现我们的 \(nxt_u\) 其实就是标记我们走了 \(u\) 的第几条出边。
输出格式¶
样例 #1¶
样例输入 #1¶
5
3 2 3 4
2 1 3
2 1 2
2 1 5
1 4
样例输出 #1¶
提示¶
样例解释¶
探险队初始时站在编号为 \(1\) 的洞穴内，编号为 \(0\) 的道路通向洞穴 \(2\)，编号为 \(1\) 的道路通向洞穴 \(3\)，编号为 \(2\) 的道路通向洞穴 \(4\)。
一种可能得满分的调用方案如下：
| C/C++ 选手的调用方法 | 说明 |
|---|---|
init(); |
初始化程序 |
look(d, sign); |
返回 \(d=3\)，\(sign=false\) |
put_sign(); |
放下路标 |
walk(0); |
选择编号为 \(0\) 的道路 |
look(d, sign); |
返回 \(d=2\)，\(sign=false\) |
walk(1); |
选择编号为 \(1\) 的道路 |
look(d, sign); |
返回 \(d=2\)，\(sign=false\) |
walk(1); |
选择编号为 \(1\) 的道路 |
look(d, sign); |
返回 \(d=3\)，\(sign=true\) |
take_sign(); |
拿起路标 |
walk(1); |
选择编号为 \(1\) 的道路 |
look(d, sign); |
返回 \(d=2\)，\(sign=false\) |
walk(1); |
选择编号为 \(1\) 的道路 |
look(d, sign); |
返回 \(d=1\)，\(sign=false\) |
report(5, 5); |
返回洞穴数为 \(5\)，道路数为 \(5\) |
注意，该例子只是对库函数的使用说明，并没有算法上的意义。
约定¶
-
洞穴数不超过 \(100\)，道路数不超过 \(4000\)。
-
迷宫是连通的，即任意两个洞穴都相互可达。
-
两个洞穴之间最多只有一条道路。
-
没有哪条道路连接两个相同的洞穴。
评分方法¶
如果你的程序有下列情况之一，该测试点 \(0\) 分：
-
访问了任何文件(包括临时文件)或者自行终止；
-
非法调用库函数；
-
让测试库异常退出。
否则你每个测试点的得分按这样来计算：
如果你所报告的洞穴数与通道数都不正确，得 \(0\) 分；如果只有其中一个正确，得 \(2\) 分；如果两个都正确，则根据 \(walk\) 函数的调用次数评分，公式如下：
\(your\_score=\left\{ \begin{aligned} &10&,your\_ans\le our\_ans\\ &5+\left\lfloor\frac{our\_ans}{your\_ans}\times 5+0.5\right\rfloor&,your\_ans>our\_ans \end{aligned} \right.\)
其中 \(your\_ans\) 表示你的程序调用 \(walk\) 函数的次数，\(our\_ans\) 表示我们的程序的结果。
如何进行本地测试¶
-
在工作目录下建立一个文件叫做
dune.in，文件的第一行包括一个整数 \(n\) 为洞穴的数目，洞穴用1到n的整数编号，以下 \(n\) 行描述迷宫的结构。文件的第 \(i+1\) 行描述编号为 \(i\) 的洞穴的情况，第一个数 \(d_i\) 表示与该洞穴相连的道路的数目，其后的 \(d_i\) 个数按照逆时针顺序给出了这些道路另一端的洞穴编号。 -
调用 \(init\) 函数之后，库将编号为 \(1\) 的洞穴作为探险队的起始洞穴，并暂定编号为 \(0\) 的道路通向的洞穴编号为文件中第二行的第二个数。比如样例中，初始时，库暂定编号为 \(0\) 的道路通向洞穴 \(4\)。
-
把你的源文件（命名为
dune.cpp）和dune_lib.hpp放在同一目录下，用命令g++ -o dune dune_lib.cpp dune.cpp来编译你的程序。 -
执行你的程序，此时测试库会产生输出文件
dune.log，该文件中包括了你程序和库交互的记录和最后的结果。 -
如果程序正常结束，
dune.log的最后一行包含一个整数，为你走的步数。 -
如果程序非法退出，则我们不保证
dune.log中的内容有意义。
样例交互库请在题目附件中下载。
T-shirts Distribution¶
题面翻译¶
编程竞赛的组织者决定向参与者赠送 T 恤。本题有六种不同的 T 恤尺码：S、M、L、XL、XXL、XXXL（尺码按升序排列）。 T恤已经准备好了。对于从 S 到 XXXL 的每个尺码，您都会获得该尺码的 T 恤的数量。
在注册过程中，组织者向每一位参与者询问了他想要的T恤尺寸。如果参与者在两个尺寸之间犹豫不决，他可以指定两个相邻的尺寸——这意味着这两个尺寸中的任何一个都适合他。
编写一个程序，确定是否可以向比赛的每个参与者展示一件 T 恤。当然，每个参与者都应该得到一件合适尺寸的 T 恤：
如果他指定一种尺寸，他想要的尺寸；
两个相邻尺寸中的任何一个，如果他指定了两个尺寸。
如果可能，程序应该找到任何有效的 T 恤分布。
输入的第一行包含六个非负整数——每种尺寸的 T 恤的数量。数字分别针对尺寸 S、M、L、XL、XXL、XXXL。 T 恤的总数不超过 \(100000\) 。
第二行包含正整数 \(n ( 1<=n<=100000)\) — 参与者的数量。
以下 \(n\) 行包含参与者指定的大小，每个参与者一行。第 \(ii\) 行包含第 \(ii\) 参与者提供的信息：单个尺寸或用逗号分隔的两个尺寸（没有任何空格）。如果有两种尺寸，则尺寸按升序写入。保证用逗号分隔的两个尺寸是相邻的。
如果不可能向每位参与者展示一件 T 恤，请输出NO。
否则，输出 \(n+1\) 行。在第一行输出YES。在接下来的 \(nn\) 行中，输出组织者应该给参与者的 T 恤尺寸，每行一件。参与者的顺序应与输入中的顺序相同。
如果有多个解决方案，请输出其中任何一个。
思路¶
先把一定要分配的分配了，剩下的就是一个 2-SAT 问题。
或者我们可以不用考虑那么复杂——也许就是个贪心。
注：下面的“人”指的是可以有两种选择的人。
因为每个人都只有可能选择两款相邻的尺码，我们按每个人第一款尺码从小到大排序后从小到大贪心地分配各个款式的衣服即可，即优先分配尺码小的衣服，不够了再分配尺码大的。
其它真的就没了。
一些字符串操作
t.find(",",0) 返回字符串 \(t\) 中第一个 , 的下标。
t.substr(0, pos) 取出下标范围内的子串，返回值为 string。
/*
CB Ntsc
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define err cerr<<"Error"
#define rd read()
#define nl putc('\n')
#define ot write
#define nl putchar('\n')
inline int rd
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int INF = 1e9;
const int N = 2e6+5;
const int M = 1e6+5;
const int S=1e6+5;
const int maxlog = 10;
string ds[10]={"S","M","L","XL","XXL","XXXL"};
struct node{
int a,b,id;
}p[N];
int tot;
int ans[N];
int c[N],n;
void cal(string s,int id,int f,int idx){
for(int i=0;i<6;i++){
if(ds[i]==s){
if(f==1)p[id].a=i,p[id].id=idx;
if(f==2)p[id].b=i,p[id].id=idx;
if(!f){
ans[idx]=i;
c[i]--;
if(c[i]<0){
cout<<"NO"<<endl;
exit(0);
}
return ;
}
}
}
}
bool cmp(node a,node b){
return a.a<b.a;
}
signed main(){
for(int i=0;i<6;i++)c[i]=rd;
n=rd;
for(int i=1;i<=n;i++){
string s;
cin>>s;
int pos=s.find(",",0);
if(pos==EOF){
cal(s,0,0,i);
}else{
cal(s.substr(0,pos),++tot,1,i);
cal(s.substr(pos+1,s.size()-1),tot,2,i);
}
}
// for(int i=1;i<=tot;i++){
// cerr<<p[i].a<<' '<<p[i].b<<endl;
// }
sort(p+1,p+tot+1,cmp);
for(int i=1;i<=tot;i++){
int a=p[i].a,b=p[i].b,id=p[i].id;
if(c[a])c[a]--,ans[id]=a;
else c[b]--,ans[id]=b;
if(c[b]<0){
cout<<"NO"<<endl;
return 0;
}
}
cout<<"YES\n";
for(int i=1;i<=n;i++){
cout<<ds[ans[i]]<<endl;
}
}
/*
2 5
0 1 1 1 1
0 1 1 2 4
0 2 1 2 1
0 2 1 1 4
*/
题目描述¶
The organizers of a programming contest have decided to present t-shirts to participants. There are six different t-shirts sizes in this problem: S, M, L, XL, XXL, XXXL (sizes are listed in increasing order). The t-shirts are already prepared. For each size from S to XXXL you are given the number of t-shirts of this size.
During the registration, the organizers asked each of the \(n\) participants about the t-shirt size he wants. If a participant hesitated between two sizes, he could specify two neighboring sizes — this means that any of these two sizes suits him.
Write a program that will determine whether it is possible to present a t-shirt to each participant of the competition, or not. Of course, each participant should get a t-shirt of proper size:
-
the size he wanted, if he specified one size;
-
any of the two neibouring sizes, if he specified two sizes.
If it is possible, the program should find any valid distribution of the t-shirts.
输入格式¶
The first line of the input contains six non-negative integers — the number of t-shirts of each size. The numbers are given for the sizes S, M, L, XL, XXL, XXXL, respectively. The total number of t-shirts doesn't exceed \(100000\) .
The second line contains positive integer \(n\) ( \(1<=n<=100000\) ) — the number of participants.
The following \(n\) lines contain the sizes specified by the participants, one line per participant. The \(i\) -th line contains information provided by the \(i\) -th participant: single size or two sizes separated by comma (without any spaces). If there are two sizes, the sizes are written in increasing order. It is guaranteed that two sizes separated by comma are neighboring.
输出格式¶
If it is not possible to present a t-shirt to each participant, print «NO» (without quotes).
Otherwise, print \(n+1\) lines. In the first line print «YES» (without quotes). In the following \(n\) lines print the t-shirt sizes the orginizers should give to participants, one per line. The order of the participants should be the same as in the input.
If there are multiple solutions, print any of them.
样例 #1¶
样例输入 #1¶
0 1 0 1 1 0
3
XL
S,M
XL,XXL
样例输出 #1¶
YES
XL
M
XXL
样例 #2¶
样例输入 #2¶
1 1 2 0 1 1
5
S
M
S,M
XXL,XXXL
XL,XXL
样例输出 #2¶
NO
Anton and Ira¶
题面翻译¶
给定两个排列 s 和 p ，每次可以交换 p 中的两个数，代价为它们间的距离，问最小代价使 p 变为 s 。要输出方案
思路¶
我们转换一下题面，对 \(p\) 建立以 \(s\) 为基底的映射，因此 \(s\) 变成了 \(1\sim n\) 的有序排列，\(p\) 变成 $1\sim n $ 的乱序排列，以便于我们进行讨论。
那么现在我们要找到一个普适化的策略来调整 \(p\) 使得 \(p\) 最终变得升序。
我们可以证明，一定存在 \((i,j),i<j\) 有 \(p_j≤i,j≤p_i\)。我们可以尝试构造反例来证明，可以发现即使是设计的构造最终也定会存在上面的情况。这也可以说明在 \(p\) 变得有序之前，一定会有以上满足条件的二元组存在。
然后当我们每次发现这种二元组，就交换其即可。
事实证明暴力出奇迹。
/*
CB Ntsc
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define err cerr<<"Error"
#define rd read()
#define nl putc('\n')
#define ot write
#define nl putchar('\n')
inline int rd
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int INF = 1e9;
const int N = 2e6+5;
const int M = 1e6+5;
const int S=1e6+5;
const int maxlog = 10;
int n;
int a[N],b[N],t[N];
int ans[N][2],top;
int cnt;
signed main(){
n=rd;
for(int i=1;i<=n;i++)a[i]=rd;
for(int i=1;i<=n;i++)b[rd]=i;
for(int i=1;i<=n;i++)t[i]=b[a[i]];
for(int i=1;i<=n;i++)b[i]=t[i];
while(1){
int f=0;
int p=0;
while(b[p]==p)p++;
for(int i=p;i<=n;i++){
if(b[i]<=i)continue;
for(int j=i+1;j<=n;j++){
if(b[j]<=i&&j<=b[i]){
cnt+=(j-i);
ans[++top][0]=i,ans[top][1]=j;
swap(b[i],b[j]);
f=1;break;
}
}
if(f)break;
}
if(!f)break;
}
cout<<cnt<<endl<<top<<endl;
for(int i=1;i<=top;i++){
cout<<ans[i][0]<<' '<<ans[i][1]<<endl;
}
}
/*
2 5
0 1 1 1 1
0 1 1 2 4
0 2 1 2 1
0 2 1 1 4
*/
题目描述¶
Anton loves transforming one permutation into another one by swapping elements for money, and Ira doesn't like paying for stupid games. Help them obtain the required permutation by paying as little money as possible.
More formally, we have two permutations, \(p\) and \(s\) of numbers from \(1\) to \(n\) . We can swap \(p_{i}\) and \(p_{j}\) , by paying \(|i-j|\) coins for it. Find and print the smallest number of coins required to obtain permutation \(s\) from permutation \(p\) . Also print the sequence of swap operations at which we obtain a solution.
输入格式¶
The first line contains a single number \(n\) ( \(1<=n<=2000\) ) — the length of the permutations.
The second line contains a sequence of \(n\) numbers from \(1\) to \(n\) — permutation \(p\) . Each number from \(1\) to \(n\) occurs exactly once in this line.
The third line contains a sequence of \(n\) numbers from \(1\) to \(n\) — permutation \(s\) . Each number from \(1\) to \(n\) occurs once in this line.
输出格式¶
In the first line print the minimum number of coins that you need to spend to transform permutation \(p\) into permutation \(s\) .
In the second line print number \(k\) ( \(0<=k<=2·10^{6}\) ) — the number of operations needed to get the solution.
In the next \(k\) lines print the operations. Each line must contain two numbers \(i\) and \(j\) ( \(1<=i,j<=n\) , \(i≠j\) ), which means that you need to swap \(p_{i}\) and \(p_{j}\) .
It is guaranteed that the solution exists.
样例 #1¶
样例输入 #1¶
4
4 2 1 3
3 2 4 1
样例输出 #1¶
3
2
4 3
3 1
提示¶
In the first sample test we swap numbers on positions 3 and 4 and permutation \(p\) becomes 4 2 3 1. We pay \(|3-4|=1\) coins for that. On second turn we swap numbers on positions 1 and 3 and get permutation \(3241\) equal to \(s\) . We pay \(|3-1|=2\) coins for that. In total we pay three coins.