『洛谷』构造

构造

构造题是一种形式灵活多样的题型。正是因为这个特点，使得构造题没有一种通用的方法。

P3599 Koishi Loves Construction

题目描述

Koishi 决定走出幻想乡成为数学大师！

Flandre 听说她数学学的很好，就给 Koishi 出了这样一道构造题：

Task1：试判断能否构造并构造一个长度为 \(n\) 的 \(1 \dots n\) 的排列，满足其 \(n\) 个前缀和在模 \(n\) 的意义下互不相同。

Task2：试判断能否构造并构造一个长度为 \(n\) 的 \(1 \dots n\) 的排列，满足其 \(n\) 个前缀积在模 \(n\) 的意义下互不相同。

按照套路，Koishi 假装自己根本不会捉，就来找你帮忙辣。

输入格式

第一行两个整数 \(X\) 和 \(T\)，分别表示 Task 类型和测试点内的数据组数。

接下来 \(T\) 行，每行一个整数表示每组数据中的 \(n\)。

输出格式

为了方便 SPJ 的编写，您需要遵从以下格式输出。

对于每组数据仅包含一行输出：

如果您认为当前数据不存在符合题意的构造，只需输出一个整数 \(0\)。
如果您认为当前数据存在符合题意的构造却不会构造，只需输出一个整数 \(1\)。
如果您认为当前数据存在符合题意的构造并成功构造，则需要先输出一个整数 \(2\)，再输出 \(n\) 个整数表示构造的方案。

每两个整数之间需要有空格作为分隔符。

样例 #1

样例输入 #1

1
2

1 1
8

样例输出 #1

1	2 8 7 6 5 4 3 2 1

样例 #2

样例输入 #2

1
2

2 1
11

样例输出 #2

1	2 1 2 3 5 10 6 7 4 9 8 11

提示

对于每组数据：

如果您对于构造的存在性判断正确，您将会得到 \(30\%\) 的分数，若您的构造符合题意或者确实不存在符合题意的构造，您将会得到剩余的 \(70\%\) 的分数。
如果您对于构造的存在性判断不正确，您将不会得到任何分数。

对于每组测试点，您的得分将是本组数据点中得分的最小值。

测试点类型 \(1\)：\(10\) 分，满足 \(X = 1\)，\(1 \leq n \leq 10\)。
测试点类型 \(2\)：\(40\) 分，满足 \(X = 1\)，\(1 \leq n \leq {10}^5\)。
测试点类型 \(3\)：\(10\) 分，满足 \(X = 2\)，\(1 \leq n \leq 10\)。
测试点类型 \(4\)：\(40\) 分，满足 \(X = 2\)，\(1 \leq n \leq {10}^5\)。

对于所有测试点，满足 \(1 \leq T \leq 10\)。

解题思路

解答代码

P5441 【XR-2】伤痕

题目背景

长日尽处，我来到你的面前，你将看见我的伤痕，你会知晓我曾受伤，也曾痊愈。——泰戈尔《深爱你这城》

题目描述

X 国经历了一场前所未有的大地震，人们伤痕累累，整个国家破碎不堪。

为了帮助人们痊愈，也为了让 X 国能够生存下去，X 国国王决定重建 X 国。

国王决定先建造 \(n\) 座城市，由于国王喜欢奇数，所以 \(n\) 为奇数。

城市建造完后，需要给每两座城市之间都修建一条道路，即一共需要修建 \(\frac{n(n-1)}{2}\) 条道路。

不过，修建双向道路的成本太高了，建造完 \(n\) 座城市后剩下的经费最多只够修建 \(n\) 条双向道路，而其余的道路只能修建成单向的。好在方向并不会影响修建单向道路所需的费用，因此所有单向道路的方向可以任意决定。

另外，等到重建完成后，国王决定将 \(4\) 座城市钦定为 X 国的核心城市。为促进 X 国的发展，这 \(4\) 座核心城市中的任意两座城市，必须能够在不经过非核心城市的情况下相互到达。

国王希望，你能够给他一种道路修建方案，使重建完成后选择 \(4\) 座核心城市的方案数最大化。

输入格式

一行一个正整数 \(n(1 \le n \le 99)\)，保证 \(n\) 为奇数，表示有 \(n\) 座城市。

输出格式

第一行包含一个整数，表示最大的选择 \(4\) 座核心城市的方案数。

接下来的 \(n\) 行每行 \(n\) 个正整数描述一个邻接矩阵，表示你的道路修建方案。

具体来说，第 \(i\) 行的第 \(j\) 个数为 \(1\) 表示第 \(i\) 座城市可以通过一条道路到达第 \(j\) 座城市，为 \(0\) 表示第 \(i\) 座城市无法通过一条道路到达第 \(j\) 座城市。我们分为 \(3\) 种情况详细说明：

\(i, j\) 之前的道路为一条 \(i\) 到 \(j\) 的单向道路，则邻接矩阵的第 \(i\) 行第 \(j\) 个数为 \(1\)，第 \(j\) 行第 \(i\) 个数为 \(0\)。
\(i, j\) 之间的道路为一条双向道路，则邻接矩阵的第 \(i\) 行第 \(j\) 个数和第 \(j\) 行第 \(i\) 个数均为 \(1\)，你需要保证最多修建 \(n\) 条双向道路。
\(i = j\)，则第 \(i\) 行第 \(j\) 个数（第 \(j\) 行第 \(i\) 个数）为 \(0\)。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

