导航栏

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

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题

一、题目概述

小红和小紫围绕小小红展开博弈。

$\hspace{15pt}$有一个 $2$ 行 $n$ 列的网格，所有格子初始为空。小小红初始在左上角 $(1,1)$。每次可以向上下左右相邻格子移动一步（不能走到障碍格，也不能走出网格）。
$\hspace{15pt}$小小红需要到达第 $n$ 列的任意一个空格子，并且总是选择最短步数的路径。

$\hspace{15pt}$小红和小紫进行博弈（小红先手），轮流执行操作：
$\hspace{23pt}\bullet\,$∙选择一个当前为空且不为起点的格子放置障碍，使小小红无法进入该格子；
$\hspace{23pt}\bullet\,$∙要求放置后，从起点 $(1,1)$ 仍然存在一条路径能够到达第 $n$ 列的某个空格子。
$\hspace{15pt}$若当前不存在满足要求的格子可放置障碍，则博弈结束。

$\hspace{15pt}$两人都按最优策略行动：小红希望最终最短步数尽量小，小紫希望最终最短步数尽量大。博弈结束后，小小红从起点出发。请输出她到达第 $n$ 列所需的最少步数。

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leqq T\leqq 10^4\right)$ 代表数据组数，每组测试数据描述如下：

$\hspace{15pt}$第一行输入一个整数 $n\left(1 \leqq n \leqq 10^9 \right)$，表示网格的列数。

二、思路分析

这道题刚读完题会想试图用搜索策略解决，但是发现没有很好的思路，并且复杂度是$10^9$，但是对于这么大的数据一般的O(n)算法是会超时的。所以我们改变策略，这是很容易想到会不会是有一个固定的规律形成的博弈。然后我们分别代入小红和小紫，尽可能地按照最优策略，这个时候就会发现只有按照如图的博弈才可以实现最优策略，这个时候的步数是最少的。

注：$▲是小红，⚪是小紫$。

三、复杂度分析

很显然只要找到最优策略后，我们就可以通过一个公式就能解决，所以复杂度是O(1)。

四、参考代码

#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;
		int pur = 4;
		if(n >= 4)
		{
			int add = (n - 4) / pur + 1;
			int ans = (n - 1) + add;
			cout << ans << endl;
			continue;
		}
		cout << n - 1 << endl;
		
	}
}

G题

一、题目概述

给定一个天平，左侧有 n 个砝码，右侧有 m 个砝码，分别用数组 a 和 b 表示其重量。

天平可能处于三种状态之一：

• 左侧总重量大于右侧
• 左右总重量相等
• 左侧总重量小于右侧

现在可以从两侧任意取走一些砝码。
为了使天平的状态发生改变（与当前状态不同），最少需要取走多少个砝码

多组数据输入，且所有测试数据中 n 与 m 的总和不超过 $2 \times 10^5$ 。

二、思路分析

这道题是简单题，如果两个重量相当，只需要移动一个砝码操作就可以。如果不相等，则对砝码重量进行排序。将重量大的那一边移动砝码到重量小的一边，并且按照从大到小的顺序移动知道重量大的一边不大于另一边则是最优解。

三、复杂度分析

排序用快排则可以复杂度到达O($n* log n$) 而后续的操作是不大于O(m+n)的，所以复杂度是O(n*logn)。

四、参考代码

#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, m;
		cin >> n >>m;
		vector<long long> a(n),b(m);
		long long sum1 = 0, sum2 = 0;
		for(long long& v: a)
		{
			cin >> v;
			sum1 +=v;
		 } 
		for(long long& v: b) 
		{
			cin >> v;
			sum2 +=v;
		 } 
		if(sum1 == sum2)
		{
			cout << 1 << endl;
			continue;
		}
		sort(a.begin(),a.end(),greater<long long>());
		sort(b.begin(),b.end(),greater<long long>());
		if(sum1 > sum2)
		{
			int ans = 0;
			int i = 0;
			while(sum1 > sum2)
			{
				sum1 -= a[i++];
				
				ans++;
			}
			cout << ans << endl;
			continue;
		}
		if(sum1 < sum2)
		{
			int ans = 0;
			int i = 0;
			while(sum1 < sum2)
			{
				sum2 -= b[i++];
				
				ans++;
			}
			cout << ans << endl;
			continue;
		}
	}
}

H题

一、题目概述

给定平面上的两个点 (A(x_a, y_a)) 和 (B(x_b, y_b))，需要在 x 轴上选择一个点 (O(x, 0))，使得三角形 (A, B, O) 的面积恰好为 2。

你的任务是判断这样的横坐标 (x) 是否存在：

• 如果存在，输出任意一个满足条件的实数 (x)（面积误差不超过 0.001 即可）；
• 如果不存在，输出 no answer。

若有多个解，输出任意一个即可。

二、思路分析

如果$y1$和$y2$的值相等，那么其与x轴是平行的，那么特判就是$(x2-x1)$乘$y$是否等于4。其中一定要注意浮点数比大小。然后再分析对于确定两点和一个在坐标轴上的点，确定这一点的横坐标。对此我们有一个公式。

给定平面上三点$$A(x_1, y_1),\quad B(x_2, y_2),\quad C(x_3, y_3)$$

三角形面积公式为（通用坐标公式）：$$S=\frac{1}{2}\left| x_1(y_2-y_3) + x_2(y_3-y_1) + x_3(y_1-y_2) \right|$$

