导航栏

• A题
• B题
• C题
• D题
• F题
• J题
• H题
• J题

A题

一、题目概述

本题要求判断给定的正整数 $x$ 是否可以表示为两个连续自然数的乘积。
也就是说，是否存在某个自然数 $k$，使得：$$x = k \times (k + 1)$$

如果存在这样的 $k$，则称 $x$ 为「终极答案」，输出 YES；否则输出 NO。

二、思路分析

由于题目中 $x \le 100$，数据范围较小，可以直接枚举 $k$，检查是否满足上述等式即可。

三、参考代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x;
    cin>>x;
    for(int i=1;i<=9;i++){
        if(i*(i+1)==x){
            cout<<"YES\n";
            return 0;
        }
    }
    cout<<"NO\n";
    return 0;
}

B题

一、题目概述

给定一个长度为 $n$ 的整数数组$$a_1, a_2, \dots, a_n$$

需要从中选择两个不同位置的元素，使得这两个元素的最大公约数满足$$\gcd(a_i, a_j) > 1$$

特殊的，保证数组元素在 $[1, 10^9]$ 范围内独立均匀随机生成。

若不存在满足条件的元素对，则输出 $-1$；
否则输出任意一组满足条件的两个元素的值。

输入包含多组测试数据，且所有测试数据中数组长度之和不超过$$2 \times 10^5$$

二、思路分析

由于测试数据是大范围随机生成的，所以实际上随着n的长度变大，对于任意两个数的gcd小于1的概率会越来越小。所以我们可以进行两层循环，且最大循环次数是500次，这样就可以满足题意。

三、正确性证明

（来自牛客题解的证明）

失败概率（随机模型估算）：对两独立随机整数，经典结论

$\Pr(\gcd(u,v)=1)=\frac{6}{\pi^2}\approx 0.6079,$

一个简短推导（容斥/莫比乌斯反演）：令事件 $A_p$​ 表示“素数 $p$ 同时整除 $u,v$”，则 $\Pr(A_p)=1/p^2$。利用容斥可得

$\Pr(\gcd(u,v)=1)=\sum_{d\ge 1}\mu(d)\Pr(d\mid u\ \text{且}\ d\mid v) =\sum_{d\ge 1}\frac{\mu(d)}{d^2},$

其中 $\mu$μ 为莫比乌斯函数（容斥系数）。另一方面

$\sum_{d\ge 1}\frac{\mu(d)}{d^2} =\prod_p\left(1-\frac{1}{p^2}\right) =\frac{1}{\zeta(2)} =\frac{6}{\pi^2}.$

因此一次检查命中 $\gcd>1$ 的概率约为 $p\approx 1-6/\pi^2\approx 0.3921$。把每次 gcd 检查近似看作独立，则做 $M=30n$ 次检查仍未命中的概率近似为

$(6/\pi^2)^M.$

当 $n=2\times 10^5$时 $M=6\times 10^6$，有

$\log_{10}(6/\pi^2)\approx -0.2163\ \Rightarrow\ (6/\pi^2)^M \approx 10^{-0.2163\cdot 6\times 10^6}\approx 10^{-1.3\times 10^6},$

几乎不可能失败。

四、参考代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		vector<int> a(n);
		for(int& v : a) cin >> v;
		int lim = min(500,n);
		
		for(int i = 0; i < lim; i++)
		{
			for(int j = i + 1; j < n; j++)
			{
				if(j > lim + i) break;
				if(gcd(a[i],a[j]) > 1 )
				{
					cout << a[i] << " " << a[j] << "\n";
					goto found;
				}
			}
		}
		
		cout << -1 << "\n";
		found:;
	}

}

C题

一、题目概述

本题给定一个长度为 $n$ 的二进制字符串$$s$$

字符串仅由字符 $0$ 和 $1$ 组成。

允许进行如下操作任意次：

• 选择字符串 $s$ 的一个非空子序列，要求该子序列中任意两个相邻字符都不相同；
• 对该子序列执行 01 反置，即将其中的 $0$ 变为 $1$，$1$ 变为 $0$。

目标是通过若干次操作，使得最终字符串中任意两个相邻字符都不相同。

对于每组测试数据，输出达到上述目标所需的最少操作次数。

输入包含多组测试数据，并且所有测试数据中字符串长度之和不超过$$2 \times 10^5$$

二、思路分析

对于目标字符串有两种形式，即“101010…” 或者“010101…”。 我们可以把给定字符串变成这两种形式然后比较哪个操作数最少即可。我们可以把原字符串与目标字符串不符合的位置单独提出来，并且构成一个新的字符串t，后续维护该字符串t。此时t表示的就是给定字符串中“错位”的字符串。对于字符串t，我们可以声明一个cnt[2]数组，并且遍历t，如果t为‘1’，则cnt[1]++,同时判断cnt[0]是否存在，如果存在就可以“接上”上一个已经存在的0，则cnt[0]–，最后的答案就是cnt[0]+cnt[1]。

三、复杂度分析

这是一个O(n)级别的算法

四、参考代码

#include<bits/stdc++.h>

using namespace std;

int solve(string s)
{
	int cnt[2] = {};
	for(char c : s)
	{
		if(c == '0')
		{
			if(cnt[1] > 0) cnt[1]--;
			cnt[0]++;
		}
		else{
			if(cnt[0] > 0) cnt[0]--;
			cnt[1]++;
		}
	}
	return cnt[1] + cnt[0];
}

