0%

    The Hat是一个快速解释/猜测单词的游戏(类似于Alias)。在这道题中,我们所讨论的是一种游戏变体,即玩家坐在桌旁,每个人都单独玩游戏。

    有 $n$ 个人聚集在一个有 $m$ 张桌子( $n \ge m \times 2$ )的房间里。他们想玩 $k$ 次 The Hat。$k$ 次游戏将在这些桌子上进行,每个人都会玩 $k$ 次游戏。

    这些玩家被分配到这些桌子上。每个玩家可以在不同的桌子上玩,但每局游戏每个玩家只能在一张桌子上玩。

    玩家们希望拥有“公平”的游戏顺序。出于这个原因,他们正在寻找一个方案,要求如下:

    • 在任意一场游戏中,所有桌子都有 $\lfloor \dfrac{n}{m} \rfloor$ 或 $\lceil \dfrac{n}{m} \rceil$ 个玩家。不同的桌子有不同数量的玩家,这些玩家可以玩不同的游戏。

    • 每个玩家都有一个值 $b_i$,它表示第 $i$ 个玩家和 $\lceil \dfrac{n}{m} \rceil$ 个玩家在一张桌子上玩游戏的次数。任意两个玩家的 $b_i$ 值相差不会超过 $1$。换句话说,对于任意两个玩家 $i,j$,满足 $|b_i-b_j| \leq 1$。

    我们称有 $\lfloor \dfrac{n}{m} \rfloor$ 个玩家的桌子为“小桌子”,称有 $\lceil \dfrac{n}{m} \rceil$ 个玩家的桌子为“大桌子”。

    例如,$n=5,m=2,k=2$,那么根据第一项要求,每张桌子上应该有 $2$ 或 $3$ 名玩家。考虑这些游戏顺序:

    • 第一局:玩家 $1,2,3$ 在第一张桌子上玩,玩家 $4,5$ 在第二张桌子上玩。第二局:玩家 $5,1$ 在第一张桌子上玩,玩家 $2,3,4$ 在第二张桌子上玩。这个顺序是不“公平”的,因为 $b_2=2$ (第二名玩家在大桌子上玩了两次),$b_5=0$ (第五名玩家没有在大桌子上玩过游戏)。

    • 第一局:玩家 $1,2,3$ 在第一张桌子上玩,玩家 $4,5$ 在第二张桌子上玩。第二局:玩家 $4,5,2$ 在第一张桌子上玩,玩家 $1,3$ 在第二张桌子。这是一种“公平”的顺序:$b=[1,2,1,1,1]$ (任意两个值的差都不超过 $1$)。

    为 $n$ 个玩家找到所有“公平”的顺序,如果他们玩 $k$ 次游戏,在 $m$ 张桌子上。

    输入格式

    第一行一个整数 $t(1 \leq t \leq 10^4)$,表示数据组数。

    接下来 $t$ 行,每行三个整数 $n,m,k(2 \leq n \leq 2 \times 10^5,1 \leq m \leq \lfloor \dfrac{n}{2} \rfloor,1 \leq k \leq 10^5)$,分别表示玩家个数,桌子个数以及游戏次数。

    保证所有测试用例的 $n \times k$ 之和不超过 $2 \times 10^5$。

    输出格式

    对于每组数据,输出 $k$ 块矩阵,每块矩阵有 $m$ 行。每一块矩阵表示一次游戏,共有 $m$ 张桌子,用一行表示一张桌子,每行先输出这张桌子的玩家数,再输出这些玩家。每组数据

    如果有多个“公平”的顺序,那么输出任意一个。保证至少有一个有效的解。

阅读全文 »

    给你一个正整数 $n$ 和三个长度为 $2\times n$ 的 01 字符串 $s_1,s_2,s_3$。你需要构造一个 01 字符串 $S$,使得:

    • 字符串 $S$ 的长度不能超过 $3\times n$。

    • $s_1,s_2,s_3$ 当中至少有两个字符串是 $S$ 的子序列。

    可以证明一定有解,有多种解时输出任意一种即可。$T$ 组数据。

    $1\leq T\leq10^4;1\leq n,\sum n\leq10^5;$

