Algo

BWT: Burrows-Wheeler transform (aka. 块排序压缩)。 一篇 Genome Biology 2009 的论文 《Ultrafast and memory-efficient alignment of short DNA sequences to the human genome》(Bowtie) 这篇文章使用BWT对人类基因组建立索引，并用贪心+回溯支持模糊匹配。 ...

愚人节专场，打一乐。官方tutorial A. Is it rated? puts("no"); B. Limericks 看样例35->57, 57->319, 391->1723，敏锐的觉察到可能是质因数分解。 for(int i=2;i<=x;i++){ while(x%i==0){ printf("%d",i); x/=i; } }...

Codeforces可以改handle了。 今年还可以改成已有的非活跃的账号的名字。 然后随便试了几个词，发现hello这个号last visit 8 yrs ago，然后就改成了hello了 233333。 ...

第一次作业 我的题目分别是Codechef Nov 2014的三道题 ： Chef and Churu https://www.codechef.com/problems/FNCS Sereja and Order https://www.codechef.com/problems/SEAORD The Spelling Problem https://www.codechef.com/problems/SPELL 福利内容？ 自认为写的题解还不如官方题解。QAQ。 T1简要题解: 分块+树状数组。对函数分块，预处理每个位置在每一块里出现次数。 T2简要题解: 贪心+排序。证明答案一定等于max(max(ai+bi),max(sumA,sumB))，然后贪心或随机化。卡掉了几个不正确的贪心。 T3简要题解: hash或trie树。给字典中的单词赋一个权值。对于每个不在字典中的词，尝试所有的出错方法，取权值最高的那个词。 ...

中文题面 题目链接 题意: 给你一个矩阵$M$,满足$M_{i,j}=M_{j,i}$，且$M_{i,j}>=0$。 让你构造一个矩阵$P$,满足： $P$是对称矩阵。 $P_{i,j}$要么等于零，要么等于$M_{i,j}$。 存在一个$S>0$,使得$P+P^2+…+P^S$中每个元素都是正数。 最小化$P$中元素和。 $M$是一个邻接矩阵，可以看成一个完全图。 我们知道$(M^k)_{i,j}$对应所有走$k$条边从$i$到$j$边权乘积的和。 满足第3个条件就需要所有点两两可达。 于是就是最小生成树了。 ...

设$f[i]$表示深度不超过i的严格n元树的数量。 有$f[i]=f[i-1]^n+1$。 $Ans=f[d]-f[d-1]$ 递推式很显然。 代码: n,d=map(int,raw_input().split()) f=[0]*17 f[0]=1 for i in range(1,d+1): f[i]=f[i-1]**n+1 print f[d]-f[d-1] 这个题目答案可能很大很大.. 所以最坏情况下是跑不出来的…

题意: 有一个字符串生成器，初始时生成的字符串为空串，它每次按照给定概率随机生成一个小写字母，加在当前已生成字符串的后面。 给定N个长度为L的字符串，每个字符串由小写字母组成。 如果在某个时候，发现每个给定字符串都在当前已生成的字符串中作为子串出现过，生成器就会停下来，将当前生成的字符串作为输出。 求输出字符串长度的期望值。 ...

给出M个询问：在[l,r]之间找到一个在这个区间里只出现过一次的数 强制在线。 设$p[i]$为$a[i]$上一次出现位置,$q[i]$为$a[i]$下一次出现位置。 每次查询的就是 $ max _{l<=i<=r} a[i] $ 且$q[i] >r$ , $p[i]< l $。 可以排序然后树套树做。 偷懒写了KD-TREE。。复杂度$O(n^{5/3})$，不强制在线的话可以做到$O(n^{3/2})$ 。 ...

给出一系列点p_1, p_2, … , p_n，将其分成不多余m个连续的段，第i段内求一个点q_i，使得q_i到这段内点的距离的最大值的最大值最小 最大值最小，先二分答案。 再从每个开始点二分，用随机增量法的最小圆覆盖判断最长能扩展长度，段数是不是$<=m$。 但是有个问题。 如果m=n的话，每段长度都是1。 这样做是$O(n^2lgn)$的。 ...

去年省选的题。 突然发现还没有A这个题。 就抽时间写了写。 询问的那个树形dp很好搞。 我们把原树中有用的点(被选的点，和他们之间的lca)拿出来，建一棵虚树。 在虚树上dp就行了。 类似"消耗战"(为啥听着像卡组名)。 ...