12
2
2014
5

【除草+净化debuff向】屯题计划

刷水严重。。不能这样了。。

屯题是不是会比较有压迫感。。


counter:

50


3787: Gty的文艺妹子序列:gty教你分块系列。。。没什么好说的吧。。分个块各种数据维护一下。

1416: [NOI2006]神奇的口袋:网上证明很多,两个性质

1.只要满足[tex]x_i>x_{i-1}[/tex],[tex]x_i[/tex]的取值不影响答案。

2.[tex]y_i[/tex]序列的顺序任意交换也不影响答案。

性质2这里用不上,性质1就可以了,另外还有高精度。

3761: Zhenhuan:乍一眼水题,仔细想想不对劲。。想通了也挺水的。。

分奇偶讨论,设答案为[tex]ans[/tex]。

若[tex]n[/tex]为偶数,则对于[tex]a_i[/tex],若[tex]i[/tex]为奇数,则使用[tex]1\sim a_i[/tex],若[tex]i[/tex]为偶数,则使用[tex]ans-a_i+1 \sim ans[/tex],这样使用显然最优,所以答案是相邻和的最大值。

若[tex]n[/tex]为奇数,最后一位和第一位按照上述方法会产生冲突,先按照上述方法取得[tex]ans[/tex]最小值。

第一位使用[tex]1\sim a_1[/tex],第二位使用[tex]a_1+1\sim a_1+a_2[/tex],对于第[tex]i[/tex]位,若[tex]i[/tex]为奇数,尽量往大的使用必然最优,偶数相反,若与前一位产生冲突,则跨越该冲突部分特殊计算,若不产生冲突,易证后面都不会冲突,所以保留跨越冲突部分的位置就可以了,外面套一个二分即可。

3759: Hungergame:无脑博弈问题,判断是否有子集xor为0。。

3751: [NOIP2014]解方程:没什么好说的。。考场上想不出来就是弱。。

3749: [POI2015]Łasuchy:枚举1号食物的状态,状态分为四种,在食物左边的人吃或不吃,在食物右边的人吃或不吃,用二进制表示就是00、01、10、11,然后判断一圈回来看是否可行。

3720: Gty的妹子树:玩烂的东西。。带插入区间K极值的做法可以搬过来。。由于是棵树,那就可以块状树。。感觉好烦。。搜了下题解发现不裂块能过。。那就不裂块把。。这样就方便很多。。

3680: 吊打XXX:温习了一下爬山。。。说实话爬山用来乱搞效果都蛮不错的。。

3722: PA2014 Final Budowa:枚举第一个游说的节点,然后check一下是否可行就好了。。证明如下,若当前状态获胜,则敌方要扳平必然需要在一个我方获胜节点花费一个代价,由题目条件可知一个点的下属是奇数个,所以若状态为平局,则必然还至少有一个空节点,我方只需要在该空节点花费代价即可,状态平局和为负同理可证。

3670: [Noi2014]动物园:填坑。先做一遍kmp,然后做一遍类似kmp的匹配,如果长度大于[tex]\lfloor \frac{i}{2}\rfloor[/tex]就往回跳,可以证明正确性。。自己找几个例子试试就好了。

3669: [Noi2014]魔法森林:填坑。LCT速度变慢了。。30min+才码出。。

3671: [Noi2014]随机数生成器:填坑。

3678: wangxz与OJ:T T。。

2109&2535:[Noi2010]Plane 航空管制:其实还算是蛮简单的拓扑排序,对于第一问,把边反向拓扑排序,对于第二问,枚举节点,删除该节点,做第一问直到队列为空即为答案。

3045: 电话线路:最短路。。我怎么又在刷水了。。

3620: 似乎在梦中见过的样子:kmp n次就好了。。为何[tex]O(n^2)[/tex]的复杂度开15000。。一开始题目看错了也是醉。

3629: [JLOI2014]聪明的燕姿:爆搜。。把约数和表示出来,把S一个一个拆约数暴力dfs就可以了。

3796: Mushroom追妹纸:很显然可以二分,那就二分+hash。。一开始拼命wa。。不知为何。。后来发现hash被卡了。。我可是双关键字hash啊。。。orz蘑队。。快去解决hash killer3

3798: 特殊的质数:分段打表,[tex]n~mod~4=1~or~n=2~(n~is~prime)[/tex]即为答案。证明不会。此题为分段打表练手题。。

3799: 字符串重组:没什么好说的。。

3789: 扫雪车:上下限最大流get

3790: 神奇项链:manacher+后缀min dp。

3606: [Sdoi2013]Insider:线段树套平衡树+射线法什么的。。出题人卡的一手好splay,query的时候都要splay才能过。。还记得当场同步赛做的时候码出了只过了两个点,当时我还想我一定是写挂了什么地方。。现在想想没准是被卡splay。。醉了。。

3682: Phorni:后缀平衡树

3791: 作业:果然是傻啊T T。。。K次操作后最多分成2*K-1段,然后就直接DP

