Lvat_s Blog

我是纸张……

自以为考虑到所有的情况了，但是却在2操作后忘记给主树加边了……

55555555555555……

-----------

这题虽然可以用高明的数据结构做但是也可以用块状树写。我写的就是块状树

把树分成若干块，父节点的块大小没到要求就加到父节点的块里面去。

这样貌似会被星形的数据卡掉但是既然过了也就不管了

定义原来的树为主树

对于块和块之间连接形成的树称为辅树

加点时一定要在辅树和主树中都更新！

然后对于辅树的每个节点维护一个数据结构(我用了vector,实际上可以是treap等平衡树而且效果肯定更好)

先把本块内的数据查询完然后往下直接走整块

就行了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int N=60005,block_size=200;

int n,lastans,m,en,h[N],w[N],belong[N],block_num,fa[N],bh[N];

struct Edge{int b,next;}e[N<<1];
inline void AddEdge(int sa,int sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}
inline void AddBkEg(int sa,int sb){e[++en].b=sb;e[en].next=bh[sa];bh[sa]=en;}

struct Node{
vector<int> Vx;int siz;
Node(){siz=0;}
inline void Insert(int x){if(!siz)Vx.push_back(x);else Vx.insert(upper_bound(Vx.begin(),Vx.end(),x),x);siz++;}
inline void Change(int x,int y){Vx.erase(lower_bound(Vx.begin(),Vx.end(),x));Insert(y);}
inline int Query(int x){return Vx.end()-upper_bound(Vx.begin(),Vx.end(),x);}
}block[N];

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

void dfsp(int u,int fat){
if(block[belong[fat]].siz<block_size)belong[u]=belong[fat];
else belong[u]=++block_num,AddBkEg(belong[fat],belong[u]);
block[belong[u]].Insert(w[u]);
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
	if(v==fat)continue;
	fa[v]=u;
	dfsp(v,u);
}
}

void dfsb(int u,int x){
lastans+=block[u].Query(x);
for(int i=bh[u];i;i=e[i].next)dfsb(e[i].b,x);
}

void dfss(int u,int x){
if(w[u]>x)lastans++;
for(int i=h[u];i;i=e[i].next){
	int v=e[i].b;
    if(v==fa[u])continue;
    if(belong[v]==belong[u])dfss(v,x);
    else dfsb(belong[v],x);
}
}

int main(){
freopen("3720.in","r",stdin);
freopen("3720.out","w",stdout);
Read(n);
for(register int i=1;i<n;i++){int u,v;Read(u);Read(v);AddEdge(u,v);AddEdge(v,u);}
for(register int i=1;i<=n;i++)Read(w[i]);
dfsp(1,0);
Read(m);
while(m--){
    int opt,u,v;
    Read(opt);Read(u);Read(v);
    u^=lastans;v^=lastans;
    if(opt==0){lastans=0;dfss(u,v);printf("%d\n",lastans);}
    if(opt==1){block[belong[u]].Change(w[u],v);w[u]=v;}
    if(opt==2){w[++n]=v;AddEdge(u,n);if(block[belong[u]].siz<block_size)belong[n]=belong[u];else belong[n]=++block_num,AddBkEg(belong[u],belong[n]);block[belong[n]].Insert(v);fa[n]=u;}
}
return 0;
}

这题是我当初学习CDQ分治时候的神级题目……当时不会做一直拖到现在

这题是动态维护最小生成树，但是是可以离线的，所以我们用CDQ分治对操作进行分治

每一层内用两个操作进行维护

$Contraction$:删除必定在最小生成树中的边并把贡献进行统计(不修改的情况下)

$Reduction$:删除必定不在最小生成树中的边(不修改的情况下)

这样到最后统计时边集的规模就已经相当小了，可以暴力Kruskal统计

但是边集是不断变化的很麻烦所以我们每层建一个边集就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=20005,M=50005,Lg2=22,INF=1000000000;

int n,m,q,siz[N],f[N],a[M],sum[M],c[M];
long long ans[M];

struct Edge{
int u,v,w,id;
inline friend bool operator<(const Edge &A,const Edge &B){return A.w<B.w;}
}e[Lg2][M],d[M],t[M];

struct Query{
int x,y;
}que[M];

