2026 牛客寒假集训营-2

1. A-比赛安排

2. B-NCPC

题目描述

欢迎大家参加NCPC!

Bingbong 正在负责 NCPC (Nowcoder Collegiate Pizza Contest, NCPC) - 牛客大学生披萨大赛的准备工作，现在有 个参赛选手，编号为 ，编号为 的选手制作的 Pizza 的美味值为 。对于每轮比赛，Bingbong 会选取当前场上任意两个未被淘汰的选手  进行对决，具体规则如下：

若 ，则制作 Pizza 的美味值较低的选手淘汰，否则两位选手都淘汰。直到只剩下一名选手时，该选手获胜，若没有选手剩下，则全部淘汰。

现在你需要帮助 Bingbong 判断，是否存在一种对决安排，使得选手 最终成为唯一剩下的选手（即获得最终胜利）。若存在，输出 ；否则输出 。

输入描述

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

第一行输入一个整数 ，表示参赛选手的数量。
第二行输入 个整数 ，表示选手制作的 Pizza 对应的美味值。

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

输出描述

对于每一组测试数据，新起一行输出一个长度为 、仅由字符 与 构成的字符串 ，其中，第 个字符 为 ，当且仅当选手 最终成为唯一剩下的选手（即获得最终胜利）。

解题思路

设美味值最大为MAXX。
如果美味值为MAXX的选手有偶数个，则只能互相抵消，所有MAXX的选手都无法留下，此后所有人都可以被MAXX的选手除掉，后续小于MAXX的选手都有机会留下。 如果美味值为MAXX的选手有奇数个，则无法互相抵消，所有MAXX的选手都可能被留下，后续小于MAXX的选手都处理不了最后留下的MAXX选手，以至于都没有机会留下。

AC 代码

void solve(){
    inpu();
    sort(v.begin()+1,v.end(),greater<>());
    map<int,int>mp;
    vector<int>ans(n+1,0);
    for(int i=1;i<=n;i++)mp[v[i][0]]++;
    bool flag=0;
    for(int i=1;i<=n;i++){
    	if(v[i][0]==v[i-1][0]){
    		ans[v[i][1]]=ans[v[i-1][1]];
    		continue;
    	}
        if(v[i][0]==maxx){
        	if(mp[maxx]&1)ans[v[i][1]]=1,flag=1;
        }
        else{
    		if(!flag)ans[v[i][1]]=1;
        }
    }
    for(int i=1;i<=n;i++){
    	cout<<ans[i];
    }
    cout<<"\n";
}

3. I-01回文

题目描述 Bingbong 拥有一个大小为 的 01 矩阵 ，矩阵的行从上至下依次为第 行到第 行，列从左至右依次为第 列到第 列，矩阵中每个元素 的取值仅为 或 。

对于矩阵中的每一个位置 ，请你判断并回答以下问题：
从位置 出发，是否存在一个非起点的位置 ，满足从 到 的某一条简单路径上的元素按路径顺序拼接形成的字符串为回文串。
若存在满足条件的位置和路径，输出 ，否则输出 。每次回答相互独立，互不影响。

每次移动，可以从当前位置 到达与其相邻（上下左右）的一个位置 ，即 。
【名词解释】
回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。 简单路径：矩阵上任意两个坐标点之间的路径，且不经过重复的坐标点。更具体地，由矩阵中若干个不重复的坐标点构成的序列 构成，其中 与 均是相邻的。

输入描述

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

第一行两个整数 ，表示矩阵大小。
此后 行，第 行输入一个长度为 ，仅由字符 和 构成的字符串 ，表示矩阵第 行的元素。

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

输出描述

对于每一组测试数据，一共 行，每行输出一个长度为 ，仅由字符 和 构成的字符串，表示矩阵中每个位置是否可以满足题意。其中，第 个字符为 当且仅当位置 可以满足题意，否则为 。

解题思路

由于矩阵中只存在01，只要矩阵中存在两个相同数字，便可以做到题意所求。否则无法做到。

PS：

