题解：P11556 [ROIR 2016 Day 2] 超级跳棋

· · 题解

原本以为是组合数学，结果打了半天发现是模拟加前缀和优化。

题目链接

传送门

简略版：给定 n 个数，取三个数 a，b，c（a≤b≤c 且 c≤a\times k），问有几种取法（顺序不同视作两种）。

显然，对于每个数有四种类型取法。

  1. A A A
  2. A A B
  3. A B B
  4. A B C

首先，我们用 num 数组记录每种数的个数并用 a 数组头部记录对应数，就得到了这 l 种数对应的个数。

第一种：因为三个数相同，位置与最终结果无关，只要 num_i≥3，就将 ans 加一。

第二种：维护一个上界 sj（即 a_{sj}>k\times a_i），当 num_i≥2 时，计算对于当前数符合题意数的种数 amount_i=(sj-1)-(i+1)+1=sj-i-1。\ 并且在该种情况下共三种情况 A A B，A B A 和 B A A。\ 所以 ans 加上 3\times amount_i=3\times(sj-i-1)。

第三种：用 nd 数组代表第 1 到第 i 种数的个数 \geq2 的数量（前缀和），同上，该种情况下共三种情况 amount_i=3\times(nd_{sj-1}-nd_i)。\ 所以 ans 加上 3\times amount_i=3\times(nd_{sj-1}-nd_i)。

第四种：当第 i 种数后面符合题意的种数 \geq2（即 sj-i>2）时，A 的位置有三种情况，B 与 C 的取法共 A^{amount_i}_2 种（amount_i 同情况二）。\ 所以 ans 加上 3\times A^{amount_i}_2=3\times(sj-i-1)\times(sj-i-2)。

Code

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define f(n) for(int i=1;i<=n;i++)
#define ll long long
ll n,k,a[100001],sj,nd[100001];
ll num[100001],l;
ll ans;
int main()
{
    cin>>n>>k;
    f(n)cin>>a[i];
    sort(a+1,a+1+n);
    f(n)if(a[i]!=a[i-1])num[++l]=1,a[l]=a[i];
    else num[l]++;
    f(l)if(num[i]>=2)nd[i]=nd[i-1]+1;
    else nd[i]=nd[i-1];
    f(l)
    {
        if(num[i]>=3)ans++;//情况一
        while(a[sj]<=k*a[i]&&sj<=l)sj++;//维护上界
        if(num[i]>=2)ans+=3*(sj-i-1);//情况二
        ans+=3*(nd[sj-1]-nd[i]);//情况三
        if(sj-i>2)ans+=3*(sj-i-1)*(sj-i-2);//情况四
    }

    cout<<ans;
    return 0;
}

综上，不算排序复杂度为 O(n+l)。

ps：记得排序（其实不排序直接 O(n) 算 l 也可以）。\ ps2：不开 long long 见祖宗 QAQ。