曹轩鸣的博客

比赛传送门 A. My Last ABC Problem 题意：有一个只含 ABC 字符串 sss，每次询问一段区间 [l,r][l,r][l,r]，问至少需要多少次操作能将这段区间变得完全相同。每次操作可以选一段区间 [a,b][a,b][a,b] 和一个 A,B,C{A,B,C}A,B,C 的排列，将这段区间内按照排列描述的方式进行替换。 很容易想到考虑连续段，以下描述中一个元素均表示一个连续段。可以发现，每次操作的元素个数要么 −1-1−1 要么 −2-2−2，所以考虑什么时候可以 −2-2−2。我们发现，当某个元素的左右两边相同时，可以直接将这个元素改为和左右两边相同，此时可以

描述：对于任意正整数 nnn，在 (n,2n](n,2n](n,2n] 间至少存在一个质数 ppp。 首先有一个引理： 对于任意 x>1x>1x>1，∏p≤xp≤4x−1\prod\limits_{p\le x}p\le 4^{x-1}p≤x∏​p≤4x−1。 证明： 考虑数学归纳法，假设对于 x∈{2,3,⋯,n}x\in\{2,3,\cdots,n\}x∈{2,3,⋯,n} 成立，证明其对于 n+1n+1n+1 成立。 分类讨论奇偶性。如果 nnn 为奇数，则显然成立，因为此时 ∏p≤np=∏p≤n+1p\prod\limits_{p\le n}p=\prod\limits_{p

D. Factorial and Multiple 题意：给你一个 kkk，求最小的 nnn 使得 k∣n!k|n!k∣n!。k≤1012k\le 10^{12}k≤1012。 做法一 考虑将 kkk 分解质因数，对于每项 prp^rpr，都要求 n!n!n! 中含有至少 rrr 次 ppp。由于 n!n!n! 的质因数单调增加，所以可以二分。对于检查某个 nnn 是否满足条件，只需要看 nnn 以内有多少个 ppp 的倍数 + nnn 以内有多少个 p2p^2p2 的倍数……以此类推。对于每个 prp^rpr 取对 nnn 限制最大的那个即可，最后可能剩下的一个 >n>\sqrt{n}>

从平均数说起 我们都知道 nnn 个数的平均数表示为： a1+a2+a3+⋯ann\frac{a_1+a_2+a_3+\cdots a_n}{n}na1​+a2​+a3​+⋯an​​ 这种最常见的平均数被称为“算术平均数”（Arithmetic Mean）。还有一种常用的平均数为“几何平均数”（Geometric Mean），计算公式如下： a1a2a3⋯ann\sqrt[n]{a_1 a_2 a_3\cdots a_n}na1​a2​a3​⋯an​​ 其几何意义为：考虑一个 nnn 维“长方体”，各边长度用 aaa 数组表示，则几何平均数为“与其体积相等的 nnn 维正方体的边长”。

题目传送门 题意：有一个矩阵，每个格子为黑色或白色。你需要向白色格子中填 1∼91\sim 91∼9 的整整睡。从某一个黑色格子的右侧往右连续的一段极长的白色格子被称为一个 run，往下连续一段同理。在每个 run 的开始位置会标记出该 run 的数字和。除此之外要求每个 run 内填的数互不相同。求一组合法解。n,m≤6n,m\le 6n,m≤6。 首先想到朴素的搜索，搜索每个格子填的数，在每个 run 的末尾进行一次 check。过程中维护 vis 和当前 run 填的数之和，进行可行性剪枝。这种做法显然无法通过此题。 首先考虑强化可行性剪枝。常规的可行性剪枝为，假设后面全填从 11

比赛传送门 C. RANDOM 题意：给你两个 01 矩阵 S,TS,TS,T，问是否可以将 SSS 以列为单位重新排列得到 TTT。 判断 S,TS,TS,T 的每列是否可以一一对应即可 做法一 以列为单位提取成字符串，S,TS,TS,T 分别排序比较即可。 By cxm1024 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include using namespace std; string s[400010],t[400010]; s

阅读全文 »

题目传送门 题意：在一个矩阵上选中了若干个格子，保证连通。你需要在这些格子中填数，使得：每行每列不能重复，且这些数进行给定运算（可以认为只有加法和乘法）的结果为给定的数值。求填数的方案数。 首先考虑朴素的搜索。将选中的格子按行列排序（顺序剪枝），依次考虑每个格子填的数，中途维护每行每列的数字使用情况（可以状压），进行可行性剪枝。这个做法虽然可以通过本题，但跑得非常慢且需要卡常。 考虑进一步优化。我们发现，“运算结果固定”这条限制与数字摆放顺序无关，而只与使用的数字集合有关；“每行每列不重复”这条限制只与数字摆放顺序和位置之间是否相同有关，而与具体数字无关。于是这两部分可以分开考虑。 假

题目传送门 题意：有一个 n×mn\times mn×m 的矩阵，用尽可能多的“T”形覆盖它（可以旋转），使得它们之间互不重叠。 可以搜索，每次考虑当前位置放哪个角度的“T”形，转移到下一个位置。主要进行最优性剪枝：如果当前填放的数量加上之后的极大值（剩余格子数 ÷5\div 5÷5）则直接返回。还有一个启发性剪枝，即左上角一定要放一个正着的“T”或往左歪的“T”。 最优性剪枝还有另一种形式：记录前 iii 行能填的最大数量 best[i]best[i]best[i]，每次填完一行后如果和 best[i]best[i]best[i] 差的过大则返回。 第一种 By cxm1024 1

题目传送门 题意：有 nnn 支球队，每两支球队之间都会进行一场较量，赢者积 333 分，输者积 000 分，如果平局则各积 111 分。给出每支球队的最终积分，求方案数。n≤8n\le 8n≤8。 首先考虑常规搜索。直接搜索每两支球队的比赛结果，中途可以进行可行性剪枝：如果当前球队剩下的比赛全赢也不能超过目标得分则直接返回；如果当前球队已经超过了目标的分则直接返回。关于搜索的顺序，可以每次只考虑一支球队，搜索时改变第二支球队，搜完这支球队后直接检查是否合法。反映在积分矩阵上则为按行搜索。 以上的做法虽然可以通过本题，但跑得非常慢，于是考虑进一步优化。 首先，我们可以使用两层搜索嵌套的

B. Doremy’s Perfect Math Class 题意：有一个集合 sss，初始有一些元素，每次操作可以选择两个元素并将它们的差加入集合。问若干次操作后集合内元素最多有多少个。 直觉告诉我们，集合中元素的 gcd⁡\gcdgcd 的倍数都能出现（前提是小于等于最大值）。证明：考虑相邻元素通过若干次减法操作可以得到它们的 gcd⁡\gcdgcd，再与下一个元素进行同样操作，最终得到所有元素的 gcd⁡\gcdgcd。有了 gcd⁡\gcdgcd 后，可以将最大值反复减 gcd⁡\gcdgcd 得到所有元素。 By QAQAutoMaton 1 2 3 4 5 6 7 8 9 1