注意：这是第十六届蓝桥杯省赛模拟题，不是正式考题

目录

题目：

题目描述：

题目链接：

思路：

暴力拿部分分：

核心思路：

思路详解：

unordered_map:

代码：

暴力代码60分：

定义数组计数满分代码：

unordered_map计数满分代码：

---

题目：

题目描述：

题目链接：

不等三元组【省模拟赛】

思路：

暴力拿部分分：

实际在考场上，如果有的题目看起来暴力模拟很简单会写的话，还是先把暴力的代码写出来提交上去好歹拿点部分分再思考怎么优化。(这也算是蓝桥杯考场上的拿分技巧，考试的时候太紧张还追求最优解的话很容易出问题)。这题就先按题意暴力三个for循环模拟，按照蓝桥官网的测试点能过60%，剩下40%超时，其实已经很不错了，毕竟这题暴力不怎么需要思考

核心思路：

计数+组合数学原理

思路详解：

由于暴力会超时，所以我们要进行优化。实际上这题是一道数学题，统计所有数出现的次数,因为三元数组所有数不相等,所以必然满足有一个数是中间大小的数。即存在一个数小于它,一个数大于它,让每个数都当一遍中间这个数,然后再利用组合数学的原理来计算满足条件的三元组数量，最后求和的就是答案。简单的计数可以就定义一个数组，也可以用unordered_map计数，可以当作补充知识了解一下

unordered_map:

unordered_map基于哈希表实现,查找,插入和删除操作平均时间复杂度为O(1),适合用于统计元素出现次数

unordered_map<int,int> cnt;   定义了一个无序映射cnt,用于记录数列中每个数出现的次数,键是数列中的数,值是该数出现的次数

代码：

暴力代码60分：

#include<bits/stdc++.h> //三重for循环暴力,能过60%的测试点,剩下测试点超时 
using namespace std;

const int N=1e5+10;

int n;
int a[N];
int ans;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n-2;i++)
	{
		for(int j=i+1;j<=n-1;j++)
		{
			for(int k=j+1;k<=n;k++)
			{
				if(a[i]!=a[j]&&a[i]!=a[k]&&a[j]!=a[k])
				{
					ans++;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

定义数组计数满分代码：

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

typedef long long ll;

const int N=1e5+10;

ll cnt[N];  //定义cnt数组来记录每个数出现的次数,cnt[2025]=3表示2025出现了三次 
ll n;
ll ans;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		ll num;
		cin>>num;
		cnt[num]++; ////每读入一个数num,将其在cnt中的计数加1,从而统计出每个数在数列中出现的次数
	}
	ll cnt1=0;  //cnt1表示当前遍历到的数之前所有数的总个数(包括当前数),初始化为0 
	ll cnt2=n;  //cnt2表示当前遍历到的数之后所有数的总个数,初始化为数列长度n
	ll cntmid;  //cntmid用于临时存储当前遍历数的出现次数
	for(int num=0;num<=1e5;num++)
	{
		if(cnt[num]==0) //如果当前数出现次数为0就跳过本次循环 
		{
			continue;
		}
		cntmid=cnt[num]; //获取当前数num在数列中出现的次数
		cnt2-=cntmid;  //更新cnt2,减去当前数num出现的次数,因为已经将当前数考虑进来,它不再属于
		               //后面的数的范畴 
		ans+=cnt1*cntmid*cnt2; //这是核心计算部分:其原理是把当前数num当作不等三元组中的中间数,
		                       //cnt1是比当前数小(或在当前数之前已经统计过)的数的总个数,cntmid是
							   //当前数的出现次数,cnt2是比当前数大(或在当前数后)的数的总个数,根据
							   //排列组合原理,以当前数为中间数能组成的不等三元组数量就是cnt1*
							   //cntmid*cnt2,将其累加到ans中
		cnt1+=cntmid; //更新cnt1,将当前数num的出现次数累加到已统计过的数的总个数中
	}
	cout<<ans<<endl;
	return 0;
}

unordered_map计数满分代码：

//一道数学题,统计所有数出现的次数,因为三元数组所有数不相等,所以必然满足有一个数是中间大小的数
//即存在一个数小于它,一个数大于它,让每个数都当一遍中间这个数,求和就是答案
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

unordered_map<int,int> cnt;  //定义了一个无序映射cnt,用于记录数列中每个数出现的次数,键是数列中的 
                             //数,值是该数出现的次数
//unordered_map基于哈希表实现,查找,插入和删除操作平均时间复杂度为O(1),适合用于统计元素出现次数 

int main()
{
	ll n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		ll num;
		cin>>num;
		cnt[num]++; //每读入一个数num,将其在cnt中的计数加1,从而统计出每个数在数列中出现的次数 
	}
	ll cnt1=0;  //cnt1表示当前遍历到的数之前所有数的总个数(包括当前数),初始化为0 
	ll cnt2=n;  //cnt2表示当前遍历到的数之后所有数的总个数,初始化为数列长度n 
	ll cntmid;  //cntmid用于临时存储当前遍历数的出现次数 
    ll ans=0;   //ans用于存储不等三元组的数量,初始化为0 
    for(int num=0;num<=1e5;num++)
    {
        if(cnt.find(num)==cnt.end()) //检查当前数num是否在数列中出现过,如果cnt中不存在这个数(即 
		{                            //find操作未找到对应的键),则跳过本次循环 
			continue;
	    }    
        cntmid=cnt[num];  //获取当前数num在数列中出现的次数 
        cnt2-=cntmid;     //更新cnt2,减去当前数num出现的次数,因为已经将当前数考虑进来,它不再属于
		                  //后面的数的范畴 
        ans+=cnt1*cntmid*cnt2; //这是核心计算部分:其原理是把当前数num当作不等三元组中的中间数,
		                       //cnt1是比当前数小(或在当前数之前已经统计过)的数的总个数,cntmid是
							   //当前数的出现次数,cnt2是比当前数大(或在当前数后)的数的总个数,根据
							   //排列组合原理,以当前数为中间数能组成的不等三元组数量就是cnt1*
							   //cntmid*cnt2,将其累加到ans中   
        cnt1+=cntmid;  //更新cnt1,将当前数num的出现次数累加到已统计过的数的总个数中 
    }
    cout<<ans<<endl;;
    return 0;
}