← 返回题目列表

AtCoder · joisp2025_j

J. 电子电路2(电路2)

中文机器翻译题面 查看原题

配点: 100 点

分发文件

如何使用AtCoder提交

使用 C++ 时

  • circuit.h 并实现问题陈述中指定的功能。
  • 不要使用标准输入/输出或文件输入/输出。

使用其他语言时

  • 请按照问题文本的 JOIG 版本中的指定进行沟通。

JOI 您正在玩电子电路组。 电子电路组 N 的 您可以创建一个包含 和零件,N 的 您可以创建一个包含 或零件 和1 的 您可以创建一个包含 电路板 它由 组成。 电路板 2N+1 的 您可以创建一个包含 开关 按住 和 按字典顺序比较 N 的 您可以创建一个包含 零件槽 它由 组成, 可以通过在各元件槽中放置 AND 元件或 OR 元件来使用。 根据安装的组件和开关的状态,电路板将: 输出 0 或 至少 1 的值。

电路板规格

  • 该开关有 它们的编号最多为 0 减去 2N ,每个开关都有 ON 或 OFF 状态。每个开关如下所示 0 或 至少 1 的值。
  • 零件槽有 它们的编号最大为 0 减去 N-1 。每个组件插槽如下所示 0 或 至少 1 的值。
  • 每个交换机和每个组件槽位的输出按照以下规则按编号降序排列(对于相同编号的交换机和组件槽位,组件槽位在前)。 关于
    • j = 2N, 2N-1, \dots, N ,切换 j 输出以下内容。 当
      • 开关 按住 j 关闭时, 当0 。 你只需要砍掉
      • 开关 按住 j 为ON时, 对于1 。 你只需要砍掉
    • j = N-1, N-2, \dots, 0 ,零件槽 j 的输出 x 当开关 输出 j 输出以下内容。 当
      • 开关 按住 j 关闭时, 当x 。 你只需要砍掉
      • 开关 按住 j 为ON时, 对于1-x 输出
    • i = N-1, N-2, \dots, 0 ,零件槽 i 是 您也可以写 2 开关 它连接到 U_i, V_i 。在这里,U_i, V_i 是 您也可以写 i < U_i < V_i \leqq 2N 很满意。开关 U_i 的输出 x,开关 当 V_i 的输出 y 时,组件槽 当 AND 部件安装在 i 输出以下内容。 当
      • 零件槽 它由 i 中时, 当 OR 部件安装在\min(x, y) 。 你只需要砍掉
      • 零件槽 它由 i 中时, 关于\max(x, y) 。 你只需要砍掉
  • j = 1, 2, \dots, 2N ,U_i = j 或 至少 V_i = j 似乎是 i (0 \leqq i \leqq N - 1)只是 1 有两个。
  • 电路板的输出是开关 相当于 0 的输出。

例如, 当分解为N = 3, U_0 = 1, V_0 = 2, U_1 = 3, V_1 = 4, U_2 = 5, V_2 = 6 ,零件槽 当AND部件、AND部件和OR部件安装在 0, 1, 2 中时,电路板如下图所示。

现在,当JOI尝试在所有零件槽中安装AND零件时,一些已安装的零件 很明显, 最大 R 個 的 OR 部分被混淆了。 由于“与”和“或”元件无法在视觉上区分,因此必须使用电路板来区分“与”和“或”元件。 你的工作是按照以下格式提出 JOI 问题。 该过程重复 1\,000 次,以确定 OR 组件安装在哪个组件插槽中。

  • 你对你来说就是 JOI 指示 2N+1 开关的状态。 JOI按照指示改变开关的状态并告诉你电路板的输出。

给定电路板上的电路连接信息以及安装的OR组件数量的上限,1\,000 使用以下问题编写一个程序来识别 OR 组件安装在哪个组件插槽中。

实施细节

你 1 您必须提交两个文件。

您提交的文件是 名称是 circuit.cpp 。 那个程序是 #include 通过预处理器指令 加载 circuit.h 。

circuit.cpp 必须实现以下功能。

  • std::string solve(int N, int R, std::vector<int> U, std::vector<int> V)
    • 此功能 仅调用了 1 次。
    • 引数 N 是组件插槽的数量 N 。
    • 引数 R 是安装的 OR 部件数量的上限 R 。
    • 引数 U,V 是长度 N 数组,U[i],V[i] (0 \leqq i \leqq N - 1) 是组件槽 连接到 i 的开关数量 U_{i}, V_{i} 。
    • 该函数满足以下条件: 长度由 & 和 按字典顺序比较 | 组成的长度 要变为 N 的字符串 t 。
      • 各 i = 0, 1, \dots, N-1 ,零件槽 i 中的部件是 AND 部件 t[i] 是 您也可以写 & ,如果它是 OR 部分 t[i] 是 您也可以写 | 。
    • 返回值 t 的长度是 N ,不正解[1] 已确定。 调用
    • 返回值 t 至 该值是 & 但是 | ,不正解[2] 已确定。 调用
    • 每个组件槽中实际安装的组件类型是返回值。 如果与 t 所代表的不同,不正解[3] 已确定。 调用

