Potassium

分类

未归档(25) 题解(1)

/ 注册

全部文章（共26篇）

P3796 【模板】AC自动机（加强版）题解（Aho-Corasick Automation）

题目链接 AC自动机解题思路 AC自动机模板题。刚学AC自动机，写一篇博客增强理解。 AC自动机最关键的一点在于，\(fail\)失配指针的构造。 \(fail\)指针指向的地方，是匹配出现错误后进行重新匹配的位置，这说明，从根开始到\(fail\)指针指向的地方这一块字符串，正是我们刚刚...

2018-12-06

0 556

BuaacodingT651 我知道你不知道圣诞节做什么题解（逻辑）

题目链接我知道你不知道圣诞节做什么解题思路第一句话：x，y不都为质数。第二句话：对于xy=t，存在唯一一种x+y使得x，y不都为质数。第三句话：对于x+y=s，存在唯一一种t=xy使得对于任意满足xy=t的x和y，存在唯一一种x+y使得x，y不都为质数。 AC代码 /* Au...

2018-11-26

0 509

P2766 最长不下降子序列问题题解（网络流）

题目链接最长不下降子序列问题解题思路分成三小问解决。第一小问，求\(LIS\)，因为\(n<=500\)，直接\(O(N^2)\)暴力求解即可。第二三小问，建立模型用网络流求解。对于第二小问 \((1)\)首先，因为每个点只能使用一次，考虑拆点，把每一个点拆成\(i，n+i\...

2018-11-24

0 670

P2516 [HAOI2010]最长公共子序列题解（LCS）

题目链接最长公共子序列解题思路第一思路： 1.用\(length[i][j]\)表示\(a\)串的前\(i\)个字符与\(b\)串的前\(j\)个字符重叠的最长子串长度 2.用\(num[i][j]\)表示 \(a\)串的前\(i\)个字符与\(b\)串的前\(j\)个字符重叠的最长子...

2018-11-20

0 698

P2188 小Z的 k 紧凑数题解（数位DP）

题目链接小Z的 k 紧凑数解题思路数位DP，把每一个数位的每一个数对应的可能性表示出来，然后求\(num(1,r)-num(1,l-1)\)，其中\(num(i,j)\)表示\([i,j]\)区间里符合要求的数的个数。其中，\(dp[i][j]\)表示第\(i\)位数字为\(j\)的选...

2018-11-12

0 445

P1725 琪露诺题解（单调队列）

题目链接琪露诺解题思路单调队列优化的\(dp\)。状态转移方程：\(f[i]=max{f[i-l],f[i-l+1],...,f[i-r-1],f[i-r]}+a[i]\) 考虑单调队列优化。因为刚学，不是很熟悉单调队列，特写一篇详细的解释。 \(queue\) 数组存储一个队列，他...

2018-11-04

0 471