• Makes And The Product CodeForces - 817B (思维+构造)

    B. Makes And The Product
    time limit per test
    2 seconds
    memory limit per test
    256 megabytes
    input
    standard input
    output
    standard output

    After returning from the army Makes received a gift — an array a consisting of n positive integer numbers. He hadn‘t been solving problems for a long time, so he became interested to answer a particular question: how many triples of indices (i,? j,? k) (i?<?j?<?k), such that ai·aj·akis minimum possible, are there in the array? Help him with it!

    Input

    The first line of input contains a positive integer number n (3?≤?n?≤?105) — the number of elements in array a. The second line contains npositive integer numbers ai (1?≤?ai?≤?109) — the elements of a given array.

    Output

    Print one number — the quantity of triples (i,? j,? k) such that i,? j and k are pairwise distinct and ai·aj·ak is minimum possible.

    Examples
    input
    Copy
    4
    1 1 1 1
    output
    Copy
    4
    input
    Copy
    5
    1 3 2 3 4
    output
    Copy
    2
    input
    Copy
    6
    1 3 3 1 3 2
    output
    Copy
    1
    Note

    In the first example Makes always chooses three ones out of four, and the number of ways to choose them is 4.

    In the second example a triple of numbers (1,?2,?3) is chosen (numbers, not indices). Since there are two ways to choose an element 3, then the answer is 2.

    In the third example a triple of numbers (1,?1,?2) is chosen, and there‘s only one way to choose indices.

     

     

    思路:

    分三种情况来逐一考虑,

    a[1]=a[2]=a[3]

    a[1],a[2]=a[3]

    a[1],a[2],a[3]

    根据题目要求的约数,只可能为这三种情况,

    分类处理下就OK

    细节见代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <vector>
    #define sz(a) int(a.size())
    #define all(a) a.begin(), a.end()
    #define rep(i,x,n) for(int i=x;i<n;i++)
    #define repd(i,x,n) for(int i=x;i<=n;i++)
    #define pii pair<int,int>
    #define pll pair<long long ,long long>
    #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    #define MS0(X) memset((X), 0, sizeof((X)))
    #define MSC0(X) memset((X), ‘\0‘, sizeof((X)))
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    #define eps 1e-6
    #define gg(x) getInt(&x)
    #define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
    using namespace std;
    typedef long long ll;
    ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
    ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
    ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
    inline void getInt(int* p);
    const int maxn=1000010;
    const int inf=0x3f3f3f3f;
    /*** TEMPLATE CODE * * STARTS HERE ***/
    map<ll,ll> m;
    ll n;
    ll a[maxn];
    ll getpc(ll m,ll n)//m 中 选 n 个
    {
        long long ans=1;
        for(long long k=1; k<=n; k++)
        {
            ans=(ans*(m-n+k))/k;
        }
        return ans;
    }
    int main()
    {
        gbtb;
        cin>>n;
        repd(i,1,n)
        {
            cin>>a[i];
            m[a[i]]=m[a[i]]+1;
        }
        sort(a+1,a+1+n);
        ll ans=0ll;
        set<ll> s;
        repd(i,1,3)
        {
            s.insert(a[i]);
        }
        // 1 1 1 1 1
        
        if(s.size()==1)
        {
            ll sum=m[a[1]];
            // c 4 3 
            ans=getpc(sum,3);
    
        }else if(s.size()==2)
        {
            // 1 1 2 2 2 2 3
            // 1 2 2 2 2 2
            ll f=m[a[1]];
            if(f==1)
            {
                ans=getpc(m[a[2]],2);
            }else
            {
                ans=m[a[3]];
            }
        }else 
        {
            // 1 2 3 3 3 3
            ans=m[a[3]];
        }
        // cout<
        cout<<ans<<endl;
        return 0;
    }
    
    inline void getInt(int* p) {
        char ch;
        do {
            ch = getchar();
        } while (ch ==   || ch == \n);
        if (ch == -) {
            *p = -(getchar() - 0);
            while ((ch = getchar()) >= 0 && ch <= 9) {
                *p = *p * 10 - ch + 0;
            }
        }
        else {
            *p = ch - 0;
            while ((ch = getchar()) >= 0 && ch <= 9) {
                *p = *p * 10 + ch - 0;
            }
        }
    }
    相关文章
    相关标签/搜索
    4887铁算王中王开奖结果小说 丁青县| 临西县| 修武县| 海口市| 湘西| 抚顺县| 滁州市| 新干县| 通河县| 景德镇市| 宁城县| 南开区| 驻马店市| 石景山区| 和平区| 奉化市| 惠来县| 靖宇县| 仙游县| 永嘉县| 太原市| 嘉鱼县| 遂平县| 浦城县| 大石桥市| 西城区| 玛多县| 新兴县| 阜城县| 潮州市| 敖汉旗| 延川县| 襄垣县| 光山县| 越西县| 佳木斯市| 济源市| http://fa.hz0j0r9vo.fun http://fa.hz0j1r9vo.fun http://fa.hz0j1r3vo.fun http://fa.hz0j2r5vo.fun http://fa.hz0j2r4vo.fun