2018 to do list

迫于最近的事情有点多,还是记录一下。 果然to do list什么的,还是要按照年份记录啊。

  • 了解linux strace命令
  • 速成go语言,并了解go于系统调用https://hackernoon.com/strace-in-60-lines-of-go-b4b76e3ecd64
  • 熟悉hustoj V2版本目前的代码
  • 看完<code in practice>
  • mit 6.828 lab1。。。感觉要咕
  • 看完<unix 系统系统手册>的20,21章信号部分, 为hustoj的重构补充基础知识.

codeforces 501 B. Obtaining the String

题目链接:http://codeforces.com/contest/1015/problem/B

题意: 给出字符串s和字符串t,问一个将s变为t的策略。 可以做的变换为,交换s中相邻的字符串,该操作最多不能超过4000次,字符串长度最大为50.

思路:

首先可以确定,当两个字符串的组成相同时(也就是有同样的字符组成,只是位置可能有所不同)一定有解。

考虑最坏情况,每个字符都要交换到最远的地方,总的操作数<50*50<4000,因此一定有解。

判断组成是否相同可以用multiset

 

 

codeforces edu #51 C. Vasya and Multisets (思维题)

题目链接

题意:有n个数,现在要分成2个集合,使得2个集合中,仅出现1次的数的个数相同,问是否有解,以及具体的分法。

思路:

一开始考虑出现多个的数的思路麻烦了,比如对于出现2次的某个数x,与其一个集合中分得一个,使得两个结合中,仅出现1次的数的个数各+1,还不如都放在同一个集合中,使得仅出现1次的数的个数不增加。

因此思路是这样的:

先考虑出现1次的数的个数,如果为偶数,那么均分,然后把其他出现多次的数全都放在第一个集合;

如果出现1次的数的个数为奇数,我们还是尽可能均分,然后不妨假设第一个集合中的只出现1次的数的个数比第二个集合中多1个。

我们现在需要让第二个集合中,仅出现一次的数增加一个。

什么样的数可以满足这个条件呢? 出现2次的数是不行的,因为这会使得两个集合中的数字各自+1

因此需要至少有一个出现3次或者以上的数。

具体见代码:

 

gRPC学习笔记

gRPC 是 google 最新发布的开源 RPC 框架, 声称是”一个高性能,开源,将移动和HTTP/2放在首位的通用的RPC框架.”. 技术栈非常的新, 基于HTTP/2, netty4.1, proto3, 拥有非常丰富而实用的特性, 堪称新一代RPC框架的典范.

//上面这段话是我抄的,其实我之前连RPC是什么都不知道,

关于RPC,如果你和我一样根本不知道是什么,请参考这里 

我对RPC的理解就是,一层封装,使得不在同一个机器上的程序A可以一个调用另一个程序B,而不需要考虑这两台机器,以及这两个程序使用的语言的不同。

而gRPC是诸多RPC框架中比较新,也比较好用的一个。

学习gRPC需要会使用protobuf3,关于protobuf,可以参考protobuf学习笔记

官方文档 还是要给出的,虽然我没怎么看就是了orz

gRPC的安装

参考这个,从源码编译安装

如果出现

参考

Compile fails on Ubuntu 14.04 ?  发现是protobuf的锅,需要手动编译一下:

 

gRPC的使用

