夜间模式暗黑模式
字体
阴影
滤镜
圆角
后缀数组复习
http://hihocoder.com/problemset/problem/1403 小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为长度为 N 的数构成的数列。小Hi在练习过很多曲子以后发现很多作品自身包含一样的旋律。 旋律可以表示为一段连续的数列,相似的旋律在原数列不可重叠,比如在1 2 3 2 3 2 1 中 2 3 2…
近期题目
http://codeforces.com/problemset/problem/89/C 网状链表模拟...有点难写... 内存有可能开不下,要分类讨论一下内存... [crayon-5ed79aad745c7064726947/] (更多…)
Codeforces Round #140 (Div. 1) C. Anniversary
通过这个题目发现了一个很奇妙的性质 \[gcd(fib(a),fib(b))=fib(gcd(a,b))\] 这样只需要枚举下标的公因数,然后看看有没有\(k\)个符合条件就可以了。 注意,因为是通过\(\frac{r}{p}-\frac{l-1}{p}\)判断的。而本质不同的\(\frac{r}{p}\)只有\(\sqrt{r}\)级别,所以只需…
Codeforces Round #277.5 (Div. 2) E. Hiking
首次接触到了这种\(01\)分数规划类的问题。 http://codeforces.com/problemset/problem/489/E \(01\)分数规划,指的是两个数组\(a\)与\(b\),通过构造一个\(01\)序列\(s_i\)使得\[\frac{\sum a_i\times s_i}{\sum b_i\times s_i}\]最大…
Codeforces 487C
http://codeforces.com/problemset/problem/487/C 感觉是很糟糕的一个题... 首先,一个合法的构造,一定是开头是\(1\),结尾是\(N\),因为如果中间出现\(1\)或者\(N\)的话,一定会有重复。 然后我就觉得所有的合数都是不行的,因为任何的合数都可以拆成\(p \times q\),但是有的合数,…
近期题目
http://codeforces.com/problemset/problem/156/C 这个题目的关键在于看出修改前后的字符串ASCII码和不变,而且所有ASCII码和相同的字符串可以互相到达。 这样就做一个简单DP就可以了。 [crayon-5ed79aad74cf2197984576/] http://codeforces.com/pro…
最近的四道题
http://codeforces.com/contest/380/problem/C 题目大意:给定一个括号序列,给出一个询问\(l\)和\(r\),回答\(l\)到\(r\)这个范围内,最长的合法子序列是多长 经过观察,这个题目符合区间合并性。 \[w[Total].len=w[Left].len+w[Right].len+min(w[Left…
Codeforces Round #369 (Div. 2) E
http://codeforces.com/problemset/problem/711/E 这个题目的关键在于,取余的数字只有\(10^6+3\) 然后这个概率其实非常简单,就是\[1-\frac{\prod_{i=0}^{k-1}(2^n-i)}{\prod_{i=0}^{k-1}2^n}\] 我们只需要求\[\frac{\prod_{i=0}…
Educational Codeforces Round 7 F. The Sum of the k-th Powers
http://codeforces.com/problemset/problem/622/F 第一次写了一下插值。 插值法主要用于解决知道某函数是几次函数(不妨设次数为n),并且可以很方便的计算出在这个函数上的n+1个点。 然后我们可以计算需要的值。 百度百科_拉格朗日插值公式 百度百科说的就不错了... [crayon-5ed79aad75126…
Codeforces AIM Tech Round 3 (Div. 1) 题解
幸好没参加,参加了就得回到Div 2。 http://codeforces.com/contest/708/problem/A 题目大意: 给定一个字符串,选择一个非空子串进行前移操作(\(...b->a->z\)),求经过操作后字典序最小的子串 傻吊题,找到第一个两个\(a\)之间串进行操作就可以了,注意\(aa...a\)要特判就行了。 [cr…