int cal(bool k, string s)
{
	string r = "";
	int n = s.size();
	for(int i = 0; i < n; i++)
	{
		if((s[i] - '0') != k)
		{
			r += s[i];
		}
		k = !k;
	}
	return solve(r);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		string s;
		cin >> n >> s;
		cout << min(cal(1,s),cal(0,s)) << endl;
	}
}

D题

一、题目概述

本题给定一个 $n \times m$ 的网格，每个格点的标记为 $0$、$1$ 或 $2$。其中，标记为 $1$ 的格点恰好有两个，标记为 $2$ 的格点也恰好有两个，其余格点均为 $0$。

需要在网格中规划两条路径：

• 一条路径连接两个标记为 $1$ 的格点；
• 另一条路径连接两个标记为 $2$ 的格点。

路径需满足以下条件：

• 路径由上下左右相邻的格点组成；
• 两条路径不能经过同一个格点；
• 每条路径不能经过不属于该路径的信号点（例如，连接 $1$ 的路径不能经过标记为 $2$ 的格点）；
• 路径可以经过标记为 $0$ 的格点，但每个 $0$ 格点最多只能被一条路径使用一次。

对于每组测试数据，判断是否存在满足上述条件的两条路径，若存在则输出 YES，否则输出 NO。

输入包含多组测试数据，并保证所有测试数据中网格总大小$$\sum (n \times m) \le 10^5$$

二、思路分析

这道题有两种解法，一种是贪心+特判的解法，相对考验平面拓扑的观察，另一种是通过bfs前驱记录加另一次bfs可以做。这道题用第二种解法。首先我们将2和2的两条最短路径连接起来，先对2进行一次bfs，并且通过前驱记录回溯最短路径，将最短路径标记为不可走，然后对1进行一次bfs，判断其能否到达另一个1。如果无法到达我们再反过来用1和1进行第一次bfs记录前驱并回溯，然后用相同的方法判断。

三、算法分析

使用的主要算法

1. 广度优先搜索（BFS）
   • 用于在网格中寻找两点之间的一条可行路径
   • 只允许上下左右移动
   • 可设置“禁止经过的格点类型”和“已占用格点”
2. 路径回溯
   • 在 BFS 中记录每个格点的前驱
   • 若成功到达终点，则回溯得到整条路径
3. 枚举路径连接顺序
   • 分别尝试：
     • 先连接两个 1，再连接两个 2
     • 先连接两个 2，再连接两个 1
   • 任意一种顺序成功即可判定答案为 YES

四、复杂度分析

这是一个O(∑(n×m))级别的算法

五、参考代码

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

/*
  四个方向的位移
*/
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int n, m;
vector<vector<int>> adj;

/*
  在网格上进行 BFS，尝试从 (sx, sy) 走到 (fx, fy)

  ban : 本次路径禁止经过的信号点类型（1 或 2）
  a   : 当前网格状态（-1 表示已被另一条路径占用）

  返回值：
  - 若不可达，返回空 vector
  - 若可达，返回一条从起点到终点的路径
*/
vector<pair<int,int>> bfs_path(
    int sx, int sy,
    int fx, int fy,
    int ban,
    vector<vector<int>> &a
) {
    queue<pair<int,int>> q;
    map<pair<int,int>, pair<int,int>> pre; // 记录前驱
    map<pair<int,int>, int> vis;            // 访问标记

    q.push({sx, sy});
    vis[{sx, sy}] = 1;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;

        if (x == fx && y == fy) break;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (vis[{nx, ny}]) continue;
            if (a[nx][ny] == ban) continue; // 不能经过另一种信号点
            if (a[nx][ny] == -1) continue;  // 不能经过已占用格点

            vis[{nx, ny}] = 1;
            pre[{nx, ny}] = {x, y};
            q.push({nx, ny});
        }
    }

    if (!vis[{fx, fy}]) return {};

    // 回溯路径
    vector<pair<int,int>> path;
    pair<int,int> cur = {fx, fy};
    while (!(cur.first == sx && cur.second == sy)) {
        path.push_back(cur);
        cur = pre[cur];
    }
    path.push_back({sx, sy});

    return path;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        adj.assign(n, vector<int>(m));

        // 读入网格
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < m; j++)
                adj[i][j] = s[j] - '0';
        }

        // 记录 1 和 2 的位置
        vector<pair<int,int>> one, two;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (adj[i][j] == 1) one.push_back({i, j});
                if (adj[i][j] == 2) two.push_back({i, j});
            }

        bool ok = false;

        /*
          情况一：先连 1，再连 2
        */
        {
            auto a = adj;

            auto p1 = bfs_path(
                one[0].first, one[0].second,
                one[1].first, one[1].second,
                2, a
            );

            if (!p1.empty()) {
                // 占用路径中的 0 格点
                for (auto &p : p1)
                    if (a[p.first][p.second] == 0)
                        a[p.first][p.second] = -1;

                auto p2 = bfs_path(
                    two[0].first, two[0].second,
                    two[1].first, two[1].second,
                    1, a
                );

                if (!p2.empty()) ok = true;
            }
        }

        /*
          情况二：先连 2，再连 1
        */
        {
            auto a = adj;

            auto p1 = bfs_path(
                two[0].first, two[0].second,
                two[1].first, two[1].second,
                1, a
            );

            if (!p1.empty()) {
                for (auto &p : p1)
                    if (a[p.first][p.second] == 0)
                        a[p.first][p.second] = -1;

                auto p2 = bfs_path(
                    one[0].first, one[0].second,
                    one[1].first, one[1].second,
                    2, a
                );

                if (!p2.empty()) ok = true;
            }
        }

        cout << (ok ? "YES\n" : "NO\n");
    }
    return 0;
}

F题