【样例 \(1\) 说明】

由于一共只有 \(3\) 个点，所以选择 \(4\) 座核心城市的方案数一定为 \(0\)，那么只需要保证修建方案满足条件即可。

【样例 \(2\) 说明】

显然，在 \(5\) 个点中任意选 \(4\) 个点，都满足核心城市的条件，因此方案数最大为 \(5\)。

【数据规模与约定】

本题一共有 \(50\) 个测试点，每个测试点 \(2\) 分。对于第 \(i\) 个测试点，\(n = 2i - 1\)。

对于每个测试点，有五种可能的结果：

输出格式错误，包括：没有输出最大方案数、没有输出邻接矩阵、输出了多余的信息等。你将无法得到该测试点的任何分数，同时我们无法确定 Special Judge 的返回结果。
没有正确计算最大方案数，即使构造的道路修建方案是正确的。你将得到该测试点 \(0\%\) 的分数（即 \(0\) 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is wrong.”
正确计算了最大方案数，但是构造的道路修建方案不满足条件，包括：邻接矩阵中有不为 \(0\) 或 \(1\) 的数、有自环、有两座城市中没有道路、有多于 \(n\) 条双向道路等。你将得到该测试点 \(50\%\) 的分数（即 \(1\) 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is correct, but your plan breaks the rules.”
正确计算了最大方案数，构造的道路修建方案满足条件但没有将选择 \(4\) 座核心城市的方案数最大化。你将得到该测试点 \(50\%\) 的分数（即 \(1\) 分），Special Judge 将会返回 WA 的结果，同时输出 “The answer is correct, but your plan is wrong.”
正确计算了最大方案数，同时正确构造了道路修建方案。你将得到该测试点 \(100\%\) 的分数（即 \(2\) 分），Special Judge 将会返回 AC 的结果，同时输出 “The answer is correct.”

解题思路

解答代码

P5595 【XR-4】歌唱比赛

题目背景

赛时提醒：本题不提供任何关于样例 4 以及无解的解释。

赛时提醒：本题不提供任何关于输出格式以及 Special Judge 的解释。

赛时提醒：抱歉，本题的 Special Judge 不忽略行末空格，请保证两行中没有多余字符。

赛时提醒：非常抱歉，本题输入数据是 Windows 格式，而非 Linux 格式，所以在末尾的 \n 之前有一个多余的 \r 字符。请使用 scanf 或 cin 读入数据，而非 getline，因为后者会多读入一个 \r。

题目描述

小 X 参加了一场歌唱比赛。

经过一路鏖战，小 X 终于挺进了决赛，他的对手是小 Y。

这场歌唱比赛的冠军是由点赞数决定的，谁的点赞数高，谁就能夺冠。

小 X 和小 Y 依次演唱完自己的最后一首歌曲后，他们最终的点赞数确定了下来。

揭晓冠军的时刻终于到来了，主持人为了增加悬念，决定从小 X 与小 Y 的点赞数的最后一位开始，依次比较。

比如，小 X 的点赞数是 \(37\)，小 Y 的点赞数是 \(28\)。首先比较最后一位，小 X 是 \(7\)，小 Y 是 \(8\)，此时小 Y 暂时领先。再加上前一位，小 X 是 \(37\)，小 Y 是 \(28\)，此时小 X 暂时领先。比较结束，如果我们用 X 代表小 X 暂时领先，Y 代表小 Y 暂时领先，那么可以写下一个字符串 XY。

再比如，小 X 的点赞数是 \(137\)，小 Y 的点赞数是 \(47\)。如果我们再用 Z 表示小 X 与小 Y 的点赞数暂时一样，那么写下的字符串应该为 XYZ。

你作为一个精通 OI 的神仙，自然知道这种比较方式是非常不科学的，这样只是在无端拖延时间罢了，但是你却对最后写下的这个字符串很感兴趣。

现在，你得到了这个最后写下的字符串，你需要构造出一种可能的小 X 与小 Y 的点赞数。

当然，有可能不存在任何一种情况的点赞数满足这个字符串，那么你只需要输出 -1 即可。

为了方便你输出，请用前导零来补足位数。

输入格式

一行一个字符串 \(s\)，表示最后写下的字符串。

输出格式

如果有解：

第一行一个整数，表示小 X 的点赞数。
第二行一个整数，表示小 Y 的点赞数。

如果无解：

一行一个整数 -1。

样例 #1

样例输入 #1

XY

样例输出 #1

1
2

37
28

样例 #2

样例输入 #2

XYZ

样例输出 #2

1
2

137
047

样例 #3

样例输入 #3

ZZZZZZ

样例输出 #3

1 2	000000 000000

样例 #4

样例输入 #4

XYZXYZ

样例输出 #4

-1

提示

本题采用捆绑测试。

Subtask 1（11 points）：\(\text{len}(s) = 1\)。
Subtask 2（42 points）：\(s_i \in \{\texttt{X},\texttt{Y}\}\)。
Subtask 3（21 points）：数据保证有解。
Subtask 4（26 points）：无特殊限制。

对于 \(100\%\) 的数据，\(s_i \in \{\texttt{X},\texttt{Y},\texttt{Z}\}\)，\(1 \le \text{len}(s) \le 10^6\)。