比赛地址:https://www.nowcoder.com/acm/contest/129#question

A.序列 发现0.5和-2是一对 共同出现偶数次即可抵消影响 1是凑数的

于是暴力dp dp[i][j][k]前i个位置选了j个0.5 k个-2的方案

实际上组合数学也可以搞 就枚举一下这个偶数到底是多少然后分别钦定一下-2和0.5的位置即可

大爷代码

 

B.随机数

设f[i]表示前i个数有奇数个1的概率,则 

f[i+1]=f[i](1p)+(1f[i])p

 

f[i+1]=(12p)f[i]+p

 

然后十进制矩阵快速幂搞掉即可 每次倍增十次

就从比如10^10变成10^100

c求全局期望 曼哈顿距离其实可以针对每个维度分开维护

菜鸡elijahqi代码写复杂了

icefox大爷的代码(icefox天下第一!

d题

设dp[t][i][j]表示t时间在i,j的方案且上一次没有移动

dp1[t][i][j][k]表示ti时间在i,j的方案且上一次移动方向i是k

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论