12
7
2018
0

http://codeforces.com/gym/100491——pjy

H

最小割

-----------------------------------------------------------------------------------------------------------------------

 

-----------------------------------------------------------------------------------------------------------------------

Category: 未分类 | Tags:
12
7
2018
0

http://codeforces.com/gym/100956

J

DP.

-----------------------------------------------------------------------------------------------------------------------

I

猜猜也是随机。。。

可以用抽屉原理+不等式(?)证明随机一对成功的概率>=1/(n+1),所以期望随机O(n)次。O(n^2/32)

Category: 未分类 | Tags:
12
2
2018
0

北大集训2018垫底记

Day1

开场看题,T1计算几何扔掉,T2&T3应该是挺正常的题可以搞搞。

写完T1的10分后开始想T2,但是怎么想都觉得Πpi^ai没法判断是否>=1,取ln也不靠谱,感觉可能有高论了。。

于是又去看T3,把题意转化了一下,就是树上染色使得相同颜色点对之间有颜色更小的,但是怎么想都觉得这东西不太好DP,觉得应该就是自己计数水平不行。

于是去写了T2的49分和T3的25分,然后对着T3发呆到考试结束。

出来后听说T2是傻逼题。。。稍微转化一下式子就做完了。。。怀疑自己有没有脑子。。。

总结:本场考试存在的唯一问题应该就是没在T2上多花点时间多想想。另外我好像发现:简单部分分越多的题正解越简单。。。争取剩下3天每天把最可做的一题(难度近似今天T2的那种)A掉吧。。

Rank:60人中41~54名都是84分。。。

Day2

开场看题,T1数据结构题,T2应该是什么找找结论乱搞?T3好像O(n^2)很简单。

于是先随手写了个T3的60,然后就扔了。

开始搞T2,打个表再说,然后发现对于一个A,合法的B是比较连续的,min到max之间除了最前面几个后面都是合法的。这样就能写49分了,6000只要跑0.1s,然后感觉并不太能直接搞100分,就溜了。

T1一眼望去感觉不太会做,还剩2个小时,暴力堆堆应该能有150,堆暴力吧。然后就走上了堆暴力的不归路,2个小时搞了35分暴力,20个叶子好像不太会做。。最后20分钟原地发呆。。

出来后听说myc,yf T1都过了n<=30000,好像是n^2+特技或者是带根号的做法。

Rank:day1+day2 60人中rank48,50人中rank39

Day3

开场看题,T1是potato,打算最后留2hour来搞,T2字符串告辞,T3决策单调之类的?

于是先搞了T3的15分和T2的50分。。然后感觉T2的80可能不会特别好搞(因为只有一个方向可以直接SA)?

T3感觉5条链应该可以直接决策单调性做,但是才10分,不如先搞T1去了。

先弄了5分然后就陷入僵局了,感觉第二个subtask很奇怪,subtask3&4应该简单的。然后冷静分析了一下,竟然只要对18/20就能拿到subtask,肯定是个乱搞,然后突然意识到可以hash。写了发交上去就有35了,最后怎么弄都只有35。

Rank:day1~day3 60人中rank44,50人中rank37。

Day4

开场看题,T1怎么题意这么长啊日,T3怎么通信题啊试机没好好试完蛋了,于是先看T2题意,读下来根本不知道题面在讲啥。。。仔细读了读还是不知道在讲啥。。。算了T3这种非传统题最后再花零碎时间搞,读T1题意去吧。。。然后看懂T1题意了,观察了一下好像24分是送的,后面还有一个23分的subtask可能需要想想。。过了一会儿skydec来讲了T2题意的一个地方,但我还是读不懂题。。又过了会儿T2题意加了点补充才懂。这时候还只有用来确认T1读对题意的7分。。。T2可能也不好做,T3先花了点时间搞懂要干啥拿了20分。。。回去稍微想了下T2就发现是个网络流模型。。但是发现好像流量是有上下界的。。完了没学过。。于是花点时间写了38分。。想乱搞发明上下界费用流但是失败了。。。然后可能已经还剩不到1个小时了,感觉T2该写的写了,T1说不定人家都A了,先去把T1堆成24吧。。然后还剩半个多小时,感觉有两种事情能干,去想想T1的那个23分subtask,或者搞搞T3,说不定T3别人又拿了很多分。。想了下感觉不是很会T1的23分的subtask,然后感觉T3好像也不太好搞。。弃疗了,剩下半个小时原地发呆,看看周围wjz和dlh走来走去,还有个小哥转来转去,在自言自语bb这个T1。。

Rank:北大集训总排名 60人中rank40,50人中rank33。成功打爆MYC

Category: 未分类 | Tags:
11
28
2018
1

https://codeforces.com/gym/100959

http://clatisus.com/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20Makoto%20rng_58%20Soejima%20Contest%204

 

E

签到题.

L

直接DP,需要用到观察.

J

prufer.

B

套用prim,用set维护.

C

BFS.

I

最短路.priority_queue用成了大根堆调了一晚上

F

[x/i]只有sqrt种,暴力.

H

根据期望的线性性每个格子独立.对于(i,j)算出第k步的概率.把每个格子的加起来一起算,暴力容斥就行了.

G

省选cbh讲过然而没听,不过挺简单的.

考虑枚举最后有多少段极长的黑块.

然后考虑每段是k条里的哪几条涂成的,容斥即可(DP算容斥系数,状态用map存).

于是转化为每段黑块的长度有个上界和下界,求铺在长度为n的链上的方案数.经典容斥.

O(挺快的).

D

DP状态很显然.f[i][j]表示第一个串前i个数第二个串前j个数形成的本质不同方案数.a[i]!=b[j]时候很容易转移.当a[i]=b[j]时候,为了不重不漏,考虑枚举往前移直到不同的那个地方的数谁在前,分别枚举是在另一个串到哪个数时候被加入的,后面那个形式的方案数可以预处理.

-----------------------------------------------------------------------------------------------------------------------

A

LJOJ4990.当时NOIP模拟赛时候其实不太会。。。

感觉这种题挺××的.

从小到大枚举质因子,如果一个数现在已经不行了,再乘上之后的质因子还是不行的(显然).不断乘新的质因子扩展即可.

O(很快).

M

感觉需要提高一下构造水平。

考虑把这东西弄得尽量均匀,所以把n个点按顺序放在圆上。

考虑这样子构造会比较均匀:每在圆上放一个三角形,就把这个三角形循环位移的所有三角形也放上,即n个n个放。

然后就转化成了相同多数量的1~n-1,要三个三个拎出来,每次拎出来的和%n=0。

不妨试试1~n-1都3个,那么总和=3n*(n-1)/2,n是奇数才有希望。举个例子n=7

1 2 3 4 5 6

1 2 3 4 5 6

1 2 3 4 5 6

注意到1+1,2+2,3+3,,,6+6 % 7 互不相同且!=0,所以直接拎{i,i,n-i-i}就OK了。

至此我们已经解决了n为奇数。

对于偶数,我们发现很难像奇数一样直接构造。

考虑构造题的一般套路,除了直接构造外,还可以把问题(递归)转化为子问题或是已经能解决的问题。

考虑化偶数为奇数,先把特殊点n拎出来。仍然考虑比较均匀地构造,比方说n向圆上所有距离为x的点对搞了个三角形,那么n与圆上所有点连了2条,圆上所有距离为x的连了一条。于是我们发现,圆上少拎一次,少拎的那3个与特殊点n去搞三角形,就做完了。

K

坐等方尤乐秒题。。。

Category: 未分类 | Tags:
11
28
2018
0

又垫底了

又垫底了

Category: 未分类 | Tags:

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