BZOJ 4430 Guessing Camels赌骆驼
2024-10-01 02:01:34
【题意概述】
给出三个n的排列,求有多少个数对在三个排列中顺序相同
【题解】
考虑用补集转化的方法,答案为总对数-不满足的对数
一对数不满足条件,当且仅当这对数在两个排列中顺序相同,在另一个排列中的顺序不同。
统计两两之间不满足偏序条件的数对的个数,那么每对数都被统计了两次
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn=200010;
int n,a[4][maxn],b[maxn],t[maxn];
LL ans,tmp;
void read(int &k){
k=0; int f=1; char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();
k*=f;
}
void add(int x){for(;x<=n;x+=(x&-x)) t[x]++;}
int query(int x){int ret=0; for(;x>0;x-=(x&-x)) ret+=t[x]; return ret;}
int main(){
read(n);
for (int j=1;j<=3;j++)
for (int i=1;i<=n;i++) read(a[j][i]);
for (int i=1;i<3;i++)
for (int j=i+1;j<=3;j++){
memset(t,0,sizeof(t)); tmp=0;
for (int k=1;k<=n;k++) b[a[i][k]]=k;
for (int k=1;k<=n;k++) a[j][k]=b[a[j][k]];
for (int k=1;k<=n;k++) tmp+=query(a[j][k]),add(a[j][k]);
ans+=1LL*n*(n-1)/2-tmp;
}
return printf("%lld\n",1LL*n*(n-1)/2-ans/2),0;
}
最新文章
- Js ==和===的区别
- HTTP协议 请求篇
- linux环境下配置java WEB项目运行环境,jdk8+tomcat8+mysql5.7.11 新手向
- 微软发布独立Android模拟器 为开发者提供测试
- BZOJ3073 : [Pa2011]Journeys
- RESEACH PAPER
- HDU 4599 概率DP
- 设计模式之单例模式(Singleton Pattern)
- PHP漏洞全解(二)-命令注入攻击
- 自定义复选框 checkbox 样式
- 在word 中复选框划勾或叉的方法
- [Usaco2008 Dec]Patting Heads 轻拍牛头[筛法]
- POJ 3659 Cell Phone Network / HUST 1036 Cell Phone Network(最小支配集,树型动态规划,贪心)-动态规划做法
- javaWeb学习之tomcat服务器
- eclipse新建工作空间后的常用设置
- Django--cookie(登录用)
- COMS3200 The RUSH protocol
- Spring MVC 请求映射 (二)
- 异步时代-java的协程路在何方
- Confluence 6 ";Duplicate Key"; 相关问题解决