MMOI R1 T1-3 题解

cjdst

2026-06-14 22:42:55

发布于：广东

14阅读

0回复

0点赞

难度大概是橙橙黄绿吧。感谢金钩大佬在百忙之中出神题 / 神人题给我们。

T1

Difficulty：3- / Easy

Tag：-

假设存在一个 $x$ 使得满足 $p_i\gt n-x$ 的数量大于 $x$ 。

注意到是排列，所以不可能。

所以修改显然不优。

所以最优解是不把任何平台修改接收平台，答案就是 $p_i\le i$ 的数量。

namespace cjdst{
    void solve(){
		int n, m;
		std::cin >> n >> m;
		int ans = 0;
		std::vector <int> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			ans += (a[i] <= i);
		}
		std::cout << ans << '\n';
		while(m--){
			int x, y;
			std::cin >> x >> y;
			ans -= (a[x] <= x) + (a[y] <= y);
			std::swap(a[x], a[y]);
			ans += (a[x] <= x) + (a[y] <= y);
			std::cout << ans << '\n'; 
		}
	}
}

时间复杂度： $O(n+q)$ 。

T2

Difficulty：3.4 / Easy

Tag：-

脑电波题。

注意到如果 $n$ 是奇数，出现的数只有奇数和 $0$ 可以这么构造：

$[n,n-2,...,9,7,5,3,1,0,1,3,5,7,9,...,n-2,n]$

偶数同理。

然后注意到把这两块拼出来，中间有三个 $0$ ，而最左边和最右边的空的距离恰好是 $n+1$ ，刚好能放进 $n$ 。所以构造如下（这里展示 $n=11$ 的）：

$[\red{9,7,5,3,1}\green{,11,}\red{1,3,5,7,9}\blue{,10,8,6,4,2},0\green{,11,}\blue{2,4,6,8,10}]$

namespace cjdst{
    void solve(){
		int n;
        std::cin >> n;
        for(int i = (n - 1) / 2 * 2 - n % 2 * 2 + 1; i >= 1; i -= 2){
            std::cout << i << ' ';
        }
        std::cout << n << ' ';
        for(int i = 1; i <= (n - 1) / 2 * 2 - n % 2 * 2 + 1; i += 2){
            std::cout << i << ' ';
        }
        for(int i = (n - 1) / 2 * 2; i >= 2; i -= 2){
            std::cout << i << ' ';
        }
        std::cout << "0 " << n << ' ';
        for(int i = 2; i <= (n - 1) / 2 * 2; i += 2){
            std::cout << i << ' ';
        }
        std::cout << '\n';
	}
}

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

T3

Difficulty：3.5 / Easy

Tag：隔板法

首先计算长度为 $n$ 的方程数。

其实就是求 $n+A_1+A_2+...+A_{n+1}=S$ ， $A_i\ge 0,A_n\gt 0$ 的整数解数量。容斥一下，分别计算 $n+...=S$ 与 $n+...=S-1$ 的非负整数解数量。这里讨论前者。

移一下项， $A_1+A_2+...+A_{n+1}=S-n$ 。根据隔板法，答案为 $S\choose n$ 。

所以总数为 $\sum_{n=1}^S {S\choose n}-\sum_{n=1}^S {S-1\choose n}=2^S-2^{S-1}=2^{S-1}$ 。第二问就是在问满足 $\sum_{n=1}^m {S\choose n}-\sum_{n=1}^m {S-1\choose n}\gt k$ 的最小的 $m$ 。

注意到 $S\choose n$ 增长极快，当 $S$ 较大时， $m=2$ 时原式就已经超过 $10^9$ 了。所以组合数怎么实现都行。

我使用了一种十分拟人的 $O(m\sqrt S)$ 实现求组合数。~~能过就是好算法~~

namespace cjdst{
    const ll mod = 998244353;
	ll C(ll n, ll m){
		if(n <= 0 || m < 0) return 0;
		if(m == 0) return 1;
		std::map <ll, ll> mp;
		for(ll i = n - m + 1; i <= n; i++){
			ll cur = i;
			for(ll j = 2; j * j <= cur; j++){
				while(cur % j == 0){
					mp[j]++;
					cur /= j;
				}
			}
			if(cur != 1) mp[cur]++;
		}
		for(ll i = 1; i <= m; i++){
			ll cur = i;
			for(ll j = 2; j * j <= cur; j++){
				while(cur % j == 0){
					mp[j]--;
					cur /= j;
				}
			}
			if(cur != 1) mp[cur]--;
		}
		ll ans = 1;
		for(auto it:mp){
			for(int j = 1; j <= it.second; j++){
				ans *= it.first;
				if(ans > int(1e9)) return 0x3f3f3f3f;
			}
		}
		return ans;
	}

	void solve(){
		int n, m;
		std::cin >> n >> m;
		ll ans = 1, x = 2, y = n - 1;
		while(y){
			if(y & 1) ans = ans * x % mod;
			x = x * x % mod, y >>= 1;
		}
		ll ans2 = 0, cur = 0;
		while(cur + C(n, ans2) - C(n - 1, ans2 - 1) < m){
			cur += C(n, ans2) - C(n - 1, ans2 - 1);
			ans2++;
		}
		std::cout << ans << ' ' << ans2 << '\n';
	}
}