ZOJ月赛 nimendongde第二场。。。

酱油记。。

这次月赛似乎很囧。。。。一开始我们很顺利。。

我刷掉了几道水题。。然后我注意到H。。觉得这个模型我在Ural上见过。。

就搞掉了。。。

然后又看了J。。觉得这个模型在TC和SC省选上都见过。。就又去写了。。

不过WA。。。想了半天才明白原来是有个很邪恶的情况。。就是可以在中间挖。。

然后也搞掉了。。。

然后去做A。。一看到A就觉得应该是双向搜索。。但是我太SB了。。搞了半天还是TLE。。。

酱油完毕。。。。

除草。。。。。Sgu一点水题题解。。。

只为除草

SGU514:看到题目之后用调整法推一点性质,就可以用集合dp乱搞了。。

SGU508:很水的概率题吧。。直接算一下就可以了吧。。。。

SGU504:二分一下就可以乱搞了。。

SGU503:题目很长很凌乱。。但仔细的阅读之后还是可以用集合dp解决的。。。

SGU513:通过观察发现3个点的某种性质。。然后就可以做了。。。

。。。。。

这还叫题解么。。。。

COCI 2010/2011 #5

这次比赛难得那么好的一个AK的机会。。然后我SB掉了。。。

前2题无视。。第三题从小到大一个个枚举过去。。。N^2就可以过。。我写成了N^2LogN。。然后最大点居然只要0.04s。。。这。。。

第四题一个简单的dp。。状态分3类就可以了。。

第五题可以线性。。具体就是直接做开始是很困难的。。可以考虑从中间往两边扩展。。那么搞出所有极大区间。。

然后用一个栈扫描一遍就能得出答案。。。

第六题其实很水啊。。把版按照棋盘黑白染色。。可以发现两个颜色是互不影响的。。就转变成了两个经典的矩阵染色问题。。

这个染色问题显然可以2d线段树。。不过我觉得这个常数过大还是用线段树扫描一下吧。。。。

然后处理一下Load和Save。。可以发现其实Load和Save只是意味着有些操作是没用的。。

删掉就行了。。。

然后我处理错了。。。只有13分>_<。。。。。。

比赛结束了按洲妹的改了一下就AC了。。。。。。擦。。。

经验+总结:

以后参加比赛都要写写总结之类的。。。这样才能吸取教训嘛>_<。。。首先是第3题。。我犹豫了半天要不要改N^2LogN的算法。。因为我觉得不怎么可能有数据能卡这个。。。这浪费了不少时间。。非常的不应该啊。。应该在写题目的时候就估算好复杂度。。直接写N^2的多好>_<。。。还有第5题狂对排了一下。。感觉上就能在比赛的时候放心不少。。
最失败的是最后一题。。这说明细节是非常重要的。。一些重要的细节问题一定要多加深思啊>_<。。。。
然后直接在脑子里自以为是的想一下就写程序是很不行的>_<。。应该在纸上多画一画之类的。。。

还有感觉自己代码能力好像还过的去。。但是平常写程序的时候变量名称有时候都要考虑一会儿>_<。。而比赛的时候无疑是很浪费时间的。。。但是混乱的名称又很那啥。。。应该组织一下自己的各种变量名称了>_<。。。

WC2011

    在这么冷的地方>_<。。。讨厌死了>_<。。。。当面Orz了各种神犇,好高欣啊~~~~~~~~~~~

    。。。。最后的比赛悲剧的一塌糊涂T_T。。。

   。。。我似乎前两个小时在写第一题的错误算法。。。最后只能交20%。。。。>_<。。。明明就不靠谱的写神马嘛T_T。。。

   然后第二题想做部分分。。。写了CQX讲的线段树然后TLE了一堆。。。不过似乎没看清题目然后最后发现还能暴力骗点分的。。最后15分钟狂敲暴力骗分。。。似乎写错了>_<。。。。没救了55555555555555.。。。

   第三题做的时候被没多少时间了。。。裸随机化乱搞骗了50分。。。。啊啊啊啊。。。。我这么弱还是去混高考啊。。。没救了

notes….

1.LQP的那个题目二进制求结果确实很霸气。。。但其实还有更囧一点的办法。。
考虑一个经典问题,就是给你n个数和两个格子,每个格子只能记一个数,然后求这堆数中出现超过n/2的那个数。。
这个是可以搞出来的。。具体的说步骤是这样的,
记录 一个数a和一个计数器c。。
考虑下一个数b,如果a==b,那么c++

如果a!=b,如果c>1,那么c–,否则将a替换为b,令c为1。。。。
这个的证明是很显然的。。因为其它所有的数也不能吧这个出现次数最多的数消掉。。
所以最后的数必然是这个出现次数超过n/2的数。。
那么。。最关键的一点是。。这个是可以合并的。。
那么我们用Lca算法就可以搞出所有询问的可能的那个答案。。
然后验证。。。。

可以用Tarjan搞。。。

验证我也有一个很那啥的方法。。。具体就是对所有相同权值的点。。提取出来。。。。可以建成一棵树(可以看成忽略其他权值的点没有价值。。那么很多节点都可以缩在一起,同时有一些0权点去啊)。。可以通过dfs的办法在搞出所有这样的树。。然后离线所有询问。。可以得出每个节点在那些这样的数中第一个祖先,然后出现个数就是这两个节点的第一个祖先间长度和。。
就是Tarjan。。。

