20241002 模拟赛
A inv
容易想到按 \(s\) 中 \(0\) 和 \(1\) 的连续段将原序列分段考虑。显然大的数放前面最好。于是按值从大到小,段从前往后分配值,\(0\) 的段降序,\(1\) 的段升序即可完成构造。求逆序对可以直接树状数组。但这题每个不同 \(01\) 段之间都有大小关系,于是每段中的每个数都与后面所有段组成逆序对,再加上倒序段中的贡献就能 \(O(n)\) 完成。
B beauty
做法:考虑枚举一个分界值 \(v\),将小于等于 \(v\) 的 \(a_i\) 设为 \(0\),其余设为 \(1\)。再枚举 \(a\) 中 \(0\) 的个数 \(cnt\)。这时一个序列的贡献就是 \(2\min(cnt, n-cnt)\)。易得这样序列的个数为 \(v^{cnt}(V-v)^{n-cnt}C_n^{cnt}\)。
考虑这样做的正确性。对于 \(a\) 中的两个对应位置的值 \(x,y(x\ge y)\),它们对答案的贡献为 \(2(x-y)\)。对于枚举到的每个 \(v\in[y,x)\),这时 \(x\) 被设置为 \(1\),\(y\) 被设置为 \(0\),这两个位置的贡献就为 \(2\)。总共造成了 \((x-1)-y+1=x-y\) 次贡献。所以每对位置的贡献都正确,从而总贡献正确。换句话说,这里就是将累加每个位置的贡献转化为累加每个分界点的贡献。
C max
注意到一个性质:每一个特征值都能用不超过 \(3\) 个数生成,原因是三维都小于 \(max\) 的三元组没有用,剩下的每个三元组至少贡献了一个 \(max\)。依次考虑选了几个三元组。
选了一个:这时方案数显然为 \(n\) 种。
选了两个:总方案数为 \(C_n^2\)。但是如果这两个三元组之间存在三维偏序关系,得到的特征值就与只选大三元组相同,减去这样的方案数。记 \(x_i=\sum_{j=1}^n [a_j<a_i\land b_j<b_i\land c_j<c_i]\)。
选了三个:总方案数为 \(C_n^3\)。仅能由三个三元组得到的特征值显然是三个 \(max\) 分别来自三个三元组。那么不合法的(与选两个重复的)就存在一个三元组贡献了至少两个 \(max\)。那么考虑贡献两个和三个的情况。
两个:不妨设两个 \(max\) 分别是 \(a,b\)(其他两种同理)。那么枚举贡献了两个 \(max\) 的这个三元组 \(i\)。那么就要求出有多少种 \(j,k\) 满足 \(a_j<a_i,b_j<b_i,a_k<a_i,b_k<b_i\)。记 \(y_i=\sum_{j=1}^n [a_j<a_i\land b_j<b_i]\)。显然对于一个 \(i\),这样的方案数就是 \(C_{y_i}^2\)(记另两种为 \(C_{z_i}^2+C_{w_i}^2\))。
三个:此时的 \(i,j,k\) 满足 \(a_j<a_i,b_j<b_i,c_j<c_i,a_k<a_i,b_k<b_i,c_k<c_i\),也就是两个三维偏序。但注意到这种情况已经被上一种包含,且被减去了三次,需要在加回去两次。
那么最后的答案就为 \(n+C_n^2+C_n^3-\sum_{i=1}^n x_i-\sum_{i=1}^n (C_{y_i}^2+C_{z_i}^2+C_{w_i}^2)+2\sum_{i=1}^n C_{x_i}^2\)。
标签:cnt,20241002,max,sum,贡献,枚举,三元组,模拟 From: https://www.cnblogs.com/luyuyang/p/18535166