111qqz的小窝

老年咸鱼冲锋!

To do list

  • 浮点数离散化
  • 矩形面积并,面积交,周长并
  • trie上SA,15年多校,金牌爷含泪推荐
  • 二维线段树(四叉树|树套树)
  • 线段树标记永久化。。是啥 。。李超线段树。。。又是啥
  • 扫描线扫描线?扫描线扫描线!
  • hdu 3255 体积并
  • hdu 5986
  • kd tree? kd tree!  (静态,动态)
  • 多个圆并,交
  • 主席树?主席树
  • 置换群,循环节
  • hdu 5558 | 2015 ICPC HeFei onsite G -> SA?SAM!
  • 拓扑+dp

[……]

Read more

英文文献中缩写的含义

学校毕设有文献的翻译任务,所以在这里记录一下,以后大概也用得到(?

e.g. for example 含义: 例如

i.e. 拉丁语 id est 含义: 也就是

s.t. 是 subject to (such that)的缩写,受约束的意思。

independent and identically distributed (i.i.d.) 独立同分布

 

20171214

记得之前被人在群里刷“宽神是我们的红太阳”还不理解…

为什么我这种菜鸡要被如此对待

现在想想,大概是觉得,“111qqz那么菜的人都还一直坚持打竞赛,我为什么放弃呢”2333

hust有2年没icpc的金了,今年N队终于拿了一个很好名次的金,还是很开心。

其实一直都有一种奇怪的自责,因为自己作为壮年选手的时候,恰好是华科实力最弱的几年,总觉得是没有担当起应有的责任。 为什么是奇怪的自责…因为我的实力并不能决定华科的upper bound 。。。

现在有了训练场地,有了各方面的支持,17级还有个很厉害的学弟,希望明年或者后年能进final吧,期待

其实我科是传统弱校,就算进过[……]

Read more

unicode 汉字表示不唯一的问题 (cjk字符集)

update:

遇到的汉字:

丹:63838

李:63969

昨天写的正则发现死活识别不了 “年”字…

放到unicode编码转化公式 查了下发现竟然是不同的字orz..

其实猜想到也许是日文的”年”…结果查询了下发现是韩文的锅?

具体参考为何Unicode中有字形完全相同的CJK字符?

以及兼容汉字的参考表:UF900

正则匹配中文及常用正则表达式 (转载)

先放一个同事安利给我的网站:regex101

查询匹配的中文字符unicode编码

 

正则表达式用于字符串处理、表单验证、日志数据分析等场合,实用高效。现将自己走网上搜索并总结的常用方法收集了一下:

匹配中文字符的正则表达式: [\u4e00-\u9fa5]
注:匹配中文还真是个头疼的事,有了这个表达式就好办了

匹配双字节字符(包括汉字在内):[^\x00-\xff]
注:可以用来计算字符串的长度(一个双字节字符长度计2,ASCII字符计1)

匹配空白行的正则表达式:\n\s*\r
注:可以用来删除空白行

匹配HTML标记的正则表达式:<(\S?)[^>][……]

Read more

tmp

 

 

PCA + kmeans

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

python2-scikit-learn

python2-numpy

python2-pandas

python2-matplotlib

python2-seaborn

pandas.DataFrame

pandas 数据结构介绍

 

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

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

其中matp[……]

Read more

基础 Haskell 学习笔记

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

打算浅尝辄止地学一下haskell

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

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

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

[……]

Read more

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位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡[……]

Read more

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与b[……]

Read more

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[……]

Read more

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

http://uoj.ac/problem/103

题意:

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

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

思路:

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

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

学习笔记之后补。

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

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

UPDATE:

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

更[……]

Read more

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)

累加即可。

[cray[……]

Read more

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[……]

Read more