111qqz的小窝

poj 1509 Glass Beads (后缀自动机求最小循环表示)

Nov 4, 2017 · 2 min read · 后缀自动机最小表示法

题意：给定一个循环字符串，问字典序最小的串的开始位置。思路：之前用poj 1509 解题报告-字符串的最小表示法 A过字符串的最小表示法的复杂度是O(n)，代码也不是很难写，不过由于最近在学SAM,所以用SAM写了一下。参照张天扬的论文：把原串复制一遍到后面，然后构建后缀自动机。从初始状态开始，每次走字典序最小的转移，走|S|之后得到的就是最小循环表示。如果求的是最小后缀，就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后，再添加一遍原串。 /* *********************************************** Author :111qqz Created Time …

Read More
hdu 4622 | 2013 Multi-University Training Contest 3 Reincarnation (后缀自动机)

Nov 4, 2017 · 2 min read · 后缀自动机

http://acm.hdu.edu.cn/showproblem.php?pid=4622 题意：给一个字符串，给出若干询问，每组询问给一个区间[l,r]，问区间中本质不同的字符串的个数。思路：观察发现，有10000组查询，字符串的长度最多才2000，所以可以预处理一波。我们先考虑如何处理整个区间中，本质不同的子串数量。考虑SAM，由于后缀自动机中每一条从初始状态出发的路径都对应的一个子串，同时后缀自动机是最简的，所以问题也就变成了从初始状态开始不同路径的数量。每个节点 u 表示的子串长度在 [min[u],max[u]]范围内. 又由于max(u.fail) = min(u)-1 因此u表示的子串的长度就是变成 …

Read More
SPOJ LCS Longest Common Substring （后缀自动机模板题）

Nov 3, 2017 · 5 min read · 后缀自动机

题意：给出2个字符串(2.5E5)，问最长公共子串的长度。思路：拿一个串建SAM 由于SAM上的任何一个状态，都对应一个或者若干个子串，然后拿另一个串在SAM上面跑就行了 20171110UPdate:我好像说得太简略了。。参考clj的冬令营讲稿： * 给两个长度小于100000的字符串A和B，求出他们的最长公共连续子串。 Ê我们构造出A的后缀自动机SAM * 对于SAM的每个状态s，令r为Right(s)中任意的一个元素，它代表的是结束位置在r的，长度在[Min(s),Max(s)]之间的所有子串。 * 我们不妨对状态s，求出所有B的子串中，从任意r开始往前能匹配的最大长度L，那么min(L,Max(s))就可以更 …

Read More
HDU 5970 | 2016 CCPC HeFei onsite J 最大公约数 (打表找规律)

Nov 2, 2017 · 2 min read · 打表

题意：有这样一个有关最大公约数的函数: 函数 f(x, y): { c=0 当 y>0: { c +=1 t = x % y x = y y = t } 返回 c * x * x } 给出三个正整数n,m,p，你需要计算: $$ \sum_{i=1}^{n} \sum_{j=1}^{m} \left \lfloor \frac{i*j}{f(i,j))} \right \rfloor $$ n <= 666,666,666, m <= 666, p <= 666,666,666。思路：打表找规律。但是找规律也要按照基本法观察到m比较小，对于固定的j,容易看出f(i,j)和f(i+j*k,k)是等价 …

Read More
hdu 6038 | 2017 Multi-University Training Contest - Team 1 E Function (置换群找循环节)

Nov 1, 2017 · 2 min read · 循环节置换群

http://acm.hdu.edu.cn/showproblem.php?pid=6038 题意：给出两个序列 a 和 b ，求满足 f[i]= b_{f[a[i]]} 的函数个数。思路：分别找两个序列的循环节，这一点是比较容易想到的。由于点都在0..n-1 或者0..m-1，因此没必要建图跑dfs找循环节，直接while就可以了。然后发现一个循环节如果符合条件，那么对答案的贡献是循环节长度。但是没有想清楚，什么才是符合条件的循环节。结论是，b的循环节长度当且近当是A的循环节的长度的因子时，b的这个循环节会对答案贡献其长度的大小。对于A的每个循环节，都是互不影响的。而且我们只关心循环节的长度。因此O（n） …

Read More
hdu 6034 2017 Multi-University Training Contest - Team 1 B Balala Power! (贪心)

Nov 1, 2017 · 3 min read · 贪心

http://acm.hdu.edu.cn/showproblem.php?pid=6034 题意：有一个仅由小写字母组成的字符串，要求将a..z的字母，对应到0..25，每个数字只能被一个字母对应，得到一个26进制的数，现在问这个数最大是多少。注意不允许有前导0，除非这个数本身就是0. 思路：贪心。看哪个字母的权值最大。可以用类似高精度加法的方式处理。对于前导0的部分，用一个bool标记首位（如果字符串长度为1就不标记）对于26个高精度数的排序，可以用交换id的技巧。以及，如果排序之后，发现权值最小的数被对应到数字0，但是又在某个长度大于1的字符串的首字母位置出现过。我初始想当然得，把该字母和最小的可以出现在首位的字 …

Read More
BZOJ 1230: [Usaco2008 Nov]lites 开关灯 (线段树区间修改，区间查询)

Nov 1, 2017 · 2 min read · lazy标记线段树

1230: [Usaco2008 Nov]lites 开关灯 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 1676 Solved: 874 [Submit][Status][Discuss] Description Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= …

Read More
hdu 6043 | 2017 Multi-University Training Contest - Team 1 K KazaQ's Socks （循环节）

Oct 31, 2017 · 1 min read · 循环节

http://acm.hdu.edu.cn/showproblem.php?pid=6043 题意： n双袜子标号1到n，初始在抽屉里，每天早晨穿一双标号最小的袜子，晚上把脏袜子放到盆里，如果放完之后喷子里已经有了n-1双脏袜子，那么就要洗，然后在第二天晚上放回抽屉里。问第k天穿的是标号为几的袜子。思路：手写了几个发现对于n双袜子,标号出现的情况是: 1,2,3...n,1,2,3...n-2,n-1,1,2,3...n-2,n 所以特判k<=n的情况然后算循环的次数即可。 /* *********************************************** Author :111qqz Created …

Read More
hdu 6033 | 2017 Multi-University Training Contest - Team 1 A Add More Zero

Oct 31, 2017 · 1 min read

http://acm.hdu.edu.cn/showproblem.php?pid=6033 题意：问最大的x,满足 $$ 10^{x} \geq 2^{m}-1 $$ 思路：看到指数的比较大小，直觉就是取下对数啦其实直接可以把1忽略，因为2的幂次显然不会出现末尾是0，所以不会影响结果两边对10取对数得到 $$ x\leq \log_{10} 2^{m} $$ 右边用换底公式就是 $$ \frac{m}{\log_{2}10 } $$ 代码： /* *********************************************** Author :111qqz Created Time :2017年10月31日 …

Read More
在wordpress 中输入数学公式

Oct 31, 2017 · 1 min read · latex

查了一些资料。。发现不是要装各种插件（还不一定能用，比如和crayon冲突。。就是讲得很不清楚orz。。又下一个win下的公式编辑器之类的软件是什么鬼啊？干脆记录一下必要步骤。只有一步。 1. 配置mathjax. 加入下面代码到该主题的header.php中 <head>和</head>之间（要放在**<?php wp_head(); ?>**） <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-MML-AM_CHTML'></script> …

Read More
- 17
- 18
- 19
- 20
- 21