其实是我晚上懒得码代码了= =
写篇题解记录下最近过的题。。
BZOJ3747
线段树
枚举右端点
每次把last[a[i]]+1~i这段答案+1
把last[last[a[i]]]+1~last[a[i]]答案-1
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 1000005
#define ls (x<<1)
#define rs (ls^1)
#define L tree[x].l
#define R tree[x].r
#define S tree[x].sum
#define A tree[x].add
#define M tree[x].mid
using namespace std;
struct node{int l,r,mid;long long sum,add;}tree[maxn*4];
int a[maxn],b,c,d,e,f,g,i,j,k,m,n,data[maxn],fa[maxn],last[maxn];
long long l,h;
inline void down(int x){
if(L==R)return;
if(!A)return;
tree[ls].sum+=A;
tree[ls].add+=A;
tree[rs].sum+=A;
tree[rs].add+=A;
A=0;
}
void build(int x,int l,int r){
L=l;R=r;S=0;A=0;
if(l==r)return ;
M=(L+R)>>1;
build(ls,l,M);
build(rs,M+1,r);
}
void add(int x,int l,int r){
if(l==L&&r==R){
S+=k;A+=k;
return;
}
down(x);
if(r<=M)add(ls,l,r);
else if(l>M)add(rs,l,r);
else {add(ls,l,M);add(rs,M+1,r);}
S=max(tree[ls].sum,tree[rs].sum);
}
long long get(int x,int l,int r){
if(l==L&&r==R){
return S;
}
down(x);
if(r<=M)return get(ls,l,r);
if(l>M)return get(rs,l,r);
return max(get(ls,l,M),get(rs,M+1,r));
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=m;i++)scanf("%d",&data[i]);
for(i=1;i<=n;i++){
fa[i]=last[a[i]];
last[a[i]]=i;
}
build(1,1,n);
for(i=1;i<=n;i++){
k=data[a[i]];
add(1,fa[i]+1,i);
k=-data[a[i]];
if(fa[fa[i]]+1<=fa[i])add(1,fa[fa[i]]+1,fa[i]);
l=get(1,1,i);
h=max(h,l);
}
printf("%lld",h);
return 0;
}
BZOJ3732
最小生成树+某种支持树上路径操作的东西
把图的最小生成树构出来
2点的答案就是最小生成树上路径的答案
证明不要问我= =
顺便学习了下倍增lca，挺好写的。。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define maxn 30005
using namespace std;
struct node {int u,v,cost;}way[maxn];
int a,b,c,d,e,f,g,h,i,j,k,l,m,n,r,Tot;
int Way[maxn*2],Last[maxn],Next[maxn*2],Fa[maxn][21],dl[maxn],deep[maxn],Cost[maxn];
int Max[maxn][21],fa[maxn];
void Bfs(){
dl[l=r=1]=1;deep[1]=0;
for(;l<=r;l++){
int s=dl[l];
for(int i=Last[s];i;i=Next[i])
if(Way[i]!=Fa[s][0]){
deep[Way[i]]=deep[s]+1;
Fa[Way[i]][0]=s;
Max[Way[i]][0]=Cost[i];
dl[++r]=Way[i];
}
}
for(int i=1;i<=r;i++)
for(int j=1;j<=20;j++){
Fa[dl[i]][j]=Fa[Fa[dl[i]][j-1]][j-1];
Max[dl[i]][j]=max(Max[dl[i]][j-1],Max[Fa[dl[i]][j-1]][j-1]);
}
}
inline int lca(int p,int q){
int ans=0;
if(deep[p]<deep[q])swap(p,q);
for(register int i=20;i>=0;i--)
if(deep[p]-(1<<i)>=deep[q]){ans=max(ans,Max[p][i]);p=Fa[p][i];}
if(p==q)return ans;
for(register int i=20;i>=0;i--)
if(Fa[p][i]!=Fa[q][i]){
ans=max(ans,Max[p][i]);
p=Fa[p][i];
ans=max(ans,Max[q][i]);
q=Fa[q][i];
}
ans=max(ans,Max[p][0]);
ans=max(ans,Max[q][0]);
return ans;
}
inline void Make(int a,int b,int c){
Way[++Tot]=b;
Next[Tot]=Last[a];
Last[a]=Tot;
Cost[Tot]=c;
}
inline bool cmp(node a,node b){return a.cost<b.cost;}
inline int get(int x){if(fa[x]==x)return x;return fa[x]=get(fa[x]);}
int main(){
int Q;
scanf("%d%d%d",&n,&m,&Q);
for(i=1;i<=m;i++)scanf("%d%d%d",&way[i].u,&way[i].v,&way[i].cost);
for(i=1;i<=n;i++)fa[i]=i;
sort(way+1,way+1+m,cmp);
for(i=1;i<=m;i++){
int u=get(way[i].u),v=get(way[i].v);
if(u==v)continue;
fa[u]=v;
Make(way[i].u,way[i].v,way[i].cost);
Make(way[i].v,way[i].u,way[i].cost);
}
Bfs();
for(;Q;Q--){
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",lca(u,v));
}
return 0;
}
BZOJ1052&3760
双倍经验~
二分+dfs
二分显然。。
总共3个正方形，所以可以dfs
当前剩下的所有点用一个矩形框起来
当前这个正方形就在矩形的其中一个角上
以此进行dfs
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Inf 20000000005ll
using namespace std;
long long a,b,c,d,e,f,g,h,i,j,k,l,m,n,vis[200005],x[200005],y[200005],mid,r;
long long dfs(long long X){
long long maxx=-Inf,maxy=-Inf,minx=Inf,miny=Inf;
for(long long i=1;i<=n;i++)if(!vis[i]){
maxx=max(maxx,x[i]);
maxy=max(maxy,y[i]);
minx=min(minx,x[i]);
miny=min(miny,y[i]);
}
if (X==3){
if(maxx-minx>mid||maxy-miny>mid)return 0;
return 1;
}
for(long long i=1;i<=n;i++)if(!vis[i])
if(maxx-mid<=x[i]&&x[i]<=maxx&&maxy-mid<=y[i]&&y[i]<=maxy)vis[i]=X;
if(dfs(X+1))return 1;
for(long long i=1;i<=n;i++)if(vis[i]==X)vis[i]=0;
for(long long i=1;i<=n;i++)if(!vis[i])
if(maxx-mid<=x[i]&&x[i]<=maxx&&miny<=y[i]&&y[i]<=miny+mid)vis[i]=X;
if(dfs(X+1))return 1;
for(long long i=1;i<=n;i++)if(vis[i]==X)vis[i]=0;
for(long long i=1;i<=n;i++)if(!vis[i])
if(minx<=x[i]&&x[i]<=minx+mid&&maxy-mid<=y[i]&&y[i]<=maxy)vis[i]=X;
if(dfs(X+1))return 1;
for(long long i=1;i<=n;i++)if(vis[i]==X)vis[i]=0;
for(long long i=1;i<=n;i++)if(!vis[i])
if(minx<=x[i]&&x[i]<=minx+mid&&miny<=y[i]&&y[i]<=miny+mid)vis[i]=X;
if(dfs(X+1))return 1;
for(long long i=1;i<=n;i++)if(vis[i]==X)vis[i]=0;
return 0;
}
int main(){
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);
for(l=0,r=Inf;l<r;mid=(1ll*(l+r))>>1){
memset(vis,0,sizeof(vis));
if(dfs(1))r=mid;
else l=mid+1;
}
printf("%lld",l);
return 0;
}
BZOJ1214
不说了= =，自己看提交记录就明白了
BZOJ3721
贪心
排序，
假设当前求k
如果前k大和为奇数，。。。
否则
把a[k]替换为a[j](a[j]<a[k]并且a[j],a[k]奇偶不同)
或者把a[j](a[j]>a[k]并且a[j],a[k]奇偶不同)替换为a[l](a[l]<a[k]并且a[l]与a[j]奇偶不同)
#include <cstdio>
#include <algorithm>
#define Inf 2000000005
using namespace std;
long long a[1000005],b,c,d,e,f,g,h,i,j,k,l,m,n,ans[1000005];
long long next[1000005][2],last[1000005][2];
inline bool cmp(long long a,long long b){return a>b;}
int main(){
// freopen("3721.in","r",stdin);
// freopen("3721.out","w",stdout);
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+1+n,cmp);
for(i=n;i;i--){
next[i][1]=next[i+1][1];
next[i][0]=next[i+1][0];
if(a[i]&1)next[i][1]=max(next[i][1],a[i]);
else next[i][0]=max(next[i][0],a[i]);
}
last[0][0]=last[0][1]=Inf;
for(i=1;i<=n;i++){
last[i][1]=last[i-1][1];
last[i][0]=last[i-1][0];
if(a[i]&1)last[i][1]=min(last[i][1],a[i]);
else last[i][0]=min(last[i][0],a[i]);
}
for(i=1;i<=n;i++){
if(i==10){
j=0;
}
h=h+a[i];
if(h&1){
ans[i]=h;
}
else{
ans[i]=-1;
if(next[i+1][(a[i]&1)^1])ans[i]=max(h-a[i]+next[i+1][(a[i]&1)^1],ans[i]);
if(last[i][(a[i]&1)^1]!=Inf&&next[i+1][a[i]&1])ans[i]=max(ans[i],h-last[i][(a[i]&1)^1]+next[i+1][a[i]&1]);
}
}
scanf("%lld",&m);
for(i=1;i<=m;i++){
scanf("%lld",&b);
printf("%lld\n",ans[b]);
}
return 0;
}
BZOJ3744
分块+树状数组
预处理：
Ans[i][j]:第i~j块的答案
Sum[i][j]:前i块中比j小的数字个数
对于每个询问
在同一块或相邻块，直接暴力求逆序对
否则把l~r分成中间一些块和左右多出来的部分
然后多出来的暴力
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int a[100005],b[100005],c,d,e,f[100005],g,i,j,k,l,m,n,r;
int sum[305][50005];
long long h,ans[305][305];
inline void inc(int x){for(;x<=n;x+=x&(-x))f[x]++;}
inline void dec(int x){for(;x<=n;x+=x&(-x))f[x]--;}
inline int Sum(int x){int s=0;for(;x;x-=x&(-x))s+=f[x];return s;}
inline int ef(int x){int l=1,r=b[0],mid=(l+r+1)>>1;for(;l<r;mid=(l+r+1)>>1)if(b[mid]>x)r=mid-1;else l=mid;return l;}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}
sort(b+1,b+1+n);
for(i=1;i<=n;i++)if(b[i]!=b[i+1])b[++b[0]]=b[i];
for(i=1;i<=n;i++)a[i]=ef(a[i]);
int X=250,Y=n/X;
for(i=1;i<=Y;i++){
for(j=1;j<=n;j++)sum[i][j]=sum[i-1][j];
for(j=X*(i-1)+1;j<=X*i;j++)sum[i][a[j]]++;
}
for(i=1;i<=Y;i++){
for(j=1;j<=n;j++)sum[i][j]=sum[i][j-1]+sum[i][j];
}
for(i=Y;i;i--){
memset(f,0,sizeof(f));
for(j=X*i;j>=X*(i-1)+1;j--){
ans[i][i]+=Sum(a[j]-1);
inc(a[j]);
}
}
for(i=Y;i;i--){
memset(f,0,sizeof(f));
for(j=X*i;j>=X*(i-1)+1;j--)inc(a[j]);
for(l=i-1;l;l--){
ans[l][i]=ans[l+1][i]+ans[l][l];
for(j=X*l;j>=X*(l-1)+1;j--)ans[l][i]+=Sum(a[j]-1);
for(j=X*l;j>=X*(l-1)+1;j--)inc(a[j]);
}
}
memset(f,0,sizeof(f));
long long lastans=0;
scanf("%d",&m);
for(;m;m--){
scanf("%d%d",&l,&r);
l=l^lastans;r=r^lastans;
if(l>r)swap(l,r);
int L=(l-1)/X+1,R=(r-1)/X+1;
if(L+1>=R){
h=0;
for(j=r;j>=l;j--){
h=h+Sum(a[j]-1);
inc(a[j]);
}
for(j=r;j>=l;j--)dec(a[j]);
lastans=h;
printf("%lld\n",h);continue;
}
L++;R--;
h=ans[L][R];
for(j=r;j>=R*X+1;j--){
h+=(R*X-(L-1)*X)-(sum[R][a[j]]-sum[L-1][a[j]]);
h+=Sum(a[j]-1);
inc(a[j]);
}
for(j=(L-1)*X;j>=l;j--){
h+=sum[R][a[j]-1]-sum[L-1][a[j]-1];
h+=Sum(a[j]-1);
inc(a[j]);
}
for(j=r;j>=R*X+1;j--)dec(a[j]);
for(j=(L-1)*X;j>=l;j--)dec(a[j]);
printf("%lld\n",h);
lastans=h;
}
return 0;
}
BZOJ3751
NOIP2014D2T3
考场上想到取模但是觉得萎。。于是没写。。。
没想到对多个数取模。。
BZOJ3781
分块/莫队
没什么说的了吧。。
比较裸的题了。。
莫队代码短点
强制在线的话写分块。。
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct node{int l,r,id;}wk[50005];
int a[50005],b,c,d,e,f[50005],g,i,j,k,l,m,n,X,r;
long long h,ans[50005];
inline bool cmp(node a,node b){if(a.l/X==b.l/X)return a.r<b.r;else return a.l<b.l;}
int main(){
scanf("%d%d%d",&n,&m,&k);
X=(int)sqrt(m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=m;i++){
scanf("%d%d",&wk[i].l,&wk[i].r);
wk[i].id=i;
}
sort(wk+1,wk+1+m,cmp);
l=1,r=0;
for(i=1;i<=m;i++){
while(r<wk[i].r){
r++;
h+=(f[a[r]])*2ll+1;
f[a[r]]++;
}
while(r>wk[i].r){
f[a[r]]--;
h-=(f[a[r]])*2ll+1;
r--;
}
while(l<wk[i].l){
f[a[l]]--;
h-=(f[a[l]])*2ll+1;
l++;
}
while(l>wk[i].l){
l--;
h+=(f[a[l]])*2ll+1;
f[a[l]]++;
}
ans[wk[i].id]=h;
}
for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}
写了好多= =
就这样吧，早点睡觉了。。。
评论 (0)
