曹轩鸣的博客

minosi 题意：有一个 n×mn\times mn×m 的矩阵，每个格子有黑白两种颜色。所有黑色的格子只能从左方或上分进入，白色格子只能从右方或下方进入。求是否能走恰好 kkk 步从 (1,1)(1,1)(1,1) 走到 (n,m)(n,m)(n,m)。n×m≤300,k≤106n\times m\le 300,k\le 10^6n×m≤300,k≤106。 做法一 可以直接 O(nmk)O(nmk)O(nmk) DP。令 f[k][i][j]f[k][i][j]f[k][i][j] 表示从 (1,1)(1,1)(1,1) 走 kkk 步是否能走到 (i,j)(i,j)(i,j)，则

比赛传送门 B. Playing Cards Validation 题意：有 nnn 个长度为 222 的字符串，判断是否满足以下条件： 1. 第一个字符为 HDCS 之一。 2. 第二个字符为 A23456789TJQK 之一。 3. 字符串两两不同。 一个模拟题。可以将两个字符可能的选择分别记录下来，循环一遍判断是否为其中之一或调用 count 函数；也可以直接写 if 判断。判断两两不同可以 n2n^2n2 枚举，也可以用 set 或排序加 unique 去重。 By cxm1024 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1

比赛传送门 A. Indirect Sort 题意：有一个排列 aaa，每次可以选三个不同的位置，从左到右依次为 i,j,ki,j,ki,j,k。如果 ai>aka_i>a_kai​>ak​，将 aia_iai​ 加上 aja_jaj​，否则交换 aj,aka_j,a_kaj​,ak​。问是否能将其排成非降序列。 贪心。如果第一个元素是 111，则一定可以：每次用 111 来当 iii，即可任意交换 j,kj,kj,k。如果不是，则一定不可以：因为对于 111 所在的位置，要么将它移到左边，要么将它增加，要么让前面的减少。容易证明这三种都是不可行的。 By tourist 1 2 3

D. Divide by 2 or 3 题意：给你一个数组 aaa，每次可以选择一个 222 的倍数除以 222，或选择一个 333 的倍数除以三。问最少多少次操作将元素统一。无解输出 -1。 如果有解，结果将会是 aaa 中元素的公因数，而所有公因数都是最大公因数的因数。由于额外的除法没有意义，最终结果一定是最大公因数。对于每个元素检查它与最大公因数是否只差了若干个 222 和若干个 333。对 aigcd⁡\frac{a_i}{\gcd}gcdai​​ 进行类似质因数分解的操作即可。 By zhoukangyang 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1

B. BAN BAN 题意：给你一个 nnn，生成一个字符串为 BAN 重复 nnn 遍。每次操作可以选择两个位置进行交换，问至少多少次交换后可以使该串不存在 BAN 的子序列。输出方案。 显然对于每个 BAN 都至少要动一下，而每次交换可以动两位，所以答案的下界是 ⌈n2⌉\lceil\frac{n}{2}\rceil⌈2n​⌉。这个下界是可以达到的，我们只需要交换最左边的 B 和最右边的 N，再交换第二段的 B 和倒数第二段的 N，以此类推，结果形如 NANNAN...BABBAB，显然满足条件。 By Um_nik 1 2 3 4 5 6 7 8 9 10 11 12 13 14

题意：给你一个由 0、1、&、|、(、) 组成的字符串，保证是一个合法的逻辑表达式。其中括号优先级最高，与运算优先级高于或运算，同级之间从左到右算。定义一次短路为，或运算的左边结果为 1，或者与运算的左边结果为 0，此时后面部分无需计算（也不统计短路）。询问该逻辑表达式的结果以及与、或运算各自的短路次数。 做法 1 我们可以先使用栈预处理出括号的匹配（分段），然后使用 DFS 来计算。 DFS 时传入当前要处理的区间，返回该区间的结果，通过 DFS 内更改全局变量统计短路次数。对于区间之间的转移，我们有以下两种处理方法： 1.1 考虑最后一次运算的位置。从最右边开始，每次往前跳一段，

题目传送门 题意：定义一个 N→N\mathbb{N}\to\mathbb{N}N→N 的函数 f(x)={1x=0f(⌊x2⌋)+f(⌊x3⌋)otherwisef(x)=\begin{cases}1&x=0\\f(\lfloor\frac{x}{2}\rfloor)+f(\lfloor\frac{x}{3}\rfloor)&\text{otherwise}\end{cases}f(x)={1f(⌊2x​⌋)+f(⌊3x​⌋)​x=0otherwise​，求 f(n)f(n)f(n)。n≤1018n\le 10^{18}n≤1018。 很容易想到暴力求解，形成 log⁡(n)\log(n

A. 假期计划 题意：有一个无向图，点有点权。定义两个节点“可达”当且仅当这两个节点的最短路不超过 k+1k+1k+1。求一组互不相同的节点 {a,b,c,d}\{a,b,c,d\}{a,b,c,d} 使得 1↔a↔b↔c↔d↔11\leftrightarrow a\leftrightarrow b\leftrightarrow c\leftrightarrow d\leftrightarrow 11↔a↔b↔c↔d↔1 每步均可达且这四个点的点权和尽可能大。n≤2500n\le 2500n≤2500。 首先跑 nnn 遍 BFS，预处理出每两个点的距离。然后我们可以考虑枚举中间两个节点 b

题目传送门 题意：给你一个 9×99\times 99×9 的矩阵，格子非黑即白，问有多少个不同的正方形，满足四个顶点都为黑色。 很容易想到直接枚举四个顶点的位置，判断、去重，但这个做法显然过于麻烦，难以实现。 于是我们可以想到如何更简洁地确定正方形位置，并尽量省掉去重的步骤。我的做法是枚举左上的顶点，再枚举右下方的某个顶点，统计得到的线段往右平移画出的正方形。实现上，我们用 (i1,j1),(i2,j2)(i_1,j_1),(i_2,j_2)(i1​,j1​),(i2​,j2​) 来表示前两个节点，则可以用数学方式推出后两个节点的坐标。 By cxm1024 1 2 3 4 5 6

题目传送门 题意：有 nnn 条鱼在数轴上，第 iii 条鱼初始在 xix_ixi​，有一个向右的速度 viv_ivi​ 以及全职 wiw_iwi​。问任选出一个时刻 ttt 并选出一个长度为 AAA 的区间，包含的鱼的权值和最大为多少。n≤2000,other val≤104n\le 2000,\text{other val}\le 10^4n≤2000,other val≤104。 可以考虑枚举最左边选哪条鱼，设为第 iii 条，例如 xi=1,vi=2,A=1x_i=1,v_i=2,A=1xi​=1,vi​=2,A=1，则其他我们可以画出两条直线： 这两条线有什么用呢？我们对于