https://atcoder.jp/contests/abc239/tasks

F - Construct Highway

n 点, m边

问是否有方案 点i的连边数 = Di

所有点连成树

范围

n 2e5

2s

1024mb

我的思路

1. 不成环
2. 每个联通块->得到需要额外的度
3. 贪心大的到小的连?

显然并查集先搞一搞

但不会实现如何后续的合并

https://atcoder.jp/contests/abc238/tasks

F - Two Exams

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

G - Range Sort Query

给你一个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

E - Average and Median

给你一个数列

从中选一些数,保证任意相邻的两个至少一个被选

求 平均数的最大值

求 中位数的最大值, 这里偶数个的时候, 取第 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

G - Gardens

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,多次得到

去考虑之间的变化