[考试记录] 2024.10.7 csp-s模拟赛37

xiaolemc / 2024-10-08 / 原文

T1 莓良心

又是这毛病，场上怎么也想不到正解，然后看了题解恍然大悟。还是太菜。🐷

大概就是，贪心地，找到所有区间最小的 $L$ 和最大的 $R$，那么所有的点都可以被放置到 $L$ 和 $R$ 这两个点上。

那就好办了，将所有的 $l$ 和 $r$ 排序后讨论，分两种情况讨论：

如果 $L\le R$，那么所有的点都可以被放到这段区间里，那么答案就全为 $0$。直接 break。
如果 $R < L$，那么它们之间的点的数量为 $n-i - i$，这些点的贡献为 $(n-2i)(L-R)$，再加上这个区间自己的那一对点即可。所以贡献是 $(L-R)(n-2i+1)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 3e5 + 5;
int n, L[N], R[N], ans;
int main(){
	freopen("case.in", "r", stdin); freopen("case.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n; for(int i=1; i<=n; ++i) cin>>L[i]>>R[i];
	sort(L+1, L+1+n, [](const int x, const int y){ return x > y; });
	sort(R+1, R+1+n, [](const int x, const int y){ return x < y; });
	for(int i=1; i<=n; ++i){
		if(L[i] <= R[i]) break;
		ans += (L[i] - R[i]) * (n - (i<<1) + 1);
	} return cout<<ans, 0;
}

T2 尽梨了

很巧妙的大思维题。可我没有思维。

题目很屎，翻译过来就是让你构造两个零一串，分别满足 $a_i$ 或者 $b_j$ 等于 $c_{i,j}$。

假设第 $i$ 行为 $00110$，如果序列 $b=00101$ 那么无解，如果序列 $b=00100$ 那么 $a_i=1$，如果序列为 $b=11111$ 那么 $a=0$。综上，只要 $b$ 中有足够的 $1$，那么这些 $1$ 都必须要踩在序列的 $1$ 。设这一行的 $1$ 的数量为 $tot$, $b$ 中 $1$ 的数量为 $cnt$。那么有：

$cnt<tot$：$a_i=1$
$cnt>tot$: $a_i=0$
$cnt=tot$：$a_i=?$

考虑枚举 $b$ 中 $1$ 的数量，然后遍历每一行。如果有 $cnt=tot$，那么这些行的 $a_i$ 是不确定的，可以发现的是，如果这些行不是完全一样的话，那么无解。所以答案 $*2^{行数}$。我们记 $le$ 为小于等于 $cnt$ 的行的并，$qe$ 为大于等于 $cnt$ 的行的并。那么 $le$ 中的 $1$ 是 必须被放的，$qe$ 中的 $1$ 是 可以被放置的。考虑到 $b$ 一共有 $i$ 个 $1$，那么还剩下 $i-cnt_{le}$ 个 $1$ 可以瞎放，而瞎放的位置还剩下 $cnt_{qe}-cnt_{le}$ 个，贡献即为答案 $*\dbinom{cnt_{qe}-cnt_{le}}{i-cnt_{le}}$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 5e3 + 5, M = 998244353;
int n, fac[N], inv[N];
inline int qpow(int a, int k){
	int ans = 1; while(k){
		if(k & 1) ans = (ll)ans * a % M;
		a = (ll)a * a % M; k >>= 1;
	} return ans;
}
inline void init(){
	fac[0] = 1; for(int i=1; i<=n; ++i) fac[i] = (ll)fac[i-1] * i % M;
	inv[n] = qpow(fac[n], M-2); for(int i=n-1; i>=0; --i) inv[i] = (ll)inv[i+1] * (i+1) % M;
}
inline int C(int a, int b){
	if(a < 0 || b < 0 || a < b) return 0;
	return (ll)fac[a] * inv[b] % M * inv[a-b] % M;
}
bitset<N> mp[N], le[N], qe[N];
vector<int> tot[N];
int ans;
int main(){
	freopen("de.in", "r", stdin); freopen("de.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n; init(); 
	for(int i=1; i<=n; ++i){
		cin>>mp[i]; mp[i] <<= 1;
		tot[mp[i].count()].push_back(i);
	}
	for(int i=1; i<=n; ++i){
		le[i] = le[i-1];
		for(int j : tot[i]) le[i] |= mp[j];
	}
	for(int i=1; i<=n; ++i) qe[n+1][i] = 1;
	for(int i=n; i>=1; --i){
		qe[i] = qe[i+1];
		for(int j : tot[i]) qe[i] &= mp[j];
	}
	for(int i=0; i<=n; ++i){
		if((le[i] & qe[i]) == le[i]){
			int cnt1 = le[i].count(), cnt2 = qe[i].count();
			ans = ((ll)ans + (ll)qpow(2, tot[i].size()) * C(cnt2-cnt1, i-cnt1) % M) % M;
		}
	} return cout<<ans, 0;
}

T3 团不过

实力不行，还去拼尽全力求解容斥……

据说容斥可做，但已经不是我力所能及的范围了。而且 DP 可以高效地将大容斥划分成小情况考虑，大大减轻思维难度。

令 $g[i]$ 表示有 $i$ 堆石子时的总方案数，$f[i]$ 表示这 $i$ 堆石子异或和不为零且互不相同的方案数。那么答案即为 $g[n] - f[n]$。

考虑递推转移。$g[i]$ 即为全排列，所以 $g[i]=g[i-1]*(tot-1)$。$tot=2^n$。$f[i]$ 既要保证异或和为零，又要保证相等，所以 $f[i]=g[i-1]-f[i-1]-(tot-i+1)*(i+1)*f[i-2]$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
constexpr int N = 1e7 + 5, M = 1e9 + 7;
int n, tot, f[N], g[N];
inline int qpow(int a, int k){
	int ans = 1; while(k){
		if(k & 1) ans = (ll)ans * a % M;
		a = (ll)a * a % M; k >>= 1;
	} return ans;
}
int main(){
	freopen("yui.in", "r", stdin); freopen("yui.out", "w", stdout);
	scanf("%d", &n); tot = qpow(2, n); g[1] = tot - 1, f[1] = 0; g[0] = f[0] = 1;
	for(int i=2; i<=n; ++i){
		g[i] = ((ll)g[i-1] * (tot - i) % M + M) % M;
		f[i] = (((ll)g[i-1] - (ll)f[i-1] - (ll)(tot-i+1) * (i-1) % M * f[i-2] % M) % M + M) % M;
	} printf("%d", ((g[n] - f[n]) % M + M) % M);
}

T4 七负我

最大团即为最优答案。证明很好证，使用基本不等式即可。

#include<bits/stdc++.h>
using namespace std;
int n, x, m, mnt;
bitset<45> G[45], R[45], P[45], X[45];
inline void Bron_Kerbosch(int d){
	if(P[d].none() && X[d].none()) return void(mnt = max(mnt, (int)R[d].count()));
	int bg = P[d]._Find_first();
	for(int i=P[d]._Find_first(); i<=n; i=P[d]._Find_next(i)){
		if(G[bg][i]) continue;
		R[d+1] = R[d], P[d+1] = P[d], X[d+1] = X[d];
		R[d+1][i] = 1, P[d+1] &= G[i], X[d+1] &= G[i];
		Bron_Kerbosch(d+1);
		P[d][i] = 0, X[d][i] = 1;
	}
}
int main(){
	freopen("nanami.in", "r", stdin); freopen("nanami.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n>>m>>x;
	for(int i=1, u, v; i<=m; ++i)
		cin>>u>>v, G[u][v] = G[v][u] = 1;
	for(int i=1; i<=n; ++i) P[0][i] = 1;
	Bron_Kerbosch(0);
	double ans = (1.0 - 1.0 / mnt) / 2 * x * x;
	cout<<fixed<<setprecision(6)<<ans;
}