第17届蓝桥杯省赛C++研究生组其他题目

第17届蓝桥杯省赛C++研究生组真题个人解析—C题2026的出现次数
第17届蓝桥杯省赛C++研究生组真题个人解析—D题评测漏洞
第17届蓝桥杯省赛C++研究生组真题个人解析—F题基态坍缩
第17届蓝桥杯省赛C++研究生组真题个人解析—G题综合应变指标

一、题目描述

1.1题目大意

判题机又卡住了！”小蓝眉头紧锁，盯着屏幕上的评测错误日志。

经过深入排查，他发现评测系统的校验逻辑存在一个隐蔽的漏洞：当系统先后读入两个参数x和y时，如果这两个数字的组合满足特定的算术性质，就会导致内存溢出，进而触发异常中止。

具体来说，若先后出现的两个参数ai和aj（其中i<j）满足以下等式，系统就会崩溃：
$$(ai+aj{)}^2=ai+aj$$

为了修复这个漏洞，小蓝导出了当前崩溃用例中的全部n个测试参数，按读入顺序排列为a1,a2,…,an。现在，他需要你帮忙统计，这串参数中究竟存在多少对下标组合(i,j)，满足1≤i<j≤n且会触发上述异常。

1.2输入格式

第一行包含一个整数n，表示测试参数的总数。

第二行包含n个整数a1,a2,…,an，表示按顺序读入的参数值。

1.3输出格式

输出一个整数，表示能够触发异常的参数对数量。

1.4示例

输入：
4
-1 0 1 2
输出：
3

1.5输入数据规模

对于40%的评测用例，2≤n≤1000。

对于所有的评测用例，2≤n≤10的5次方，−10的9次方≤ai≤10的9次方。

要求时间限制在1s，内存为256MB。

二、题目分析及解题代码

2.1题目分析

对题目初步分析，如果（a+b）的平方等于（a+b），那么（a+b）一定等于0或1，题目中求存在多少个下标组合(i,j)，那么很自然地想到进行两层循环，最外层i从1到n，内层j从i+1到n，查找(ai+aj)=0或1的个数。

但是这样程序复杂度为O(n*n)，时间限制在1s的条件下，n只能是1000这个数量级，那么只能通过40%的测试数据。

进一步思考，

1. 对于ai来说，查找数组中ai+x=0或1的数量，其实就是对-ai和1-ai进行计数，例如ai=2，那么数组中有多少个-2和多少个-1，就有多少个满足条件的组合数(i,j)；
2. 那么可以遍历一遍数组，对每个元素ai，进行操作num[-ai]++，num[1-ai]++，由于ai的取值范围很大，因此不能使用数组，可以使用map类型；
3. 计数完毕后，再进行一次循环，对每个元素ai，累加（num[-ai]+num[1-ai]）。但是有两个细节需要注意；
4. 细节一，对于ai=0时，虽然0+0=0满足要求，但是不满足i≠j的要求，所以最后要减去num[0]；
5. 细节二，累加过程中存在重复计数，例如对于ai=2，累加（num[-2]+num[-1]），而对于ai=-2，累加（num[2]+num[3]），也就是说对于（-2，2）重复了两次，因此最后结果要除以2。

2.2解题代码

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

const int INF=1e5+10;
int a[INF];
int n;
map<int,int> mp;
LL res;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n; i++) mp[a[i]]++;
	int t;
	for(int i=1; i<=n; i++)
	{
		t=a[i];
		res+=mp[1-t]+mp[-t];
	}
	res-=mp[0];
	res/=2;
	cout<<res<<'\n';
	return 0;
}

2.3代码说明

代码使用了map容器来存储计数，插入、删除、查找的时间复杂度为O(logn)，整体复杂度约为O(nlogn)，在输入数据为10的5次方规模时满足1s的时间限制。

三、洛谷平台提交验证

3.1洛谷链接

该题目在洛谷平台的链接地址为：https://www.luogu.com.cn/problem/P16249
题目名称为：P16249 [蓝桥杯 2026 省研究生组] 评测漏洞

3.2提交结果

提交解题代码结果如下图，测试用例全部通过：