inline void Clear(const int &cnt){for(register int i=1;i<=cnt;i++){f[d[i].u]=f[d[i].v]=0;siz[d[i].u]=siz[d[i].v]=1;}}
int Find(int x){return !f[x]?x:f[x]=Find(f[x]);}
inline void Merge(int x,int y){x=Find(x);y=Find(y);if(siz[x]>siz[y])f[y]=x,siz[x]+=siz[y];else f[x]=y,siz[y]+=siz[x];}

inline void Reduction(int &tot){
int tp=0;
Clear(tot);
sort(d+1,d+tot+1);
for(register int i=1;i<=tot;i++){
    if(Find(d[i].u)!=Find(d[i].v)){
		Merge(d[i].u,d[i].v);
		d[++tp]=d[i];
		c[d[i].id]=tp;
    }
    else if(d[i].w==INF){
        d[++tp]=d[i];
        c[d[i].id]=tp;
    }
}
tot=tp;
}

inline void Contraction(int &tot,long long &val){
int tp=0;
Clear(tot);
sort(d+1,d+tot+1);
for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v)){Merge(d[i].u,d[i].v);t[++tp]=d[i];}
for(register int i=1;i<=tp;i++)f[t[i].u]=f[t[i].v]=0,siz[t[i].u]=siz[t[i].v]=1;
for(register int i=1;i<=tp;i++)if(Find(t[i].u)!=Find(t[i].v) && t[i].w!=-INF){Merge(t[i].u,t[i].v);val+=t[i].w;}
tp=0;
for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v)){d[++tp]=d[i];c[d[i].id]=tp;d[tp].u=Find(d[tp].u);d[tp].v=Find(d[tp].v);}
tot=tp;
}

void CDQ(int l,int r,int now,long long val){
int tot=sum[now];
if(l==r)a[que[l].x]=que[l].y;
for(register int i=1;i<=tot;i++)e[now][i].w=a[e[now][i].id];
for(register int i=1;i<=tot;i++)d[i]=e[now][i],c[d[i].id]=i;
if(l==r){
	ans[l]=val;
    Clear(tot);
    sort(d+1,d+tot+1);
	for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v))ans[l]+=d[i].w,Merge(d[i].u,d[i].v);
    return;
}
for(register int i=l;i<=r;i++)d[c[que[i].x]].w=-INF;
Contraction(tot,val);
for(register int i=l;i<=r;i++)d[c[que[i].x]].w=INF;
Reduction(tot);
sum[now+1]=tot;
for(register int i=1;i<=tot;i++)e[now+1][i]=d[i];
int mid=l+r>>1;
CDQ(l,mid,now+1,val);CDQ(mid+1,r,now+1,val);
}

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

int main(){
freopen("2001.in","r",stdin);
freopen("2001.out","w",stdout);
Read(n);Read(m);Read(q);sum[0]=m;
for(register int i=1;i<=m;i++)Read(e[0][i].u),Read(e[0][i].v),Read(a[i]),e[0][i].id=i,e[0][i].w=a[i];
for(register int i=1;i<=q;i++)Read(que[i].x),Read(que[i].y);
CDQ(1,q,0,0);
for(register int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}

本来想用树状数组+主席树水过去的……20min码完后发现空间炸了

卡了几发空间后发现自己并不会卡空间的高明技巧就弃疗了

后来写了一个CDQ分治就水过去了

主席树做法就不说了

CDQ分治主要就是按照位置划分第一层，按照时间(操作顺序)划分第二层，按照值划分第三层

第一层我们读入进来的就是有序的所以不用管

第二次我们可以用CDQ分治分治第二层

分治时用树状数组统计第三层

最后递归前要还原树状数组

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;

int L[N],R[N],BIT[N],time,n,m,pos[N];
long long ans[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Operation{
int t,a,b;
}a[N],b[N];

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){BIT[x]+=y;x+=lowbit(x);}}
inline int Sum(int x){int ans=0;while(x){ans+=BIT[x];x-=lowbit(x);}return ans;}