比较呆比较呆，赛时将矩阵中所有字符相同且相邻的位置通过并查集合并成同一个连通块，并记录每个连通块边界上与不同字符相邻的边数；对于每个位置(i,j)，如果它存在相邻的同字符位置（即路径长度为2的回文如00或11），则直接标记为可行；否则，检查其相邻的异字符连通块，通过计算“该连通块边界上不与当前位置相邻的异字符边数+1”来判断是否能形成更长的回文路径——如果这个值≥2，说明存在另一条异字符边可以与当前位置形成类似“0-1-0”或“1-0-1”结构的回文路径，因此标记为可行，否则不可行。
完全没考虑更简单的思路，需要多思考

AC 代码

void solve(){
    inpu();
    int f1=0,f2=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='1')f1++;
            else f2++;
        }
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		if(g[i][j]=='1'&&f1>=2)cout<<'Y';
    		else if(g[i][j]=='0'&&f2>=2)cout<<'Y';
            else cout<<'N';
    	}
    	cout<<"\n";
    }
}

4. F-x?y?n!

题目描述

Bingbong 给定一个整数 ，你需要找到两个整数 满足如下条件：
在满足 、 且 的基础上，使得 最小。
可以证明，在上述的条件下，始终存在满足条件的 。

【名词解释】
：指两个或多个整数共有约数中最大的一个。例如， 和 的公约数有 ，其中最大的约数是 ，因此记作 。特别地，单个整数的 定义为其自身。
：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。

输入描述

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

输出描述

对于每一组测试数据，新起一行输出两个整数 ，表示你所找到的两个整数。

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

解题思路

因为gcd(x,y)==n,则x和y都是n的不同倍数。
因为异或的性质 |x-y|<=x^y<=|x+y|，即异或的最小可能值为n 当在二进制上除了涉及到n的位置都要异或抵消掉，最后只剩下n 于是我们构建了 x= n * 2 ^ 31 ,y= n * 2 ^ 31 + n，在高位是相同的，完全抵消，低位保留n的值，最后异或的值为n，同时保证最大公约数为n.

PS：

很好观察出，n是理论最小值，蒙了一个思路是 n * k 和 n * ( k + 1 ) , WA了，又尝试了一下 n * 2 ^ k 和 n * (2 ^ k + 1) , AC了

AC 代码

void solve(){
    inpu();
    int num=1ll<<31;
    int l=n*num;
    int r=l+n;
    cout<<l<<" "<<r<<"\n";
}

5. H-权值计算

题目描述

如上是一段计算数组权值的伪代码，通过调用 计算一个长度为 的数组 的权值，现在 Bingbong 有一个长度为 的数组 ，请你帮助他求出所有非空子数组的权值之和。
【名词解释】
子数组：从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。

输入描述

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

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

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

输出描述

对于每一组测试数据，新起一行输出一个整数，表示所有子数组的权值之和。

解题思路

在某一个子数组中，一个数字只有第一次出现的时候才会产生贡献，产生的贡献一直持续到最后一个位置 记录第i个位置前面最近的相同数字的位置prei,子数组不包含prei以及之前的位置时，才能产生贡献。 对于第i个位置为左端点，右端点越长，当前位置的贡献就越多，计算出为 ( n - i + 1 ) * ( n - i + 2 ) / 2

于是，对每一个位置i，左边的长度是有多少个产生贡献的左端点，右边的长度相关着左端点可以产生的贡献多少，相乘一下得到答案。

PS：

一个标准的求贡献的题目

AC 代码

void solve(){
    inpu();
    for(int i=1;i<=n;i++){
    	int l=i-mp[a[i]];
    	int r=(n-i+1)*(n-i+2)/2;
    	ans+=1ll*l*r;
    	mp[a[i]]=i;
    }
    cout<<ans<<"\n";
}

6. E-01矩阵

题目描述

Bingbong 从哆啦A梦那里得知，一个仅由 和 组成的 阶矩阵 是好的，当且仅当满足以下所有条件：

记第 行的数字和为 ， 集合仅由 的整数组成，且每个数字仅出现一次。

记第 列的数字和为 ， 集合仅由 的整数组成，且每个数字仅出现一次。

该矩阵中 的连通块个数和 的连通块个数总和恰好为 个。
现在大雄给定一个整数 ，你需要帮助 Bingbong 画出该矩阵，保证在上述条件约束下始终存在符合条件的 阶矩阵。

