暑假集训Day12 G (定位计数)

题目大意是必须要找一对相等的数，然后这两对数的位置是要交叉的。

最朴素的暴力可以是枚举一对数，然后看这对数中间和前后有多少相同的对。

关于区间相同数的个数我们可以通过维护一个前缀和最后用O(1)的复杂度跑出来。

由于我们要求的四个数里面只有两个不同的数，所以优化一下只要枚举这两个数的位置就好了，剩下的可以用前缀和解决

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAX=3005;
 5 LL t,n,a[MAX],tot;
 6 LL cnt[MAX][MAX],cc[MAX];
 7 struct Node{
 8     LL b[MAX],cn,no;
 9 }stu[MAX];
10 bool cmp(Node x,Node y){
11     return x.cn<y.cn;
12 }
13 LL mul(LL x){return ((x==1||x==0)?1:x*mul(x-1));}
14 LL C(LL x,LL y){
15     return mul(x)/(mul(y)*mul(x-y));
16 }
17 int main(){
18     freopen ("g.in","r",stdin);
19     freopen ("g.out","w",stdout);
20     LL i,j,ans;
21     scanf("%d",&t);
22     while (t--){
23         scanf("%d",&n);
24         memset(cnt,0,sizeof(cnt));
25         tot=0;
26         for (i=1;i<=n;i++){
27             for (j=1;j<=n;j++) cnt[i][j]+=cnt[i-1][j];
28             scanf("%d",a+i),cnt[i][a[i]]++;
29             cc[a[i]]++;
30         }
31         for (i=1;i<=n;i++)
32             if (cc[i]>1){
33                 stu[++tot].cn=cc[i];
34                 stu[tot].no=i;
35             }
36         sort(stu+1,stu+tot+1,cmp);
37         i=1;ans=0;
38         while (stu[i].cn<4 && i<=tot) i++;
39         for (;i<=tot;i++) ans+=C(stu[i].cn,4);
40         ans=0;//cout<<i<<endl;
41         for (i=1;i<n;i++)
42             for (j=i+1;j<=n;j++){
43                 ans+=(cnt[n][a[i]]-cnt[j][a[i]])*cnt[i-1][a[j]];
44                 //cout<<i<<' '<<j<<(cnt[n][a[i]]-cnt[j][a[i]])*cnt[i-1][a[j]]<<endl;
45             }
46         printf("%lld
",ans);
47     }
48     return 0;
49 }

未来是什么样，未来会发生什么，谁也不知道。但是我知道，起码从今天开始努力，肯定比从明天开始努力，要快一天实现梦想。千里之行，始于足下！ ——《那年那兔那些事儿》