12
2
2014
12

【除草+净化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: 4579
Avatar_small
wjh720 said:
Wed, 17 Dec 2014 21:55:07 +0800

简直神到爆

Avatar_small
Memphis said:
Thu, 18 Dec 2014 16:32:35 +0800

@wjh720: 大哥泥垢。。

Avatar_small
GTWGTW said:
Thu, 07 May 2015 13:42:56 +0800

简直神到爆

Avatar_small
DPE Result Comilla said:
Tue, 30 Aug 2022 01:26:07 +0800

Right now there is a press announcement issued by Education Ministry Bangladesh for PSC Exam Result Date 2022, based on the announcement the PSC Result 2022 will be announced on 30th or 31st December 2022 in case of any early announcement the Grade-5 exam result announced on 24th December 2022 respectively for all education boards and all divisions in the country.According to the previous reports, DPE Result Comilla the PSC Result Date 2022 Comilla Board is also last week of December, however, we will update the official result date here after the official announcement by DPE, as per DPE previous five years result from the announcement of this year result will be announced likely on 30th or 31st December 2022.

Avatar_small
meidir said:
Tue, 06 Dec 2022 05:28:12 +0800

It’s difficult to acquire knowledgeable folks during this topic, nevertheless, you be understood as do you know what you’re referring to! Thanks 攝影器材

 

===============

 

I got what you mean , appreciate it for posting .Woh I am pleased to find this website through google. 승무패

Avatar_small
meidir said:
Thu, 12 Jan 2023 21:38:08 +0800

I’d must verify with you here. Which isn’t something I often do! I take pleasure in reading a post that may make people think. Additionally, thanks for allowing me to comment! 바카라사이트

Avatar_small
meidir said:
Sun, 19 Feb 2023 16:27:05 +0800

Do you mind if I quote a few of your articles as long as I provide credit and sources back to your site? My website is in the very same niche as yours and my users would genuinely benefit from some of the information you present here. Please let me know if this ok with you. Cheers! 슈어맨

Avatar_small
meidir said:
Sun, 05 Mar 2023 00:34:49 +0800

Thanks for sharing excellent information. Your website is very cool. I am impressed by the info that you have on this website. It reveals how nicely you understand this subject. Bookmarked this website page, will come back for extra articles. 룸알바

Avatar_small
meidir said:
Wed, 23 Aug 2023 18:17:28 +0800

There a few interesting points soon enough on this page but I do not determine if they all center to heart. There is some validity but I will take hold opinion until I check into it further. Great post , thanks and that we want a lot more! Put into FeedBurner at the same time 插花課程

Avatar_small
jnanabhumiap.in said:
Mon, 08 Jan 2024 18:09:10 +0800

JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.


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