专栏文章

NOIP_2025_T2

ddruzewang
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimx4clv
此快照首次捕获于
2025/12/01 16:59
3 个月前
此快照最后确认于
2025/12/01 16:59
3 个月前
查看原文

闲话

赛时 1h1h 思考 m=2m = 2 的部分分，结果发现好像可以拓展到所有的 mm，然后就花了 1h1h 写了个假的写法，发现之后，又用了 2h2h，去写正解，极限写完。
感谢zcq巨佬祝我破鼎。（虽然没帮助我什么）

写法

jzpjzp 曾经说过，一个好的题目，一定能从部分分来启发正解，对于这道题，我们首先把目光放在数据点7,8,9,14,15,发现一个共同点，居然是 m=2m = 2 !!!
对于只有两块钱的情况：
  1. 购买两个花费为 w=1w = 1 （或者一个，有可能不够）。
  2. 购买一个花费为 w=2w = 2。
不妨设两个 w=1w = 1 的是 x,y(x<y)x,y(x < y) 一个 w=2w = 2 的是 zz。
那么如果现在购买 x,yx,y，不合法的情况也就是 x+y<zx + y < z，但是我们有要先买 yy，所以有 y>x>z2y > x > \frac{z}{2} oror y>z2>xy > \frac{z}{2} > x
  1. y>x>z2y > x > \frac{z}{2} 又有 x+y<zx + y < z 所以 x2+y2<z2<x<y\frac{x}{2} + \frac{y}{2} < \frac{z}{2} < x < y 显然不合法，所以舍掉，因为 y2>x2\frac{y}{2} > \frac{x}{2}。
  2. y>z2>xy > \frac{z}{2} > x 又有 x+y<zx + y < z 所以 x2+y2<z2<y\frac{x}{2} + \frac{y}{2} < \frac{z}{2} < y，肯定可以，因为 x2<y2\frac{x}{2} < \frac{y}{2}。
现在购买 zz，那么就是 z<x+yz < x + y 并且 z2>x,y\frac{z}{2} > x,y，但是并不满足 x2+y2>z2>x,y\frac{x}{2} + \frac{y}{2} > \frac{z}{2} > x,y，所以舍掉。
综上，只有 m=2m = 2 并且 y>z2>xy > \frac{z}{2} > x 才是不行的方案
OHHHHHHHHH，我们居然退出来了 m=2m = 2 的办法，那我们试着推广一下？
那也就是 zz 会被在性价比比 z2\frac{z}{2} 要大的那些正好卡到 m−1m - 1 才是不行的方案数，所以枚举以下就可以了！ O(n3)O(n^3) 成功拿到 52pts52 pts，我可真厉害。

正解（过了民间数据）

发现直接计算和发方案不太行，直接考虑容斥，我们只需要统计上述不合法方案数，使用 2n−2^n - 不合法方案数 就可以了。
为了更好理解些，直接浪费 O(n)O(n) 的复杂度来枚举被卡掉的点 ii，这样才好统计填补的点 jj。
将所有 aia_i 从大到小排序，这时候我们会发现可以把其他的点都归类到三种集合中。
  • 集合 A(j<i)A (j < i)：aj>aia_j > a_i：
    • 无论 wjw_j 是 1 还是 2，性价比都排在 ii 的前面。这些糖果一定在 ii 之前被考虑。
  • 集合 B(j<iB(j < i 并且 2×aj>ai)2 \times a_j > a_i)：
    • 若 wj=1w_j = 1，那么性价比比 ii 要高，排在 ii 的前面
    • 若 wj=1w_j = 1，那么性价比比 ii 要低，排在 ii 的后面
  • 集合 C(j<i)C(j < i) 并且 aj<aia_j < a_i：
    • 不管 wjw_j 是 1 还是 2，性价比都比 ii 第，永远排在 ii 的后面。
对于固定的 ii (wi=2)(w_i = 2)，要使其成为因为没钱被调过的糖果，就用到了我们上面的理论——性价比比 ii 高的正好花费了 m−1m - 1 元钱，包括 AA 中的所有糖果，花费 wjw_j，以及 BB 中 wj=1w_j = 1 的糖果。
设 CA=∣A∣,CB=∣B∣C_A = |A|,C_B = |B|，设 KAK_A 是 AA 中所有 wj=2w_j = 2 的个数， KBK_B 是 BB 中所有 wj=1w_j = 1 的个数。
总花费 = (CA−KA)×1+KA×2+KB×1=CA+KA+KB(C_A - K_A) \times 1 + K_A \times 2 + K_B \times 1 = C_A + K_A + K_B。
NA+CA+KB=m−1⇒KA+KB=m−1−CAN_A + C_A + K_B = m - 1 \Rightarrow K_A + K_B = m - 1 - C_A。
方案数变成了从 CA+CBC_A + C_B 个位置中选出 m−1−CAm - 1 - C_A 个位置的方案数：
(CA+CBm−1−NA)\begin{pmatrix} C_A + C_B \\ m - 1 - N_A \\ \end{pmatrix}
在 ii 被跳过之后，只剩下一块钱，BB 中剩余的糖果一定是 wj=2w_j = 2，（不然前面就已经选走了），买不起，跳过。
CC 中的糖果按照顺序考虑
  • 如果 w=2w = 2，那么买不起，跳过
  • 遇到的第一个 w=1w = 1 糖果就是 jj
  • 如果遍历完也没看到 w=1w = 1 的，那么就没有 jj
