2026 牛客寒假集训营-3

（本题解按照题目难度排序，仅用作补题记录）

1. A-宙天

题目描述

小红正在探索宇宙的奥秘，她认为某些数字承载着特殊的意义。
小红定义一个正整数 为「终极答案」，当且仅当它能表示为两个连续自然数的乘积。

形式化的，若存在自然数 ，满足 ，则称 为「终极答案」。
给定一个正整数 ，请你帮小红判断它是否是一个「终极答案」。

输入描述

在一行上输入一个整数 。

输出描述

如果 是一个「终极答案」，输出 ；否则输出 。

解题思路

数据量很小，提前把所有符合条件的数都找出来，直接判断是否是符合条件的就行

AC 代码

void solve(){
    inpu();
    for(int i=1;i<=150;i++){
        s.insert(i*(i+1));
    }
    if(s.find(n)!=s.end()){
        cout<<"YES\n";
        return ;
    }
    cout<<"NO\n";
    return ;
}

2. B-Random

题目描述 小红拿到了一个长为 的数组 。她想要选择其中两个不同位置的元素，要求这两个元素的最大公约数大于 ，请你帮帮她。
特殊的，保证数组元素在 范围内独立均匀随机生成。

【名词解释】
最大公约数（gcd）：指两个或多个整数共有约数中最大的一个。例如， 和 的公约数有 >，其中最大的约数是 ，因此记作 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，代表数组长度。
第二行输入 个整数 ，代表数组元素。

除此之外，保证单个测试文件的 之和不超过 。

输出描述

对于每组测试数据，如果不存在符合要求的两个元素，直接输出 ；否则，在一行上输出两个整数，代表选中的两个元素的值。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

解题思路

任意选两个偶数，最大公约数一定大于等于2，如果n很小，就在暴力搜索，如果n很大（由于均匀生成的性质，会很容易就找到两个偶数），就只暴力搜索前100或前1000个数字。

AC 代码

void solve(){
    inpu();
    int len=min(3000ll,n);
    for(int i=1;i<=len;i++){
        for(int j=i+1;j<=len;j++){
            int res=__gcd(a[i],a[j]);
            if(res>1){
                cout<<a[i]<<" "<<a[j]<<"\n";
                return ;
            }
        }
    }
    cout<<-1<<"\n";
    return ;
}

3. G-スピカの天秤

题目描述 小红有一个天平，天平的左侧有 个砝码，砝码的重量用数组 表示；右侧有 个砝码，砝码的重量用数组 表示。我们认为天平有三种状态：
左侧的重量大于右侧。
左侧的重量等于右侧。
左侧的重量小于右侧。
现在小红想知道，想要改变天平的状态，她最少需要拿走多少个砝码？

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示天平左侧的砝码数量、天平右侧的砝码数量。
第二行输入 个整数 ，表示天平左侧的砝码重量。
第三行输入 个整数 ，表示天平右侧的砝码重量。

除此之外，保证单个测试文件的 之和、 之和不超过 。

输出描述
对于每组测试数据，新起一行输出一个整数，代表最少需要拿走的砝码数量。

解题思路

如果重量相同，随便拿走一个就行

如果重量不一样，在重量大的那一部分，按重量从大到小去累加，状态改变即停止

AC 代码

void solve(){
    inpu();
    if(suma==sumb){cout<<1<<"\n";return ;}
    int ans=0;
    if(suma>sumb){
        int cnt=0;
        sort(a+1,a+1+n,greater<>());
        while(suma>sumb){
            suma-=a[++cnt];
        }
        cout<<cnt<<'\n';
        return ;
    }
    else{
        int cnt=0;
        sort(b+1,b+1+m,greater<>());
        while(suma<sumb){
            sumb-=b[++cnt];
        }
        cout<<cnt<<'\n';
        return ;
    }
}

4. J-Branch of Faith

题目描述 小红有一棵包含 个节点的完全二叉树，其中 号节点为根， 号节点的左儿子编号是 ，右儿子编号是 。
现在有 次询问，每次查询一个 ，你需要回答与 号节点深度相同的节点有多少个（包含 本身）。

