首页 > 代码库 > [训练日志] 7月14日
[训练日志] 7月14日
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; text-align: justify; font: 12.0px Helvetica; color: #454545 }
p.p2 { margin: 0.0px 0.0px 0.0px 0.0px; text-align: justify; font: 12.0px "PingFang SC"; color: #454545 }
p.p3 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; color: #454545 }
p.p4 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "PingFang SC"; color: #454545 }
span.s1 { font: 12.0px Helvetica }
span.s2 { font: 12.0px "PingFang SC" }</style>
56D
[给串A串B,求串A变换到串B的最小代价]
[二维DP,分四种情况,其中三种对应操作,另一种为直接接上]
[Warning: 提交时删除调试语句。对偶语句注意I和J]
729F
[给a1-an。两个玩家分别从左右取数。如果上一个玩家取了k个,下一个玩家只能取k或k+1个。博弈]
[博弈,f[L][R][K]记录当前取得区间为L-R,目前是取K个。分左右分别DP。然而是n^3的。进一步优化,k(k+1)/2<=n,左右取的差也是<K的。所以可以将状态表示为f[L][D][K],其中D是左右取数之差。这样D和K都是O(根号2n)级别的。整体复杂度O(n^2)]
[如何简化状态,可以考虑维与维之间的关系,以及每个维度实际的范围。另外本题空间有限,也是在提示状态可以简化(不简化不会T但会MLE)]
39E
[a^b.每轮可以a++或b++,若>=n则输。求局面情况]
[博弈。注意考虑a==1,会平局。B==1,会MLE。]
482C 好题
[有n个串,A随机选一个。B每次猜一位,问期望多少位能猜出来]
[首先要预处理出猜了mask位之后哪些串还猜不出来。如果nm2^m会T,但观察到两个串如果猜不出来,一定是只猜了相同的那些位。所以可以n^2m枚举两两,然后m2^m处理mask的情况下哪些猜不出来]
[接下来有两种处理方法。一种是自顶向下,处理出每个状态的概率。加个该状态有sum个串没猜出来,则ans+=f[x]*sum。因为没猜出来就要再猜一次,该状态对结果得贡献为1]
[另一种是自下而上。F[i][x]= Σf[i][y]/tot+1。若令s[x]= ΣF[i][x]。则s[x]= Σs[y]/tot+sum[x]。]
[预处理不能想当然,要多考虑如何优化。]
[训练日志] 7月14日
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。