那我们找到了固定的 i,ji,j，方案是不合法的仅当：已经存在购买过的一元糖果 kk，使得 ak<ai−aja_k < a_i - a_j。
其中 kk 可以来自 A(w=1)A (w = 1) 或者 B(w=1)B (w = 1)。
对于所有满足 ak<ai−aja_k < a_i - a_j 的时候选择 kk，那么 wkw_k 必须选择 2（如果在 AA）或者不能选择 1（如果在 BB 中，也就是必须是2）。
那我们可以记录一个阈值 D=ai−ajD = a_i - a_j ，设 S=A∪BS = A \cup B 中满足 ak<Da_k < D 的元素集合。
要避免交换，必须强制 SS 中的所有元素 w=2w = 2，这回固定 SS 中元素对 KA,KBK_A,K_B 的贡献：
  • A∩BA \cap B 中的元素必须是 2⇒KA2 \Rightarrow K_A 增加 ∣A∩S∣|A \cap S|。
  • B∩SB \cap S 中的元素必须是 2⇒KB2 \Rightarrow K_B 其实就是不增加，因为 KBK_B 统计的是 w=1w = 1。
剩余任意可选的：(CA+CB)−∣S∣(C_A + C_B) - |S|。
需要统计的方案数：(m−1−CA)−∣A∩S∣(m - 1 - C_A) - |A \cap S|。
方案数：
(CA+CB−∣S∣m−1−CA−∣A∩S∣)\begin{pmatrix} C_A + C_B - |S| \\ m - 1 - C_A - |A \cap S| \end{pmatrix}
于是当前 (u,v)(u,v) 的贡献：
((CA+CBm−1−CA)−(CA+CB−∣S∣m−1−CA−∣A∩S∣))×2r( \begin{pmatrix} C_A + C_B \\ m - 1 - C_A \\ \end{pmatrix} - \begin{pmatrix} C_A + C_B - |S| \\ m - 1 - C_A - |A \cap S| \end{pmatrix} ) \times 2^r
其中 rr 表示 jj 之后的 CC 中可以任意取的值。
复杂度 O(T×n2)O(T \times n^2)
OHHHHHHHHHHHHHHHH！！！
切出来了！！！
（虽然用了 4h4h）

Code

CPP
#include<bits/stdc++.h>
using namespace std;

/*
剩余2元时
只有可能1把更有的2给卡住
也就是当前1的最大值的性价比比2的最大值的性价比要大
1:x,y
2:z
y > z/2 && x + y < z
如果满足上述条件，那就是完damn了

剩余大于2元时
总是可以转换成2元的效果

考虑枚举z

O(n^2)可过吗？？？ sigma_n <= 5*10^4 应该差不多吧，？。万一数据卡掉那不就直接炸了。。。。。。
OOOOO 说了n <= 5000 ，所以应该差不多大概好像可以。

那么总合法方案数量就是总方案数(2^n) - 总不合法方案数
求一下上面那个条件就可以了，枚举？

欸？在上述中x可能不存在

现在枚举被卡掉的2
首先降序排序
当前第i个为ai
设A集合为所有的j且aj >= ai
设B集合为所有的j且j > i && 2aj >= ai(也就是选2排在i后，选1排在i前)
设C集合为所有的j且j > i && 2aj <= ai(也就是不论怎样都要在i的后面) 
设Na = |A|,Nb = |B|,kA中取w=2的个数，kB为B中取w=1的个数。
总花费：(Na - kA) * 1 + kA * 2 + kB * 1 = Na + kA + kB
Na + kA + kB = m - 1 => kA + kB = m - 1 - Na
方案数为从 Na + Nb 个位置中选m - 1 - Na个位置贡献额外全值的方案数：
	C_{m - 1 - Na}^{kA + kB} 
在u被跳过后，剩下的钱只有1
B中剩余的糖果必然是w=2，否则会在u的前面买，那就没钱了
C中的糖果按照顺序考虑
	如果也是w=2，买不起，跳过
	遇到的第一个w=1的糖果也就是v
	如果遍历完c也没有w=1的糖果，也就是v不存在
对于固定的uv，方案是坏的仅当：存在已经购买的一元糖果z，az < au + av
其中z可以来自AorB

所以对于当前uv的贡献，也就是 ([ka + kb,m - 1 - Na] - [(Na + Nb - |S|),(m - 1 - Na) - |A U S|]) * 2^c 
*/
#define int long long//十年oi一场空，不开__见__
#define O(i,e,r) for (register int i = (e);i <= (r);++i)
#define U(i,e,r) for (register int i = (e);i >= (r);--i)
#define I(e,r) for (auto e : (r))
#define gc getchar
#define mul(a,b) a = (a * b) % mod
#define add(a,b) a = (a + b) % mod
#define sub(a,b) a = (a - b + mod) % mod
#define fi first
#define se second