【名词解释】
完全二叉树：满足以下全部条件的二叉树。
若树的层数为 ，则除第 层外，其他各层（ 至 层）的节点数均达到最>大值（即第 层节点数为 ）；
第 层的所有节点都连续集中在左侧，即节点之间不存在任何空位。
二叉树：满足以下全部条件的树。
二叉树可以是空集；若不为空，则由一个根节点以及两棵互不相交的、分别称为左子树和右>子树的二叉树组成；
每个节点要么没有父节点连接（此时该节点被称为根节点）、要么被 个父节点连接>（此时该节点被称为父节点的子节点）；
每个节点连接的子节点数量要么为 （此时该节点被称为叶子节点），要么不超过 ，且此时每个子节点都有明确的“左”或“右”属性。
深度：从根节点到节点 的唯一路径上的边数，称为节点 的深度。根节点的深度为 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示二叉树的节点数、询问次数。
此后 行，第 行输入一个整数 ，表示第 次询问的节点编号。

除此之外，保证单个测试文件的 之和不超过 。

输出描述

对于每一次询问，新起一行输出一个整数，代表与 号节点深度相同的节点数量。

解题思路

根据完全二叉树的定义，第i层的节点，左边界是2^(i-1)，右边界是 2 ^ i - 1 ，每一次查询都在log复杂度，可以接受

AC 代码

void solve(){
    inpu();
    while(q--){
        int x,l=2,r;cin>>x;
        if(x==1){cout<<1<<'\n';continue;}
        while(l<=x)l*=2;l/=2;
        r=l*2-1;
        r=min(r,n);
        cout<<r-l+1<<"\n";
    }
}

5. H-Tic Tac DREAMIN’

题目描述

小红在二维平面地图上标记了两个关键点 和 。
她现在需要在 轴上寻找一个锚点 ，使得以 为顶点的三角形面积恰好等于 。
请你帮小红判断是否存在符合条件的锚点横坐标 。如果存在，请找出一个符合条件的 。

输入描述

第一行输入两个整数 ，代表点 的坐标。
第二行输入两个整数 ，代表点 的坐标。

输出描述

如果存在满足条件的 ，输出一个实数表示该坐标（你只需要保证最终构造的三角形面积与  的绝对误差不超过  即可）；否则，输出 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

解题思路

如果 b和y相同，三角形的面积是固定值，任意符合要求的点都不影响面积，只需要判断面积是否为2即可

若b!=y : 已知三个坐标(a,b)(x,y)(p,q)

面积公式如下： S=(a * (y - q) + x * (q - b) + p * (b - y)) / 2.0
由题意可知，q 值为 0, 代入得到p值(之一)的公式为 ：p = ( x * b - a * y + S * 2 ) / ( b - y )

PS:

第一种情况是这样的，当b不等于y时，三点共线时面积为 0 ，从共线点往两侧延伸，面积都是单调递增，于是想用浮点数二分 [共线点，1e18] 计算面积 , 来查找面积为2.0的横坐标点，用了海伦公式和向量积公式计算面积，但通过率都止步于95%，应该是计算过程中精度损失过多了。

AC 代码

void solve(){
    inpu();
    cout<<fixed<<setprecision(12);
    if(fabs(b-y)<eps){
        long double area=0.5*fabsl(x-a)*fabsl(b);
        if(fabsl(area-2.0)<=0.001)cout<<5.000000<<"\n";
        else cout<<"no answer\n";
        return;
    }
    long double ans;
    ans=(x*b-a*y+4.000)/(b-y);
    cout<<ans<<"\n";
}

6. F-Energy Synergy Matrix

题目描述

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

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

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

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

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示网格的列数。

输出描述

对于每组测试数据，新起一行输出一个整数，代表最终小红的移动次数。

解题思路

小红可以利用先手，构造出放置障碍就会导致无路可走的状态，防止小紫操作，小紫只能在更后面的位置放置障碍造成一次改变方向，周期为5，会改变n/5次方向。

PS

一开始模拟的就是对的，周期算成4了，后面没想好，思路一直往歪，红温下机

AC 代码

void solve(){
    cin>>n;
    int res=n/5;
    cout<<n-1+res<<'\n';
}

7. C-Inverted World

题目描述

小芳拿到了一个仅由字符 和 组成的长为  的字符串 ，他可以进行任意次如下操作：
选择  的一个非空子序列，该子序列任意两个相邻元素都不相同>，将该子序列进行 01 反置。
小芳想知道，最少需要多少次操作才能使得  中任意两个相邻元素都不相同？

