洛谷P2178 [NOI2015] 品酒大会 题解
洛谷P2178 [NOI2015] 品酒大会 题解 题目链接:P2178 [NOI2015] 品酒大会 题意: 一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战 两个环节,分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项,吸引了众多品酒师参加。 在大会的晚餐上,调酒师 Rainbow 调制了 \(n\) 杯鸡尾酒。这 \(n\) 杯鸡尾酒排成一行,其中第 \(n\) 杯酒 (\(1 ≤ i ≤ n\)) 被贴上了一个标签 \(s_i\) ,每个标签都是 \(26\) 个小写 英文字母之一。设 \(\text{str}(l, r)\) 表示第 \(l\) 杯酒到第 \(r\) 杯酒的 \(r - l + 1\) 个标签顺次连接构成的字符串。若 \(\text{str}(p, p_0) = \text{str}(q, q_0)\),其中 \(1 \le p \le p_0 \le n\), \(1 \le q \le q_0 \le n\), \(p \ne q\),\(p_0-p+1 = q_0 - q + 1 = r\) ,则称第 \(p\) 杯酒与第 \...
CF1227F2 Wrong Answer on test 233 (Hard Version) 题解
CF1227F2 Wrong Answer on test 233 (Hard Version) 题解 题目链接:CF1227F2 Wrong Answer on test 233 (Hard Version) 题意: qwq 要参加一场考试,这场考试有 \(n\) 道选择题,每个选择题有 \(k\) 个选项。 但是 qwq 昨天玩某中文二字英文七字游戏玩过头了,导致她这次考试时十分困倦以至于居然填错了答题卡! 具体地,qwq 错误地将第 \(i\) 道选择题的答案填到第 \((i \bmod n) + 1\) 道题去了。 不过她是怎么做到将第 \(n\) 道题的答案填到第 \(1\) 道去的?果然是玩【数据删除】玩的。 显然,此时 qwq 非常焦虑,但是她不记得自己每道题原来填了什么选项了 现给出每道题的答案 \(h_i\) ,请帮助 qwq 计算有多少种可能的初始答案,使得错误填涂后比原来正确的多了。 输入格式: 第一行给出 \(n,k~(1 \le n \le 2\times 10^5,\,1\le k \le 10^9)\) 。 第二行给出 \(n\) 个数 \(h_1...
CF1370F2 The Hidden Pair (Hard Version) 题解
CF1370F2 The Hidden Pair (Hard Version) 题解 题目链接:The Hidden Pair (Hard Version) 题意: 这是一道交互题,且本题有多组数据。 已知一棵 \(n\) 个顶点的树(边集已知),其中有两个不同的顶点被暗中做了标记。 你现在需要通过若干次询问,猜出两个被标记顶点的编号。 一次询问的格式为 ? c x1 x2 ... xc,表示向交互库请求关于 \(x_1,x_2,\cdots,x_c\) 这 \(c(c \le n)\) 个点的信息。 对于一次询问,交互库的返回格式为 x d,表示在询问的集合中,到两个被标记点的距离之和最小的点是 \(x\),这个最小值为 \(d\)。如果有多个最小值点,\(x\) 的值可能是其中任意一个。 如果已经知晓答案,请用 ! x y 的格式来输出你的答案,任意顺序均可。在这之后,你会收到一个字符串 Correct 或者 Incorrect,代表你的猜测是否正确。如果收到了 Incorrect,请立即终止程序,否则请继续处理下一组数据。 对于每组数据,请你在不超过 \(11\) 次询问...
AT_agc028_b [AGC028B] Removing Blocks 题解
AT_agc028_b [AGC028B] Removing Blocks 题解 题目链接:AT_agc028_b [AGC028B] Removing Blocks 题意: 有 \(N\) 块砖块排列成一行,从左到右编号为 \(1\) 到 \(N\) 。每一个砖块都有一个重量,砖块 \(i\) 的重量为 \(A_i\)。 qry 会对这些 \(N\) 个砖块执行如下操作: 选择一个还没有被移除的砖块,然后移除它。这个操作的代价是与被移除的砖块相邻的砖块(包括它自己)的重量之和。我们定义两块砖 \(x\) 和 \(y ~(x \leq y)\) 是相邻的,当且仅当对于所有 \(z ~(x \leq z \leq y)\) ,砖块 \(z\) 仍然没有被移除。 有 \(N!\) 种移除砖块的可能顺序。你需要对于所有可能的顺序计算出移除完所有 \(N\) 块砖块的代价,并计算这些代价的和。由于答案可能非常大,答案需要对 \(10^9+7\) 取模。 数据范围: \(1 \le n \le 10^5,~1 \le A_i \le 10^9\) 。 这题它本可以问你期望是什么的,但是...
CF1290D Coffee Varieties (hard version) 题解
CF1290D Coffee Varieties (hard version) 题解 题目链接:Coffee Varieties (hard version) 题意: 这是一道交互题。 给定正整数 \(n,k~(1 \le k \le n \le 1024)\) ,保证 \(n,k\) 是 \(2\) 的整数次幂,并且 \(\frac{3n^2}{2k}\le 15000\)。 有 \(n\) 个数 \(a_1,a_2,\dots,a_n\) 初始未知,有一队列 \(Q\) 初始为空。 每次查询你可以给出一个编号 \(x\) ,交互系统会依次进行如下操作: 告诉你当前 \(Q\) 中是否有与 \(a_x\) 相同的数 将 \(a_x\) 放入 \(Q\) 的尾部 如果此时 \(Q\) 中元素多于 \(k\) 个,弹出队首元素 此外,你还可以重置队列,这将使得 \(Q\) 中所有元素被弹出。重置队列不算入查询次数。 现请你求出 \(a_1,a_2,\dots,a_n\) 中有多少个不同的数。 要求你的查询次数不超过 \(\frac{3n^2}{2k}\) ,重置次数不超过 \...
CF653F Paper task 题解
CF653F Paper task 题解 题目链接:Paper task 题意: 给定一个长度为 \(n\) 的括号串,问有多少种本质不同的合法括号子串。 输入:长度 \(n\) 和字符串 \(S\) ,\(S\) 仅包含 ( 和 ) 。输出:答案。数据范围:\(1\le n\leq 5\times 10^5\) 。 考虑怎么算合法子串。把 ( 和 ) 分别看作 \(1\) 和 \(-1\) ,记 \(d_i\) 为他们的前缀和。 那么一个任意字符串 \(S\) 是合法的当且仅当 \(\forall i(1 < i \le |S|) ,~d_i \ge d_1 - 1\) 且 \(d_{|S|} = d_1 - 1,~d_1 = 1\) 。 对于固定的 \(i\) ,考虑二分合法的长度,用 ST 表维护区间 min ,这样可以找到最远的 \(r\) 使得 \(S[i..r]\) 合法 现在需要统计 \([i,r]\) 里有多少个点的 \(d\) 刚好等于 \(d_i-1\) ,这个可以用 vector 维护每个值的位置二分得到。 那么如何求出本质不同的子串呢?思路有点类...
洛谷P6246 [IOI2000] 邮局 加强版 加强版 题解
洛谷P6246 [IOI2000] 邮局 加强版 加强版 题解 题目链接:P6246 [IOI2000] 邮局 加强版 加强版 题目描述 高速公路旁边有 \(n\) 个村庄。高速公路表示为整数轴,每个村庄的位置用单个整数坐标标识。两个位置之间的距离是其整数坐标差的绝对值。 现在要建立 \(m\) 个邮局,邮局将建在一些,但不一定是所有的村庄中。为了建立邮局,应选择他们建造的位置,使每个村庄与其最近的邮局之间的距离总和最小。 你要编写一个程序,已知村庄的位置和邮局的数量,计算每个村庄和最近的邮局之间所有距离的最小可能的总和。 输入格式 第一行包含两个整数,分别表示村庄的数量 \(n\) 和邮局的数量 \(m\)。 第二行共 \(n\) 个整数,表示每个村庄的坐标,第 \(i\) 个整数表示第 \(i\) 个村庄的坐标 \(a_i\)。 输出格式 输出一行一个整数表示答案。 数据范围 保证最终答案不超过 \(10^9\)。 保证 \(1 \leq m \leq n \leq 5 \times 10^5\),\(0 \leq a_i \leq 2\times 10^6\),且 \(a...
洛谷P10596 & BZOJ2839 集合计数 题解
洛谷P10596 & BZOJ2839 集合计数 题解 题目链接:P10596 BZOJ2839 集合计数 题意: 一个有 \(N\) 个元素的集合有 \(2^N\) 个不同子集(包含空集) 现在要在这 \(2^N\) 个集合中取出若干集合(至少一个),使得它们的交集的元素个数为 \(K\) 求取法的方案数,答案模 \(10^9+7\)。 输入格式: 一行两个整数 \(N,K\)。 输出格式: 一行一个整数表示答案。 数据范围: \(1\leq N\leq 10^6,~0\leq K\leq N\)。 先选出 \(k\) 个元素为交集,然后在剩下的 \(2^{n-k}\) 个集合里选 \(i\) 个和它并上 于是列出一个感觉也不太对的式子 \[ \binom{n}{k}\sum_{i=1}^{2^{n-k}}\binom{2^{n-k}}{i} = \binom{n}{k} \left(2^{2^{n-k}}-1\right) \] 由于我们选的集合不能有交集,所以上面这个东西多算了有交集的情况。 看上去直接算也不好算,考虑容斥。那么钦定后选的集合交集至少为 \(i\...
SP422 TRANSP2 - Transposing is Even More Fun 题解
SP422 TRANSP2 - Transposing is Even More Fun 题解 题目链接:TRANSP2 - Transposing is Even More Fun 题意: 假设你有一个 \(2^a\times 2^b\) 的数组。它在内存中以通常的方式按顺序存储,先是第一行的值,然后是第二行的值,依此类推。你希望对它进行转置,但没有任何额外的内存。你唯一能执行的操作是交换两个内存单元的内容。进行转置所需的最少操作数是多少? 输入格式: 输入的第一行包含测试用例的数量 \(c~(1 \le c \le 4\times 10^6)\) 。 每个测试用例由两个整数 \(a\) 和 \(b\) 组成 \((0 \le a + b \le 1\times 10^6)\) 。 输出格式: 对于每个测试用例,输出转置一个 \(2a\times 2b\) 数组所需的最少交换次数。 由于这个数可能非常大,你需要输出它除以 \(1000003\) 的余数(是的,\(1000003\) 是一个质数:) )。 我们可以把答案看作将一个序列转化为排列 \(p=0,1,\cdots\...
洛谷P2561 [AHOI2002] 黑白瓷砖 题解
洛谷P2561 [AHOI2002] 黑白瓷砖 题解 题目链接:P2561 [AHOI2002] 黑白瓷砖 题意: 输入格式: 一行,一个正整数 \(n(n \leq 20)\) 。 输出格式: 以一行的形式输出问题的解 \(s\) (解的位数不超过 \(200\) 位)。 这个题面也是有点难绷,而且洛谷上连最后那张图片都没贴。 显然这道题考察了 Pólya 定理,搬个介绍过来吧(不会这个还做这道题?)。 \(\mathcal{Part}\ 1\) Burnside 引理 设 \(A,B\) 为有限集合,\(X\) 为一些从 \(A\) 到 \(B\) 的映射组成的集合。 \(G\) 是 \(A\) 上的置换群,且 \(X\) 中的映射在 \(G\) 中的置换作用下封闭。 \(X / G\) 表示 \(G\) 作用在 \(X\) 上产生的所有等价类的集合,则 \[ |X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^g\right| \] 其中 \(X^g=\{x \mid x \in X,~g(x)=x\}\) 。 Pólya 定理...
洛谷P2252 【模板】威佐夫博弈 题解
洛谷P2252 【模板】威佐夫博弈 题解 题目链接:P2252 [SHOI2002] 取石子游戏|【模板】威佐夫博弈 题意: 有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。 游戏规定,每次有两种不同的取法: 一是可以在任意的一堆中取走任意多的石子; 二是可以在两堆中同时取走相同数量的石子。 最后把石子全部取完者为胜者。 现在给出初始的两堆石子的数目,你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。 输入格式: 输入共一行。 第一行共两个数 \(a, b\),表示石子的初始情况。 输出格式: 输出共一行。 第一行为一个数字 \(1,0\) 或 \(-1\),如果最后你是胜利者则为 \(1\);若失败则为 \(0\);若结果无法确定则为 \(-1\)。 数据范围: 对于 \(100\%\) 的数据满足 \(0\le a, b \le 10^9\)。 定义后手必胜态为奇异局势(什么鬼名字?),容易列举出一些这样的状态 \[ \begin{aligned} & 0:(0,0) \\[6pt]& 1:(1,2) \\[6pt]& 2:...
洛谷P4931 [MtOI2018] 情侣?给我烧了!(加强版) 题解
洛谷P4931 [MtOI2018] 情侣?给我烧了!(加强版) 题解 题目链接:P4931 [MtOI2018] 情侣?给我烧了!(加强版) 题意: 有 \(n\) 对情侣来到电影院观看电影。在电影院,恰好留有 \(n\) 排座位,每排包含 \(2\) 个座位,共 \(2n\) 个座位。 现在,每个人将会随机坐在某一个位置上,且恰好将这 \(2n\) 个座位坐满。 如果一对情侣坐在了同一排的座位上,那么我们称这对情侣是和睦的。 你的任务是求出共有多少种不同的就坐方案满足恰好有 k 对情侣是和睦的。 两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现,一共会有 \((2n)!\) 种不同的就坐方案。 由于结果可能较大,因此输出对 \(998244353\) 取模的结果。 输入格式: 输入包含多组数据。 输入的第 \(1\) 行包含 \(1\) 个正整数 \(T\),表示数据的组数。 接下来 \(T\) 行,每行包含 \(2\) 个正整数 \(n,k\)。 输出格式: 输出共 \(T\) 行。 对于每组输入数据,输出共 \(1\) 行,包含 \(1\) 个整...
![洛谷P2178 [NOI2015] 品酒大会 题解](/qwq/img/p202.webp)


![AT_agc028_b [AGC028B] Removing Blocks 题解](/qwq/img/p136.webp)

![洛谷P6246 [IOI2000] 邮局 加强版 加强版 题解](/qwq/img/p186.webp)


![洛谷P2561 [AHOI2002] 黑白瓷砖 题解](/qwq/img/p214.webp)

![洛谷P4931 [MtOI2018] 情侣?给我烧了!(加强版) 题解](/qwq/img/p165.webp)
![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)