3600: 没有人的算术:替罪羊树好像很爽的样子?曾经亲测替罪羊树艹treap速度n倍,写写也好方便。。我要成为替罪羊树选手。。

3792: 跑步:边当点做矩阵乘法。。我会告诉你我这么长时间没写矩乘导致写错了么T T。。

3797: Ural 1745 Yet Another Answer:把一个括号序列缩成 )))((( 的形式,设左部分的右括号为l,右部分的左括号r,删去的括号长度为v,先按照r>=l在前,r<l在后为第一关键字,这样可以保证左括号先递增,然后第一部分按照l递增排序,可以YY正确性,如果小的l都无法与之前匹配,那么大的l就更不必谈了,第二部分同理,按照r递减排序,然后做dp即可。

[tex]f_{i,j}=max\{f_{i-1,j},f_{i-1,j-a_i.l+a_i.r}+a_i.v+a_i.l*2\}(j-a_i.l>=0)[/tex]

3601: 一个人的数论:将狼踩尽的blog写的非常详细,证明那个式子是个d+1次多项式在杜教的在某篇论文里有证明。

3439: Kpm的MC密码:网上全是主席树维护dfs序?为什么我感觉每个点上挂个链表就没了?

3516: 国王奇遇记加强版:题解一大拨。。

3806: Neerc2011 Dictionary Size:字母树前缀后缀搞一下。

3681: Arietta:可持久化线段树优化网络流

3809: Gty的二逼妹子序列:莫队+块状数组。。除了这个小技巧外什么都没有了。。

2466: [中山市选2009]树:异或方程组。。没什么好说的。。在补知识点QAQ。。

1923: [Sdoi2010]外星千足虫:异或方程组。。bitset压位。。

2115: [Wc2011] Xor:异或方程组。。问题可以转化为任意一条简单路径和所有简单环的最大xor子集。

3813: 奇数国:压位一下就好了。。

2822: [AHOI2012]树屋阶梯:卡特兰数。

2322: [BeiJing2011]梦想封印:类似2115的做法,先考虑静态做法,现在可以到所有点,那么跑一棵xor生成树,生成树上所有点的dx代表1号点到x点xor和,每一条非树边代表了一个简单环,把简单环压入异或方程组消元,不等价的简单环最多只有w个,w为number的位数,设有s个,考虑1号点到每个点的方案,那就是所有不等价简单环的子集即[tex]2^s[/tex]个,到这里我们可能会单纯的把[tex]2^s*n-1[/tex]记为答案,但是有些节点是等价的,表现在异或方程组中就是消元后是否相等,最坏情况下不等价的节点数是[tex]2^{w-s}[/tex]级别的,但是条件是树边全是构造的大值,非树边所代表的简单环是构造的小值,然而我们的生成树是随机跑的,所以远远到不了这个级别。设不等价的节点数为t,答案就是[tex]2^s*t-1[/tex]。现在扩展到动态加边做法,生成树显然是可以扩展的,然后每次加点都判一次有多少不等价的节点,然后就没了。。判等价我用了map。。用hash会快很多。。

upd.2015.1.13:后来发现链就可以卡掉这种做法,可以改进一下,只有当加入了一条有效的非树边对所有点的简单路径判不等价节点,有效非树边只有[tex]w[/tex]条,这样复杂度就有保证了。

2460: [BeiJing2011]元素:排个序做异或方程组。。没什么好说的。。

2844: albus就是要第一个出场:网上有题解。。那就不多说了。。

3812: 主旋律:十分鬼畜的容斥+压位+枚举子集DP,代码很短。。写起来欲仙欲死。。

3823: 定情信物:比较有趣的题目,很容易找到一个[tex]O(n^2)[/tex]的递推式,[tex]f_{i,j}[/tex]表示i维下的j维元素有几个,递推式就是[tex]f_{i,j}=f_{i-1,j}*2+f_{i-1,j-1}[/tex],表现在现实意义上就是第j维的某个元素经过拖动一分为二,第j-1维拖动轨迹成为第j维,其实画出来就是一个竖直转移带乘二的权的杨辉三角。[tex]O(n)[/tex]递推式就比较有趣了,通过上面这个递推式推出得到前几项的通项公式,观察通项公式即可得出递推式。[tex]f_i=\frac{f_{i-1}*(n-i+1)}{2i}[/tex],线性逆元就不说了,但是有问题,逆元可以不存在= =。。。那我只要再保存一个数字里有多少p就可以了,有p就是0。

2426: [HAOI2010]工厂选址:贪心。

3106: [cqoi2013]棋盘游戏:记忆化搜索。

3609: [Heoi2014]人人尽说江南好:公式题。。

2282: [Sdoi2011]消防:直径上跑一下就好了。

3505: [Cqoi2014]数三角形:题解一大波。。我就不说了。


第一次屯题完结。。感觉棒(he)棒(he)的(da)


 

Category: Something Boring | Tags: Something Boring | Read Count: 2619

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com