【名词解释】
子序列：从原序列中删除任意个（可以为零，也可以为全部）元素，且保持剩余元素相对顺序不变得到的新序列。
01 反置：同时将字符串中的 变成 ， 变成 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，代表字符串长度。
第二行输入一个长为 ，仅由字符 和 构成的字符串 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述

对于每组测试数据，新起一行输出一个整数，代表所需要的最少操作次数。

解题思路

解决这个问题的核心在于将复杂的字符操作转化为简单的数学计算。首先，我们要明确最终目标只有两种可能的模式（即 0101... 或 1010...），因此我们只需分别计算变成这两种模式的代价并取较小值即可。以变成 0101... 为例，我们并不直接去数有多少个“错误”的字符，而是把原字符串中所有本来就符合该位置要求的字符按原顺序提取出来（例如偶数位的 0 和奇数位的 1），形成一个新的“正确子序列”。接着，我们将这个子序列数字化：把其中的 1 记作 ，把 0 记作 。此时，问题就变成了一个求最大绝对子段和的问题——因为如果这个数字序列的和在一某段区间内累积得很大（正数或负数），说明这里堆积了大量相同的字符（即正确字符“扎堆”了，没有交替开），而每一次翻转操作本质上就是为了消除这种堆积。因此，这个数字序列中绝对值最大的子段和，也就精确对应了打破这些堆积、让序列完全交替所需的最少操作次数。

PS

有点难抽象的模型

AC 代码

int check(string t){
	int res=0;
	int maxx=0;
	for(char &c:t){
		if(c=='1')res++;
		else res--;
		if(res<0)res=0;
		maxx=max(maxx,res);
	}
	res=0;
	int minn=0;
	for(char &c:t){
		if(c=='1')res++;
		else res--;
		if(res>0)res=0;
		minn=min(minn,res);
	}
	minn=-minn;
	return max(maxx,minn);
}
void solve(){
	cin>>n>>s;
	string t="";
	for(int i=0;i<s.size();i++){
		if(i%2==1&&s[i]=='1')t+=s[i];
		if(i%2==0&&s[i]=='0')t+=s[i];
	}
	int ans=check(t);
	t="";
	for(int i=0;i<s.size();i++){
		if(i%2==0&&s[i]=='1')t+=s[i];
		if(i%2==1&&s[i]=='0')t+=s[i];
	}
	ans=min(ans,check(t));
	cout<<ans<<"\n";
}

8. I-BenzenE

题目描述 小苯拿到了两个长度为 的数组 和 。
小红想让小苯基于这两个数组生成一个新数组 ，需要满足：
对于 ， 或者 ；
。
你能帮帮小苯吗？

【名词解释】
：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示数组长度。
第二行输入 个整数 。
第三行输入 个整数 。

除此之外，保证单个测试文件的 之和不超过 。

输出描述

对于每一组测试数据，新起一行。如果不存在满足条件的数组，直接输出 ；否则，直接输出 个整数，表示你所构造的数组。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

解题思路

一、问题转化

设原数组的异或和为：

如果将第 i 个元素 ai 替换为 bi，则新的异或和为：

定义每个位置的「变化量」：

此时，替换第 (i) 个位置对异或和的净影响就是 (c_i)。

若我们选择若干个位置进行替换（下标集合为 (S)），则最终异或和为：

要求最终异或和为 (0)，即：

等价于：

问题转化为：
从数组 c1 , c2,...., cn 中选出一个子集，使其异或和 恰好等于 (X)，并输出对应的替换方案。

二、线性基与方案构造

由于 n <= 10^5 ，枚举子集不可行。
我们使用 线性基 来判断可行性，并构造具体方案。

1. 简化线性基（快速判可行）

先构建普通线性基（仅存数值，不记录组成信息）：

  • 遍历 ci，插入线性基
  • 若最终 X 不能被基表示 → 无解
  • 否则存在解，且我们只需要利用线性基中的 最多 30 个基向量

2. 带组成信息的线性基（构造方案）

在第二步，我们只关心第一步得到的 基向量（不超过 30 个），并记录每个基向量是由哪些原始 ci 异或组合 而来的。

3. 回溯替换方案

