暑假集训Day12 G (定位计数)
2021/7/27 6:06:22
本文主要是介绍暑假集训Day12 G (定位计数),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接在这里:Problem - G - Codeforces
题目大意是必须要找一对相等的数,然后这两对数的位置是要交叉的。
最朴素的暴力可以是枚举一对数,然后看这对数中间和前后有多少相同的对。
关于区间相同数的个数我们可以通过维护一个前缀和最后用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\n",ans); 47 } 48 return 0; 49 }
这篇关于暑假集训Day12 G (定位计数)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)