void CDQ(int l,int r){
if(l>=r)return;
int mid=l+r>>1;
int Lx=l,Rx=mid+1;
for(register int i=l;i<=r;i++){
	if(a[i].t<=mid)b[Lx++]=a[i];
	else b[Rx++]=a[i];
}
Lx=l,Rx=mid;
for(register int i=mid+1;i<=r;i++){
	for(;Lx<=mid && b[Lx].a<=b[i].a;Lx++)Add(b[Lx].b,1);
	L[b[i].t]+=Lx-l-Sum(b[i].b);
}
for(register int i=l;i<Lx;i++)Add(b[i].b,-1);
for(register int i=r;i>mid;i--){
	for(;Rx>=l && b[Rx].a>b[i].a;Rx--)Add(b[Rx].b,1);
	R[b[i].t]+=Sum(b[i].b-1);
}
for(register int i=Rx+1;i<=mid;i++)Add(b[i].b,-1);
for(register int i=l;i<=r;i++)a[i]=b[i];
CDQ(l,mid);CDQ(mid+1,r);
}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);time=n;
for(register int i=1;i<=n;i++)Read(a[i].b),a[i].a=i,pos[a[i].b]=i;
for(register int i=1;i<=m;i++){int x;Read(x);a[pos[x]].t=time--;}
for(register int i=1;i<=n;i++)if(!a[i].t)a[i].t=time--;
CDQ(1,n);
for(register int i=1;i<=n;i++)ans[i]=ans[i-1]+L[i]+R[i];
for(register int i=n;i>=n-m+1;i--)printf("%lld\n",ans[i]);
return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,BIT[N],cnt,a[N],b[N],ls[N*108],rs[N*108],sum[N*108],q[N],bq[N],pts;
long long ans,an[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

inline void Pushup(const int &rt){sum[rt]=sum[ls[rt]]+sum[rs[rt]];}

void Insert(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]+1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid)Insert(ls[rt],ls[lrt],l,mid,v);
if(v>mid)Insert(rs[rt],rs[lrt],mid+1,r,v);
Pushup(rt);
}

void Delete(int &rt,int lrt,int l,int r,int v){
rt=++cnt;
sum[rt]=sum[lrt]-1;
ls[rt]=ls[lrt];
rs[rt]=rs[lrt];
if(l==r)return;
int mid=l+r>>1;
if(v<=mid){if(sum[ls[rt]]==1){ls[rt]=0;return;}Delete(ls[rt],ls[lrt],l,mid,v);}
if(v>mid){if(sum[rs[rt]]==1){rs[rt]=0;return;}Delete(rs[rt],rs[lrt],mid+1,r,v);}
Pushup(rt);
}

long long FindU(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return sum[rs[rt]]+FindU(ls[rt],l,mid,v);
return FindU(rs[rt],mid+1,r,v);
}

long long FindD(int rt,int l,int r,int v){
if(l==r)return 0;
int mid=l+r>>1;
if(v<=mid)return FindD(ls[rt],l,mid,v);
return sum[ls[rt]]+FindD(rs[rt],mid+1,r,v);
}