当我们判断 (X) 可被表示时，从高位到低位扫描：

  • 若当前基向量需要选入，则将它的 mask 异或 进总集合 ans
  • 最后 ans 中为 1 的位，即对应需要替换的下标 这样我们就能得到一组 具体的替换位置集合 (S)。

PS

非常好理解线性基的一道题，我喜欢这道题

AC 代码

bool check(int x) {
	vector<int>base(33,0);
	vector<int>st;
	for(int i=1;i<=n;i++){
		int val=c[i];
		for(int j=31;j>=0;j--){
			if((val>>j)&1){
				if(!base[j]){
					base[j]=val;
					st.push_back(i);
					break;
				}
				val^=base[j];
			}
		}
	}
	vector<int>sbase(33,0);
	vector<int>mask(33,0);
	int sz=st.size();
	for(int k=0;k<sz;k++){
		int idx=st[k];
		int val=c[idx];
		int msk=1ll<<k;
		for(int j=31;j>=0;j--){
			if((val>>j)&1){
				if(!sbase[j]){
					sbase[j]=val;
					mask[j]=msk;
					break;
				}
				val^=sbase[j];
				msk^=mask[j];
			}
		}
	}
	int ans=0;
	for(int j=31;j>=0;j--){
		if(x>>j&1){
			if(sbase[j]){
				x^=sbase[j];
				ans^=mask[j];
			}else{
				return false;
			}
		}
	}
	vector<int>res;
	for(int k=0;k<sz;k++){
		if(ans>>k&1){
			int idx=st[k];
			a[idx]=b[idx];
		}
	}
	return true;
}

9. D-系ぎて

题目描述

小红正在一块  行  列的电路板上修复信号。电路板的每个格点上可能标记着数字 、 或 。其中，标记为  的格点恰好有两个，标记为  的格点也恰好有两个，其余格点均为 。

小红需要规划两条路径，分别连接两个  信号点和两个  信号点。
一条合法的路径定义为：
 路径由一系列相邻的格子组成（上、下、左、右）。
 两条路径不能经过同一个格子。
 每条路径不能经过不属于该路径的信号点（例如，连接  的路径不能经过任何标记为  的格点）。
 路径可以经过标记为  的格点，每个  格点最多只能被一条路径使用一次。

请你帮小红判断是否存在这样的两条路径。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示网格的行数和列数。
接下来 行，每行输入一个长度为 的字符串，由字符 、、 组成，表示电路板的每个格点上的标记。保证 和 的数量恰好为 。

除此之外，保证单个测试文件的 之和不超过 。

输出描述

对于每组测试数据，新起一行输出  或 ，表示是否存在满足要求的两条路径。

解题思路

特判一下
1.如果形成了2X2的特殊方格是无法找到的.
2.如果一个1或2点在四个顶点时，若两个相邻的位置被堵死，也无法找到
3.如果四个点都在边界上，且顺序相间，1212 或者 2121，也无法找到
其余情况都是YES

PS

一开始就想用特判，没考虑到第二种情况，一直没过

使用BFS也没有太成熟的思路，GGG

AC 代码

