https://atcoder.jp/contests/abc238/tasks
n个人,每个人两个考试排名分别为pi,qi. 每个人的pi都不同,每个人的qi都不同
问选k个人,且如果i被选,则严格比它排名更小的必选,
方案数 mod 998244353
n 300
2s
1024mb
就是拓扑图,然后每次取一个min值, 取了k次,被取出的点集的情况数
想说 属性i = {i以及比它小的全被选}
做容斥, f(点集) = 满足 更小必选要求且 个数为k时,贡献 =1
看似 属性的交满足要求, 但是未被选的任意选择话就难以统计了
https://atcoder.jp/contests/abc237/tasks
给你一个1-N的排列
Q次操作, 每次指定区间排成指定升序/降序
问所有操作结束后,X的位置
n 2e5
q 2e5
8s
1024mb
先考虑特殊情况
X=1
那么只用持续跟踪它的位置就好了, 每次有覆盖的区间,计算新位置
而如果X=2
会发现, 每次排序与,1是否在其中有关, 维护量变成2个位置
这样下去3,就是3个位置
x就是x个位置
但其实一想, 整个排序,对X位置有影响的可以只考虑< X的个数, 或者说只考虑> x的个数
那么每次对含X的排序 = [l…r] 变成 < x的个数,X,> x的个数
啊不就是区间查询和连续区间修改
segment tree + lazy tag 就可以了?
https://atcoder.jp/contests/abc236/tasks
给你一个数列
从中选一些数,保证任意相邻的两个至少一个被选
求 平均数的最大值
求 中位数的最大值, 这里偶数个的时候, 取第 n/2 个 而不是中间两个的平均数
n 1e5
ai [1,1e9]
想dp吧, 但是如果是dp[i][0/1] 表示第i个是否选的最大平均值
那么问题是, 前面更小的平均值可能让结果更大
因为 (v0c0+a[i])/(c0+1) < (v1c1+a[i])/(c1+1), 并不意味着 v0和v1的大小关系
但如果把数量带上, 啊不就n^2空间
然后思路二, 先任意选一些合法, 然后剩下的没选的中, 从大到小,只要比当前平均值大, 则选择, 否则不选
这样最优 = 最优
问题是 如何枚举所有初步合法, 就算枚举了, 这样搞 至少还有个n倍
再就是,直接从大到小选,选到合法为止, 但是看起来样例就是反例
再就是 考虑二分答案, 答案是否小于 val, 如果小于, 则所有大于它的都必选, 因为如果不选,而答案小于val,则选了可以更大
这样对于剩下的来说, 依然和数量和和有关比如 200 100 1 100 200,
不会了
https://atcoder.jp/contests/abc235/tasks
A个种子1
B个种子2
C个种子3
N个花园
要满足条件, 任何花园都有种种子
每个花园每种的个数[0,1]
不需要把所有都种植
求方案数mod 998244353
n 5e6
3s
1024mb
R(i,j) 表示,i个花园,种完其中j个花园的方案数
T(n) 表示,n个花园,恰好种满这n个花园的方案数, T(n) = R(n,n)
ans = T(n)
S(n) = R(n,n) + R(n,n-1) + R(n,n-2) + … + R(n,0);
S(n) = R(n,n) * binom(n,n) + R(n-1,n-1) * binom(n,n-1) + .. + R(0,0) * binom(n,0)
S(n) = T(n) * binom(n,n) + T(n-1) * binom(n,n-1) + .. + T(0) * binom(n,0)
S(n) 很容易算, 相当于A,B,C互不影响, = prod (sum binom(n,0..X)), X=A,B,C, 问题是这个依赖于n需要O(n),
如果能反过来得到T(n) 就好了
T(n) = S(n) - (T(n-1) * binom(n,n-1) + … + T(0) * binom(n,0))
T(n)/n! = S(n)/n! - sum T(i)/i!/(n-i)!
考虑花园状态只有2^3-1=7 种,那么就是 七种中,总个数小于a,b,c的
生成方程?
$\sum \lbrack pwr_x\le a,pwr_y\le b,pwr_z\le c \rbrack ((1+x)(1+y)(1+z)-1)^n$
$= \sum_{i\in[0, n],i_x\le a,,i_y\le b,i_z\le c} (-1)^{n-i} \binom{n}{i} \binom{i}{i_x}\binom{i}{i_y}\binom{i}{i_z} $
$= \sum_{i\in[0, n],i_x\le a,,i_y\le b,i_z\le c} (-1)^{n-i} \binom{n}{i} \binom{i}{min(i,i_x)}\binom{i}{min(i,i_y)}\binom{i}{min(i,i_z)} $
并没法算
再就是, 假设 a<=b<=c
ans(a,b,c) 通过 ans(b,b,b) 让每次头-1,或者尾+1,多次得到
去考虑之间的变化
https://atcoder.jp/contests/abc234/tasks
长n数组A
2^{n-1}种方式切割成非空顺序数字
f(切割) = $\prod$每个子数组的 (max-min)
求 $\sum$ f(所有切割)
mod 998244353
2s 1024mb
dp搞一搞
考虑最后一个数组长度
dp[i] = dp[i-len] * ((max-min)([i-len+1..i]))
但这样就O(n) 状态, n^2转移了
然后,算的时候,max和min可以拆开, 但是如果 两两不等的话, 即使用了 区间sum dp * max, 也可能max需要一个一个枚举,也是n^2
问题变成说
dp[i] = sum max(a[i-len+1..i]) * dp[i-len] - min(a[i-len+1..i]) * dp[i-len]
考虑相邻转移
i-1: sum max(a[j+1..i-1]) * dp[j]
a[i]是[j+1..i]的最大值, 那么找最小的j, 这之家你的贡献 = a[i] * sum dp[j..i-1]a[i]不是[j+1..i]的最大值, 那么这贡献 = sum max(a[j+1..i])*dp[j] = sum max(a[j+1..i-1])*dp[j]因此相邻的dp虽然没有直接关系, 但是可以利用上次的计算
dp[i] = a[i] * sum(dp[j..i-1]) + sum f(0..j)
min同理
似乎就没了