https://atcoder.jp/contests/abc231/tasks
n个盒子, 初始第i个盒子有ai个球
k次操作
每次 等概率选一个盒子, 增加1个球
分数 = 最终每个盒子的球的个数之乘积
求分数期望 mod 998244353
n 1000
k 1e9
ai [0, 1e9]
2s
1024 mb
感觉上可以 做n和n-1的关系, 然后直接算频次, 最后除总次数 转成概率
F(n,k) = 前n个所有方案的乘积和, Ans = F(n,k) / n^k
对于最后一个盒子, 选择了j次, 对应的方案乘积和为 C(k,j) * F(n-1,k-j) * (a[n]+j)
F(n,k) = sum (a[n]+j) * F(n-1,k-j) * C(k,j), j=0..k
这里n虽然小, 但是k很大, 上面这个显然TLE, 如果能搞到n^2 左右的就好了
C(k,j) 的部分拆出来 分配给F的分母可以简化,但是依然没有去掉k的维度
https://atcoder.jp/contests/abc230/tasks
给一个1~N的排列p
问有多少个有序对 (i,j), (i<=j), 满足 gcd(i,j) != 1, gcd(p[i],p[j]) != 1
n 2e5
5s
1024mb
有点想暴力 然后证明复杂度?
对于 (i,Pi), 取两个中较小的一个, 找所有包含它下标的, 用较大的去验证gcd
最多有6个不同质数因子, 最坏情况 1/2+1/3+1/5+1/7+1/11+1/13 = 1.3左右
所以最坏情况是 找n个坐标
先写个代码再说
https://atcoder.jp/contests/abc230/submissions/34500571
显然 有很多是2 的倍数的,它们如果每个都会去访问n/2, 那么已经就是n^2了, 肯定会超时
想法就是 如果 (2的倍数,3的倍数) 之类做容斥? 但是我容斥完全不会
https://atcoder.jp/contests/abc229/tasks
一个包含字符’Y’和’.’的长n字符串S,
可以操作[0,k] 次,交换S中的两个相邻字符
问可以得到的最终S的内部最长的连续Y的长度
n 2e5
k 1e12
2s
1024mb
考虑移动
最终假设是[l..r]
那么对于初始这些y的位置的大范围是[l0..r0]
那么一定可以分成两部分
[l0..m0][m0+1..r0]
一部分向右,一部分向左
显然有个点不需要动
如果选定了第i个点p[i]和期望个数c那么,移动代价为min( 左侧k0, 右侧k1个), k0+k1+1=c
= min(sum(p[i]-k0..p[i]-1) - sum(p[i-k0]..p[i-1]) + sum(p[i+1]..p[i+k1]) - sum(p[i]+1..p[i]+k1))
换个角度
所有值变成p[i]-cnt1[i]
那么就是找一个值, 尽量多的数变成它, 且代价和 <= K
显然每多一个,代价的增量是非严格递增的
是个凸函数(下凹)
但感觉, 这样看起来, 其实左侧右侧影响不大,而是距离影响更大,
所以直接枚举中点,二分距离(选定的点的最大距离) => 去计算距离和范围,以及点数范围
这里 < 距离的必选, >距离必定不选, =距离可选可不选
似乎就没了?
https://atcoder.jp/contests/abc228/tasks
w乘h的矩阵初始全白色,每个有数字aij
T 可以染黑 h1 w1
A 可以染白 h2 w2
T 操作一次, S操作一次
分数= 黑色块之和
T 让尽可能大, A让T尽可能小, 求答案
h,w 1000
aij [1,1e9]
2s 1024mb
感觉就是二维常见运算
因为长度如果超了长度, 可以贪心把对应位置全覆盖,可以取min, h2=min(h2,h1), w2=min(w2,w1)
ans = max(f(i,j))
f(i,j) = sum(i,j) - max(g((range))
应该就过了吧
这场UI还有红色特效
https://atcoder.jp/contests/abc227/tasks
长n数组a
每次选k个不同的下标, 让值减1,(保证所有值非负), 求多减的次数
n 2e5
ai [1..1e12]
2s
1024mb
感觉如果数据量小,每次最大k个下标减1
但这样每次要排序, 而且ai很大