cf406E Hamming Triples (推公式)

考虑某两行a和b的dis

如果相同:$|a-b|$

如果不同:$n-|a-b|$

然后考虑三行的dis,不妨设a>=b>=c

那么有4种情况:

1.a,b,c 0/1的种类相同:$|a-b|+|a-c|+|b-c|=2a-2c$

2.a和b相同:$2n+2c-2b$

3.a和c相同:$2n$

4.b和c相同:$2n+2b-2a$

所以我们排序后枚举这个b,预处理出前缀和后缀的是0/1的最大值个数、最小值个数以及总共的个数,加一加乘一乘统计答案即可

注意如果记权值的时候用int,那要先减再加,防爆

 #include<bits/stdc++.h>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
const int maxn=1e5+,inf=1e9+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} struct Node{
int v;ll n;
Node(int a=,ll b=){v=a,n=b;}
}f[][maxn][],g[][maxn][],ans;
int N,M;
pa a[maxn]; inline void update(int v1,ll n1){
// printf("~%d %d\n",v1,n1);
if(!n1) return;
if(v1>ans.v) ans=Node(v1,n1);
else if(v1==ans.v) ans=Node(v1,n1+ans.n);
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),M=rd();
for(i=;i<=M;i++){
a[i].second=rd(),a[i].first=rd();
}sort(a+,a+M+);
f[][][].v=f[][][].v=g[][M+][].v=g[][M+][].v=inf;
for(i=;i<=M;i++){
int tp=a[i].second,x=a[i].first;
memcpy(f[!tp][i],f[!tp][i-],sizeof(f[][]));
if(x>f[tp][i-][].v) f[tp][i][]=Node(x,);
else if(x==f[tp][i-][].v) f[tp][i][]=Node(x,f[tp][i-][].n+);
else f[tp][i][]=f[tp][i-][]; if(x<f[tp][i-][].v) f[tp][i][]=Node(x,);
else if(x==f[tp][i-][].v) f[tp][i][]=Node(x,f[tp][i-][].n+);
else f[tp][i][]=f[tp][i-][]; f[tp][i][].n=f[tp][i-][].n+;
}
for(i=M;i;i--){
int tp=a[i].second,x=a[i].first;
memcpy(g[!tp][i],g[!tp][i+],sizeof(g[][]));
if(x>g[tp][i+][].v) g[tp][i][]=Node(x,);
else if(x==g[tp][i+][].v) g[tp][i][]=Node(x,g[tp][i+][].n+);
else g[tp][i][]=g[tp][i+][]; if(x<g[tp][i+][].v) g[tp][i][]=Node(x,);
else if(x==g[tp][i+][].v) g[tp][i][]=Node(x,g[tp][i+][].n+);
else g[tp][i][]=g[tp][i+][]; g[tp][i][].n=g[tp][i+][].n+;
} for(i=;i<=M-;i++){
int tp=a[i].second,x=a[i].first;
int v1=*g[tp][i+][].v-*f[tp][i-][].v;ll n1=g[tp][i+][].n*f[tp][i-][].n;
update(v1,n1); v1=*N-*x+*f[!tp][i-][].v,n1=f[!tp][i-][].n*g[tp][i+][].n;
update(v1,n1); v1=*N,n1=f[!tp][i-][].n*g[!tp][i+][].n;
update(v1,n1); v1=*N-*g[!tp][i+][].v+*x,n1=f[tp][i-][].n*g[!tp][i+][].n;
update(v1,n1);
}
printf("%I64d\n",ans.n);
return ;
}
上一篇:技术贴 本地代码与svn关联教程 svn upgrade问题解决


下一篇:[转]Java 常用排序算法/程序员必须掌握的 8大排序算法