Codeforces开坑
于是开始被虐了= =不知道能撑多久,有的题目还真是sxbk。尤其是乱搞题智商有限没办法= =
玛德英文题面看起来真尼玛蛋疼啊
计数器应该是手动计数的吧。。
UPD 10.14 一直颓废到现在才差不多半百,接下来效率++吧。
UPD 11.1 感觉做到现在状态越来越萎废,于是先来一波BZOJ找找状态好了。
UPD 11.25 玛德不管了。弃坑了弃坑了= =
464E:毛子脑洞还真是大,一开始乱搞了一个搞法并没有过,膜了一发题解原来是用主席树搞高精度。还要加什么优化感觉就很蛋痛于是先留坑好了= =
464D:一开始还设期望和概率DP,因为i比较大的时候概率基本上没有所以直接设一个范围就好了。结果T地爽爽的。后来膜了一发Tourist的卡常技巧才过。
301D:对数只有n log n个,所以询问和关系都变成点然后排个序用树状数组维护一下扫一遍就好了
463E:之前还一直在想些奇怪的做法但是并弄不出来。原来是DFS一遍顺便每个质数维护一个栈,复杂度50*n log n,因为单点时限10s所以不虚。
319D:暴力能A实在厉害。正解分段搞?不明觉厉,然而sxbk出题人题解都没有贴出来= =
342D:裸状压DP
273E:首先把SG函数值打出来发现段数不多,于是暴力预处理出每一段,然后算出值为0~2的SG值分别有多少个,就可以矩阵快速幂搞了。
257E:裸的模拟题,搞几个set就好了
305E:看错题了,结果一直卡在第二问,后来重新看题才发现好水= =
316E3:线段树维护所需答案,合并用矩阵乘法。常数卡的好紧
263E:花式前缀和乱搞
293B:一种奇怪的爆搜姿势,想了很久状压、爆搜还有其它奇怪的东西都没搞出来。后来还是膜了tourist的code= =
关键的剪枝是没出现过的颜色用组合数算
325E:奇怪的结论题,不会捉= =
241B:奇怪的乱搞题,不过最后还是搞出来了= =
260E:主席树。
338E:Splay裸题。
249E:python写这个常数真是大,连T6次爽爽爽
306B:水
339E:记得以前有人讲课讲过吧。反正乱搞就好了,反正可以作为翻转的端点的一定是什么断点,然后设个常数什么的,如果断点超过一定个数就退出,否则枚举端点然后递归。
286E:颓了很久题面勉强看懂了点,然后颓了很久都不会做。看了代码我才知道一个袋子最多只能装两个的,a set of原来是一对而不是一堆的意思。真是报警。题意懂了就是个比较明显的FFT
332D:题意艹蛋,式子很水,但是一开始低估了long double的范围,以为还要用高精度除法或者要用python写,感觉不管哪一个都很虚啊,没想到ld是存的下600位的数的,不过也应该是没保证精度的吧。
261D:想很久没想出来,后来get了个新DP姿势才A:设一个f数组,f数组中值为k的最小的下标i代表扫到目前这个位置的时候长度为k的最长上升子序列的最右边元素的最小值为i,于是把t*n个元素扫一遍,同时如果当前元素的值减一的f值等于当前元素的f值就暴力往右更新f数组。题目里面的限制保证了t在一定范围内所以枚举t并不会爆,复杂度最多也就是f数组的数值和也就是O(min(maxb^2,n*maxb))的样子。
335D:由于坐标大小被限制,所以有很多个量都被限制在一定范围内所以就可以花式前缀和乱搞了。
235C:首先对于每个xi KMP一下求出最长循环节,预处理出母串的SAM和每个节点的ri集合大小和最短长度,然后放到母串的SAM上面跑,ans加上此节点的ri集合大小,调整位置就是如果当前状态是当前节点的最短长度就调整到pre位置否则不动,然后再加上一个字符。玛德隔了个把月已经不会写SAM了TAT。
311E:最小割= =就是每个富人和狗都建个点,然后分别跟S或T连对应权值边,两者之间连INF,具体连哪边需要根据0/1判断
295D:DP
258D:没想到设a[i][j]为ti>tj的概率,全程在想些奇怪的搞法。人弱智商低没办法
286D:set、heap一起乱搞
273D:小狗好像也讲过,反正花式乱搞。真是写的人想☀狗
283E:好萎,没想出来= =比赛结果是一个n*n的矩阵,每次翻转一个子矩阵中的值,所以是扫描线+线段树维护求出每个人赢了多少场,最后答案是C(n,3)减去每个人赢得场数k的C(k,2)(因为一个非环的结果有且仅有一个人赢了两盘)
305D:乱搞
261E:满足要求的数个数有限,所以求出来之后DP出每个数的最小次数。复杂度虽然是很虚但是还是能过
253E:二分答案
243C:一开始没睡醒的时候想了很久平面图还有扫描线相关做法。看到数据范围之后就是离散化之后暴力矩阵染色+BFS了。
316G3:一开始没想到把所有串建在一个SAM上面而是准备让两个指针在两个SAM上面一起跑,但是母串的SAM每个节点还要维护可行集合,感觉虽然貌似可以卡过的样子但是写到一半100行还是弃疗了,果然还是有更优美的做法= =
256D:N^4DP,还要打表真是差评
303D:狗哔结论题= =首先n+1必须是质数,然后从大到小枚举b,b必须不是n+1的倍数,如果不存在任何n的因子k使得b^k%(n+1)==1||b^(n/k)%(n+1)==1就输出b。你问我怎么证我怎么知道
338D:范围艹蛋
266E:线段树维护每段区间六种值。
332E:乱搞,但是要注意细节,在160+的测试点wa了也真是爽快
584E:考场上一直naive地以为这个就是把环上面最长的边去掉,但其实答案就是每个点到目标点的距离和。构造方法是:枚举目标位置从1~n的点,然后让其与一直往前面扫,如果遇到一个目标位置在其后面的点就与其交换,这样的最大交换次数是n^2的。由于其前面总会有目标位置在其后面的点所以其总能够移动到目标点。
333C:恶心乱搞,很久没有搞出来。
240F:裸线段树
235D:一棵树上的情况就是分别算对于每个点i,删第i个点的时候j点对它的贡献就是1/(dis(i,j)+1),环套树就是如果有的点有两个距离就1/len1+1/len2-2/(len1+len2+R-2),len1、len2、R分别为路径1、路径2、环的点数。但是犯逗了很多次
301C:英语弱看不懂题(话说后来问了英语大神还是看不懂TAT),看代码更看不懂,毛子语文题真是厉害
301E:182这场这两题怎么这么神啊,有的人n^5时间还能在100ms内实在厉害,而且DP也好神。按数值从小到大DP,然后方案总数只跟上一个数值的个数有关,所以预处理出组合数,DP设的是算到第i个数、这一个数值有j个、一共用了k个并且有s种方案的时候的方法数。当然以上都是在一个前提下:把所有从上往下的路径除了最下面那个数其它的数全部删掉。
309B:预处理出每个单词最多能到后面哪个单词都能组成一行,然后就O(n)乱搞了。有点卡常
309D:推了个式子,但是各种被卡常,看了标程维护方程解的姿势还真是厉害,没有实数运算所以能卡过
277D:英语果弱看漏了条件,更神奇的是样例也看错了于是想了很久想不出来,后来看到条件推下式子之后就是很显然的贪心+背包。不过好像在一些奇怪的地方卡了精度
341E:完全没有头绪。。。感觉这种弃疗状态下做不了智商题= =正解是任意三个数都可以通过倍增+辗转相消变成两个
323B:奇数情况很快想出来了,就是每个点i连向i+1然后i+2到i-1交替连向i、连向i+k,但是被偶数情况卡住了TATQAQ2333,原来只要多出来那个点连向1和2就可以了。。。
325C:有印象小狗讲过,翻课件还翻到了翻译感觉真是良心,只是记得讲课的时候好像全程在颓。。不过纯码农题没听思路也没什么关系。首先求无法停止的分裂方式就是先找出所有无后继的分裂方式,对于每个怪物如果可停止的方式这个怪物也是可停止的,如此BFS求出。则得出所有无法停止的怪物,删掉这些点及相关方案。剩下点求SCC,用所有被缩的点更新其所有前驱,被标记点都是最大值无穷大的。剩下点的最大值可以拓扑排序求出最大值。所有点的最小值就是SPFA了。做这题简直像是NOIP图论四合一,不过没调多久还是很开心的。(en不对为什么CF上面的代码都写得这么短)
266D:Floyd之后枚举每条边,每个点在这条边上面的最短距离可以看作一条两段共端点的斜率为1、-1的射线,排序之后扫一遍就可以统计答案了
311C:1操作就是模k之后SPFA,另外两个操作用个set就好了。
316D3:推公式推的人萌萌哒,发现了同一置换中最多只能有两个1,通过优化时空都是n^2的,然后就不会了。。。题解里面的自行证明简直厉害。看老司机的博客这题的题解发现了“不求甚解”这句话,感觉真是很有道理。
323C:离线有个经典做法扫描线+线段树,在线直接主席树好了。第二种方法好像代码比第一种短好多。分块做法因为复杂度跟n无关所以常数要小些。
343E:en就是ZJOI那个题,最小割互不相交,于是求n次最小割然后建出树贪心就好了。有个地方的标记打错了调了好久TAT
267C:一开始被题意卡了好久,思路也是好神的高斯消元,并没有想到。。对于每个顶点设从1到它的最短距离为未知数,则可以通过每个点入流量和出流量相等列方程。最后得出来的答案再缩放一下就好了。精度还有细节都有点卡。
314E:我说怎么神题这么多,TM又看错题了TATQAQ2333。以为输入里面大小写字母都有的。首先所有小写字母都是一样的显然。然后设a[i][j]为前i个字符处理完了之后又j的多出来的左括号。常数艹蛋
240E:看了好久不会= =后来才发现是朱刘裸题,不过好像有一些很明显是错误的算法都过了而且n和m都是10w的朱刘算法O(VN)的都过的毫无压力,数据是有多弱。话说朱刘这种东西还要输出方案写起来还真是异常爽快。我真是不会写了。。。
303E:真是不明白为什么什么不科学的复杂度都有,正解n^5还真是爽快。。
285E:好狗哔神,并没想出来= =容斥+DP,直接DP不知道可不可做,但是可做也好麻烦的样子= =首先状态是前i个数造了j个GN,其它的数都无视的方案数,然后就可以求出至少有j个GN的方案数,然后容斥一下就好了。。
331C3:人弱没想到这种DP。。。贪心选最大数位减去显然。设a[i][j][k]为后面i位为999..k,前面位的最大值为i的时候把后面i位减完的总次数。
293E:一眼点分治,对于每次计算答案将所有节点按权值和排序,然后在树状数组里面维护到重心长度。这煞笔东西调了好久都是肥爷的锅。最后发现有个地方爆long long了。。。我个煞笔。。。
288E:花式数位DP,细节好多。。
241F:什么狗哔题面啊。。。
274C:这题的题解的结论都是错的,是锐角三角形和能够任意能够构成至少两个直角三角形的四边形。
319E:en线段相交但不重合之后是可以并成一条线段的,至于找相交线段明显转换成二维平面问题之后K-D Tree搞一搞就可以了。至于线段树解法好像是离散化之后线段树每个节点维护个vector,然后每次插入的时候就合并,询问就是并查集。感觉很厉害,并没有想到。
235E:DP,DP[i,j,k,p]代表a<=i&&b<=j&&c<=k且用到第1~p个质数的时候的答案。则其等于sum DP[i/p^a1,j/p^a2,k/p^a3,p-1]。
306C:组合数学,水
241E:差分约束系统,但是不知道哪里看错题了一直在wa。。
268D:DP。。开始设状态的时候完全没考虑怎么写起来方便。。
254D:先判掉rats>=327的点,然后所有ratsBFS一遍找出所有可以到达rats个数至少为总数一半的点,然后剩下的ratsBFS一遍找出可以覆盖剩下rats的点即为答案。简直跑的飞起。
269D:按高度排序之后用set维护水平区间被覆盖的情况。感觉最近写什么都跑的飞起?
264D:一开始想维护左端点右端点发现不对劲,转换成二维平面之后维护斜线上的左右端点发现也不对,还想了些奇怪的东西,然后就不会了。。原来只要判掉所有后缀分别为AB-BA的情况就好了。。感觉好厉害。。
总感觉后面的题会很愉悦啊。。。
280C:先玩个C冷静一下,虽然是看D题解的时候看这题的所以被剧透了一脸,但是感觉还是比较显然,因为对于每个点只要它和它的父亲都在的时候先选择它而不是它的祖先的概率都是1/(h[1][i]+1)。
280D:岛娘场简直SXBK。。。线段树维护费用流?。。。感觉用费用流建模证明贪心有点不明所以啊。感觉我有证明?:对于选取k块和k+1块的两种最优状态,如果两者不是能由一次翻转得到的则其中必定能选取一段被翻转的连续部分使得只翻转这一部分能增加块数为1,因为翻转一部分的状态这部分连通块数改变的绝对值最大为1。其余部分不跟这个相连而且选取了能使答案更优肯定在只有k块的时候就选取肯定能使答案更优,由此k块的状态不是最优状态,由此相邻块数的两种最优状态肯定是由一次翻转得到的。en比想象中好写。。
590E:这题我真是做的好感动。一开始并不知道怎么做,而且没有题解,于是膜拜标程发现是用AC自动机上面标记每个字符串的结束位置,然后求fail还有最近的带标记的fail祖先,于是就可以n个字符串在上面跑一遍通过带标记fail求出两两之间的关系。至于求最长反链是很水只要一个dinic,但是还要求方案就sxbk了吧。。。我看了半天真心没看懂他求方案的操作的原理。。。留坑好了。然后准备不求甚解先写了再说的时候TM总是TLE在第66个test。最后爆了10+次终于知道了Dinic跑二分稠密图爆炸了。。(但是为什么我记得这是msqrt(n)的比其它姿势都要快啊)。。总之这题终于A了。。。。。。(UPD:好像有人贴出证明来了?戳这里)
329D:en思路当然就肯定是要重复利用。。。
335F:第一眼SB贪心,看了样例感觉神神的,看完standing不敢做了。。感觉思路确实脑洞,总感觉不会证明。。。
294D:en有结论:边上所有点都走过的时候刚好完成任务。感觉怎么搞都可以?暴力建图然后直接搞?有点恶心= =
241D:狗哔结论题,只要管小于等于二十几的就能过?
249D:缩放坐标变成直角?并没有想到= =而且数学弱不会推公式= =
274E:像是294D去掉了结论?将所有点黑白染色之后发现所有点只会走同色的格子,所以说不会出现两次路径相交的情况,所以长度不用去重。然后就是把所有的边界上面的点还有黑格子上面的点排序之后维护一些东西连下边就好了?细节比294D恶心多了。。。我竟然A了。。感觉整个人真是愉快。。
317E:想到一个做法:先一直往影子靠近,然后如果到了外面就通过四个顶点调整。但是感觉好虚总感觉除了不连通之外是不是还存在什么-1情况?关键是这做法感觉一点都不优美= =然后膜拜正解发现就是这样我真是naive。。。感觉乱搞模拟题什么的真是够了。。
后面的题目怎么都这么丧病啊,老湿我可以弃疗了么TAT
325D:en感觉做的时候智商并不在线= =复制一遍原图然后判断两点能否在八连通图里面互相到达= =实在不知道把八连通格子的并查集root标记然后看两个点有没有重复标记是怎么错的。。最后发现还是自己犯逗了= =
360D:感觉要去补数学了= =首先推导一下就可以发现第i项的集合是一个等比数列,比是所有b值还有p-1的gcd,循环节的长度一定是p-1的因数,所以就可以枚举最小的循环节长度leni,则leni、2leni……p-1都在这个集合里面了。一开始求这东西我还想用BSGS。。然后很明显就是个容斥一开始我还想枚举子集求答案我真是naive,这种容斥明显是n^2。
264E:这题不会我是不是要废。。维护两棵线段树分别以高度和位置为下标,然后两种操作就是暴力乱搞。第一个测试点TLE的人不知道什么鬼。。明明就是样例数据本机上面怎么跑怎么过,爆了几发OJ发现h数组值在我还什么事情都没干的情况下就改变值了?反正在上面坑了几组数据没问题之后就弃坑了= =UPD:后来借了个号子在tsinsen上面测了可能是常数原因吧,除了T了三个点之外其他的都是过的。。管他的。。
329E:神题。。不会。。一开始猜了个结论是错的,后来弃疗看题解也都是些smg。。
346E:为什么随便挑了个又是结论题。看了还是感觉不明觉厉。。代码长度应该是唯一良心的地方吧。。
251D:犯逗了。。一开始看到10w数据范围就没往高斯消元方向想。
248E:关键在于数据范围很小。。于是可以记录每个点记录下有i个满罐子的概率。然后暴力枚举取出的满罐子个数转移。
351D:首先我们要求的问题是:询问区间内不同数个数。还有判断区间内存不存在某一个数使得所有这个数的位置是个等差数列。前者就是DQUERY,主席树搞搞。后者我们扫一遍处理出n个矩形之后扫描线+线段树搞搞。基本上一遍写对还是挺爽的。
2015年10月29日 22:47
事实上 51nod 有很多翻译的CF题, 另外祝noip取得好成绩。
2015年10月29日 23:03
@Dash: en,多谢,同NOIP加油
2015年11月20日 00:14
@HJWJBSR: dash不是贼爷?我不信
2015年12月20日 22:18
@Clare: 你真机智!!
2015年12月20日 22:32
@Heristor: Orzei!