您的程序可以调用以下函数。

  • int query(std::string s)
    • 您可以使用此功能向 JOI 提问。 必须是字符串
    • 引数 s 是 您也可以写 0 和 按字典顺序比较 1 组成的长度 要变为 2N + 1 。每个 j = 0, 1, \dots, 2N ,s[j] 是 在 0 然后切换 关闭 j 关闭s[j] 是 在 1 然后切换 关闭 j 。
    • 引数 s 的长度是 2N+1 ,不正解[4] 已确定。 调用
    • 引数 s 至 该值是 0 但是 1 ,不正解[5] 已确定。 调用
    • 此功能 调用次数不得超过 1\,000 次。 如果调用次数超过1\,000 次,不正解[6] 已确定。 调用
    • 该函数的返回值是参数 这是开关状态更改时电路板的输出,如 s 所示。

重要说明

  • 您可以自由地实现其他函数并声明全局变量以供内部使用。
  • 您提交的程序不得以任何方式与标准输入、标准输出或其他文件交互。但是,允许将调试信息等输出到标准错误输出。

如何编译执行

用于测试创建的程序的评分程序示例是 它包含在可以从竞赛网站下载的存档中。 该存档还包含必须提交的示例文件。

评分程序的示例是 1 由两个文件组成。 该文件是 grader.cpp 。 为了测试你的程序, 这些文件 将 grader.cpp, circuit.cpp, circuit.h 放在同一目录中并运行以下命令。

g++ -std=gnu++20 -O2 -o grader grader.cpp circuit.cpp

存档中还包含 您可以改为运行文件 compile.sh 。在这种情况下,请运行以下命令。

./compile.sh

如果编译成功, 将生成一个名为grader 的可执行文件。

请注意,实际评分程序与示例评分程序不同。 示例评分程序作为单个进程运行。 该程序从标准输入读取输入并将结果输出到标准输出。

输入示例评分程序

T 作为函数 solve 应返回的长度 设其为字符串 N 。示例评分程序按以下格式从标准输入读取输入。

N R
U_0 V_0
U_1 V_1
\vdots
U_{N-1} V_{N-1}
T

评分程序的示例输出

示例评分程序将以下信息输出到标准输出。

  • 如果正确,则函数 呼叫 query 的次数是 如果不是 Accepted: 22 。
  • 如果答案不正确,则错误答案的类型为 Wrong Answer [4] 。

当满足任何错误答案条件时,示例评分程序将结束执行。 如果要执行的程序满足多个错误答案条件,则显示的错误答案类型将是其中之一。 1 只有一个。

评分注意事项

实际评分程序不是自适应的,而是从交互开始就有固定的答案。

制約

  • 1 \leqq N \leqq 8\,000.
  • 1 \leqq R \leqq \min(N, 120).
  • i < U_i < V_i \leqq 2N (0 \leqq i \leqq N - 1).
  • j = 1, 2, \dots, 2N ,U_i = j 或 至少 V_i = j 似乎是 i (0 \leqq i \leqq N - 1)只是 1 有两个。

小課題

  1. (1 点) N = 1.
  2. (4 点) N \leqq 1\,000,R = 1.
  3. (5 点) N \leqq 1\,000.
  4. (17 点) U_i = i + 1,V_i = N + 1 + i (0 \leqq i \leqq N - 1),R \leqq 70.
  5. (8 点) U_i = i + 1,V_i = N + 1 + i (0 \leqq i \leqq N - 1).
  6. (23 点) U_i = 2i + 1,V_i = 2i + 2 (0 \leqq i \leqq N - 1),R \leqq 70.
  7. (8 点) U_i = 2i + 1,V_i = 2i + 2 (0 \leqq i \leqq N - 1).
  8. (27 点) R \leqq 70.
  9. (7 点)没有额外的限制。

交互示例

下面是示例评分程序读取的输入示例以及相应函数调用的示例。

入力例 1

1 1
1 2
|

1 第 query 的调用,电路板的输出可以计算如下。

  • 开关 按住 1, 2 的状态分别为 ON 和 OFF,因此开关 1, 2 分别是 它总是能被 1, 0 。 你只需要砍掉
  • 零件槽 它由 0 安装了 OR 部件,并连接了开关 输出 1, 2 分别是 它总是能被 1, 0 ,因此组件槽 0 是 您也可以写 \max(1, 0) = 1 。 你只需要砍掉
  • 开关 按住 0 的状态为OFF,组件槽为 0 的输出是 1 ,所以切换 0 的输出是 1 。
  • 因此,电路板的输出为 1 。

此输入示例满足所有子任务约束。


入力例 2

3 3
1 2
3 4
5 6
&&|

问题文本中的图表代表此输入示例的电路板。

此输入示例是一个小作业。 3, 6, 7, 8, 9 满足约束。

在可以从竞赛网站下载的文件中,sample-01-in.txt 是一个输入示例 对应于 1 , 对应于sample-02-in.txt 是一个输入示例 对应于 2 。 另外,sample-03-in.txt 是一个小作业 3, 4, 5, 8, 9 满足约束,sample-04-in.txt 是一个小作业 3, 6, 7, 8, 9 满足约束。