阅读全文 »

    如果一个长度为 $n$ 的排列 $a$ 满足对于任意整数 $i\in[1,n-1]$ 都有 $a_{i+1}\geq a_i-1$,我们就说这个排列是“几乎有序的”。

    给定 $n,k$,求所有长度为 $n$ 的“几乎有序的”排列中,字典序第 $k$ 小的那个。特别的,如果这样的排列不存在,输出 $-1$。$T$ 组数据。

    $1\leq T\leq10^3;1\leq n,\sum n\leq10^5;1\leq k\leq10^{18};$

阅读全文 »

    数组 $b$ 是数组 $a$ 的一个排列。每次操作只能交换 $b$ 数组的两个元素。一个数组 $b$ 的“难过值”是使 $b$ 复原为 $a$ 的最小操作次数。

    现在给定数组 $a$ ,求出“难过值”最大的数组 $b$(任意一组)。

    $\sum n \leq 2\times 10^5$ 。

阅读全文 »

    有 $t$($1\le t\le 500$)组数据,对于每组数据给出一个长度为 $n$($1\le n\le 20$)的序列 $a$($-20\le a_i\le 20$)。

    可以进行 $k$($0\le k\le 31$)次操作,每次操作任选一组 $i,j$($1\le i,j\le n$),把 $a_i\leftarrow a_i+a_j$,最后使得整个序列单调不减。

    对于每组数据,第一行输出 $k$,之后 $k$ 行输出执行操作的 $i,j$。

阅读全文 »

    给定长为 $n$ 的格子和 $m$ 种颜色。

    Dreamoon 会依次刷这 $m$ 种颜色,对于第 $i$ 种颜色,他会从第 $p_i$ 格开始刷到第 $p_i+l_i-1$ 格。$p_i$ 不能超过 $n-l_i+1$ 或小于 $1$,这样会超出格子。

    您的任务是找出一组 $p_i$,使得 Dreamoon 刷完所有颜色之后每种颜色至少出现了一次,且每个格子都被刷上了颜色。

    $1 \leq m \leq n \leq 10^5$,$1 \leq l_i \leq n$

    翻译 by Meatherm

阅读全文 »

    本题为交互题,使用 IO 交互。

    在你输出一行后,请清空缓冲区:

    • 在 C++ 中,使用 fflush(stdout)cout.flush()

    • 在 Pascal 中,使用 flush(output)

    • 在 Python 中,使用 stdout.flush()

    • 其他语言请自行查阅文档。

    请遵循题目完成交互,发出不合法询问可能会出现 TLE,WA 等问题。


    给定一个长度为 $n$ 且只包含小写字母的字符串 $S$,你需要猜出它。

    一共有 $4$ 种交互方式:

    | 格式 | 允许调用次数 | 限制 | 返回值 | 说明 |

    | :----------: | :----------: | :----------: | :----------: | :----------: |

    | 无 | $1$ | 无 | 一个整数,$n$ 的值。 | 在最开始调用。 |

    | ? 1 i | $26$ | $i$ 为 $[1,n]$ 范围内的整数。 | 一个字符,$S_i$($S$ 的第 $i$ 个字符)。 | 无 |

    | ? 2 l r | $6 \times 10^3$ | $1 \le l \le r \le n$,且 $l,r$ 为整数。 | 一个整数,$S_{l \ldots r}$($S$ 的第 $l$ 至 $r$ 个字符)中不同字符的种数。 | 无 |

    | ! s | $1$ | $s$ 是一个字符串,代表你所认为的 $S$。 | (评测结果——AC 或 WA。) | 最后调用,然后停止交互。 |


    对于 $100\%$ 的数据,$1 \le n \le 10^3$。

阅读全文 »