文章

发布于

[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连接远程服务器”

发布于

[DP][思维][×] codeforces 1183H Subsequences (hard version)

题目链接

题意：给定一个字符串S，长度为n≤100，然后定义一个操作是将S的一个含有L个字符的子序列看作一个字符串插入到一个无重复元素的set里，每次操作的cost是(n-L)，然后问对于给定的k（k最大可取1e12），最少需要多少总cost才能使得set的元素个数达到k。难度2200分，有点虚高其实，不过还是不那么好想的。用先后顺序去重是关键idea。

做这种代码段但是考思维的小题还是挺有意思的。。。。

这题是mike出的，感觉挺经典那种。他有一个easy version是k≤100，这个要求的话就很松了，mike的题解直接用了一种及其暴力的方法：把每个subsequence当作一个点，相差一个字符的点之间连边建图，直接暴力跑bfs。。。这个肯定是个时间和空间复杂度都爆炸的算法，但是k≤100的时候很快就能搜到，只要及时跳出bfs就可以了。

这个H版本要求k最大可能是1e12，这就不能再那么操作了。首先写几个简单的样例就可以发现这个主要跟unique的子序列的长度和数量有关系，如果我们能求出来对应于某一长度j的unique子序列有多少个，那就可以解决这个问题了。这个就是一个引导方向，可以先试着设dp[i][j]表示以i为结尾的长度为j的子序列个数。状态定义好了之后考虑转移，按照大问题转化为小问题的思想，dp[i][j]表示的以i结尾的unique子序列，那么如果去掉s[i]之后这些子序列一定是互不相同的长度为j-1的子序列，数量没有多也没有少。所以现在就是要考虑怎么算出来前i-1个字符构成的子序列里面有多少个了。利用已经计算得得信息，这个一定是某些dp[pos][j-1]之和，但是有一种情况的是不同的pos对应的子串可能一样，所以这个题目最精彩的部分就来了，每次在相同的字符中选取最靠后的作为计算点。第一这样起码不会比选择前面的点坏，如果前面的点能凑成q个子序列那么后面的点凑成的相同长度的子序列只会多不会少，即不漏；第二这个就避免了重复计算的现象，不重不漏即为正确的dp转移。所以如果用\[lst[i][w]\]表示前i个字符里面字符为\[‘a’+w (w \in [0,25])\],可以写出来状态转移方程为

\[dp[i][j]=\sum_{w=0}^{25} dp[lst[i-1][w]][j-1]\]

至于lst显然很简单的一个dp就推出来了lst[i][j]=((int)(s[i]-‘a’)==j)?i:lst[i-1][j];
继续阅读“[DP][思维][×] codeforces 1183H Subsequences (hard version)”

发布于

强化学习入门: Q-Learning的python实现

强化学习入门: Q-Learning的python实现

观摩了微软俱乐部游戏组大佬的一个unity+tensorflow搞出来的的游戏AI之后对强化学习产生了点兴趣（其实说起来我当时进俱乐部面试的是游戏组最后给我整到软件了？？？），准备从小白开始学习一下强化学习和游戏里的AI。不过，查了很多资料之后直观感受是，国内这方面的优质资源真的很少，尤其是面向新手的。。。讲的乱七八糟，看的头皮发麻。经过一番扒拉后，找到了两个非常nice的国外大神做的入门教程，链接分别在

当我看到这两个Tutorial的时候感觉就像这位朋友的评论一样hhh

这里的代码用到的环境是openAI-gym里的Taxi-v2，这个游戏的界面长这样

简单说下这个图的含义：

总共5*5个空格，RGBY是四个表示乘客/目的地的位置 继续阅读“强化学习入门: Q-Learning的python实现”

发布于

[填坑] 一个私人视频站

忽然想起来自己还有一个一块钱一年买的垃圾.xyz域名，然后意识到我的一个月5美元的小鸡其实现在的存在很鸡肋，就想了想怎么能让它再多做点贡献。。。。

然后捣鼓了一天就整出来一个这样的垃圾视频站

目前pc端可以正常播放，这个资源采集的api更新的还挺快，权游第八季基本上当天更新的样子。。。

不过我还没做手机端适配，手机上现在会黑屏，不过我最近一段时间应该是没空做了emmmmm又得比赛又得学习又得准备考试，留了个坑等到有空填吧坑已填好，早上做了下手机端适配，顺便把m3u8播放器也整好了

发布于

机器学习中的数学 –标量函数对矩阵求导的方法

标量函数对矩阵求导的方法

写这个是因为今天在推CNN的反向传播的时候遇到了数学上无法理解的操作2333，google了一波发现主要问题出在我并没有学会矩阵求导运算，这个东西和普通的标量函数运算还是有很大区别的，比如认为AX对X的导数为A就是错的。因此今天专门来学习一下这个知识。

符号规定：使用小写字母x表示标量，粗体小写字母\[\boldsymbol{x} \]表示列向量，大写字母X表示矩阵。

首先思考一下标量函数对矩阵（向量）求导的定义，假设函数为f，求其对矩阵X的导数，可以记为
$$\frac{\partial f}{\partial X} = \left[\frac{\partial f }{\partial X_{ij}}\right]$$
可以发现我们要得到的其实是一个标量函数对矩阵X里的所有元素逐个求导然后把这些求导的结果根据与X里元素的位置关系排成与X同样形状的矩阵这么一个东西。当然我们可以把矩阵squeeze一下搞成一堆分离的变量逐个求，但是这样就与使用矩阵的初衷相抵触了，本来使用矩阵就是为了运算的方便整洁，那要拆开变成分散的变量还用矩阵干什么，所以有必要研究下从矩阵这个整体的角度出发的求导方法。

回想一下高等数学中多元函数的微分，可以写成
$$df = \sum_{i=1}^n \frac{\partial f}{\partial x_i}dx_i $$
换个写法把求和转变成向量内积的形式的话就是
$$df = \frac{\partial f}{\partial \boldsymbol{x}}^T d\boldsymbol{x}$$

按照之前的定义，矩阵的导数可以写成
$$df = \sum_{i=1}^m \sum_{j=1}^n \frac{\partial f}{\partial X_{ij}}dX_{ij}$$
那么同样的仿照上一段用矩阵表示多元函数微分的方式，比如内积表示这个式子的话，可以写成
$$df = \text{tr}\left(\frac{\partial f}{\partial X}^T dX\right)$$
其中tr表示矩阵的迹（仿真对角线元素之和），满足对尺寸相同的矩阵A,B，\[\text{tr}(A^TB) = \sum_{i,j}A_{ij}B_{ij}\]，即\[\text{tr}(A^TB)\]是矩阵A,B的内积。

然后来考察一下基本的运算规则。 继续阅读“机器学习中的数学 –标量函数对矩阵求导的方法”

发布于

配置websocket+tls+web+cdn科学上网

提前说好，这一套主要是抗封锁强，速度和延迟都不是太好，尤其是用了cdn之后，现在我这个只能满足我搜索网页和看高清视频的需求，需求很高的时候我还是蹲宿舍连网线用同一个vps上ipv6的shadowsocks（话说现在看上去我校的网络对ipv6没有任何管制）。当然有钱买得起国外付费cdn的话体验可能会不错。

另外，没有折腾欲望的可以直接用大佬的一键脚本，输下面这一行按提示做，ssl证书，nginx配置，服务端/客户端v2ray的配置文件，直接全搞定。（当然域名还是要自己买，dns和cdn还是要自己操作。

bash <(curl -L -s https://raw.githubusercontent.com/wulabing/V2Ray_ws-tls_bash_onekey/master/install.sh) | tee v2ray_ins.log
wget --no-check-certificate https://github.com/teddysun/across/raw/master/bbr.sh && chmod +x bbr.sh && ./bbr.sh

必要的准备

  • 一台外网ip的vps，目测do的已经被我校封杀殆尽，我现在用的vultr
  • 一个域名，可以去godaddy之类的网站买，几块钱一年的比如sunxiaochuan.me之类的随便弄一个（反正又不是真的网站不求体面
  • 注册个cloudfare，cdn用

VPS安装v2ray和nginx

我用的Ubuntu18.04，nginx直接apt安装就行，很简单。

apt-get install nginx

继续阅读“配置websocket+tls+web+cdn科学上网”

发布于

[比赛补题][FFT][组合数学][母函数][×]2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅

2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅

题目链接

网络赛最难的一个题，也是我唯一一个不会做的。

看了大大的题解发现我其实已经推到了倒数第二步T_T

但是眼拙没看出来可以写成卷积形式。。。所以按照那个推法无论如何都是O(n^2)的复杂度，变成卷积形式就可以用fft加速直接O(nlogn)一次性求出所有点的值了。。。
继续阅读“[比赛补题][FFT][组合数学][母函数][×]2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅”

发布于

[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR

2019 ICPC南昌邀请赛网络赛 K MORE XOR

题目链接

(⊙﹏⊙)不知道为什么比赛时候这个题和D题死推不出来，比赛完了5分钟ac，我大概脑子坏掉了。真的是超超超超级简单的一个题，但是我光顾着用数学公式推了所以推出来结果巨复杂(⊙﹏⊙)服了自己了。

题解：先说怎么求g(l,r): 首先f(l,r)很好求，利用异或的性质，预处理出来前缀异或和就可以了。设预处理出来p1[x]表示从a[1]到a[x]的异或和，那么很容易得到\[f(l,r)=p1[l-1]\oplus p2[r] \], 那么可以由g的定义就可以知道 \[ g(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} f(i,j) =\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} p1[i-1]\oplus p1[j] \];当然这个东西还是很复杂的，我们想办法把他复杂度搞到O(1)：考虑每个p1[x]出现的次数，列个表可以发现，在这个求和式中出现的所有下标，从l-1变化到r, 而每个下标出现的次数都是一样的，这个次数等于 r-l+1 ，那么就可以得出结论，如果r-l+1为偶数，则g(l,r)应为0，否则应为\[ \sum_{i=l-1}^{r} p1[i] \]，注意到这个式子又可以用p1的前缀和来O(1)计算，所以又可以提前求出来p1的前缀和p2，这样的话g(l,r)就可以表示为

\[g(l,r)=
\begin{cases}
0& \text{(r-l+1) is odd}\\
p2[l-2]\oplus p2[r]& \text{else }
\end{cases}\]

有了g(l,r)再来考虑w(l,r)，\[w(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} g(i,j) \],就跟g的表达式很像，但是这里不能直接再套用g关于p1的公式，因为g里面有很多的0是跟p2无关的，换句话说这些0并不是由p2[l-2]^p2[r]求出来的，所以要分类讨论。分析方法跟g是类似的，列一个表观察每个p2出现的规律，可以发现，这个规律是4个一循环的结构，设\[t=（r-l+1)\mod 4\]; 则当t==0时，所有的p2下标出现次数均为偶数次，也就是结果一定为0，t==2时，所有的p2下标出现次数均为奇数，这样的话即等于\[\sum_{i=l-1}^{r} p2[i] \]，这个式子说明我们可以再用一个p2的前缀和p3来O(1)计算这个结果。这是比较简单的两种情况，另外两种是t==1和t==3，这两种一种是奇数项的出现次数为奇数偶数项为偶数，另一种是奇数项出现次数为偶数而偶数项出现次数为奇数，这意味着可以用一个分奇偶的前缀和来O(1)求得这个式子只不过仍需要分类讨论一次。。若令p31[i]和p32[i]分别表示p2的奇偶前缀和，t=(r-l+1)%4, 则w(l,r)的表达式为

\[
w(l,r)=
\begin{cases}
0& \text{t=0}\\
p31[r]\oplus p31[l-3]& \text{t=1 and r is odd}\\
p32[r]\oplus p32[l-3]& \text{t=1 and r is even}\\
p3[l-3]\oplus p3[r]& \text{t=2}\\
p32[r-1]\oplus p32[l-2]& \text{t=3 and r is odd}\\
p31[r]\oplus p31[l-3]& \text{t=3 and r is even}
\end{cases}
\]

这样的话整个问题就可以O(1)解决了。。不知道我当时脑子怎么回事就没推出来
继续阅读“[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR”

发布于

[动态规划][状压DP][剪枝搜索] XDOJ 1420 2019西电acm校赛网络赛J题 垒箱子

题目链接

这次学校网络赛还是挺不错的，有3道题（F I J）都是值得一做的emm，J题胡乱暴力+dp拿了个一血，I题胡乱暴力也过了

当然由于我FFT/NTT&斯特林数学的不行所以F题并不会做，虽然推出来公式和dalao一样但是没法把复杂度降下去，等到学会了应该会放个F的题解

J题吧，跟UVa 437 The Tower of Babylon很像，当然只是看上去很像，UVa 437的限制是每种箱子必须叠在比他严格小的另一个上，然后箱子无限用，XDOJ 1420 是叠在长宽大于等于该箱子的另一个箱子上，但是每种箱子只能用一次。
如果箱子的数量少一点的话，其实完全可以直接完全状态压缩动态规划，但是这题数量是30，压缩成二进制的话2^30肯定会超时，所以需要一点操作。。

首先先全部暴搜，dfs(x,S)表示当前以箱子x号为最底部箱子，之前已经用过的也就是还在x更底下的箱子情况为S（S是一个十进制数，展开成01二进制串表示30个箱子是否被使用过）所能达到的最高的高度，每次都打一遍结果，很快可以发现，当取到某一个箱子之后，在某些情况下他后面的搜索路径就是固定的。

就比如说 某次搜到了箱子3，然后他之后的搜索路径就只能放箱子6和7，然后把每次搜索路径都打出来就会发现，其实之后的每次搜到3都会是走6和7，除非6和7之前已经被用过了也就是说6或7变成了3底下的箱子，这时候后面的路径会发生一些变化，因为每个箱子只能用一次。（这里本该举一组样例但我实在找不到当时画的样例了emm）

然后到这里就可以想一下是不是可以用这个特性对dfs(x,S)进行剪枝和记忆化搜索，首先把S的定义反转，让S这个二进制数表示尚未使用过的箱子”的情况，比如00101表示1号和3号箱子还没有被用过，245号箱子已经被用过了。这样的话，每次dfs的时候可以记录下来一个dp(x,TS)的记忆化结果，其中TS是S和“理论上可以放到x上的所有箱子的集合”KS相与的结果，这里后者可以n^2复杂度枚举预处理，我的代码里是存储到ky[x]的数组里。这样的话，每次dfs就是先把TS求出来，然后判断(x,TS)这个对有没有在之前被搜索过，如果有的话就直接返回结果，这里的这个结果可以用一个map<pair<int,int>, int> 来保存，如果没有出现过的话的话就直接暴搜，这样的话每种箱子作为底的每种情况只会被搜到一次，就等于提前把绝不可能走到的箱子和已经走过的路径都剪掉了。把所有的状况想象成图的话，每个箱子三种形态那就是有90个节点，每个结点出发能走的最长的路径最多30个，如果能保证每种情况只走一次其实是相当快的（主要是我并不会严格证明复杂度emmm）

继续阅读“[动态规划][状压DP][剪枝搜索] XDOJ 1420 2019西电acm校赛网络赛J题 垒箱子”