于是可以很复杂的用两次Tarjan搞定。。复杂度为O(N*a(N)),a为某函数的反函数>_<。。。。

复杂度似乎好了一点。。编写的话好像复杂了一点。。不过也不是很难写。。。。

 

2.Stone的那道有些相似的题似乎是POI2009的Lyz?我做过啊。。。

可是还是没想出来。。。太弱了T_T。。。。

 

3.JZP教主的题目似乎还有NLog^2N的算法。。。。如果树分治的话。。

关键的问题说白了就是给一些有序数组,然后求所有数的第K大。。。

这个问题。。。有一个论文算法是Log(总大小)*数组个数的。。

然后放到这个题目里面似乎就是N*LogN*LogN。。。

(。。。。。但那个算法似乎只有理论价值>_<。。。。。太BT了。。。)

 

不过也有一个比单纯的二分答案好很多的算法:
具体是维护所有有序数组的中点,
那么如果当前Kth>=Size/2。。那么最小的那个中点的前面是没用的。。删掉前面那些。。

如果Kth<Size/2。。那么最大的那个中点的后面是没用的。。。删掉后面那些。。

然后需要删Sum(Log Size[i])次。。。
同时维护的代价是Log Log(N)。。。

Sum(Size[i])=N。。

Sum(Log(Size[i]))=

Log(Mult(Size[i]))<=Log(N/Log N)^LogN)=

Log(N/LogN)*LogN。。。

 

Mult(S)表示集合S各个数相乘。。。。
那么复杂度就是Log(Log(N))*Log(N/LogN)*LogN。。。

比Log^3N的那个要好一点囧。。。。

@Update:lqp那题的证明:

设出现最多的数的出现次数大于一半,设其为x

令S表示一个序列,F(S)表示该序列的权值(见后面的定义),G(S)表示该序列中x的个数-不是x的数的个数。。

假设通过合并,S这个序列对应的二元组是a和c

令F(S)= c (a=x)

         -c (a!=x)

我们只需要证明F(S)>=G(S)。。

由于G(所有数)>0,故F(所有数)>0,既最后的a是x。。

使用归纳法。

首先长度为1的序列满足条件。

将S分成L和R顺次相接,

因为F(L)>=G(L),F(R)>=G(R),

同时G(S)=G(L)+G(R),

我们只需要证明F(S)=F(L+R)>=F(L)+F(R)即可。

考虑合并的过程,

令L对应的二元组为aL和cL,

R为aR和cR。。

若aL=x并且aR=x,那么F(S)=cL+cR满足条件

若aL和aR中有且只有一个不为x。。

那么F(S)=F(L)+F(R)满足条件。

若aL和aR都不等于x。

那么F(S)=-|cL-cR|>=-cL-cR=F(L)+F(R)。。

故归纳命题成立,由归纳法只F(S)衡大于等于G(S)。

CF 51

这次比赛。。。我吸取教训。。。踏实做题。。。
终于做到了交了的都过了。。。真高欣啊。。。
。。最后rank 9。。。rating狂涨又变红了。。。。。
A:是个送分题。。有O(N)的做法。。不过在比赛的时候显然直接模拟10^7次就差不多了。。。
B:爆搜。。。
C:忽悠题。。。自己多试几次可以发现只要有个棋子跟边缘的距离小于等于4。。那么必然能弄出去。。
E:USACO和APIO的原题?乱搞就行了。。。。。
D:数位统计Dp。。注意一点,如果要记录mod 8*9*5*7=2520。。。可能就要MLE了>_<。。
解决的办法是注意到mod 10只跟最后一位有关。。那么只需要记录mod 252的值就行了。。
同时没有必要记录用过的数位。。。它们只有最小公倍数是管用的。。。
那么状态就是长度,用过的数位的最小公倍数,mod 252的值。。。。
可惜我写了一半的时候被我爸拉去吃饭了哎T_T。。。。

增强型LCP

增强型LCP

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:3 
Case Time Limit:1000MS

Description

 

Input

 

Output

对于每个Lcp(a,b)操作输出最长公共前缀

Sample Input

47 abab L 13 A 1 ab L 1 3 C 56 cb L 1 3 D 1 2 L 1 3

Sample Output

2 4 2 0

Source

看这个规模和时限Splay维护Hash值显然不靠谱。。
关键是修改操作很少。。于是我们平衡一下。。
那么就用块状链表吧。对每个块维护一个hash数组。
假设长度为N,分成S快。。那么可以在O(S+Log(N/S))的时间求出Lcp。。。
同时修改是O(N/S)的。。。
由于修改很少。。把S改的很小就可以让效率大幅提高。。。
由于本人代码能力太差。。就不写了T_T。。。
开哥就是用块链A的。。Orz啊!!!!!!

CF 50

。。。。悲剧了。。。rating跌停。。。直接变黄55555555555555

。。。。fail了两题。。

@Update:
总结:。。悲剧了就悲剧了。。要吸取教训!
B:。。。居然是因为题目看的不仔细。。把面积最小看成了x最小然后y最小。。。
5555555555555555555555555太傻叉了。。。。
D:。。。。完全是在乱做啊。。。胡乱构造怎么行呢555555555555555我是不是脑残啊。。。
好伤心。。。求安慰。。求抱抱。。。

Page 10 of 56« First...89101112...203040...Last »