inline int lowbit(const int &x){return x&(-x);}
inline void Add(int x,int y){while(x<=n){Insert(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline void Del(int x,int y){while(x<=n){Delete(BIT[x],BIT[x],1,n,y);x+=lowbit(x);}}
inline long long SumU(int x,int y){long long ans=0;while(x){ans+=FindU(BIT[x],1,n,y);x-=lowbit(x);}return ans;}
inline long long SumD(int x,int y){long long ans=0;while(x){ans+=FindD(BIT[x],1,n,y);x-=lowbit(x);}return ans;}

int main(){
freopen("3295.in","r",stdin);
freopen("3295.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(a[i]);b[a[i]]=i;}
for(register int i=1;i<=m;i++){Read(q[i]);bq[q[i]]=1;}
for(register int i=1;i<=n;i++){
	if(bq[a[i]])continue;
	Add(i,a[i]);
	ans+=SumU(i,a[i])+SumD(n,a[i])-SumD(i-1,a[i]);
}
an[++pts]=ans;
for(register int i=m;i;i--){
	Add(b[q[i]],q[i]);
	ans+=SumU(b[q[i]],q[i])+SumD(n,q[i])-SumD(b[q[i]]-1,q[i]);
    an[++pts]=ans;
}
for(register int i=pts;i>1;i--)printf("%lld\n",an[i]);
return 0;
}

怎么交都是RE

找来hzwer的程序RE

找来PoPoQQQ的程序RE

找来ww140142的程序RE

一开始我还以为自己写错了

毁我AC率

-------------------------

树上莫队

我没用王室联邦的分块方法，我写了一个块状树的版本

目前莫名RE

等我要到数据再修复……

-------------------------

本机怎么测都AC(Lemon)

以为是爆栈了写个手工栈照样RE

把数组放大10倍还是RE

不管了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=50005,M=100005,block_size=300,T=17;

int n,m,color[N],en,h[N],belong[N],cnt[N],dfn[N],indexs[N],colornum,dep[N],L,R,fa[N][20],Index,siz[N],block_cnt,ans[N],root;

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Edge{
int b,next;
}e[M];

struct Queries{
int l,r,a,b,id;
friend inline bool operator<(const Queries &A,const Queries &B){return belong[A.l]<belong[B.l] || (belong[A.l]==belong[B.l] && dfn[A.r]<dfn[B.r]);}
}que[M];

inline void AddEdge(const int &sa,const int &sb){e[++en].b=sb;e[en].next=h[sa];h[sa]=en;}

inline void Add(const int &x){cnt[x]++;if(cnt[x]==1)colornum++;}
inline void Del(const int &x){cnt[x]--;if(cnt[x]==0)colornum--;}
inline void Change(const int &x){if(indexs[x])Del(color[x]);else Add(color[x]);indexs[x]^=1;}

void dfs(int u,int f){
dfn[u]=++Index;fa[u][0]=f;
if(siz[belong[f]]==block_size)belong[u]=++block_cnt;
else belong[u]=belong[f];
siz[belong[u]]++;dep[u]=dep[f]+1;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==f)continue;
    dfs(v,u);
}
}

inline void Prepare(){
for(register int i=1;i<=T;i++){
    for(register int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
}
}

inline int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int deep=dep[u]-dep[v];
for(register int i=T;~i;i--)if(deep&(1<<i))u=fa[u][i];
for(register int i=T;~i;i--)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return u==v?u:fa[u][0];
}

int main(){
freopen("3757.in","r",stdin);
freopen("3757.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)Read(color[i]);
for(register int i=1;i<=n;i++){int u,v;Read(u);Read(v);if(u==0 || v==0)root=u+v;else AddEdge(u,v),AddEdge(v,u);}
dfs(root,0);
Prepare();
for(register int i=1;i<=m;i++){
    Read(que[i].l);Read(que[i].r);Read(que[i].a);Read(que[i].b);que[i].id=i;
    if(dfn[que[i].l]>dfn[que[i].r])swap(que[i].l,que[i].r);
}
sort(que+1,que+m+1);L=R=root;
for(register int i=1;i<=m;i++){
    int y=LCA(que[i].l,L);
	for(int j=que[i].l;j!=y;j=fa[j][0])Change(j);
	for(int j=L;j!=y;j=fa[j][0])Change(j);
	y=LCA(que[i].r,R);
	for(int j=que[i].r;j!=y;j=fa[j][0])Change(j);
	for(int j=R;j!=y;j=fa[j][0])Change(j);
	L=que[i].l;R=que[i].r;
    int x=LCA(L,R);
    Change(x);
    ans[que[i].id]=colornum;
    if(cnt[que[i].a] && cnt[que[i].b] && que[i].a!=que[i].b)ans[que[i].id]--;
    Change(x);
}
for(register int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}

考虑dp

设$d[x]$为到达$x$号点时的期望长度

因为会随机选一个点，所以到达$x$号点的期望长度为所有能到x号点的点的期望长度乘以到达x号点的边长度

这就告诉我们需要拓扑排序

首先边反向(这样不用处理根本到不了终点的点，而且可以避免计算错误)

(当然反向是比正向快多了)(我正向TLE了)

然后直接在拓扑序上面搞就行

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int N=100005;

int n,m,h[N],en,nxt[N];
double d[N],p[N];
queue<int> Q;

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Edge{int b,v,next;}e[N<<1];
inline void AddEdge(const int &sa,const int &sb,const int &sc){e[++en].b=sb;nxt[sb]++;e[en].v=sc;e[en].next=h[sa];h[sa]=en;}

inline void bfs(){
for(register int i=1;i<=n;i++)p[i]=1.0/nxt[i];
Q.push(n);
while(!Q.empty()){
	int u=Q.front();Q.pop();
	for(register int i=h[u];i;i=e[i].next){
		int v=e[i].b;
		d[v]+=p[v]*(d[u]+e[i].v);
		if(!--nxt[v])Q.push(v);
	}
}
}

int main(){
freopen("3036.in","r",stdin);
freopen("3036.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=m;i++){
	int u,v,w;
    Read(u);Read(v);Read(w);
    AddEdge(v,u,w);
}
bfs();
printf("%.2lf\n",d[1]);
return 0;
}

设$dp[i][j]$为有i张红j张黑时的期望最大值

因为随时可以停止所以当期望小于0时直接改成0

同时因为会爆空间所以改成滚动数组

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5005;

int R,B;
double dp[2][N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("1419.in","r",stdin);
freopen("1419.out","w",stdout);
Read(R);Read(B);
for(register int i=1;i<=R;i++){
	int now=i&1,pre=now^1;
	dp[now][0]=i;
	for(register int j=1;j<=B;j++){
		double Px=1.0*i/(i+j);
		dp[now][j]=Px*(dp[pre][j]+1)+(1-Px)*(dp[now][j-1]-1);
		if(dp[now][j]<0)dp[now][j]=0;
	}
}
printf("%.6lf\n",dp[R&1][B]-0.0000005);
return 0;
}

明天就要上课了

这题是一个莫队+分块

据说莫队+树状数组会T掉

所以我就把整个答案按照权值分块卡卡常就做完了

目前bzoj用时为$20808ms$

数组开小wa两次我真是太弱了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005,block=300;

int n,m,s[N],ans[N*10],cnt[N],bk[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

inline int Gi(const int &x){return (x-1)/block+1;}

struct Query{
int l,r,a,b,id;
friend inline bool operator<(const Query &A,const Query &B){return Gi(A.l)<Gi(B.l)||(Gi(A.l)==Gi(B.l) && A.r<B.r);}
}que[N*10];

inline void Up(int x){
cnt[s[x]]++;
if(cnt[s[x]]==1)bk[Gi(s[x])]++;
}

inline void Down(int x){
cnt[s[x]]--;
if(cnt[s[x]]==0)bk[Gi(s[x])]--;
}

inline int Q(const int &l,const int &r){
int ls=Gi(l)+1,rs=Gi(r)-1,lv=Gi(l)*block,rv=(Gi(r)-1)*block+1,ans=0;
if(ls-rs==2)for(register int i=l;i<=r;i++)ans+=(cnt[i]>0);
else {
	for(register int i=ls;i<=rs;i++)ans+=bk[i];
	for(register int i=l;i<=lv;i++)ans+=(cnt[i]>0);
	for(register int i=rv;i<=r;i++)ans+=(cnt[i]>0);
}
return ans;
}

int main(){
freopen("3809.in","r",stdin);
freopen("3809.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++)Read(s[i]);
for(register int i=1;i<=m;i++)Read(que[i].l),Read(que[i].r),Read(que[i].a),Read(que[i].b),que[i].id=i;
sort(que+1,que+m+1);
register int L=1,R=0;
for(register int i=1;i<=m;i++){
	while(L>que[i].l)Up(--L);
	while(L<que[i].l)Down(L++);
	while(R>que[i].r)Down(R--);
	while(R<que[i].r)Up(++R);
    ans[que[i].id]=Q(que[i].a,que[i].b);
}
for(register int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}

题解clj大神有了就不放了

链接

一道非常好的题目，只是调试能死人罢了

注意要点:

1.此时的极角排序必须加上象限的判断不然会出错(重要!)

2.注意每次point数组必须清空而不能复用因为编号乱了

3.以后数组开到原来的4倍左右防止因数组开小而出错

4.使用long long类型可以有效避免精度误差

5.以后碰到这种题我就写一个$O(n^3)$的暴力，因为这题数据很良心是可以过的，而且我考场上几乎100%不能调试成功

下面版本复杂度为$O(n^2logn)$

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int N=4005;
const double eps=1e-17;

int n,cnt,ind[N];
double ans;

struct Point{
long long x,y;
int id;
Point(){}
Point(long long _x,long long _y){x=_x;y=_y;}
friend inline Point operator+(const Point &A,const Point &B){return Point(A.x+B.x,A.y+B.y);}
friend inline Point operator-(const Point &A,const Point &B){return Point(A.x-B.x,A.y-B.y);}
friend inline long long operator*(const Point &A,const Point &B){return A.x*B.y-A.y*B.x;}
friend inline bool operator==(const Point &A,const Point &B){return A.x==B.x && A.y==B.y;}
}ChosenPoint,point[N<<1];

inline int Check(Point A){
if(A.x-ChosenPoint.x>0 && A.y-ChosenPoint.y>=0)return 0;
if(A.x-ChosenPoint.x<=0 && A.y-ChosenPoint.y>0)return 1;
if(A.x-ChosenPoint.x<0 && A.y-ChosenPoint.y<=0)return 2;
return 3;
}

inline int Dist2(const Point &A,const Point &B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
inline bool cmp(const Point &A,const Point &B){int x=Check(A),y=Check(B);if(x!=y)return x<y;return (A-ChosenPoint)*(B-ChosenPoint)>=0;}
inline bool OnRight(const Point &A,const Point &B,const Point &C){return (B-A)*(C-A)>=0;}

struct Pair_Points{
Point A,B;
}poi[N];

int main(){
freopen("1225.in","r",stdin);
freopen("1225.out","w",stdout);
scanf("%d",&n);
if(n<3){puts("0.000000");return 0;}
for(int i=1;i<=n;i++)scanf("%lld %lld %lld %lld",&poi[i].A.x,&poi[i].A.y,&poi[i].B.x,&poi[i].B.y);
for(int i=1;i<=n;i++){
	ChosenPoint=poi[i].A;
	cnt=0;
	for(int j=1;j<=n;j++){
		if(i==j)continue;
		point[++cnt]=poi[j].A;point[cnt].id=j;point[++cnt]=poi[j].B;point[cnt].id=j;
	}
	sort(point+1,point+cnt+1,cmp);
	memset(ind,0,sizeof(ind));
	int cntx[3]={n-1},pos=1;
	for(int j=cnt+1;j<=2*cnt;j++)point[j]=point[j-cnt];
	for(int j=1;j<=cnt;j++){
		while(pos<j+cnt && OnRight(ChosenPoint,point[j],point[pos])){
			ind[point[pos].id]++;
			cntx[ind[point[pos].id]]++;
			cntx[ind[point[pos].id]-1]--;
            pos++;
		}
		//printf("%d %d %d %d\n", pos, cntx[0], cntx[1], cntx[2]);
		if(cntx[1]+cntx[2]==n-1){
			double afk=0.125;
			if(ind[point[j].id]==1)afk/=pow(2,cntx[1]-1);
			else afk/=pow(2,cntx[1]);
			ans+=afk*(ChosenPoint*point[j]);
		}
		ind[point[j].id]--;
		cntx[ind[point[j].id]]++;
		cntx[ind[point[j].id]+1]--;
	}
}
for(int i=1;i<=n;i++){
	ChosenPoint=poi[i].B;
	cnt=0;
	for(int j=1;j<=n;j++){
		if(i==j)continue;
		point[++cnt]=poi[j].A;point[cnt].id=j;point[++cnt]=poi[j].B;point[cnt].id=j;
	}
	sort(point+1,point+cnt+1,cmp);
	memset(ind,0,sizeof(ind));
	int cntx[3]={n-1},pos=1;
	for(int j=cnt+1;j<=2*cnt;j++)point[j]=point[j-cnt];
	for(int j=1;j<=cnt;j++){
		while(pos<j+cnt && OnRight(ChosenPoint,point[j],point[pos])){
			ind[point[pos].id]++;
			cntx[ind[point[pos].id]]++;
			cntx[ind[point[pos].id]-1]--;
            pos++;
		}
		//printf("%d %d %d %d\n", pos, cntx[0], cntx[1], cntx[2]);
		if(cntx[1]+cntx[2]==n-1){
			double afk=0.125;
			if(ind[point[j].id]==1)afk/=pow(2,cntx[1]-1);
			else afk/=pow(2,cntx[1]);
			ans+=afk*(ChosenPoint*point[j]);
		}
		ind[point[j].id]--;
		cntx[ind[point[j].id]]++;
		cntx[ind[point[j].id]+1]--;
	}
}
printf("%.17lf\n",ans);
return 0;
}

two points+线段树

按长度排序之后一个个加就行

我考场上居然没想到

数组开小wa了2次……身败名裂

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=500005,INF=1000000000;

int b[N<<1],n,m,cnt,ans=INF,tot;

struct Inside{
int l,r,len;
friend bool operator<(const Inside &A,const Inside &B){return A.len<B.len;}
}ins[N];

inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct SegTree{
int l,r,tag,cnt;
}tree[N<<3];

inline void Pushup(const int &rt){
tree[rt].cnt=tree[rt].tag+max(tree[rt<<1].cnt,tree[rt<<1|1].cnt);
}

void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r)return;
int mid=l+r>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
}

void Add(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].cnt++;tree[rt].tag++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Add(rt<<1,l,r);
if(r>mid)Add(rt<<1|1,l,r);
Pushup(rt);
}

void Del(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt].cnt--;tree[rt].tag--;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Del(rt<<1,l,r);
if(r>mid)Del(rt<<1|1,l,r);
Pushup(rt);
}

int main(){
freopen("222.in","r",stdin);
freopen("222.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<=n;i++){
	Read(ins[i].l);Read(ins[i].r);
	ins[i].len=ins[i].r-ins[i].l;
	b[++cnt]=ins[i].l;b[++cnt]=ins[i].r;
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;i++)ins[i].l=lower_bound(b+1,b+cnt+1,ins[i].l)-b,ins[i].r=lower_bound(b+1,b+cnt+1,ins[i].r)-b;
sort(ins+1,ins+n+1);
Build(1,1,cnt);
int cur=0;
for(int i=1;i<=n;i++){
    while(cur<n && tree[1].cnt<m){cur++;Add(1,ins[cur].l,ins[cur].r);}
    if(tree[1].cnt<m)break;
    ans=min(ans,ins[cur].len-ins[i].len);
    Del(1,ins[i].l,ins[i].r);
}
printf("%d\n",ans==INF?-1:ans);
return 0;
}

这次比赛我打的很不好……其实是因为懒

没写暴力

当时做掉了A，BC当时不会做，现在也不会做

所以暂时只有A的题解

A.奥林匹克五子棋

我们思考怎么摆放最优

首先我们发现每一行的摆放是否连通只和上一行的摆放方式有关

所以我们要尽量减少连通

想让上下不联通得左右放

想让左右不联通得上下放

那么我们就得到了一种摆放的方式

0101010101

0101010101

1010101010

1010101010

这样就可以完成目标了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int n,m,k;
queue<pair<int,int> > Q1,Q2;

int Abs(int x){return x>0?x:-x;}

int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
if(k==1){puts("-1");return 0;}
else if(k==2){if(n<2 || m<2){if(n==1)for(int i=1;i<=m;i++)printf("%d %d\n",1,i);else if(m==1)for(int i=1;i<=n;i++)printf("%d %d\n",i,1);}else puts("-1");return 0;}
else if(k>min(n,m)){
	for(int i=1;i<=n;i++){
        if(i%2){if(m%2)for(int j=1;j<=m;j++)printf("%d %d\n",i,j);else for(int j=m;j;j--)printf("%d %d\n",i,j);}
        else for(int j=1;j<=m;j++)printf("%d %d\n",i,j);
	}
	return 0;
}
else if(k>2){
	for(int i=1;i<=n;i++){
		if(i%4==1 || i%4==2){for(int j=1;j<=m;j++){if(j&1)Q1.push(make_pair(i,j));else Q2.push(make_pair(i,j));}}
		else {for(int j=1;j<=m;j++){if(j&1)Q2.push(make_pair(i,j));else Q1.push(make_pair(i,j));}}
	}
	if(Abs(Q1.size()-Q2.size())>=2){
		while(!Q1.empty())Q1.pop();
		while(!Q2.empty())Q2.pop();
		swap(n,m);
		for(int i=1;i<=n;i++){
			if(i%4==1 || i%4==2){for(int j=1;j<=m;j++){if(j&1)Q1.push(make_pair(j,i));else Q2.push(make_pair(j,i));}}
			else {for(int j=1;j<=m;j++){if(j&1)Q2.push(make_pair(j,i));else Q1.push(make_pair(j,i));}}
		}
		if(Abs(Q1.size()-Q2.size())>=2){puts("-1");return 0;}
		else {
            int x=n*m,flg=1;
			while(x--){
				if(flg){printf("%d %d\n",Q1.front().first,Q1.front().second);Q1.pop();}
				else {printf("%d %d\n",Q2.front().first,Q2.front().second);Q2.pop();}
				flg^=1;
			}
		}
	}
	else {
		int x=n*m,flg=1;
		while(x--){
			if(flg){printf("%d %d\n",Q1.front().first,Q1.front().second);Q1.pop();}
			else {printf("%d %d\n",Q2.front().first,Q2.front().second);Q2.pop();}
			flg^=1;
		}
	}
	return 0;
}
return 0;
}

B.奥林匹克环城马拉松

正在思考中

C.奥林匹克数据结构

正在思考中