ABC178

(1 min to read)

比较水的一场

A

!运算符

B

四种边界取个max

C

简单容斥

D

问你有多少个序列满足所有元素都$\geq 3$并且和等于s$s\leq 2000$考虑枚举这个序列的长度为n那么就要满足$x_1+\dots +x_n = s - 2n$,其中$x_i$​为正整数,每个数$\geq 3$,那么我们给每个数减掉2就转化为正整数的要求,下面就是一个经典的组合数插板问题,答案是$\binom{s-2n-1}{n-1}$

E

给定n个点的坐标,求两点间的最大曼哈顿距离很套路的题,保存(+x,+y),(+x,-y),(-x,+y),(-x,-y)四种情况的最值,枚举取max即可,容易发现虽然枚举中有不合法的情况,但一定不是最优解(因为这时候我们把绝对值取负了)

F

给定两个长度为n递增序列a和b,要求重排b,使得对于所有i,满足$a_i \neq b_i$​$n \leq 2\times 10^5$可以转化为一个网络流问题,对于每个$b_i$​,你可以放的位置就是a中所有$a_j \neq b_i$​的j,连边跑最大流即可,然而显然会爆这种特殊的网络流,考虑贪心的解法维护一个优先队列,对于每个$a_i$​,我们选择不等于$a_i$​的且可放置位置最少的那个$b_j$​,即在a中和它相等的元素最多。这样贪心即可。