9.6
最小得分和
将({a_N,a_N})从小到大排序。换个思路想，我们找这样一个数：在这些两两数之差的绝对值组成的序列中从这个数开始，就已经有大于等于K个数小于等于这个数。
于是自然想到要转化为判定性问题，即二分这K对数里差值最大的数相差多少，判断是否有大于等于K对满足条件。因为找有多少对满足条件又需要对于所有i二分满足条件的区间，所以时间复杂度为(O（NlogNlogaN）)。
其实我们无需再二分有多少对满足条件的，因为({ l a_N,a_N})都排完序了，对于特定的差值最大的数，如果你从小到大枚举(a_i)，其满足条件的数的区间必定是单调不下降的，所以用两个指针扫一遍就可以了（实际上只要1个，因为当前你只要统计它左边满足的数的个数），时间复杂度为(O（NlogN+NlogaN）)，因为常数很小，可以过所有数据。
至于O（KlogN）的做法运用的是堆，首先将每相邻两个元素差值入堆，每次选取当前堆中最小的数，找到它在原序列中的位置i，然后向左找到第一个没有取的数对（i，p[i]），将堆顶元素变为(s[i]-s[p[i]-1]，s[i])为前缀和，然后(dec（p[i]）)，做K次得到答案。
还有细节需要考虑，请自行思考。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
#define Abs(x) ((x)<0?-(x):(x))
#define ls (o<<1)
#define rs (o<<1|1)
const int N=1000006+10,M=1e5+50,inf=0x3f3f3f3f;
int n,a[N];
ll k,ans;
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
ll check(int lim){
ll sum=0,cnt=0;ans=0;
for(int i=1,j=1;i<=n;++i){
while(j<i&&lim<a[i]-a[j]) sum-=a[j++];
cnt+=i-j,ans+=(ll)a[i]*(i-j)-sum;
sum+=a[i];
}
return cnt;
}
int main(){
freopen("T1.txt","r",stdin);
//freopen("and.out","w",stdout);
rd(n),rd(k);
for(int i=1;i<=n;++i) rd(a[i]);
sort(a+1,a+n+1);
int l=0,r=a[n]-a[1],mid;
while(l<r){
mid=l+r>>1;
if(check(mid)>=k) r=mid;
else l=mid+1;
}
ll kk=check(r-1);
ans+=r*(k-kk);
printf("%lld",ans);
return 0;
}
总统竞选
==就是最优比率生成树的模板
r不应该是10的 只是懒得搞那个迭代的那个版本了
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define Abs(x) ((x)<0?-(x):(x))
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
const int N=1000+5,M=5e5+5,INF=1e9+7,inf=0x3f3f3f3f;
const double eps=1e-5;
int n,k;
double a[N][N],b[N][N];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
struct cou{int x,y,z;}c[N];
double qdis(int x,int y){return sqrt((double)(1.0*x*x)+(1.0*y*y));}
bool vis[N];
double sum,dis[N],d[N][N];
bool check(double mid){
for(int i=0;i<=n;++i) dis[i]=1e20,d[i][i]=0.0,vis[i]=0;
dis[1]=sum=0.0;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
d[i][j]=d[j][i]=b[i][j]-mid*a[i][j];
for(int i=1,u=0;i<=n;++i,u=0){
for(int j=1;j<=n;++j)
if(!vis[j]&&dis[j]<dis[u]) u=j;
vis[u]=1,sum+=dis[u];
for(int v=1;v<=n;++v)
if(!vis[v]) dis[v]=Min(dis[v],d[u][v]);
}
return sum>0;
}
int main(){
//freopen("build.in","r",stdin);
// freopen("build.out","w",stdout);
while(scanf("%d",&n)!=EOF&&n){
for(int i=1;i<=n;++i) rd(c[i].x),rd(c[i].y),rd(c[i].z);
double l=0.0,r=10.0,mid;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
a[i][j]=a[j][i]=qdis(c[i].x-c[j].x,c[i].y-c[j].y),b[i][j]=b[j][i]=(double)Abs(c[i].z-c[j].z);//,r=Max(r,b[i][j]/a[i][j])
while(r-l>=eps){
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.3f
",l);
}
return 0;
}
位运算
==到处都是锅
初步想法：因为只有区间的元素修改与查询操作，很容易想到线段树。
因为混合运算时不满足交换率，导致不能直接使用lazy进行标记。
先从特殊情况考虑：如果所有数均为0或1，且K为0或1。
于是只要简单的lazy标记即可。
由于位运算时二进制不同位互不影响，将每一位分开做，再将每一位的答案合并，即可得到最终答案。
时间复杂度(O（Mloga_nlogN))
就是拆开成两位 ==
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
#define Abs(x) ((x)<0?-(x):(x))
#define ls (o<<1)
#define rs (o<<1|1)
const int N=200000+10,M=1e5+50,inf=0x3f3f3f3f;
int n,m,a[N],K[20];
template <class t>void rd(t &x){
x=0;int w=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=w?-x:x;
}
struct node{int tg[19];bool val[19];}t[N<<2];
void pup(int o){
for(int i=0;i<18;++i) t[o].val[i]=t[ls].val[i]^t[rs].val[i];
}
void pudw(int o,int l,int r){
int mid=l+r>>1;
for(int i=0;i<18;++i)
if(t[o].tg[i]){
if(t[o].tg[i]==1) t[ls].val[i]=t[rs].val[i]=0;
else t[ls].val[i]=(mid-l+1)&1,t[rs].val[i]=(r-mid)&1;//区间赋为1 异或和:奇为1 偶为0
t[ls].tg[i]=t[rs].tg[i]=t[o].tg[i];
t[o].tg[i]=0;
}
}
void And(int o,int l,int r,int x,int y){
if(l>y||r<x) return;
if(x<=l&&r<=y){
for(int i=0;i<18;++i)
if(!K[i]) t[o].val[i]=0,t[o].tg[i]=1;
return;
}
pudw(o,l,r);
int mid=l+r>>1;
And(ls,l,mid,x,y),And(rs,mid+1,r,x,y);
pup(o);
}
void Or(int o,int l,int r,int x,int y){
if(l>y||r<x) return;
if(x<=l&&r<=y){
for(int i=0;i<18;++i)
if(K[i]) t[o].val[i]=(r-l+1)&1,t[o].tg[i]=2;
return;
}
pudw(o,l,r);
int mid=l+r>>1;
Or(ls,l,mid,x,y),Or(rs,mid+1,r,x,y);
pup(o);
}
int Ans,ans[20];
void Xor(int o,int l,int r,int x,int y){
if(l>y||r<x) return;
if(x<=l&&r<=y){
for(int i=0;i<18;++i) ans[i]^=t[o].val[i];
return;
}
pudw(o,l,r);
int mid=l+r>>1;
Xor(ls,l,mid,x,y),Xor(rs,mid+1,r,x,y);
pup(o);
}
void print(int l,int r){
Ans=0;
memset(ans,0,sizeof(ans));
Xor(1,1,n,l,r);
for(int i=0;i<18;++i)
if(ans[i]) Ans|=(1<<i);
printf("%d
",Ans);
}
void build(int o,int l,int r){
if(l==r){
for(int i=0;i<18;++i) t[o].val[i]=(a[l]>>i)&1;
return;
}
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
pup(o);
}
int main(){
freopen("T3.txt","r",stdin);
//freopen("and.out","w",stdout);
rd(n),rd(m);
for(int i=1;i<=n;++i) rd(a[i]);
build(1,1,n);
for(int i=1,opt,x,y,k;i<=m;++i){
rd(opt);
if(opt==3) rd(x),rd(y),print(x,y);
else if(opt==1||opt==2){
rd(x),rd(y),rd(k);
for(int i=0;i<18;++i) K[i]=(k>>i)&1;
if(opt==1) And(1,1,n,x,y);
else if(opt==2) Or(1,1,n,x,y);
}
}
return 0;
}
summary
- 模板不够熟练 ==居然现场推分数规划
- 不会融会贯通 前面都考了这么多位运算了为什么不长点记性！！！ 从位运算的性质去分析