月度归档： 2019 年 7 月

发布于

[比赛补题][DP][递推计数][思维] 牛客2019多校 第一场 E ABBA

比赛时候：第一眼这不就DP吗，第二眼欸这东西怎么转移啊。。gg

当时迷了一直在想以AB和BA的数目为下标推，但是这样会有很多去重的问题。。。于是就没整出来，后来滚去推高数题了

看了叉姐的一句话题解大概懂了，推的时候直接用x和y的数目做下标，这样首先可以避免重复的问题。也就是设dp[i][j]为i个A，j个B时可用的前缀有多少种。这里面最重要的就是这个“可用的”怎么确定。这里的判断写出来很简单(i-j<=n&&j-i<=m).为什么是这样的呢？现在来考虑一个前缀，什么时候我们可以判断这个前缀一定不能作为最终答案中的某一个方案的前缀（也就是对最终答案没有任何贡献）？首先考虑凑AB，要用这个前缀的话，最终的结果是在他后面再补上(n+m-i)个A和(n+m-j)个B，注意这里的后面的排列并没有确定，也就是说我为了用到这个前缀（使答案+=它这种情况），可以尽力的去想办法摆布后面的A和B使得满足要求。那么有一个结论是在i-j>n的时候无论后面如何摆都满足不了要求：这个前缀至少可以配成j-1个AB或者BA，在加一个AB或者BA，然后如果i比j多了n个以上，那么意味着这多出来的i-j个A跟后面的配对只能配AB了，这样的话AB的总数就超过了n，由于AB和BA的总数确定的，这时候就一定不满足要求了；反之如果i-j<=n，则一定可以通过后面的调整来满足n个AB，m个BA的要求，可以自己试试看，只要注意到AB和BA的互换就行了。比如ABAB可以看出俩AB也可以看出一个AB一个BA（中间的）。。

然后dp边界是dp[i<=n][0]=1,dp[0][j<=m]=1，这个很好理解，全是A或者全是B就只有一种情况的。。。

这题还有点卡常，dp每次不要都memset，否则会tle 继续阅读“[比赛补题][DP][递推计数][思维] 牛客2019多校 第一场 E ABBA”

发布于

[DP][字符串匹配][子序列] codeforces 1150 D Three Religions

vp了这一场，这个D题难到出现断层。。。C过了1k人的时候D没人过，太狠了

主要是能想到用dp搞字符串匹配的。。。div2里这样的人应该不多吧

但是这个题其实内涵里有诱导dp的思想：刚开始没有搞懂他这里的append是什么意思，后来才懂得他每次的+-操作都是在修改对应的religion的描述，这个描述是一个只有小写字母的先后顺序固定的字符串。。然后题目问的就是给定你一个字符串叫做word of universe，问3个religion能不能共存，其实意思就是能不能从这个word of universe分离出来三个subsequence，他们互不相交，又正好是3个religion的描述。

vp的时候毫无头绪，正解里的预处理表倒是想到了也写了但是没用上。确实没想到会是dp emmmm 。既然dp那一定有个数值型的对象吧，他这里就很妙的把问题转化为满足这三个subsequence共存的序列至少要多长了。。。当然给定的word of universe是确定的，这里其实可以认为后面还有无限长的字符串。。。但是长度大于n的时候我们认为没用了。。就输出NO就可以。不得不说确实是很精妙，legendary出的题确实厉害👍

具体地，设dp(n1,n2,n3)为region1满足前n1个字符，region2满足前n2个，region3满足前n3个这样的情况下所需要的在word of universe里的前缀至少有多长。有一个暴力的计算O(250^3)复杂度的，就是

\[
dp\left(n_{1}, n_{2}, n_{3}\right)=\min \left\{\begin{array}{ll}{Nst\left(dp\left(n_{1}-1, n_{2}, n_{3}\right)+1, \text{description}_{1}\left[n_{1}\right]\right)} & {\text { if } n_{1} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}-1, n_{3}\right)+1, \text{description}_{2}\left[n_{2}\right]\right)} & {\text { if } n_{2} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}, n_{3}-1\right)+1, \text { description }_{3}\left[n_{3}\right]\right)} & {\text { if } n_{3} \geq 1}\end{array}\right.
\]

继续阅读“[DP][字符串匹配][子序列] codeforces 1150 D Three Religions”

发布于

配置vscode连接远程服务器

今年5月左右微软给vscode加了新操作，有了官方的远程连接的插件，不过好像现在只在insider版本里提供。要安装的话直接在插件里搜索Remote，安装Remote Development这一套就行了。

服务器上操作

这里配置一下使用ssh key登录，相对于输密码比较安全（其实是我懒得每次都敲密码）。首先在服务器上生成一对公私钥

root@itemqqSS:~# ssh-keygen
Generating public/private rsa key pair.
Enter file in which to save the key (/root/.ssh/id_rsa): 
Created directory '/root/.ssh'.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in /root/.ssh/id_rsa.
Your public key has been saved in /root/.ssh/id_rsa.pub.
The key fingerprint is:
SHA256:RWDHVoBeg7jvzTdC/nPPTwemzGl0vogQwUzmooas root@itemqqSS
The key's randomart image is:
+---[RSA 2048]----+
|       o=*+o.    |
|    . o====      |
|   . o+o +..     |
|  . . .o..       |
|   .   .S   . +  |
|  .    o. .+ * . |
| .     .o=. * . o|
|E       .o=++..+.|
|          .+o+..=|
+----[SHA256]-----+

这里最好不要再用passphrase了。。直接回车就行。。主要是图省事，加了之后vscode的自动连接似乎不是很方便。
继续阅读“配置vscode连接远程服务器”