AT_icpc2014spring_e Parentheses 题解
AT_icpc2014spring_e Parentheses 题解 题目链接:Parentheses 题意: 给定 \(n\) 个字符串 \(s_1,s_2,\cdots s_n\),每个字符串由括号 ( 和 ) 组成。 请问是否可以排列这 \(n\) 个字符串,使得这些字符串拼接后是一个合法的字符串。 合法的字符串定义如下: 空字符串是合法的。 如果 \(A\) 和 \(B\) 是合法的,那么 \(A\) 和 \(B\) 拼接后也是合法的。 如果 \(A\) 是合法的,那么将 \(A\) 放在一对匹配的括号内得到的字符串也是合法的。 任何其他字符串都是不合法的。 例如,()() 和 (()) 是合法的,而 ()) 和 ((() 是不合法的。 输入格式: 输入的第一行包含一个整数 \(n~(1 \leq n \leq 100)\),表示字符串的数量。 接下来 \(n\) 行,每行包含一个字符串 \(s_i~(1 \leq | s_i | \leq 100)\)。\(s_i\) 中的所有字符都是 ( 或 )。 输出格式: 如果可以组成一个合法的字符串,则输出一行 Yes,否...
洛谷P5361 [SDOI2019] 热闹的聚会与尴尬的聚会 题解
洛谷P5361 [SDOI2019] 热闹的聚会与尴尬的聚会 题解 题目链接:P5361 [SDOI2019] 热闹的聚会与尴尬的聚会 题意: 小 Q 的生日快到了,他决定周末邀请一些朋友到他的新房子一起聚会! 他的联系薄上有 \(n\) 位好友,他们两两之间或者互相认识,或者互相不认识。小 Q 希望在周六办一个热闹的聚会,再在周日办一个尴尬的聚会。 一场热闹度为 \(p\) 的聚会请来了任意多位好友,对于每一位到场的好友来说都有至少 \(p\) 位他认识的好友也参加了聚会,且至少对于一位到场的好友来说现场恰好有 \(p\) 位他认识的好友; 一场尴尬度为 \(q\) 的聚会请来了恰好 \(q\) 位好友,且他们两两互不认识。 两场聚会可能有重复的参与者,联系薄上也有可能有某些好友同时缺席了两场聚会。 小 Q 喜欢周六聚会的热闹度 \(p\) 与周日聚会的尴尬度 \(q\) 之间满足:\(\left\lfloor \frac{n}{p+1} \right\rfloor \le q\) 且 \(\left\lfloor \frac{n}{q+1} \right\rfloor ...
CF1379F2 Chess Strikes Back (hard version) 题解
CF1379F2 Chess Strikes Back (hard version) 题解 题目链接:Chess Strikes Back (hard version) 题意: 请注意,简单版本和困难版本之间的区别在于,困难版本中不可用的格子可以再次变为可用,而简单版本中则不可以。只有在所有版本都解决后,才能进行破解。 伊尔达和伊万对国际象棋感到厌倦,但他们非常喜欢棋盘,于是他们发明了一种新游戏。棋盘是一个 \(2n \times 2m\) 的棋盘:它有 \(2n\) 行,\(2m\) 列,如果第 \(i\) 行和第 \(j\) 列的格子满足 \(i+j\) 是偶数,那么该格子是白色,否则是黑色。 游戏进行如下:伊尔达将棋盘上的某些白色格子标记为不可用,并要求伊万在剩余的白色格子上放置 \(n \times m\) 个国王,使得没有国王相互攻击。一个国王可以攻击另一个国王,如果它们位于共享一个边或一个角的相邻格子上。 伊尔达想探索不同的格子组合。最初所有格子都标记为可用,然后他有 \(q\) 个查询。在每个查询中,他要么将一个格子标记为不可用,要么将之前不可用的格子标记为可用。...
洛谷P2312 [NOIP2014 提高组] 解方程 题解
洛谷P2312 [NOIP2014 提高组] 解方程 题解 题目链接:P2312 [NOIP2014 提高组] 解方程 题意: 已知多项式方程: \[ a_0+a_1x+a_2x^2+\cdots+a_nx^n=0 \] 求这个方程在 \([1,m]\) 内的整数解(\(n\) 和 \(m\) 均为正整数)。 输入格式: 输入共 \(n + 2\) 行。 第一行包含 \(2\) 个整数 \(n, m\) ,每两个整数之间用一个空格隔开。 接下来的 \(n+1\) 行每行包含一个整数,依次为 \(a_0,a_1,a_2\ldots a_n\) 。 输出格式: 第一行输出方程在 \([1,m]\) 内的整数解的个数。 接下来每行一个整数,按照从小到大的顺序依次输出方程在 \([1,m]\) 内的一个整数解。 数据范围: \(0<n\le 100,|a_i|\le 10^{10000},a_0\ne 0,m<10^6\) 。 这个题有点哈希的味道。注意到对于质数 \(p\) , \[ a_0+a_1x+a_2x^2+\cdots+a_nx^n\equiv 0 \pmod...
洛谷P5283 [十二省联考 2019] 异或粽子 题解
洛谷P5283 [十二省联考 2019] 异或粽子 题解 题目链接:P5283 [十二省联考 2019] 异或粽子 题意: 小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。 小粽面前有 \(n\) 种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编号为 \(1\) 到 \(n\)。第 \(i\) 种馅儿具有一个非负整数的属性值 \(a_i\)。每种馅儿的数量都足够多,即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 \(k\) 个粽子。 小粽的做法是:选两个整数数 \(l\), \(r\),满足 \(1 \le l \le r \le n\),将编号在 \([l, r]\) 范围内的所有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的异或和。(异或就是我们常说的 xor 运算,即 C/C++ 中的 ˆ 运算符或 Pascal 中的 xor 运算符) 小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的 粽子。 小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧! 输入格式: 第一行两个正整数 \(n\...
CF995E Number Clicker 题解
CF995E Number Clicker 题解 题目链接:Number Clicker 题意: 有三种操作: 令 \(u \gets u + 1 \pmod p\) 令 \(u \gets u - 1 \pmod{p}\) 令 \(u \gets u^{p-2} \pmod{p}\) 给定 \(u,v\) 和质数 \(p\) ,构造一种方案让 \(u\) 变成 \(v\) ,操作数不超过 \(200\) 次。 输入格式: 一行, \(u,v,p\) 。 输出格式: 第一行输出操作次数,第二行输出每次操作的序号 \(c_i(1\le c_i \le 3)\) 。 数据范围: \(0 \le u,v \le p - 1,~3 \le p \le 10^9 + 9\) 。 直接 bfs 的话肯定是过不了的,不过因为这里的操作都是可逆的,所以我们可以尝试双向 bfs 。 因为 \(u^{p-2} \bmod{p}\) 的值难以预测,所以 \(u \gets u^{p-2} \pmod{p}\) 这个操作可以近似看作随机的。 由于我们的算法可以看作在 \([0,p-1]\) 随机...
AT_agc006_e [AGC006E] Rotate 3x3 题解
AT_agc006_e [AGC006E] Rotate 3x3 题解 题目链接:AT_agc006_e [AGC006E] Rotate 3x3 题意: 有一个 \(3\) 行 \(N\) 列的初始矩阵,\((i,j)\) 位置的数为 \(i+3\times j-3\)。 然后有一个这样的操作:选择一个 \(3 \times 3\) 的子矩阵,将这个子矩阵旋转 \(180°\)(具体见下面的图)。 现在给出一个 \(3\) 行 \(N\) 列的矩阵(矩阵中的数各不相同) 问能否通过若干次上述操作将初始矩阵变为给定的矩阵。 输入格式: 第一行给出 \(n\) ,然后三行共 \(3 \times n\) 个数表示初始矩阵。 输出格式: 一行,答案。 数据范围: \(1\le n \le 10^5,~1 \le a_{i,j} \le 3n\) 。 看题解区好多 \(\mathcal{O}(n)\) 的神仙解法,我来讲一讲好理解的 \(\mathcal{O}(n \log n)\) 解法吧。 首先判掉明显不对的情况,这样每一行就可以看作一个数,并且有正负之分 注意到一次旋转只...
AT_agc003_c [AGC003C] BBuBBBlesort! 题解
AT_agc003_c [AGC003C] BBuBBBlesort! 题解 题目链接:AT_agc003_c [AGC003C] BBuBBBlesort! 题意: 给定一个序列 \(a\),元素两两不同,可以使用两种操作。 翻转相邻两个元素。 翻转相邻三个元素。 问怎么操作使这个序列变成升序,并使操作一的次数最少。输出这个最少的次数。 输入:\(n\) 和 \(a_i\) 。输出:答案。 数据范围: \(1\le n \le 10^5,~0 \le a_i \le 10^9\) 。 先离散化一下(不用去重),这样权值就是正确的编号。 可以发现,只使用操作二可以将奇数位&偶数位的数分别排序 但是在奇数位上的数编号可能不是偶数, 这种情况必须用一下操作一,把奇数位和偶数位上错位的两个憨憨交换一下。 时间复杂度 \(\mathcal{O}(n \log n)\) 代码: #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3...
洛谷P4691 Nephren Ruq Insania & P3934 [Ynoi2016] 炸脖龙 I 题解
洛谷P4691 Nephren Ruq Insania & P3934 [Ynoi2016] 炸脖龙 I 题解 本题 P4691 Nephren Ruq Insania 和 P3934 [Ynoi2016] 炸脖龙 I 完全一致。 题目链接:P4691 Nephren Ruq Insania(本题没有数据,需要在 P3934 提交) 题意: 奈芙莲·卢可·印萨尼亚 (Nephren-Ruq-Insania) 威廉想要救下奈芙莲,但是他自己也已经处于崩溃的边缘。 冥冥之中他想起了曾经学习过的一种魔法。在这最后一刻,或许已经是唯一的办法了。 这种魔法操作的对象是一个咒语组成的序列,每一个单独的咒语拥有自己的法力值。 威廉需要不断地按照之前的记忆,对某一段区间的法力值加上一个数,或者求出某一段区间的法咒共鸣。 法咒共鸣具体而言是这么计算的: 对于区间 \([l,r]\) , 查询 \[ \mathrm{pow}(a_l,\,\mathrm{pow}(a_{l+1},\,\mathrm{pow}(a_{l+1},\,\cdots))) \bmod p \] 一直到 \(\ma...
洛谷P5043 【模板】树同构([BJOI2015]树的同构) 题解
洛谷P5043 【模板】树同构([BJOI2015]树的同构) 题解 题目链接:P5043 【模板】树同构([BJOI2015]树的同构) 题意: 树是一种很常见的数据结构。 我们把 \(N\) 个点,\(N-1\) 条边的连通无向图称为树。 若将某个点作为根,从根开始遍历,则其它的点都有一个前驱,这个树就成为有根树。 对于两个树 \(T_1\) 和 \(T_2\),如果能够把树 \(T_1\) 的所有点重新标号,使得树 \(T_1\) 和树 \(T_2\) 完全相同,那么这两个树是同构的。也就是说,它们具有相同的形态。 现在,给你 \(M\) 个无根树,请你把它们按同构关系分成若干个等价类。 输入格式: 第一行,一个整数 \(M\)。 接下来 \(M\) 行,每行包含若干个整数,表示一个树。第一个整数 \(N\)表示点数。接下来 \(N\) 个整数,依次表示编号为 \(1\) 到 \(N\) 的每个点的父亲结点的编号。根节点父亲结点编号为 \(0\)。 输出格式: 输出 \(M\) 行,每行一个整数,表示与每个树同构的树的最小编号。 数据范围: \(1\leq N,M\leq...
洛谷P5926 [JSOI2009] 面试的考验 题解
洛谷P5926 [JSOI2009] 面试的考验 题解 题目链接:P5926 [JSOI2009] 面试的考验 题意: 求区间最接近且不相等的两数之差的绝对值。最接近指数值上最接近。 输入格式: 第一行输入两个整数 \(N,Q\),分别代表序列的长度和询问的个数。 第二行包含 \(N\) 个由一个空格分开的正整数,代表了整个序列,从左向右依次编号为 \(A_1, A_2……A_n\)。 接下来 \(Q\) 行,每行两个整数 \(i,j\) 表示了一个询问区间。 输入数据保证 \(1\le i<j\le N\)。 输出格式: 对于每一个询问输出一行,为所问区间中最接近两个数之差的绝对值。 数据范围: \(1\le N,Q\le10^5,1\le A_i\le10^9\)。数据为全部纯随机生成。 思路是考察对答案有贡献的点对。 对于 \(i < j,~a_i < a_j\) 的点对,其中 \(i\) 固定。 如果 \(x\) 是 \(i\) 之后对答案有贡献的第一个点,则 \(a_x \in [a_i + 1, +\infty)\) 且 \(x\) 是 \([i...
note[19]
note[19] 题:问 \[ \mathcal{O}(\log (n!)) \] 解: \[ \begin{aligned} \mathcal{O}(\log (n!)) &= \mathcal{O}\left(\int_1^n \log x \, \mathrm{d} x\right) \\[8pt] &= \mathcal{O}\left( {(x-1)\log x\Big|_1^n} \right) \\[8pt] &= \mathcal{O}(n \log n) \end{aligned} \] 这里用到了 \(\int \log x \, \mathrm{d}x\) 的公式 \[ \int \log x \, \mathrm{d}x = (x - 1) \log x + C \] 证明: 考虑分部积分法 \[ \int u \, \mathrm{d} v = uv - \int v \, \mathrm{d} u \] 其中 \(u = \log x,~ \mathrm{d}u = \frac{1}{x}\mathrm{d}x,~v = x,~...

![洛谷P5361 [SDOI2019] 热闹的聚会与尴尬的聚会 题解](/qwq/img/p136.webp)

![洛谷P2312 [NOIP2014 提高组] 解方程 题解](/qwq/img/p112.webp)
![洛谷P5283 [十二省联考 2019] 异或粽子 题解](/qwq/img/p80.webp)

![AT_agc006_e [AGC006E] Rotate 3x3 题解](/qwq/img/p40.webp)
![AT_agc003_c [AGC003C] BBuBBBlesort! 题解](/qwq/img/p146.webp)
![洛谷P4691 Nephren Ruq Insania & P3934 [Ynoi2016] 炸脖龙 I 题解](/qwq/img/p148.webp)
![洛谷P5043 【模板】树同构([BJOI2015]树的同构) 题解](/qwq/img/p72.webp)
![洛谷P5926 [JSOI2009] 面试的考验 题解](/qwq/img/p180.webp)
![note[19]](/qwq/img/p140.webp)

![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

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