Todo List

Python 和 Java都要学会。。
TCO2010做完。。(还差3场)
TCO2009准备去做掉。。。
Latex要学会。。。用Latex把POI2010的报告写好。。(这个不急。。寒假最好能完成)
gdb sed gawk gprof 等等都得会啊。。。
。。。苦练计算几何。。。
还是做做OJ把。。争取寒假结束之前SGU刷到rank 50。。。(目前rank137)

CF 48

哎。。今天的状态感觉很烂。。。
A都resubmit了一次>_<。。。
不过后来感觉好一点了。。做了A之后发现B好麻烦。。就去做C。。然后我SB了。。C Fail了>_<。。。
5555555555 C不Fail我就能前10了么T_T。。
写了B之后去写D。。。。
然后我的D看错了题意。。。最后才发现。。被Cha了2次同时交了3次。。结果只剩600分。。。
幸好E做出来了。。。跟tourist的算法一样yeah~~~~不过他比我快了一倍>_<。。。
tourist太BT了。。。
rating居然没跌停。。太不可思议了。。。

434. Chemists

http://acm.sgu.ru/problem.php?contest=0&problem=434
题意自己看>_<
首先,令A[i]=S[i]-D[i]。。那么题目的目的就是把所有A[i]变成0
可以发现。。对于和为0的t个数来说。。可以用t-1次完成倒水。。。
那么。。这个题目就变成了把n个数分成尽量多的部分。每个部分的和都是0。。
显然可以3^n的集合dp。。不过这显然是要TLE的。。
其实最关键的地方就在这里。。。
考虑任何一个数的序列。。比如a1,a2,a3,a4这样的。。如果只能把一些连续的分成一段。。那么显然是每当部分和为0的时候分一下最优。。。
那么问题就转化成了。。求一个最优的序列。。为0的部分和尽量多!
这是和很傻叉的。。可以dp在2^n解决。。。

Sgu 388. Soap Opera

http://acm.sgu.ru/problem.php?contest=0&problem=388
。。。开始写点题解了。。
题目大意:
给你一个二分图,然后有红色和蓝色两类边,求一个最大子集,
使这个子集不论对于红色边,还是对于蓝色边,都能有完美匹配。。
比如红色边是1-2,3-4,蓝色边是1-4,3-2。。那么1,2,3,4满足条件。。

这个题目初看很不可捉。。仔细想想发现还是可捉的。。关键是说。。在这个结果子集中,每个点都被一条红边和蓝边
连接,那么可以看成红边进入该店,蓝边离开该点。。那么其实就是说。。。。是一个流>_<。。。
那么我们给边一个费用1。。找一个最大费用可行流就可以了。。
算法具体就不说了。。我是用消圈算法的。。。因为有正环所以spfa之类的就要悲剧了。。

P.S.洲妹妹好厉害。。SPOJ已经轻松Rank50了Orz!!!!!!!!!!!!1

SPOJ 最近做的题目

傻叉题就不说了。。
Trees Again 
令Dp[root][Dep]表示子树根为root,最大深度(从root往下)是Dep的个数。。
然后考虑计算。。可以发现子树的状态只跟最深的两个节点有关。。
那么枚举这两个节点和它们的深度。。
然后有一点就是假如两个节点深度一样。。就会有重复。。要考虑一下。。
Easy Longest Common Substring
二分+Hash。。
Two Paths
跟TREECST一样的做法。。首先两个条路径必然有一条边把它们分开。。那么我们需要计算的就是对于每一条边。。它的上发子树和下方子树的直径。。画个图仔细想想就可以写出来了。。注意常数小心TLE。。。
Counting Arborescence
注意这里的图是有向的。。所以没法用那个xx矩阵。。。
所以只好集合动态规划Dp[set][root]表示set的顶点集合。。以root为顶点。。有几个Arboresecence。。。
然后推一下方程就可以了。。
Highway
块状数组。。我记得好像是GDOI的题目?
Copying DNA
集合DP。。记录一下目标串哪些被覆盖了。。常数优化一下>_<。。
好吧。。写的有点简陋。。有时间充实一下。。。

Plans

哎。。最近越来越颓废了。。。。做题目也没有神马精神。。。题解也懒得写>_<。。
效仿洲妹弄个plan激励一下自己>_<。。。
OJ:
    SPOJ有生之年刷到前50吧。。
    SGU暂时就不做了>_<。。。
    BZOJ好久没做了。。。哎。。。。
    MAIN里的POI15-17,PA08-10争取AK。。
算法:
    我的计算几何好差>_<。。。。好好学习学习计算几何。。。
    其它的各种算法似乎还是有一点漏洞的。。。。各种模块有时间复习复习吧。。。
    :各种网络流我其实不是很熟练。。需要加强>_<。。。字符串的各种算法AC自动机和KMP神马的好像长久不写真的是容易忘啊>_<。。上次我就被AC自动机鄙视了。。还一直不知道哪里写错了。。。。
    各种贪心之类的也要好好领悟。。。
    不能盲目做题啦。。。以后弄个本子记录记录心得体会吧。。。。
比赛:
    TC和CF和CodeChef能参加都参加参加吧。。。
    TC以前比赛的题目都去做做。。锻炼代码能力。。。
    多多看看别人的代码。从中学习。。。
一些需要做的东西:
    果然看了题解之后不写代码等于不会啊>_<。。。
    GCJ的题目都去写写吧。。参考参考别人的代码。。。
    国家集训队的作业也要多看看。。。。
PS:
    别再看神马微小说了>_<。。浪费时间啊。。。
@Update:
    SPOJ rank:220
    SGU rank:165
    POI 17:差Ones。。
    PA 2010:差很多。。。
@Update 12.25:
    发现我从来都只是在SPOJ上挑会做的题目捉。。这毫无意义啊>_<
    SPOJ先放放。。。
    TCO 2005-2010都去做掉。。这主要是锻炼代码能力。。
    TCO 2010 Q1-Q3,R1,R2 Finished。。
    还有就是系统学习字符串理论,恶补计算几何。。至少要熟练起来。。然后对贪心的题目也要学会深入理解。。。
    Crotian还有一个类似中国CTSC的比赛啊,题目还是挺好玩的。。好好做做吧。。。
    NOI剩下的题目都应该做掉了。。。
    CTSC尽量吧。。。
    先把POI2007给AK掉。。

SPOJ 5103. Top 10

这道题我一年前看到过。。。当时吓死了。。毫无思路。。
现在再看看。。发现好像是。。傻叉题?
https://www.spoj.pl/problems/TOP10/

首先注意到一个性质。。就是一些字符串按字典序排序后。。以某个字串开始的字符串是一个区间。。
那么对于这个题目。。我们将所有的字符串的后缀排序。。由于后缀的前缀就是子串。。所以对于一个询问
只需要用线段树来找区间前10大值就可以了。。

注意到显然不能直接将后缀提取再排序。。
可以使用hash搞。。复杂度NLogN^2。。

Page 1 of 212