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

G - Round Robin

n 个人

两两之间打比赛

已知 已经结束了m场,每场wi赢,li输

问 如果所有比赛结束后 可能成为赢得比其它人都多的可能的id有哪些?

范围

n 50

2s

1024mb

我的思路

如果一个人目前全胜,那当然可能

那如果一个人输过,那么可能是比其他所有人多吗?

显然是 n(n-1)/2 场比赛, 那么有n(n-1)/2个胜场, n(n-1)/2个负场

如果最多的t场,其它最多t-1场, t + (t-1)(n-1) >= n(n-1)/2

t >= (n-1)(n+2)/2n = (n-1)(1/2+1/n)

看起来似乎不一定要全胜

试一试

1
2
3
4
5
6

 12345
1 yyyx
2x yxy
3xx yy
4xyx y
5yxxx

这样的话 1胜3也是胜最多的

看数据量n 50, n(n-1)/2 = 1225

看起来能接受n^4

既然只讨论可能性, 那么不妨直接贪心这个人赢得最多, 得到他赢的次数t

那么变成剩下的点组成的图,能否让最大胜利次数 < t

感觉dp点或者dp边, 都不知道怎么处理互相关联的问题, 怎么做局部性

以及另外一个问题是, 如果剩下的点没有边已经确定,那么最小的胜利局数是怎么 去分配边

毫无头绪

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

G - Teleporting Takahashi

从(0,0,0)开始,可以6邻移动1个单位, 不能不动

问 N次后恰好在(x,y,z)的方案数 mod 998244353

范围

n 1e7

x,y,z [-1e7,1e7]

3s

我的思路

感觉有点生成方程 $( x+x^{-1} +y+y^{-1}+z+z^{-1})^n$

然后求$x^Xy^Yz^Z$的系数

如果x选了i 次, 那么x^{-1}选了 i-X 次

$\binom{n}{i}\binom{n-i}{i-X}$

如果y选了j 次, 那么y^{-1}选了 j-Y 次

$\binom{n-2i+X}{j} \binom{n-2i+X-j}{j-Y}$

那么z选了k次, 且z^{-1}选了k-Z次

有 2i-X+2j-Y+2k-Z = n

k = (n+X+Y+Z)/2 -i -j

$\binom{n-2i-2j+X+Y}{k} \binom{n-2i-2j+X+Y-k}{k-Z}$

所以合起来

$= \sum \binom{n}{i}\binom{n-i}{i-X}\binom{n-2i+X}{j}\binom{n-2i+X-j}{j-Y}\binom{n-2i-2j+X+Y}{k}\binom{n-2i-2j+X+Y-k}{k-Z}$

$= \sum \frac{n!}{i!(i-X)!j!(j-Y)!k!(k-Z)!}$

$= \sum \frac{n!}{i!(i-X)!j!(j-Y)!(\frac{n+X+Y+Z}{2}-i-j)!(\frac{n+X+Y-Z}{2}-i-j)!}$

$i \ge max(0,X)$

$j \ge max(0,Y)$

$\frac{n+X+Y+Z}{2} - i - j = k \ge max(0,Z)$

$i+j \le \frac{n+X+Y+Z}{2} - max(0,Z)$

直接算,得n^2会TLE

但如果给定i, 看能不能把j相关的变成一个表达式

$\sum_{j=max(0,Y)}^{\frac{n+X+Y+Z}{2}-max(0,Z)-i} \frac{1}{j!(j-Y)!(\frac{n+X+Y+Z}{2}-i-j)!(\frac{n+X+Y-Z}{2}-i-j)!} $

右侧看起来 是$\frac{1}{j!(j-Y)!}$ 与剩余部分的卷积

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 就可以了?