【名词解释】
连通块：在网格中，若两个坐标间的曼哈顿距离为 则视为相邻。由数值相等的格子按该相邻关系划分的极大连通子集称为一个连通块。

输入描述

输入一个整数 ，表示矩阵的边长大小。

输出描述

一共 行，第 行输出一个长度为 、仅由字符 与 构成的字符串，表示矩阵的第 行。

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

解题思路

n=3：
000
011
010
n=4
0000
0111
0100
0101
打表感受规律，这道题规律很多，符合要求就行，赛时想到的是构造0的行列

AC 代码

void solve(){
    inpu(); 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int minn=min(i,j);
            cout<<(minn&1);
        }
        cout<<"\n";
    }
}

7. J-终于再见

题目描述

 在 2025 年的春天我们与大家相见，从那时起，小团体思念过去，憧憬未来，我们《还会再见吗？》
原来 2026 年时，2025 年的《那是我们的影子》已经是过去对未来的写照，期待下次再见! 
--- 以此纪念故人

有 个城市，编号为 到 ，城市之间通过 条无向道路连接，每条道路的边权为 ，对于一个城市的繁华度是该城市所连接的道路数量。
我们将每个城市的繁华度列出并去重后，从小到大排序得到 ，现在将所有繁华度为 的城市称作 级城市。
Bingbong 现在需要你帮助他回答对于任意编号为 的城市，从该城市出发，前往比该城市级别更高的城市的最短路径长度，或报告无法到达。
注意：此处 级城市为最高级城市。

输入描述

    第一行输入两个整数 ，表示城市个数和道路条数。
此后 行，第 行输入两个整数 ，表示第 条道路连接城市 和 。
保证数据不存在重边和自环。

输出描述

在一行上输出 个整数，其中第 个整数表示编号为 的城市通往更高级城市的最短路径长度，若无法到达，则输出 。

解题思路

高级别城市数量一般较少，以它们为源点做 BFS，可以一次性更新很多低级城市的距离。 而低级别城市数量可能很多，如果以它们为起点找高级城市，会重复搜索很多次，浪费计算。

简单比喻：
多个目标点（高级城市）到所有起点的最短距离，可以用一次多源 BFS 得到； 多个起点分别去找目标点，就需要多次 BFS，除非目标点数量极少（但这里高级别城市可能比低级别少很多，但不一定只有一个，所以反向做更划算）。

PS

我的代码需要慢慢写慢慢改

AC 代码

void bfs(queue<array<int,2>>q,int res){
	int cnt=num[res].size();
	while(q.size()){
		auto [cost,x]=q.front();q.pop();
		if(vis[x]==res)continue;
		vis[x]=res;
		for(int &v:V[x]){
			if(d[v]==res&&ans[v]==inf){
				ans[v]=min(ans[v],cost+1);
				cnt--;
			}
			q.push({cost+1,v});
		}
		if(cnt==0)break;
	}
}
void inpu(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
    	int u,v;cin>>u>>v;
    	V[v].push_back(u);
    	V[u].push_back(v);
    	d[v]++,d[u]++;
    	maxx=max({d[v],maxx,d[u]});
    }
    vis.assign(n+1,maxx);
    for(int i=1;i<=n;i++){
    	num[d[i]].push_back(i);
    	ans[i]=inf;
    }
    queue<array<int,2>>q; 
    for(int i=maxx;i>=0;i--){
    	if(i==maxx||i==0){
    		goto part;
    	}
        if(num[i].size()==0)continue;
    	bfs(q,i);
    	part:
    	for(auto &x:num[i]){
    		q.push({0,x});
    	}
    }
    
}
void solve(){
    inpu();
    for(int i=1;i<=n;i++){
    	if(ans[i]==inf){
    		cout<<-1<<" ";
    	}
    	else cout<<ans[i]<<" ";
    }
    cout<<"\n";
}

8. D-数字积木

题目描述

Bingbong 给定一棵包含 个节点的积木树，树的节点编号为 ，节点 的权值为 ，其中 由 的数字组成，且每个数字只出现一次。
定义树上一个连通子图的权值为：构成该连通子图的所有节点的权值中未出现过的最小非负整数。

