曹轩鸣的博客

赛时AC 3道，补题做出来一道 A. Computer Game ProblemProblemProblem 有一个 2×n2\times n2×n 的01矩阵，1为障碍，你要从 (1,1)(1,1)(1,1) 走到 (2,n)(2,n)(2,n)，每一步只能向右、上、下、右上、右下走，问能不能走到。 t≤100,n≤100t\le 100,n\le 100t≤100,n≤100 SolutionSolutionSolution 如果有一列的两个数都是1，则一定会被堵住，否则一定能到，因为每一列至少有1个0，而我们可以斜着走，所以一定可以从一列走到下一列。 B. Groups

赛时AC 2道题，赛后补题做出来一道（赛时交了4发，赛后交了十几发才过，太残忍了） 总体难度比较高，可能题解会比较冗长 A. Regular Bracket Sequences ProblemProblemProblem 输入 nnn，输出 nnn 个互不相同的、合法的、长度为 2n2n2n 的括号序列。 t≤50,n≤50t\le 50,n\le 50t≤50,n≤50 Solution1Solution\ 1Solution1 update: 我的解法非常复杂，可以直接看 Solution2Solution\ 2Solution2 CF官方题解的做法（想看看我的憨批做法也

VP做出来一道，补题又做出来3道。 A. Gamer Hemose ProblemProblemProblem 你有 nnn 个武器，要打一个体力为 HHH 的敌人，第 iii 个武器可以对敌人造成 aia_iai​ 的伤害，每把武器不能连续使用两次，问至少需要多少次才能打败敌人。 t≤105,∑n≤2×105t\le 10^5,\sum n\le 2\times 10^5t≤105,∑n≤2×105 SolutionSolutionSolution （读错题意调了半天） 肯定是最厉害的武器和次厉害的武器轮番上阵，把它们看作一组，首先算要用多少组，剩余的再单独处理。 时间复杂度

没打比赛，赛后做出3道。 这场比赛题目质量很高，非常巧妙。 A. CQXYM Count Permutations ProblemProblemProblem 求有多少 2n2n2n 的排列满足存在超过 nnn 个 iii 使得 pipi+1p_i>p

阅读全文 »

字体 * default : 123abcABC\color{red}123abcABC123abcABC * mathrm : 123abcABC\mathrm{123abcABC}123abcABC * mathbb : 123abcABC\mathbb{123abcABC}123abcABC * mathbf : 123abcABC\mathbf{123abcABC}123abcABC * mathcal : 123abcABC\mathcal{123abcABC}123abcABC * mathfrak : 123abcABC\mathfrak{123abcABC}123a

赛时 AC 2道题，掉大分（哭） A. Casimir’s String Solitaire 题目传送门 ProblemProblemProblem 给你一个仅含 A,B,C 的字符串，每次可以删掉一个 A 和一个 B，或一个 B 和一个 C，位置、顺序不限，问能不能删完。 t≤1000,len≤50t\le 1000,len\le 50t≤1000,len≤50 SolutionSolutionSolution 大水题，只需要判断 A 的数量加 C 的数量是否等于 B 的数量。一开始脑抽还判断 A 的数量是否等于 C 的数量 B. Shifting Sort 题目传送门

hexo的LaTeX可算把我给折腾死了。。。 问题：多行公式无法显示（hexo-renderer-marked，mathjax） 看到网上说是因为渲染引擎把\\渲染成\，然后才交给mathjax渲染公式 都说把hexo-renderer-marked换成hexo-renderer-kramed，然后再node_modules/kramed/lib/rules/inline.js里修改escape项，照做了，确实解决了问题，但是却出现了新的问题：复杂公式显示错乱，遂放弃。 又看到在node_modules/marked/lib/marked.js里修改escape项，失败。 后来发现那

基础的DP各位大佬已经讲得很明白了，本文主要讲一讲优化 DP状态很容易想到：f[i]f[i]f[i] 表示打完第 iii 只鼹鼠能获得的最多数量。 转移：f[i]=min⁡j=dis(i,j)f[j]+1f[i]=\min\limits_{j=dis(i,j)}f[j]+1f[i]=j=dis(i,j)min​f[j]+1 ，即对于每一个打完第 jjj 个能来得及走到第 iii 个的 jjj，算最大的 f[j]+1f[j]+1f[j]+1。 重点来了！！ 优化 我们发现，如果时间差大于 2×n2\tim

阅读全文 »

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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 const int MAXL=1e3; st

本篇题解献给和我一样看不懂其他题解的状压DP小白 相信大家都是看了其他题解看不懂才看到这篇题解的（莫名自信），所以什么每行棋子数递减啊，每行的棋子都排在左边啊，就不用我多说了，直接切入正题（大段文字多，请耐心观看）。 轮廓线DP 没见过不用慌，我也没见过（雾 轮廓线，就是把矩阵从右上角到左下角沿着有棋子和没棋子的分界线描一下，往下走就用1表示，往左走就用0表示。这样我们就得到了一个01串，即一个二进制数，这就是我们的DP状态。 例如（图丑勿喷） 这种情况下轮廓线状态为左左下左下下左左下，即001011001(2)=89001011001_{(2)}=89001011001(2)