E1. Close Tuples (easy version)

矫情吗；* 2021-07-16 22:03 264阅读 0赞

[题目][Link 1]

原谅兄弟我只A了easy…所以就写个easy的题解吧…

思路：用一个map记录各个值的次数，然后如果某数字数量>=3则可以构成n\*(n-1)*(n-2)个相同的3个数组成的元组，如果某数字(a)数量>=2则可以构成n*(n-1)/2\*(a-1的数量+a-2的数量+a+1的数量+a+2的数量)个两个数字为a，其余一个为a+1或a-1或a+2或a-2的元组,如果某数字a的数量>=1则可以构成a的数量*a-1的数量*a+1的数量三个数字不同（a-1,a,a+1）的元组。对了，还要注意下开long long，因为两个2e5相乘会爆int,我因此还wa了一发。

Code:

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<bitset>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int lst[Max];
    int Mod = 1e9 + 7;
    
    
    int main()
    { 
    	FAST;
    	int t;cin >> t;
    	while (t--)
    	{ 
    		ll n;cin >> n;
    		map<ll, ll> ma;
    		for (int i = 1;i <= n;i++)
    		{ 
    			int g;cin >> g;
    			ma[g]++;
    		}
    		ll sum = 0;
    		for (auto i = ma.begin();i != ma.end();i++)
    		{ 
    			if (i->second >= 3)
    			{ 
    				ll p = i->second;
    				sum += (p * (p - 1) * (p - 2) / 6);
    			}
    			ll p = i->first;
    			sum += (ma[p - 1] * ma[p] * ma[p + 1]);
    			if (i->second >= 2)
    			{ 
    				sum += ((ma[p] * (ma[p] - 1) / 2) * (ma[p - 1] + ma[p + 1]+ma[p+2]+ma[p-2]));
    			}
    			if (ma[p - 1] == 0)ma.erase(ma.find(p - 1));
    			if (ma[p + 1] == 0)ma.erase(ma.find(p + 1));
    			if (ma[p + 2] == 0)ma.erase(ma.find(p + 2));
    			if (ma[p -2] == 0)ma.erase(ma.find(p -2));
    		}
    		cout << sum << endl;
    	}
    }

[Link 1]: https://codeforces.ml/contest/1462/problem/E1