现在，Bingbong 想让你帮忙计算树上所有连通子图的权值之和。由于答案可能很大，请将答案对 取模后输出。
【名词解释】
连通子图：满足是原图的一个子图，连通子图内的任意两个顶点之间都存在路径相连，且路径上的点也在连通子图内；单独的点也构成一个连通子图。

输入描述

第一行输入一个整数 ，表示树的结点个数。
第二行输入 个整数 ，保证每个整数恰好出现一次。
此后 行，第 行输入两个整数 ，表示第 条树边连接节点 和 。

输出描述

输出一个整数，表示树上所有连通子图的权值之和对 取模后的结果。

解题思路

理解题意可知，只有当子图中存在0值时mex值>0,才会对答案有贡献。

以至于我们以0值节点可以为根节点，这样我们的操作只在往下找子树这一个方向中进行。

暴力枚举是不行的，无法接受，要考虑每一个连通子图的贡献。

一个MEX值为k的连通子图必须包含权值0到k-1的所有节点，但不能包含权值k。通过动态维护一个包含当前已处理的最小权值节点的"骨架"，并计算包含整个骨架的连通子图方案数。每次将新权值i的节点加入骨架后，对应的方案数就是所有MEX ≥ i+1的子图个数。根据层叠求和原理，MEX值之和等于所有MEX ≥ 1、MEX ≥ 2、...、MEX ≥ n的方案数之和，因此看似只是简单累加方案数，实际上每个MEX值为k的子图都被恰好计数了k次，自然得到了正确的权值总和。

PS

有点难抽象的模型，也比较考验树状操作的理解

AC 代码

void dfs(int u,int fa){
    dp[u]=1;
    par[u]=fa;
    for(int v:V[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u]*=(dp[v]+1);
        dp[u]%=mod;
    }
    return;
}
int get(){
    if(cnt>0)return 0;
    return res;
}
void inpu(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]]=i;
    }
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        V[u].push_back(v);
        V[v].push_back(u);
    }
}
void solve(){
    inpu();
    root=pos[0];
    dfs(root,0);
    int temp=dp[root]%mod;
    cnt=0;
    ans=0;
    res=1;
    st[root]=1;
    if(temp==0)cnt++;
    else res=res*temp%mod;
    ans=(ans+get())%mod;
    for(int i=1;i<n;i++){
        int u=pos[i];
        while(!st[u]){
            st[u]=1;
            int temp=(dp[u]+1)%mod;
            if(temp==0)cnt--;
            else res=res*inv(temp)%mod;
            if(dp[u]==0)cnt++;
            else res=res*dp[u]%mod;
            u=par[u];
        }
        ans=(ans+get())%mod;
    }
    cout<<ans<<'\n';
}

9. C-炮火轰炸

题目描述

炮火轰炸

Bingbong 有一个无限大的网格图，第 行第 列的坐标为 ，现在给定 个炮火点，每个点的坐标为 ，当两个炮火点满足 并且 ，则认为两个炮火点连接在一起。这些炮火点可能连接出很多的炮火圈(即圈出一个封闭区域)，也有可能没有炮火圈。若一个询问点无法通过连续的上下左右移动到达无穷远处（移动过程中不能经过炮火点），则认为该点位于炮火圈中。
Bingbong 会询问 个坐标点 （保证不为炮火点），对于每个点你需要单独回答其是否位于任意一个炮火圈中。

输入描述

第一行输入两个整数 ，表示给定的炮火点个数和询问次数。
此后 行，第 行输入两个整数 ，表示第 个炮火点的坐标，保证每个炮火点坐标互不相同。
此后 行，第 行输入两个整数 ，表示第 次询问的坐标，保证不为炮火点。

输出描述

对于每一次询问，新起一行。若询问点位于任意一个炮火圈中，输出 ；否则输出 。

解题思路

创建一个虚拟点，和这个虚拟点连通意味着不在包围圈内

无限大的地图，无法枚举每一个坐标点，我们以每一个火炮点的8连通坐标点作为参考系，每一个8连通点往4个方向去寻找，如果没有被炮火点阻碍的话，就可以和虚拟点合并，如果被阻碍的话，就和阻碍的跑火点的前一个点合并，期待合并的点能找到一条出去的通路。

PS

体感难度比D题小

AC 代码

