PCA + kmeans

先记录一下PCA实战需要用到的安装包(arch下,python2环境)

python2-scikit-learn

python2-numpy

python2-pandas

python2-matplotlib

python2-seaborn

pandas.DataFrame

pandas 数据结构介绍

 

几个和科学计算数据分析有关的重要的python库: NumpyMatplotlib ,pandas

(之前数字图像处理课程都接触过了orz)

其中matplotlib 主要用于图像绘制

sklearn 是用于机器学习的python 模块

Seaborn也是用于图像绘制

 

 

str.fomat() 是 python2语法

format中的变量会按照str中{} 出现的顺序替换

 

 

 

 

PCA+kmeans 时间对比:

代码:

 

基础 Haskell 学习笔记

出于对函数式编程语言这一技能点的缺失…以及退役之后闲得蛋疼

打算浅尝辄止地学一下haskell

这篇笔记不会写成文档那样的详尽..毕竟函数式编程语言也是编程语言…有很多和其他编程语言(命令式?)相似的地方…

所以只会写一些简单的语法+让我感到惊讶的地方orz

总体的感觉…在里面看到了些python和pascal的影子orz…比如子界…已经好久没见到了

继续阅读“基础 Haskell 学习笔记”

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用拓扑序更新下即可。

 

hdu 6059 | 2017 Multi-University Training Contest – Team 3 Kanade’s trio (trie)

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

题意:

含 N 个数字的 A 数组,求有多少个三元组  (i,j,k) 满足 i<j<k 且a[i]^a[j] < a[j]^a[k]

思路:

考虑a[i]和a[k]二进制不同位中的最高位,此时满足题意的a[j]是该位与a[i]相同,其他位任意的所有a[j]的个数。

我们可以从1..n,依次插入a[k]到trie中,插入时,顺便用num[i][j]统计二进制第i位为j的数的个数。

当要插入a[k]时,a[1]..a[k-1]已经插入到了trie中。

trie上统计当某个节点,该位为0的数的个数和该为为1的数的个数。

需要注意这样统计出的数并不能保证i<j (但是可以保证i<k。。。)

因为我们的trie需要额外维护一部分ext.具体解释见代码注释。

 

 

hdu 5558 | 2015ACM/ICPC亚洲区合肥站 G Alice’s Classified Message (后缀自动机)

题目链接:

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

题意:

说了一大堆。。其实就是询问位置i开始的后缀和以位置[0…i – 1]开始的所有后缀中最大匹配的公共前缀长度

思路:

这个动态的过程很容易想到SAM啊。。

所以就一边匹配。。一边构建SAM就好了。。

需要注意的是,如果有多个最长,需要输出最左边的位置。

因此多维护一个leftmost,表示某个字符串第一次出现的结尾的位置。

 

 

 

 

SPOJ LCS2 Longest Common Substring 2[后缀自动机+dp]

题意:

求n个串的最长公共子串,n<=10

思路:

不会啊orz

先放一波参考资料&题解好了。

codeforces_Understanding Suffix Automaton in depth

code风景区_spoj_lcs2

code风景区_sam教学

candy SPOJ 1812 LCS2 [后缀自动机 DP]

 

首先参考下2个串的LCS的做法spoj-lcs

 

卧槽终于懂了…

一个串在上面走的时候记录与每个状态公共子串的最大值,注意出现次数向父亲传递,一个状态能到达说明了Suffix Link指向的状态可以取到最大子串,这一步对val后基数排序然后倒着更新就行了

 

…代码之后补

关键是理解这句话:一个状态能到达说明了Suffix Link指向的状态可以取到最大子串

比如如果状态S(从初始状态到S状态所表示的子串是abcbc) 能够最长向前匹配的长度是x,那么状态s的par的状态Q(从初始状态到Q状态所表示的子串是bc)也至少为x.

所以dp[link[v]] = Max{dp[link[v]],dp[v]}

 

妈个鸡。。。

没事改什么字符集大小啊。。。

上道题做的是数字。。就手贱把字符集的大小改成了12.。。忘了改回来。。WA到死。。。