上海计算机学会2022年11月月赛C++乙组T1数对统计
发布时间
阅读量：
阅读量
数对统计
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
给定 n 个数字 a1,a2,…,an，从 1 到 n 中挑出 i 与 j 并要求 i<j，将 ai 与 aj 组成一个有序的序对 (ai,aj)。
请统计，能从序列中挑选出多少种互不相等的数对？两个数对 (x,y) 与 (p,q) 称之为不相等，是指 𝑥≠𝑝 或 𝑦≠𝑞。
输入格式
- 第一行，单个整数 n
- 第二行，𝑛n 个整数 a1,a2,…,an
输出格式
单个整数：表示互不相等的数对数量。
数据范围
- 对于 30% 的数据，n≤10
- 对于 60% 的数据，n≤1000
- 对于 100% 的数据，1≤n≤100000
- ≤ai≤n
样例数据
输入:
4
3 1 3 2
输出:
5
说明:
(3,1)
(3,3)
(3,2)
(1,3)
(1,2)
解析：
详见代码：
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
bool b[100005];//是否出现过
int c[100005];//c[i]表示从第i个到第n个数中有多少个数不重复
bool d[100005];//d[i]表示之前i这个数字是否算过了
long long ans=0;
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=n;i>=1;i--){//倒序计算c[i]
if (b[a[i]]==0){//a[i]在i+1到n中未出现过
b[a[i]]=1;//现在出现了
c[i]=c[i+1]+1;//c[i]比c[i+1]多了一个
}else{//出现过了
c[i]=c[i+1];//c[i]同c[i+1]一样多
}
}
for(int i=1;i<=n;i++){//正序
if (d[a[i]]==0){//如果a[i]在1到i-1中没出现过
ans+=c[i+1];//则它可以和后边不重复的c[i+1]个数组成数对
d[a[i]]=1;//标记a[i]出现过了
}
}
cout<<ans;//输出答案
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~