const int mod = 998244353;
const int N = 200000; 
int Case,T_T,n,m,tot;
int a[N + 5],fact[N + 5],inv[N + 5],finv[N + 5],qp2[N + 5];

inline void read(int &x){
	x = 0;
	int f = 1;
	char c = gc();
	while (c < '0' || c > '9'){
		if (c == '-') f = -1;
		c = gc();
	}
	while (c >= '0' && c <= '9'){
		x = (x << 1) + (x << 3) + (c - 48);
		c = gc();
	}
	x *= f;
}

inline bool cmp(int x,int y){return x > y;}

inline int qpow(int x,int y){
	int base = x,ans = 1;
	while (y){
		if (y & 1) mul(ans,base);
		mul(base,base);
		y >>= 1;
	}
	return ans;
}

inline int Cc(int x,int y){
	if (y < 0 || y > x) return 0;
	return fact[x] * finv[y] % mod * finv[x - y] % mod;
}

inline void init(){
	fact[0] = finv[0] = qp2[0] = 1;
	O(i,1,N){
		fact[i] = fact[i - 1] * i % mod;
		finv[i] = qpow(fact[i],mod - 2);//超慢逆元
		qp2[i] = qp2[i - 1] * 2 % mod;
	}
/*
ai + b = 0
a * invi * i * invb + invi * invb * b = 0
a * invb + invi = 0
invi = -b * inva
*/
}

signed main(){
	//zcq_qwq AK IOI !!!!!!  zcq巨佬保我这道题AC！！！！！
//	freopen("sale.in","r",stdin);
//	freopen("sale.out","w",stdout);
	read(Case), read(T_T);
	init();
	while (T_T--){
		
	read(n), read(m), tot = 0;
	O(i,1,n) read(a[i]);
	sort(a + 1,a + n + 1,cmp);
	O(i,1,n){
		int idx = i + 1;
		while (idx <= n && 2 * a[idx] > a[i]) ++idx;//寻找B集合的
		int A = i - 1,B = idx - 1 - i,C = n - idx + 1;//A，B，C集合的
		int tmp = Cc(A + B,m - 1 - A);
//		cout << A << ' ' << B << ' ' << C << ' ' << idx << ' ' << tmp << '\n';
		if (tmp == 0) continue;
		vector <pair<int,int> >vec;
		int x1 = 1,x2 = i + 1;
		while (x1 < i && x2 < idx){//双指针 
			if (a[x1] >= a[x2]){
				vec.push_back({a[x1],0});
				++x1;
			}else{
				vec.push_back({a[x2],1});
				++x2;
			}
		}//0表示A集合的，1表示B集合的 
		while (x1 < i){
			vec.push_back({a[x1],0});
			++x1; 
		}
		while (x2 < idx){
			vec.push_back({a[x2],1});
			++x2;
		}
		int k = vec.size() - 1,kA = 0,kB = 0;
		O(j,0,C){
			int val = 0;
			if (j < C) val = a[idx + j];
			int D = a[i] - val;
//			cout << a[i] << ' ';
//			cout << val << ' ' << D << ' ' << k << '\n';
			while (k >= 0 && vec[k].fi < D){
				if (vec[k].se == 0) ++kA;
				else ++kB;
				--k; 
			} //统计vec里面的A，B元素
			int b = (tmp - Cc(A + B - kA - kB,m - 1 - A - kA) + mod) % mod;
			if (b > 0){
				if (j < C) tot = (tot + b * qp2[C - 1 - j]) % mod;
				else tot = (tot + b) % mod; 
			} 
		}
//		cout << tot << '\n';
	}
	cout << (qp2[n] - tot + mod) % mod << '\n';
	
	}
}

总结

是个题目，并且大于等于红，小于等于黑。
Q_Q 真的不是我用 pq2pq2 卡常数，不然会真的 TLE。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...