概率与期望 - hzwer.com

2016 Multi – University Training Contest 5
本场抱住卓神大腿最后过了7题。。。感觉把PKU的牌子砸了。。。我做了100110051011随便口胡几句。。。1010看起来像后缀数组。。。但是交wa了几发不知道什么情况1001ATMMechine这题似乎0元钱也要取1次1元的来确认一下，不然没法解释样例\(f(i,j)\)表示有i元以内的钱，j次warning的机会然后枚举询问点k，有t种可能warning，那么转移给\(f(t-1,j-1)\)有i-k+1种可能取钱，转移给\(f(i-t,t)\)边界j为1的情况，有k元钱需要询问k+1次...
12016年8月3日5,426回文自动机,递推与动规,概率与期望

「CF698X」Codeforces Round #363 (Div. 1)
A.Vacations题意：给出每天contest和gym的开关状态，不能连续俩天参加相同活动，问n天最少休息多少天用F(i,0-2)表示前i天，第i天的状态为（rest，contest，sport），最多能有多少天不休息简单dp一下[crayon-67679b7882f5f573096073/]B.FixaTree给出n个结点的父亲，问至少修改多少个能够使得其变成一棵树先用拓扑排序消去外向树，剩下的每个环要选出一个当根，然后再把所有的环连成树答案是环数-（是否存在自环）[crayon-6767...
02016年7月20日4,800递推与动规,状压动规,拓扑排序,概率与期望
「CF335X」MemSQL start[c] up Round 2 – online version
A.Banana枚举sheet数，找到第一个不能用已有sticker凑出的[crayon-67679b7883467406177781/]B.Palindromef(i,j)表示末尾在i之前，长度为j的回文序列的最大头位置[crayon-67679b7883470679781653/]C.MoreReclamation用(len,x,y)表示一个游戏状态，2*len的完整格子，左端的状态为x，右端的状态为yx，y=0/1/2分别表示（完整），（左侧/右侧第一行第一格不可删），（左侧/右侧第二行第一格不可删）边界情况：len=0时sg值为0len=...
12015年6月23日4,099递推与动规,模拟,STL,贪心,博弈论,记忆化搜索,概率与期望
「CF235X」Codeforces Round #146 (Div. 1)
A.LCMChallenge显然是在接近n数内找三个两两互质的，由于懒得推公式所以可以小范围暴力一下[crayon-67679b7883d4e614190420/]B.Let'sPlayOsu!计算出到每个位置的期望连续长度就可以得到如果该位置正确的期望得分，就可以dp辣[crayon-67679b7883d57814475394/]C.CyclicalQuest一道很正经的后缀自动机建出s串的后缀自动机把xi复制一遍接在后面，然后在s串上匹配，就可以得出后缀自动机上贡献答案的结点[crayon-67679b788...
02015年6月15日7,558深度搜索,广度搜索,后缀自动机,概率与期望,莫比乌斯反演
「CF293X」Croc Champ 2013 – Round 2
A.WeirdGame两个人都应该采取贪心策略根据规则，先取0而对方不取0则败，所以有1则取1，当然尽量取对方也是1的那些取0的时候同理，尽量取对方是1的那些我们模拟游戏进程得出两个人的最终序列比较即可[crayon-67679b78842fa962455391/]B.DistinctPaths容易发现，n+m-1>K时是无解的，那么有解的棋盘就很小了，状压使用的颜色+dfs然而这样的状态还是太多，我们发现dfs到一个格子的时候，所有未在棋盘上出现的颜色并无差别，所...
22015年6月11日5,301贪心,深度搜索,点分治,数学,状压动规,概率与期望
POJ训练记录3
1379.RunAway模拟退火裸题[crayon-67679b7884bf1545480214/]2758.CheckingtheText暴力+哈希[crayon-67679b7884bfb784392049/]poj3156.Interconnect由于状态是满足拓扑序的，所以直接dp上，再用个hash记忆化[crayon-67679b7884c01936806367/]1837.Balancef(i,j)前i个力矩为j的方案,dp[crayon-67679b7884c08572301269/]3609.ResetSequence状压+bfs初始集合是0-n-1每个指令会使得集合中的一些元素消失，目标状态是只有一个0[c...
02015年5月19日4,652递推与动规,状压动规,广度搜索,哈希表,几何,记忆化搜索,概率与期望
「CF540X」Codeforces Round #301 (Div. 2)
A.CombinationLock模拟[crayon-67679b788525e610578917/]B.SchoolMarks塞一堆中位数，特判什么的[crayon-67679b7885267448109837/]C.IceCave深搜连通性，出点入度特判[crayon-67679b788526c513801594/]D.BadLuckIsland期望dp+记忆化[crayon-67679b7885272935555101/]E.InfiniteInversions离散树状数组乱搞[crayon-67679b7885277951093678/] ...
02015年5月13日3,378模拟,深度搜索,树状数组,记忆化搜索,概率与期望
「BZOJ4008」[HNOI2015] 亚瑟王
Description小K不慎被LL邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂亮。众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。作为一个非洲人，同时作为一个前OIer，小K自然是希望最大化造成伤害的期望值。但他已经多年没写过代码，连Spaly都敲不对了，因此，希望你能帮帮小K，让他感受一下当欧洲人是怎样的体验。本题中我...
12015年4月22日7,490递推与动规,概率与期望
「BZOJ3036」绿豆蛙的归宿
Description随着新版百度空间的下线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为1/K。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？Input第一行:两个整数NM，代表图中有N个点、M条边第...
22015年2月27日5,388递推与动规,概率与期望
「BZOJ3270」博物馆
Description　　有一天Petya和他的朋友Vasya在进行他们众多旅行中的一次旅行，他们决定去参观一座城堡博物馆。这座博物馆有着特别的样式。它包含由m条走廊连接的n间房间，并且满足可以从任何一间房间到任何一间别的房间。两个人在博物馆里逛了一会儿后两人决定分头行动，去看各自感兴趣的艺术品。他们约定在下午六点到一间房间会合。然而他们忘记了一件重要的事：他们并没有选好在哪儿碰面。等时间到六点，他们开始在博物馆里到...
42015年2月6日6,647高斯消元,概率与期望
「CF398B」Painting The Wall
Useraintadecidedtopaintawall.Thewallconsistsofn2tiles,thatarearrangedinann × ntable.Sometilesarepainted,andtheothersarenot.Ashewantstopaintitbeautifully,hewillfollowtherulesbelow.Firstlyuseraintalooksatthewall.Ifthereisatleastonepaintedcelloneachrowandatleastonepaintedcelloneachcolumn,hestopscoloring.Otherwise,hegoestostep2.Useraintachooseanytileonthewallwithuniformprobability.Ifthetil...
02015年2月1日4,070递推与动规,概率与期望
「CF498B」Name That Tune
ItturnsoutthatyouareagreatfanofrockbandAC/PE.Peterlearnedthatandstartedthefollowinggame:heplaysthefirstsongofthelistofnsongsofthegroup,andyouhavetofindoutthenameofthesong.Afteryoutellthesongname,Peterimmediatelyplaysthefollowingsonginorder,andsoon.Thei-thsongofAC/PEhasitsrecognizabilitypi.Thismeansthatifthesonghasnotyetbeenrecognizedbyyou,youlistentoitforexactlyonemoresecondandwithpr...
12014年12月25日3,621递推与动规,概率与期望