因此我们可以代入C(x,0)，则可以得出x的解，要注意浮点数位数的处理。

三、参考代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	if(y1 == y2)
	{
		double absx = abs(x1-x2);
		double ans = abs(absx * y1) * 0.5;
		if(fabs(ans - 2.0) < 1e-8)
		{
			cout << 0.0 << endl;
		}
		else{
			cout <<"no answer" << endl;
		}
	}
	else{
		double  upper =4 - x1*y2 + x2*y1;
		double  under = y1 - y2;
		double x = upper / under;
		printf("%.8f\n", x);
        
	}
}

J题

一、题目概述

给定一棵共有 n 个节点的完全二叉树，节点按层序编号，根为 1，节点 i 的左儿子是 2i，右儿子是 2i+1（编号不超过 n 才存在）。

有多次查询，每次给出一个节点编号 x。你需要求出在这棵树中，与节点 x 处于同一深度（同一层） 的节点数量（包含 x 本身）。

注意：

• 树的节点总数最多可达$10^{18}$，不能真正建树；
• 每个查询独立，输出对应层在编号范围 $1 \sim n$ 内实际存在的节点个数。

二、思路分析

这道题目实际上考的是对完全二叉树的理解，我们可以对于每一次查询都找到不大于该数的最大$2^d$,则答案是R – L + 1，R = min(n，$2^{d+1}-1$), L = $2^d$。

三、复杂度分析

该题的复杂度是查询复杂度O(q)

四、参考代码

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

void solve(){
    unsigned long long n;
    int q;
    cin>>n>>q;
    while(q--){
        unsigned long long x;
        cin>>x;
        unsigned long long L=1ULL<<(63-__builtin_clzll(x));
        unsigned long long R=min(n,L*2-1);
        cout<<(long long)(R-L+1)<<"\n";
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)solve();
    return 0;
}

I题

一、题目概述

给定两个长度为 n 的数组 a 和 b。对于每个位置$i（1 ≤ i ≤ n）$，可以选择：
$c_i = a_i 或 c_i = b_i$

要求构造数组 c，使得：
$c_1 ⊕ c_2 ⊕ … ⊕ c_n = 0$

如果存在满足条件的方案，输出任意一个；否则输出 -1。

数据范围：
$1 ≤ T ≤ 100$
$1 ≤ n ≤ 10^5$
$0 ≤ a_i, b_i < 2^{30}$
所有测试数据中，$∑n ≤ 2 × 10^5$

二、思路分析

我们可以构造数组$c_i$的值为$a_i$，然后判断c的按位异或和是不是等于0，这样可以直接输出a数组的值。然后我们可以发现如果不等于0，则将若干个$b_j$的值异或上去，则整个式子$S=a_1⊕a_2⊕…⊕a_i⊕$然后再异或$d = a_j ⊕b_j$，此时求是否存在这样若干个值异或后整个式子等于0。这样可以等价转换为是否存在这样若干个d的异或和等于S，即数集的子集异或等于某个值，并输出。

问题转换之后，我们如果尝试用暴力方法，复杂度高达$2^n$，对于题目数据是无法接受的。所以我们要想一个复杂度更低的算法。这里引入线性基的策略。异或线性基就是把一串数字变成基向量，然后它们互相不能进行异或操作，然后这些线性基可以用来判断一串数字的任意子集是否能构成某个要求的数。这样的复杂度就会很小，能够通过这道题。

线性基（OI Wiki）

三、复杂度分析

这道题目用线性基的方法，复杂度可以简化为O(31*n)，是一个很快的算法。

四、参考代码

#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+1,0);
		vector<int> b(n+1,0);
		int temp = 0;
		for(int i = 1; i <= n; i++) {
			cin >> a[i];
			temp ^= a[i];
		}
		for(int i = 1; i <= n; i++) cin >> b[i];
		if(temp == 0){
			for(int i = 1; i <= n; i++) cout << a[i] << " ";
			cout << endl;
			continue;
		}
		vector<int> bas(35,0);
		vector<unsigned long long> msk(35,0);
		int id[70] = {0};
		int cnt = 0;
		for(int i = 1; i <= n; i++)
		{
			int cur = a[i]^b[i];
			if(!cur) continue;
			unsigned long long curm = 1ull << cnt;
			for(int j = 30 ; j >= 0 ; j--)
			{
				if(((cur >> j) & 1) == 0) continue;
				if(!bas[j])
				{
					bas[j] = cur;
					msk[j] = curm;
					id[cnt++] = i;
					break;
				}
				cur ^= bas[j];
				curm ^= msk[j];
			}
		}
		int cur = temp;
		unsigned long long pick = 0;
		char use[202020] = {0}; 
		for(int j = 30 ; j >= 0; j--)
		{
			if((cur >> j) & 1)
			{
				if(!bas[j])
				{
					cout << -1 << endl;
					goto skip;
				}
				cur ^= bas[j];
				pick ^= msk[j];
			}
		}
		
		for(int i = 0; i < cnt; i++)
		{
			if((pick >> i) & 1)
			{
				use[id[i]] = 1;
			}
		}
		for(int i = 1; i <= n; i++)
		{
			cout << (use[i] ? b[i] : a[i] )<< " ";
		}
		cout << endl;
	skip:
		continue;
	}
}