本文使用 $\LaTeX$ 语法。若出现渲染失败或错误,请刷新页面并耐心等待刷新完成。

CF1462E2 Close Tuples (easy)

组合数

看不懂的题目传送门

同步于蒟蒻的博客

分析

  • 首先恶心人的是这是道纯英文的题的题意。借助奇怪的手段,我们可以明白这题面的意思是 :给定一个数组 $a$,取 $x \ ,y \ ,z\in a$ 满足 $x \ne y \ne z$,使得 $max(x \ ,y \ ,z) - min(x \ ,y\ ,z) \leqslant 2 $,问最多能找出多少组。
  • 拿到题首先想的是 dfs,写了一个 $O(n^2)$ 的code 。当然对于一个 $2^5$ 的数据不 TLE 才怪。还好数据不算太强,勉强搞过几个点。

    (随后听到机房大犇 @xspcz 在议论能不能用 map 存数据。但我不会啊……)

  • 最终在大犇们早都做完这题之后,我才感觉这题和组合数有些沾边(果然还是我太蒻了),于是想到了一个优雅的暴力算法。

    什么?你不知道组合数?巧了,我本来也不清楚,帮你度娘。

  • 本想一发 sort 之后从头开始求区间的组合,但是窝发现有问题,由于数据可能重复

    如数据 $1 \ 2 \ 3 \ 3 \ 4$,按上述方法就是答案计数器先加上 $1$ 和 $3$ 之间的组合数,求完之后再加上 $2$ ~ $4$ 之间的组合数,但是 $1$ ~ $3$ 之间的 $2 \ 3 \ 3$ 和 $2$ ~ $4$ 之间的 $2 \ 3 \ 3$ 重复了。于是卡了一节课 窝太菜了

  • 后经学长点拨,在排序后先取一个值 $a[i]$,再在 $(a[i],a[i+2])$ 范围内取两个值,便可以避免重复。(妙哉!)

    例如,求 $1$ ~ $3$ 时,取最小值 $1$,在 $(1,3]$ 区间内(即 $2 \ 3 \ 3$)任取两个值;

    接着求 $2$ ~ $4$ 时,取最小值 $2$,在 $(2,4]$ 区间内任取两个值。

      不难看出,以上情况无重复。 
    
  • 想清楚原理后就不难实现了

实现

贴核心代码:


   int t, /*anti-cheating*/ n;
    //本来想用桶,但后来想想没甚必要 
   int main(){ ios::sync_with_stdio(0);//加速cin、cout ,使其复杂度接近printf、scanf   
    cin>>n;  
    while(n--){  
        ll cnt=0;//!!!不开long long 见祖宗!!! 
        cin>>t;        
        for(int i=1;i<=t;i++)
            cin>>ght[i];        
        sort(ght+1, ght+t+1);//排序数据以便枚举 
            int r=1;
        for(int i=1;i<=t;i++){
            while(ght[r+1]<=2+ght[i] && r+1<=t) 
                r++;            
            if(r>=i+2)
                cnt+=(ll)(r-i-1)*(r-i);//!!被long long 卡死了一次 !!
            }
        cout<<cnt<<endl;
        }
    }

满分17,目测已过。。

Hard 版本就是将组合数的最大最小值之差改为了输入的数据,原理是一样的。

重申一遍!!不开龙龙爆零零!!!!


The Only Thing That's Changed is EVERYTHING .