昨晚CF，你知道的。

复仇者_帅童

2025-09-25 06:37:30

发布于：广东

19阅读

0回复

0点赞

https://codeforces.com/bestRatingChanges/18546898

A

我们将 $B$ 分为 $n$ 组，每组分别为 $[1],[1,2],[1,2,3],[1,2,3,4],...,[1,2,3,...,n]$ 。

显然，有以下两种情况：

$A$ 在某些组内。显然，这种情况的 $A$ 为 $[...,A_{m-1},A_{m}]$ ，即满足 $A_i=A_{i-1}+1$ ，在 $B$ 中出现了 $n-A_m+1$ 次。
$A$ 在某两个组之间。显然，这种情况 $A$ 不满足上面的性质，并且在 $B$ 中只出现了 $1$ 次。

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
void solve(){
	int n, m;
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> a[i];
	for(int i = 2; i <= m; i++){
		if(a[i] != a[i - 1] + 1){
			cout << "1\n";
			return;
		}
	}
	cout << n - a[m] + 1 << '\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度： $O(tm)$ 。

B

怎么 B 题就这么逆天。

注意到当第 $i$ 个人进行完操作后后面的人都会重复执行这些操作。由于是结束后再染色，所以考虑最后一个操作的不同对后面的人的影响。

操作 $\tt{A}$ ：没有影响，该往后 $1$ 格就往后 $1$ 格。
操作 $\tt{B}$ ：染黑了后会前进 $1$ 格，然后再到后面的白色格子。

所以可以递推解决。

#include <iostream>
#include <cstdio>
#include <set>
#define int long long
using namespace std;
int a[100005];
void solve(){
	int n, m;
	string s;
	cin >> n >> m >> s;
	s = ' ' + s;
	for(int i = 1; i <= m; i++) cin >> a[i];
	set <int> ans;
	for(int i = 1; i <= m; i++) ans.insert(a[i]); 
	bool flag = 0;
	int cur = 1;
	for(int i = 1; i <= n; i++){
		if(s[i] == 'A'){
			cur++;
			ans.insert(cur);
		}else{
			cur++;
			while(ans.count(cur)) cur++;
			ans.insert(cur);
			cur++;
			while(ans.count(cur)) cur++;
		}
	}
	cout << ans.size() << '\n';
	for(int i:ans) cout << i << ' ';
	cout << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度： $O(\sum n+m\log (n+m))$ 。

C

我不知道啊，随便蒙了个结论。

呃就是先进 $k$ 个人然后出 $1$ 进 $1$ 出 $1$ 进 $1$ 最后全出就行了，我不会证，但也想不到更好的办法了。

呃呃呃。

呃呃呃呃呃呃呃。

然后乱搞。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
int a[400005]; 
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n * 2; i++) cin >> a[i];
	int ans = 0;
	for(int i = 1; i <= n; i++) ans -= a[i];
	for(int i = n + 1; i <= n * 2; i++) ans += a[i];
	int cur = 0;
	vector <int> v;
	for(int i = n; i; i--){
		ans += cur;
		cur = -cur;
		cur += a[i] * 2;
		cur -= a[n * 2 - i + 1] * 2;
		v.push_back(ans);
	}
	reverse(v.begin(), v.end());
	for(int i:v) cout << i << ' ';
	cout << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度： $O(\sum n)$ 。

D

这个我是真会。

自己模拟一下，可以发现第 $i$ 列只能有一个黑格，并且必须在前 $\min\{i,n-i+1\}$ 行之内。

然后范围就是一个到三角形。

注意到后面的格子在前面的格子中也有，所以我们可以倒着计算。

对于第 $i$ 行，一共有 $n-2\times (i-1)-\sum_{i+1}^n A_i\choose A_i$ 中情况。

乘起来就行了。

注意特判不合法的情况。

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
int a[200005];
int f[200005];
int invf[200005];
const int mod = 998244353;
int inv(int n){
	int ans = 1, t = mod - 2;
	while(t){
		if(t & 1) ans = ans * n % mod;
		n = n * n % mod, t >>= 1;
	}
	return ans;
}
int C(int n, int m){
	if(m == 0 || m == n) return 1;
	return f[n] * invf[n - m] % mod * invf[m] % mod;
}
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int ans = 1;
	for(int i = n / 2 + (n % 2) + 1; i <= n; i++){
		if(a[i]){
			cout << "0\n";
			return;
		}
	}
	int cur = 0;
	for(int i = n / 2 + (n % 2); i; i--){
		if(a[i] + cur > n - (i - 1) * 2){
			cout << "0\n";
			return;
		}
		ans *= C(n - (i - 1) * 2 - cur, a[i]);
		ans %= mod;
		cur += a[i];
	}
	if(cur != n) cout << "0\n";
	else cout << ans << '\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	f[1] = 1;
	for(int i = 2; i <= 200000; i++){
		f[i] = f[i - 1] * i % mod;
	}
	invf[200000] = inv(f[200000]);
	for(int i = 199999; i; i--){
		invf[i] = invf[i + 1] * (i + 1) % mod;
	}
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}