grpc/examples下有一些例子,自己搞搞就会写基本的了。(已经硬着头皮用gRPC写了一个项目的通信部分了orz…其实还挺容易的。但是项目的代码没办法放上来。。。所以。。直接看examples的代码就好了。

8102年了,来更新一波vim配置

现在用的vim配置还是2015年7月的时候写的。

三年过去了,vim到了8.0,很多功能也有了更多选择。因此打算来更新一波vim配置。目前还在更新过程中。。。等差不多折腾完再来记录一些信息。

 

2014 Xi’An ACM-ICPC Regional Contest Problem G. The Problem to Slow Down You (回文自动机(模块化写法))

http://codeforces.com/gym/100548

题意:

切换面板:标签
标签
添加新标签

回文自动机、 给2个字符串,问2个字符串中,相等并且都是回文串的对数。

思路:

构建2个PAM.然后奇偶起点分别跑dfs即可。

PAM写成了模块化的形式orz

bzoj 2160: 拉拉队排练 (回文自动机+快速幂)

2160: 拉拉队排练

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 1938  Solved: 743
[Submit][Status][Discuss]

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球队增加士气,赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道,帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束,在雨荨和校长的挑选下,n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡,为艾利斯顿篮球队加油助威。一个阳光明媚的早晨,雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行,每个人手中都举了一个写有26个小写字母中的某一个的牌子,在比赛的时候挥舞,为小伙子们呐喊、加油。雨荨发现,如果连续的一段女生,有奇数个,并且他们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体,并且按照女生的个数降序排序之后,前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大,雨荨只要你告诉她,答案除以19930726的余数是多少就行了。

Input

输入为标准输入。第一行为两个正整数n和K,代表的东西在题目描述中已经叙述。接下来一行为n个字符,代表从左到右女生拿的牌子上写的字母。

Output

输出为标准输出。输出一个整数,代表题目描述中所写的乘积除以19930726的余数,如果总的和谐小群体个数小于K,输出一个整数-1。

Sample Input

5 3
ababa

Sample Output

45
【样例说明】
和谐小群体女生所拿牌子上写的字母从左到右按照女生个数降序排序后为ababa, aba, aba, bab, a, a, a, b, b,前三个长度的乘积为。

HINT

总共20个测试点,数据范围满足: 

 

 

思路:

直接PAM.

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

ural 1960. Palindromes and Super Abilities (回文自动机,统计本质不同的回文串个数)

http://acm.timus.ru/problem.aspx?space=1&num=1960

题意:

给一个字符串S,依次输出字符串S的所有前缀中,本质不同的回文串个数。

思路:

考虑构建PAM是一个增量算法…所以一边构建一边输出答案就好了。。。

某一时刻本质不同的回文串个数就是sz-1 (标号是从0..sz,一共sz+1个,减去2个根,所以是sz-1)

 

 

BZOJ 2565: 最长双回文串 (回文自动机)

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S

Output

一行一个整数,表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

12

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分,且两者都是回文串。

对于100%的数据,2≤|S|≤10^5

2015.4.25新加数据一组

Source

 

 

思路:

我们考虑增量构建PAM的时候

构建到pos,当前的状态的len其实就是到以pos位置结尾的最长回文串的长度。

那么我们只需要正着做一遍,再倒着做一遍,然后枚举断点就行了。

时间复杂度O(n)

 

hdu 3948 | 2011 Multi-University Training Contest 11 The Number of Palindromes (回文自动机模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=3948

题意:

给一个字符串,问本质不同的回文子串的个数。

思路:

考虑回文自动机。

我们知道,对于PAM上的一个节点,表示的就是一个本质不同的回文串。

UPDATE: 弃用了这种代码风格,新的写法见下面。

那么sz-2就是本质不同的回文子串个数了orz(减掉2是因为PAM有2个根,这2个根不表示回文串)

 

对于新的代码风格,节点数标号是从0到siz,其中标号为0和标号为1的是2个根。

因此答案是siz-1

新的代码风格:

 

 

UOJ #103. 【APIO2014】Palindromes (回文自动机模板题)

http://uoj.ac/problem/103

题意:

给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 s,求所有回文子串中的最大存在值。

思路:

回文自动机,也叫回文树,但其实并不是树2333,所以以后还是称为回文自动机,缩写为PAM

学会了(?)SAM之后再看PAM真是简单得一逼。

学习笔记之后补。

对于这道题,PAM中一个状态的cnt表示的该状态所表示的回文串出现的次数

len表示的是该状态所表示的回文串的长度

UPDATE:

下面的代码风格太丑了,打算弃用。

更新的代码风格见最后

 

 

 

codeforces 123D. String(后缀自动机)

题目链接:http://codeforces.com/problemset/problem/123/D

题意:

如果字符串y在字符串x中出现n次,那么F(x,y)=n*(n+1)/2

现在给一个字符串,求所有的F(s,x)的和,x为字符串的所有不相同的子串.

思路:

这道题可以考虑用后缀数组做,麻烦一点:codeforces-123D-解题报告(SA)

直接SAM

right[v]就是SAM上状态表示的所有字符串出现的次数。

那么每个状态的答案就是right[v](right[v]+1)/2(st[v].len-st[st[v].link].len)

累加即可。

 

 

poj 3415 Common Substrings (后缀自动机+parent树上的lazy标记)

http://poj.org/problem?id=3415

题意:

给出两个字符串,问公共长度大于等于k的子串个数(只要两个串的位置不同就认为是不同)

思路:

考虑SAM的性质。

SAM上的一个节点所能接受的本质不同的子串个数是st[v].len – st[st[v].link].len

而这些子串,都出现了right[v]次,因为不同子串的个数就是(st[v].len-st[st[v].link].len)*right[v]

现在有了限制条件,要求长度大于等于k.

没有限制的话,SAM上的一个节点所能接受的字符串的长度范围是在[st[st[v].link].len+1,st[v].len]

那么现在范围其实就变成了[MX,st[v].len],其中MX = max{st[st[v].link].len+1,k}

对于A串构建SAM,然后B串在SAM上运行

考虑对于SAM的某个状态,B串此时的最大匹配长度为len,那么len>=MX时,满足条件的字符串的范围就变成了[MX,len] 

len<MX时无贡献。

所以该状态(v)对答案的就是  (len-MX+1)*right[v]

然而这还不算完,和之前的LCS2一样,如果SAM上的一个节点能匹配字符串B的长度大于等于k,那么该节点的祖先节点(父亲节点,父亲的父亲的节点…)

能匹配的字符串B的长度也都大于等于k…

如果我们一边匹配一边沿着parent树自底向上传递的话…复杂度n^2,一首凉凉送给自己

但是正常人会这样?.jpg

我们先打个标记,最后沿parent树自底向上把标记传递上去就行了。。

需要注意的是,此题的字符集是大小写字母都会包含…RE了2发orz

 

hdu 4416 Good Article Good sentence (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=4416

题意:

给出一个字符串A和n个字符串B,问A的子串中,不在任何一个B中出现的本质不同的子串有多少。

思路:

还是根据len搞事情

我们知道,如果不加任何条件,SAM中一个节点所表示的本质不同的子串数量是st[i].len – st[st[i].link].len

现在加了限制条件。

那么该状态中,有一些长度的字符串就会不满足条件。

我们考虑对母串A构建SAM

那么只需要维护B的所有串,对于某个状态能匹配的最大长度,设为maxlen,那么 长度为[maxlen+1,st[i].len]的字符串可以贡献答案。

如果maxlen为0,则该状态所表示的所有本质不同的子串都可以贡献答案。

维护最大匹配长度 可以参考   spoj-lcs2 解题报告 

有所不同的是不需要在每一个B中都匹配,只需要至少一个匹配就行了,因此是取所有串的最大匹配长度即可。

 

hdu 3518 Boring counting (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=3518

题意:

给一个字符串,问字符串中,至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。

思路:

考虑SAM

SAM上的一个节点表示的是一段长度从[st[st[i].link],len+1,st[i].len]的字符串。

考虑其right集合,如果right集合中最大的r设为rightmost,最小的r设为leftmost.

那么如果rightmost-leftmost+1 > st[i].len ,说明什么呢?

说明该状态所表示的最长的字符串能够至少放下两个而不重叠。

即从[leftmost-st[i].len+1,leftmost]一段 和 从[rightmost-st[i].len+1,rightmost]一段。

如果最长的能放下,那么其他的也一定能放下。因此对答案贡献为st[i].len – st[st[i].link].len

如果rightmost-leftmost+1<=st[i].len,也就是rightmost-leftmost<st[i].len

这个时候长的字符串因为重叠了不能出现2次,但是短的字符串仍然可以贡献答案。

考虑如下图:

此时对答案的贡献为rightmost-leftmost+1 – (st[st[i].link].len+1),化简得到rightmost-leftmost-st[st[i].link].len

综合2种情况,SAM中每个节点对答案的贡献是 min(rightmost-leftmost,st[i].len)-st[st[i].link].len

需要注意的是只有在st[i].link存在并且rightmost-leftmost>st[st[i].link].len 时 才更新答案

leftmost可以在构建的时候直接求出,rightmost用拓扑序更新下即可。