官方题解 | 第三届飞翔杯普及组

NoonMaple

2025-06-14 17:05:19

发布于：浙江

43阅读

0回复

0点赞

T1 考试（exam）

模拟判断两条原则是否满足，首先判断第一个原则：是否有连续的两个 $1$ ，其次判断第二个原则：对于每一个为 $0$ 的位置，判断其前后是否没有 $1$ ，如果都不是 $1$ 则可以将这个 $0$ 变为 $1$ ，输出 No。

注意边界的情况，如果前面的三个位置是 $001$ 时不满足第二个条件，同理最后三个位置是 $100$ 时也不满足条件。

#include<bits/stdc++.h>
using namespace std;
char s[100005];
int main()
{
	int n,q;
	freopen("exam.in","r",stdin);
	freopen("exam.out","w",stdout);
	scanf("%d%d",&n,&q);
	while(q--)
	{
		int opt=0;
		scanf("%s",s+1);
		for(int  i=1;i<=n;i++)
		{
			if(s[i]=='1'&&s[i+1]=='1')opt=1;
			else if(s[i]=='0'&&s[i-1]!='1'&&s[i+1]!='1')opt=1;
		}
		if(!opt)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

T2：好数（number）

40%

$O(n^4)$ 枚举即可。

70%

$A[i] = A[x] + A[y] + A[z] ， x < y < z < i$

维护小于 $i$ 的 $A[x]+A[y]+A[z]$ 的和即可，时间复杂度 $O(n^3)$

100%

$A[x]+A[y]+A[z]$ 通过类似 $01$ 背包的方式维护，维护两个数字构成的和的情况，三个数字构成和的情况，用bitset优化加速即可，时间复杂度 $O(\frac{n^3}{64})$

100%

表达式类问题可以通过移项优化枚举策略

$A[i] = A[x] + A[y] + A[z] \rightarrow A[i] - A[z] = A[x] + A[y]， x < y < z < i$

枚举 $i$ 和 $z$ ，维护小于 $i$ 的 $A[x]+A[y]$ 的和即可。

复杂度 $O(n^2)$

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

const int maxn = 5005;
int a[maxn], n, ans;
unordered_set<int> s;

int main() {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
    cin>>n;
    for(int i = 1; i <= n; ++i) cin>>a[i];
    for(int i = 1; i <= n; ++i) {
        bool flag = false;
        for(int j = 1; j < i; ++j) {
            if(s.find(a[i] - a[j]) != s.end()) flag = true;
        }
        ans += flag;
        for(int j = 1; j <= i; ++j) s.insert(a[i] + a[j]);
    }
    cout<<ans;
    return 0;
}

T3 小 Z 的手套（gloves）

20分做法

$N=M$ ，将左手手套和右手手套排序后，首位逐一匹配即可。

另外50分

发现瓶颈在于匹配，匹配的前提是不会超过答案，因此可以考虑从小到大枚举丑陋度（即尺码差）的最大值，然后对于每一个左手手套贪心匹配右手手套，这个可以通过排序和二分来加速。

同时发现丑陋度（即尺码差）的最大值一定是左手和右手手套尺码组合出来的值，可能的答案不超过 $n^2$ 种，复杂度 $O(n^3)$ 。

100分做法

最小化最大值，考虑二分答案。

首先，我们需要确定丑陋度的可能范围。最小丑陋度显然是 $0$ （如果恰好有匹配的尺码），最大丑陋度则是左手手套和右手手套中的最大差值。我们可以使用二分答案来在这个范围内搜索最优解。

在二分查找的每一步中，我们假设一个丑陋度阈值 mid，然后尝试找到满足这个阈值的最大匹配数。我们可以对左手手套和右手手套的尺码分别进行排序，然后使用双指针的方法从两端开始匹配，如果两只手套的尺码差小于等于mid，则它们可以配对，然后移动两个指针。最终，我们得到了满足丑陋度阈值mid的最大匹配数。

如果匹配数等于最大能够配对成功的手套数量（即左手手套和右手手套数量中的最小值），那么mid可能是一个解，我们尝试缩小搜索范围到左半部分；否则，我们需要增加丑陋度阈值，所以搜索范围移动到右半部分。

复杂度 $O(n \log |L_i| )$ 。

「补充证明双指针配对的正准确性」

讲左右手套按照大小从小到大排序，然后两个指针从头开始配对，证明 $i$ 配对的 $j$ 一定是单调的，并且此时一定是最优匹配。
$L:~...ab...$ $L : ... ab ...$ ； $R:~...cde...$ $R : ... c d e ...$ ，假设 $a$ $a$ 与 $d$ $d$ 配对，已知 $|a-d|\le x$ $∣ a - d ∣ \leq x$ 并且 $|a-c|>x$ $∣ a - c ∣ > x$ ，需要证明 $|b-c|>x$ $∣ b - c ∣ > x$
- 只有两种情况使得上述情况成立
  1. $c\le a\le d,a\le b$
  2. $c\le d \le a,a\le b$
- 无论是哪种情况，都有 $|b-c|>x$

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

const int maxn = 1e5 + 5;
int n, m, l[maxn], r[maxn];

bool check(int x) {
    int j = 1;
    for(int i = 1; i <= n; ++i) { // 用数量少的手套匹配多的手套
        while(j <= m && abs(l[i] - r[j]) > x) ++j;
        if(j > m) return false;
        ++j;
    }
    return true;
}

int main() {
    freopen("gloves.in", "r", stdin);
    freopen("gloves.out", "w", stdout);
    cin>>n>>m;
    for(int i = 1; i <= n; ++i) cin>>l[i];
    for(int i = 1; i <= m; ++i) cin>>r[i];
    if(n > m) {
        for(int i = 1; i <= n; ++i) swap(l[i], r[i]);
        swap(n, m);
    }
    sort(l + 1, l + 1 + n);
    sort(r + 1, r + 1 + m);
    int left = 0, right = 1e9, mid, ans;
    while(left <= right) {
        mid = (left + right) / 2;
        if(check(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout<<ans;
    return 0;
}

T4 刷题训练（train）

20分做法

对于 $20\%$ 的数据， $m=0$

没有任何操作可以做，所以只有所有的 $a_i$ 都满足 $a_i\le k$ 才可以，答案是 $0$ ；否则是 $-1$

另外20分

对于另外 $20\%$ 的数据，只有第一种类型的魔法（即修改某一道题的难度）

如果所有 $a_i>k$ 的都可以修改，答案就是这样子的题目个数；否则是 $-1$

另外20分

对于另外 $20\%$ 的数据，第一种类型的魔法只有一个。

考虑图论做法，交换两个题，本质上是连边，只要一个点能被换到有第一类操作的地方，那么这个点就可以被修改。

因此找到第一类魔法操作的点，跑一个单源最短路，答案就是所有不合法的点的 dis 之和 + 不合法点的个数。

满分做法

对于全部数据， $1\le n,m,k,a_i\le 2\ast 10^6, 1\le x,y\le n$ 。

我们可以把所有第一类魔法操作的点放到队列中，跑最短路。

因为图没有边权，所以可以直接用 BFS 求最短路即可，复杂度 $O(n)$ 。

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

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 2e6 + 5;
int a[maxn], dis[maxn], n, m, k;
bool vis[maxn];
vector<int> g[maxn], v;
queue<int> q;

int main() {
    freopen("train.in", "r", stdin);
    freopen("train.out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>k;
    for(int i = 1; i <= n; ++i) {
        cin>>a[i];
        if(a[i] > k) v.push_back(i); // 不合法的点
    }
    memset(dis, 0x3f, sizeof(dis));
    while(m--) {
        int op, x, y;
        cin>>op;
        if(op == 1) {
            cin>>x;
            dis[x] = 0;
        } else {
            cin>>x>>y;
            g[x].push_back(y); g[y].push_back(x);
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(dis[i] == 0) {
            vis[i] = true;
            q.push(i);
        }
    }
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int v: g[u]) {
            if(!vis[v]) {
                dis[v] = dis[u] + 1;
                q.push(v);
                vis[v] = true;
            }
        }
    }
    for(int x: v) {
        if(dis[x] == inf) {
            cout<<-1;
            return 0;
        }
    }
    ll ans = v.size();
    for(int x: v) ans += dis[x];
    cout<<ans;
    return 0;
}