[ABC429]C - Odd One Subsequence题解

题目摘要：给定长度为N的整数序列A，找出所有满足条件的三元组(i,j,k)，其中1≤i<j<k≤N且Ai,Aj,Ak中恰好有两个不同的值。即有两个元素相等，另一个不同。约束条件为3≤N≤2×10^5，1≤Ai≤N。输入为N和序列A，输出满足条件的三元组数量。示例1输入N=5，A=[3,2,5,2,2]，输出6个满足条件的三元组。示例2输入N=3，A=[1,1,1]，输出0。解法思路是

bz02_2023f2

905人浏览 · 2025-10-25 21:46:08

bz02_2023f2 · 2025-10-25 21:46:08 发布

Time Limit: 2 sec / Memory Limit: 1024 MiB
时间限制：2 秒 / 内存限制：1024MiB

Score : 300 points 分数： 300 分

Problem Statement 题目描述

You are given an integer sequence of length N, A=(A1,A2,…,AN).
给定一个长度为 N ， A=(A1,A2,…,AN) 的整数序列。
Find the number of triples of integers (i,j,k) satisfying 1≤i<j<k≤N that satisfy the following condition:
找出满足以下条件的整数三元组 (i,j,k) 的数量：

Exactly two distinct values are contained in Ai,Aj,Ak. That is, two of Ai,Aj,Ak are equal, and the remaining one is different.
Ai,Aj,Ak 中恰好包含两个不同的值。也就是说， Ai,Aj,Ak 中的两个值相等，剩下的一个值不同。

Constraints 约束条件

3≤N≤2×105
1≤Ai≤N
All input values are integers.
所有输入值都是整数。

Input 输入

The input is given from Standard Input in the following format:
标准输入中给出的输入格式如下：

N
A1 A2 … AN

Output 输出

Print the number of triples of integers that satisfy the condition.
打印满足条件的整数三元组的数量。

Sample Input 1 示例输入 1 复制

Copy 复制

5
3 2 5 2 2

Sample Output 1 样本输出 1 复制

Copy 复制

For example, (i,j,k)=(1,2,4) satisfies the condition because exactly two distinct values, 2 and 3, are contained in A1=3, A2=2, and A4=2.
例如， (i,j,k)=(1,2,4) 满足条件，因为恰好有两个不同的值， 2 和 3 ，包含在 A1=3 、 A2=2 和 A4=2 中。
Including this, the six triples (i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) satisfy the condition.
包括这个，共有六个三元组 (i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) 满足条件。
Therefore, print 6.
因此，输出 6 。

Sample Input 2 示例输入 2 复制

Copy 复制

3
1 1 1

Sample Output 2 样例输出 2 复制

Copy 复制

There may be no triples that satisfy the condition.
可能没有三元组满足条件。

思路

直接统计即可。

代码见下

#include<bits/stdc++.h> 
using namespace std;
long long n,a[200005],b[200005],op=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(i==1||a[i]!=a[i-1]){
            b[++b[0]]=1;
        }
        else{
            b[b[0]]++;
        }
    }
    for(int i=1;i<=b[0];i++){
        op=op+b[i]*(b[i]-1)*(n-b[i])/2;
    }
    cout<<op<<endl;
	return 0; 	
}