bool check(int x,int y){
	return (x==1||x==n||y==1||y==m);
}
bool safe(int x,int y,int a1,int b1,int a2,int b2){
	char p=g[x][y];
	if(p!='1'&&p!='2')return false;
	char q=(p=='1'?'2':'1');
	return g[a1][b1]==q&&g[a2][b2]==q;
}
void solve(){
	cin>>n>>m;
    v.clear();
	g.assign(n+1,vector<char>(m+1,'0'));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='1'||g[i][j]=='2'){
				v.push_back({i,j});
			}
		}
	}
	if(safe(1,1,1,2,2,1)){
		cout<<"NO\n";return ;
	}
	if(safe(1,m,1,m-1,2,m)){
		cout<<"NO\n";return ;
	}
	if(safe(n,m,n,m-1,n-1,m)){
		cout<<"NO\n";return ;
	}
	if(safe(n,1,n,2,n-1,1)){
		cout<<"NO\n";return ;
	}
	for(int i=1;i+1<=n;i++){
		for(int j=1;j+1<=m;j++){
			if(g[i][j]=='1'&&g[i][j+1]=='2'&&g[i+1][j+1]=='1'&&g[i+1][j]=='2'){
				cout<<"NO\n";
				return ;
			}
			if(g[i][j]=='2'&&g[i][j+1]=='1'&&g[i+1][j+1]=='2'&&g[i+1][j]=='1'){
				cout<<"NO\n";
				return ;
			}
		}
	}
	for(auto x:v){
		if(!check(x[0],x[1])){
			cout<<"YES\n";
			return ;
		}
	}
	vector<char>vv;
	for(int i=1;i<=m;i++){
		if(g[1][i]!='0'){
			vv.push_back(g[1][i]);
		}
	}
	for(int i=2;i<=n;i++){
		if(g[i][m]!='0'){
			vv.push_back(g[i][m]);
		}
	}
	for(int i=m-1;i>=1;i--){
		if(g[n][i]!='0'){
			vv.push_back(g[n][i]);
		}
	}
	for(int i=n-1;i>1;i--){
		if(g[i][1]!='0'){
			vv.push_back(g[i][1]);
		}
	}
	for(int i=1;i<vv.size();i++){
		if(vv[i]==vv[i-1]){
			cout<<"YES\n";
			return ;
		}
	}
	cout<<"NO\n";
	return ;
}

10. E-躯树の墓守

题目描述

小芳最近学会了最小生成树，现在她想要用几道题来检验自己。
请你生成一个包含 个点， 条边，对于每条边的边权 都有 > 且边权互不相同的无向简单连通图，它的最小生成树的边权之和恰好为 。点的编号为 到 。

【名词解释】
简单连通图：指不包含自环（连接节点自身的边）和重边（两个节点之间存在多条边）、且任意两个顶点之间都存在路径相连的图。
最小生成树：对于一张由 个节点构成的连通图，选出 > 条边将所有节点连通，且使得这 条边的权重之和最小，这样的结构称为最小生成树。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

第一行输入三个整数 。

除此之外，保证单个测试文件的 之和、 之和均不超过 。

输出描述

对于每组测试数据，如果不存在符合要求的图，直接输出 ；否则：
第一行输出 ；
此后 行，第 行输出三个整数 ，表示第 条边连接点 ，边权为 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

解题思路

贪心的选择 1..n-1 的边，如果权值和>K,则无法满足题目要求
否则，在这n-1条边中添加 增量，使得n-1条边***添加了 K-(n-1)(n)/2 的增量和
在连接第i条边（i->i+1）时，由于增量的存在所跳过的边数，一定要在前i个点形成的联通块中出现，否则会影响i->i+1的连接。这种可以使用跳过的边 具有(i-1)(i-2)/2 的数量限制，同时第i条选择边的增量要严格小于第i+1条边的增量选择( lim < x[i+1] )，保持n-1条生成树边的选择顺序严格保持递增（逆序递减）。
生成树边选择之后，把权值记录一下，然后把非生成树权值尽量小的往前分配到生成树中

PS

我也可以成为算法糕手吗？

AC 代码

void solve(){
	cin>>n>>m>>k;
	int num=n*(n-1)/2,d=k-num;
	if(k<num){
		cout<<"NO\n";
		return ;
	}
	vector<int>st(m+5,0);
	vector<int>x(n+5,0);
	vector<array<int,3>>e;
	for(int i=n-1;i>=1;i--){
		int lim=(i-1)*(i-2)/2;
		if(i<n-1)lim=min(lim,x[i+1]);
		if(i==n-1)lim=min(lim,m-(n-1));
		int add=min(d,lim);
		x[i]=add;
		d-=add;
		int val=x[i]+i;
		if(val>m){
			cout<<"NO\n";
			return ;
		}
		st[val]=1;
		e.push_back({i,i+1,val});
	}
	if(d>0){
		cout<<"NO\n";
		return ;
	}
	cout<<"YES\n";
	queue<int>q;
	for(int i=1;i<=m;i++){
		if(!st[i])q.push(i);
	}
	for(int i=3;i<=n;i++){
		for(int j=1;j<=i-2;j++){
			if(q.size()){
				e.push_back({j,i,q.front()});q.pop();
			}
			else goto part;
		}
	}
	part:
	for(auto xx:e){
		cout<<xx[0]<<" "<<xx[1]<<" "<<xx[2]<<"\n";
	}
}