Q779’s Blog

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 题解 题目链接：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] 邮局 加强版 加强版 题意： 高速公路旁边有 \(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\)，且 \...

洛谷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 题解 题目链接：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] 黑白瓷砖 题意： 输入格式： 一行，一个正整数 \(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 [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] 情侣？给我烧了！（加强版） 题意： 有 \(n\) 对情侣来到电影院观看电影。在电影院，恰好留有 \(n\) 排座位，每排包含 \(2\) 个座位，共 \(2n\) 个座位。 现在，每个人将会随机坐在某一个位置上，且恰好将这 \(2n\) 个座位坐满。 如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。 你的任务是求出共有多少种不同的就坐方案满足恰好有 k 对情侣是和睦的。 两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 \((2n)!\) 种不同的就坐方案。 由于结果可能较大，因此输出对 \(998244353\) 取模的结果。 输入格式： 输入包含多组数据。 输入的第 \(1\) 行包含 \(1\) 个正整数 \(T\)，表示数据的组数。 接下来 \(T\) 行，每行包含 \(2\) 个正整数 \(n,k\)。 输出格式： 输出共 \(T\) 行。 对于每组输入数据，输出共 \(1\) 行，包含 \(1\) 个整...

CF1333E Road to 1600 题解 题目链接：Road to 1600 题意： 埃戈尔希望在著名的国际象棋门户网站 ChessForces 上达到 1600 分的评分，他需要你的帮助！ 在你开始解决问题之前，埃戈尔想提醒你国际象棋棋子的移动方式。国际象棋中的车沿直线方向上下左右移动，可以移动任意多的格子，并且可以随时停下来。皇后可以在所有垂直和对角线方向上任意距离移动。你可以参考下面的示例图。 为了达到目标，埃戈尔应该研究下一个主题： 有一个 \(N \times N\) 的棋盘。棋盘的每个格子里都有一个从 \(1\) 到 \(N^2\) 的数字，且所有格子中的数字都是不同的。 一开始，有一个棋子站在编号为 \(1\) 的格子上。注意，这个格子已经被视为访问过了。之后的每一步移动遵循以下规则： 在所有尚未访问过且棋子可以通过一步到达的格子中，它会前往编号最小的那个格子。 如果所有可到达的格子都已经访问过但仍有未访问的格子，那么棋子会传送到尚未访问的编号最小的格子。如果发生此步骤，棋子会支付 1 个 vun 的费用。 如果所有格子都已访问，过程停止。 埃戈尔应该...

SP2124 FCTRL4 - Last Non-Zero Digit of Factorials 题解 题目链接：FCTRL4 - Last Non-Zero Digit of Factorials 题意： 多组数据，每次给出一个正整数 \(n(n \le 10^{100})\) ，求 \(n!\) 最后一位非零数字。 例如 \(5! = 1\times 2 \times 3 \times 4 \times 5 = 120\) ，它的最后一位非零数字是 \(2\) 。 好像我是这题代码最短的，只有 202B 。 记 \(a = \left\lfloor\frac{n}{5}\right\rfloor,~b = n - 5\times \left\lfloor\frac{n}{5}\right\rfloor\) ，并记 \(L(n)\) 为 \(n!\) 最后一位非 \(0\) 数字，则 \[ \begin{aligned} L(n) &= 5\times 10\times 15\times \cdots\times (1 \times 2 \times 3 \tim...

洛谷P5319 [BJOI2019] 奥术神杖 题解 题目链接：P5319 [BJOI2019] 奥术神杖 题意： Bezorath 大陆抵抗地灾军团入侵的战争进入了僵持的阶段，世世代代生活在 Bezorath 这片大陆的精灵们开始寻找远古时代诸神遗留的神器，试图借助神器的神秘力量帮助她们战胜地灾军团。 在付出了惨痛的代价后，精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后，神杖上镶嵌的奥术宝石已经残缺，神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石，并重金悬赏天下能工巧匠修复这件神杖。 你作为神术一脉第五百零一位传人，接受了这个艰巨而神圣的使命。 神杖上从左到右镶嵌了 \(n\) 颗奥术宝石，奥术宝石一共有 \(10\) 种，用数字 0123456789 表示。有些位置的宝石已经残缺，用 . 表示，你需要用完好的奥术宝石填补每一处残缺的部分（每种奥术宝石个数不限，且不能够更换未残缺的宝石）。古老的魔法书上记载了 \(m\) 种咒语 \((S_i,V_i)\) ，其中 \(S_i\) 是一个...

洛谷P4094 [HEOI2016/TJOI2016] 字符串 题解 题目链接：P4094 [HEOI2016/TJOI2016] 字符串 题意： cxy 过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 \(n\) 的字符串 \(s\)，和 \(m\) 个问题。cxy 必须正确回答这 \(m\) 个问题，才能打开箱子拿到礼物，升职加薪，出任 CEO，嫁给高富帅，走上人生巅峰。 每个问题均有 \(a,b,c,d\) 四个参数，问你子串 \(s[a..b]\) 的所有子串和 \(s[c..d]\) 的最长公共前缀的长度的最大值是多少？cxy 并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？ 输入格式： 输入的第一行有两个正整数 \(n,m\)，分别表示字符串的长度和询问的个数。 接下来一行是一个长为 \(n\) 的字符串。接下来 \(m\) 行，每行有 \(4\) 个数 \(a,b,c,d\)，表示询问 \(s[a..b]\) 的所有子串和 \(s[c..d]\) 的最长公共前缀的最大值。 输出格式： 对于每一次询问，输...