POJ2926
先學會這個哈夫曼距離的處理才能做 cf 的G
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define maxn 100005
const int inf = (int)1e9;
double a[maxn][6];
double mi[1<<5+1],mx[1<<5+1];
int main(){
int n;
scanf("%d",&n);
for(int j=0;j<n;j++){
for(int k=0;k<5;k++){
scanf("%lf",&a[j][k]);
}
}
for(int j=0;j<(1<<5);j++){
mi[j] = inf;
mx[j] = -inf;
}
// double mx = 0,mi = inf;
double ans = -inf;
for(int j=0;j<n;j++){
//int cur = 0.
for(int k=0;k<(1<<5);k++){
double cur = 0;
for(int i=0;i<5;i++){
if(k&(1<<i)){
cur += a[j][i];
}else{
cur -= a[j][i];
}
}
//cout<<cur<<endl;
mx[k] = max(mx[k],cur);
mi[k] = min(mi[k],cur);
//ans = max(ans,mx[j]-mi[j]);
}
}
for(int j=0;j<(1<<5);j++){
//cout<<mx[j]<<" "<<mi[j]<<endl;
ans = max(ans,mx[j]-mi[j]);
}
printf("%0.2f\n",ans);
} 點一下 題目連結
CF G 用線段樹處理一下
就ok
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define inf (int)1e9
int a[4*maxn][33];
int b[4*maxn][6];
int n,m;
void build(int l,int r,int in){
if(l==r){
for(int j=0;j<(1<<m);j++){
int cur = 0;
for(int k=0;k<m;k++){
if(j&(1<<k)){
cur+=b[l][k];
}else cur-=b[l][k];
}
//cout<<cur<<endl;
a[in][j] = cur;
}
return ;
}
int mid = (l+r)/2;
build(l,mid,in*2);
build(mid+1,r,in*2+1);
for(int j=0;j<(1<<m);j++){
a[in][j]=min(a[in*2][j],a[in*2+1][j]);
}
}
void up(int l,int r,int x,int in){
if(l==r){
for(int j=0;j<(1<<m);j++){
int cur = 0;
for(int k=0;k<m;k++){
if(j&(1<<k)){
cur+=b[l][k];
}else cur-=b[l][k];
}
a[in][j] = cur;
}
return ;
}
int mid = (l+r)/2;
if(x>mid){
up(mid+1,r,x,in*2+1);
}else{
up(l,mid,x,in*2);
}
for(int j=0;j<(1<<m);j++){
a[in][j]=min(a[in*2][j],a[in*2+1][j]);
}
}
int query(int l,int r,int x,int y,int i,int in){
//if(x>y) return inf;
if(l==x&&r==y){
return a[in][i];
}
int mid = (l+r)/2;
if(x>mid){
return query(mid+1,r,x,y,i,in*2+1);
}else if(y<=mid){
return query(l,mid,x,y,i,in*2);
}
return min(query(l,mid,x,mid,i,in*2),query(mid+1,r,mid+1,y,i,in*2+1));
}
int main(){
cin>>n>>m;
for(int j=1;j<=n;j++){
for(int k=0;k<m;k++){
scanf("%d",&b[j][k]);
}
}
build(1,n,1);
// for(int j=0;j<(1<<m);j++){
// cout<<a[1][j]<<endl;
// }
int t; cin>>t;
while(t--){
int z;
scanf("%d",&z);
if(z==1){
int i;
scanf("%d",&i);
for(int j=0;j<m;j++){
scanf("%d",&b[i][j]);
}
up(1,n,i,1);
}else{
int l,r,mx = 0;
scanf("%d%d",&l,&r);
for(int j=0;j<(1<<(m-1));j++){
int x = query(1,n,l,r,j,1);
int y = query(1,n,l,r,j^((1<<m)-1),1);
//cout<<x<<" "<<y<<endl;
mx = max(mx,abs(x+y));
}
printf("%d\n",mx);
}
}
return 0;
} 轉載于:https://www.cnblogs.com/DyLoder/p/10548787.html