void solve(){
	cin>>n>>q;
	b.resize(n);
	qq.resize(q);
	vector<array<int,2>>b(n);
	for(int i=0;i<n;i++){
		cin>>b[i][0]>>b[i][1];
		c[b[i][1]].push_back(b[i][0]);
		r[b[i][0]].push_back(b[i][1]);
		st.insert({b[i][0],b[i][1]});
	}
	for(int i=0;i<q;i++){
		cin>>qq[i][0]>>qq[i][1];
	}
	for(auto &x:r)sort(x.begin(),x.end());
	for(auto &x:c)sort(x.begin(),x.end());
	for(auto &temp:b){
		auto [x,y]=temp;
		for(int i=0;i<8;i++){
			int sx=x+dx[i],sy=y+dy[i];
			if(sx>=0&&sy>=0&&st.find({sx,sy})==st.end()){
				if(!mp[{sx,sy}]){
					get(sx,sy);
					v.push_back({sx,sy});
				}
			}
		}
	}
	for(int i=0;i<qq.size();i++){
		auto &[x,y]=qq[i];
		get(x,y);
		v.push_back({x,y});
	}
	p.resize(idx+5);
	iota(p.begin(),p.end(),0);
	for(int i=0;i<v.size();i++){
		auto [x,y]=v[i];
		int u=get(x,y);
		auto it=upper_bound(c[y].begin(),c[y].end(),x);
		if(it==c[y].end()){
			merge(0,u);
		}
		else{
			int res=*it-1;
			merge(get(res,y),u);
		}
		it=lower_bound(c[y].begin(),c[y].end(),x);
		if(it==c[y].begin()){
			merge(0,u);
		}
		else{
			it--;
			int res=*it+1;
			merge(get(res,y),u);
		}
		it=upper_bound(r[x].begin(),r[x].end(),y);
		if(it==r[x].end()){
			merge(0,u);
		}
		else{
			int res=*it-1;
			merge(get(x,res),u);
		}
		it=lower_bound(r[x].begin(),r[x].end(),y);
		if(it==r[x].begin()){
			merge(0,u);
		}
		else{
			it--;
			int res=*it+1;
			merge(get(x,res),u);
		}
	}
	for(auto [x,y]:qq){
		int id=get(x,y);
		int fx=find(id),fy=find(0);
		if(fx==fy){
			cout<<"NO\n";
		}
		else{
			cout<<"YES\n";
		}
	}
}

10. G-宝藏拾取

题目描述

给定一个长度为 的宝藏数组 。Bingbong 从起点 出发，向索引增大的方向移动。对于经过的每个位置 ：
若是起点 ，则直接获得 ；
若 ，当且仅当当前持有的宝藏总和 时，可以获得 ；
每个位置的宝藏只能在其被经过时领取一次，且移动过程不可逆。
现在你需要对于任意的 ，回答以 为起点可以获得的最多宝藏数量，每次回答相互独立，互不影响。

输入描述

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

第一行输入一个整数 ，表示宝藏数组长度。
第二行输入 个整数 ，表示每个位置的宝藏数量。

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

输出描述

对于每一组测试数据，新起一行输出 个整数，分别表示以 为起点可获得的最大宝藏数量。

解题思路

最小的那个点是无法吞噬其他宝藏的，每一轮都发现当前没有发现的最小的宝藏 i，1到i-1的位置中比他小的已经找过了，比他大的都需要加上第i个宝藏的值,查询和添加的过程使用懒标记线段树来实现，线段树中维护一个区间中的最小宝藏值和下标，方便查询使用。

PS

题解说用Treap，我不会，我发现了懒标记线段树，爽写线段树，MLE怎么被卡空间了，array<ll,2>能过吗，还是卡住了，pair<ll,int>，小省一个int 就过啦

AC 代码

struct node{
	int l,r;
	long long lazy;
	pair<long long,int> mp;
}tr[N<<2];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ans[i]=0;
	}
	build(1,1,n);
	for(int i=1;i<=n;i++){
		pair<long long,int> p=query(1,1,n);
		ans[p.second]=p.first;
		add(1,p.second,p.second,2e16);
		if(p.second>1){
			add(1,1,p.second-1,a[p.second]);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
}