T1输出0有20分结果我输出1爆0（题目说精度差为整数有40%的分数，结果告诉我只能差0.5……），T2打了20分暴力，T3交了个感觉能拿50分的结果是正解……被卡常了一个点，总分110/300
T1.圆
计算几何，正解好像是什么什么积分，什么什么扫描线，什么什么公式，不管了，以后有机会再说
T2.方
题目大意：一个n*m的01矩阵，q个操作，每次修改矩阵中一个元素，并询问最大的全是0的正方形的边长。（n*m<=4,000,000，q<=3,900）
思路：如果列多于行我们转置矩阵，然后用线段树维护行，线段树中每个节点维护对应的行区间中每列上方有多少连续的0，下方有多少连续的0，每次合并信息时利用这些信息计算行区间内的答案，每次为左右儿子的答案与过中线的答案的最大值，计算过中线答案的方法如下：从左到右用两个单调队列维护上半行区间下方连续0的数量和下半行区间上方连续0的数量单调递增，用左右两个指针表示当前考虑的正方形的左右端点，每次把右指针所在的列加入队列，并考虑若右指针到左指针的距离超过左指针所在列的上下宽度，说明此时左指针应向右移动，重复这样既可统计出答案，更具体的实现可参见下面的代码，这样每次更新是O(min(n,m))的，总复杂度O(nm+qmin(n,m)logmax(n,m))。
#include<cstdio> #include<algorithm> using namespace std; inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } inline int get(){char c;do c=getchar();while(c!='.'&&c!='X');return c=='.';} #define MN 2000 #define MM 4000000 #define L k<<1 #define R k<<1|1 int m,*a[MM+5],qx[MN+5],qxl,qxr,qy[MN+5],qyl,qyr; struct node{int l,r,ans,*u,*d;}t[MM*4+5]; void up(int k) { t[k].ans=max(t[L].ans,t[R].ans);qxr=qyr=0; for(int i=qxl=qyl=1,j=1;i<=m;++i) { while(qxl<=qxr&&t[L].d[i]<=t[L].d[qx[qxr]])--qxr;qx[++qxr]=i; while(qyl<=qyr&&t[R].u[i]<=t[R].u[qy[qyr]])--qyr;qy[++qyr]=i; for(;i-j>=t[L].d[qx[qxl]]+t[R].u[qy[qyl]];)++j>qx[qxl]?++qxl:0,j>qy[qyl]?++qyl:0; t[k].ans=max(t[k].ans,i-j+1); t[k].u[i]=((t[L].u[i]==t[L].r-t[L].l+1)?t[R].u[i]:0)+t[L].u[i]; t[k].d[i]=((t[R].d[i]==t[R].r-t[R].l+1)?t[L].d[i]:0)+t[R].d[i]; } } void init(int k,int x) { t[k].ans=0; for(int i=1;i<=m;++i)t[k].ans|=t[k].u[i]=t[k].d[i]=a[x][i]; } void build(int k,int l,int r) { t[k].u=new int[m+5];t[k].d=new int[m+5]; if((t[k].l=l)==(t[k].r=r)){init(k,l);return;} int mid=l+r>>1; build(L,l,mid);build(R,mid+1,r);up(k); } void renew(int k,int x,int y) { if(t[k].l==t[k].r){a[x][y]^=1;init(k,x);return;} renew(x>t[k].l+t[k].r>>1?R:L,x,y);up(k); } int main() { freopen("s.in","r",stdin); freopen("s.out","w",stdout); int n,q,rv=0,i,j; n=read();m=read();q=read(); if(n<m)swap(n,m),rv=1; for(i=1;i<=n;++i)a[i]=new int[m+5]; if(rv)for(i=1;i<=m;++i)for(j=1;j<=n;++j)a[j][i]=get(); else for(i=1;i<=n;++i)for(j=1;j<=m;++j)a[i][j]=get(); build(1,1,n); while(q--) { i=read();j=read(); renew(1,rv?j:i,rv?i:j); printf("%d ",t[1].ans); } fclose(stdin);fclose(stdout);return 0; }
T3.树
题目大意：给出一棵n个节点的树，每个节点可以染成黑色或白色，给出B条黑链和W条白链，若黑链上的点全被染成黑色，则可获得该条链对应的权值，白链同理，求最大收益。（n<=100,000，B,W<=30,000）
思路：容易想到二分图最小割模型，黑白链中相交的连边跑最小割，这样边是O(BW)的，我们考虑优化这个建图，我们树剖原树，建出对应的线段树，这样每条链在线段树上能表示为log段区间，对应log^2个节点，若黑白链有相交，则它们对应的线段树上节点必然存在祖孙关系，我们建两棵线段树，一棵所有父亲向儿子连边，另一棵儿子向父亲连边，每条链再向对应的线段树节点连边，边数被优化到O((B+W)*logn^2)，时限比较大，Dinic比较快，于是就能过，总复杂度O(最大流(n+B+W,(B+W)*logn^2))。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 100000 struct tedge{int nx,t;}te[MN*2+5]; int th[MN+5],ten,fa[MN+5],f[MN+5],s[MN+5],mx[MN+5],l[MN+5],cnt,dep[MN+5]; inline void tins(int x,int y) { te[++ten]=(tedge){th[x],y};th[x]=ten; te[++ten]=(tedge){th[y],x};th[y]=ten; } void pre(int x) { s[x]=1; for(int i=th[x];i;i=te[i].nx)if(te[i].t!=fa[x]) { fa[te[i].t]=x; dep[te[i].t]=dep[x]+1; pre(te[i].t); s[x]+=s[te[i].t]; if(s[te[i].t]>s[mx[x]])mx[x]=te[i].t; } } void work(int x,int k) { l[x]=++cnt;f[x]=k; if(mx[x])work(mx[x],k); for(int i=th[x];i;i=te[i].nx) if(te[i].t!=fa[x]&&te[i].t!=mx[x])work(te[i].t,te[i].t); } #define MV 860000 #define ME 10000000 #define S MV+1 #define T MV+2 #define INF 0x7FFFFFFF struct node{int l,r;}t[MN*4+5]; struct edge{int nx,t,w;}e[ME*2+5]; int h[MV+5],en=1,d[MV+5],q[MV+5],qn,c[MV+5]; inline void ins(int x,int y,int w) { e[++en]=(edge){h[x],y,w};h[x]=en; e[++en]=(edge){h[y],x,0};h[y]=en; } void build(int k,int l,int r) { if((t[k].l=l)==(t[k].r=r))return; int mid=l+r>>1; ins(k,k<<1,INF);ins(k,k<<1|1,INF); ins((k<<1)+MN*4,k+MN*4,INF);ins((k<<1|1)+MN*4,k+MN*4,INF); build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void insb(int k,int l,int r,int p) { if(t[k].l==l&&t[k].r==r){ins(MN*8+p,k,INF);ins(MN*8+p,k+MN*4,INF);return;} int mid=t[k].l+t[k].r>>1; if(r<=mid)insb(k<<1,l,r,p); else if(l>mid)insb(k<<1|1,l,r,p); else insb(k<<1,l,mid,p),insb(k<<1|1,mid+1,r,p); } void insw(int k,int l,int r,int p) { if(t[k].l==l&&t[k].r==r){ins(k,MN*8+p,INF);ins(k+MN*4,MN*8+p,INF);return;} int mid=t[k].l+t[k].r>>1; if(r<=mid)insw(k<<1,l,r,p); else if(l>mid)insw(k<<1|1,l,r,p); else insw(k<<1,l,mid,p),insw(k<<1|1,mid+1,r,p); } void buildb(int k,int x,int y) { while(f[x]!=f[y]) if(dep[f[x]]>dep[f[y]])insb(1,l[f[x]],l[x],k),x=fa[f[x]]; else insb(1,l[f[y]],l[y],k),y=fa[f[y]]; insb(1,min(l[x],l[y]),max(l[x],l[y]),k); } void buildw(int k,int x,int y) { while(f[x]!=f[y]) if(dep[f[x]]>dep[f[y]])insw(1,l[f[x]],l[x],k),x=fa[f[x]]; else insw(1,l[f[y]],l[y],k),y=fa[f[y]]; insw(1,min(l[x],l[y]),max(l[x],l[y]),k); } bool bfs() { int i,j; memset(d,0,sizeof(d)); for(d[q[i=qn=0]=S]=1;i<=qn;++i)for(j=c[q[i]]=h[q[i]];j;j=e[j].nx) if(e[j].w&&!d[e[j].t])d[q[++qn]=e[j].t]=d[q[i]]+1; return d[T]; } int dfs(int x,int r) { if(x==T)return r; int k,u=0; for(int&i=c[x];i;i=e[i].nx)if(e[i].w&&d[e[i].t]==d[x]+1) { k=dfs(e[i].t,min(r-u,e[i].w)); u+=k;e[i].w-=k;e[i^1].w+=k; if(u==r)return u; } return d[x]=0,u; } int main() { freopen("t.in","r",stdin); freopen("t.out","w",stdout); fread(B,1,1<<26,stdin); int n,b,w,i,x,ans=0; n=read();b=read();w=read(); for(i=1;i<n;++i)tins(read(),read()); pre(1);work(1,1);build(1,1,n); for(i=1;i<=b;++i)buildb(i,read(),read()),ins(S,MN*8+i,x=read()),ans+=x; for(i=1;i<=w;++i)buildw(i+b,read(),read()),ins(MN*8+b+i,T,x=read()),ans+=x; while(bfs())ans-=dfs(S,INF); printf("%d",ans); fclose(stdin);fclose(stdout);return 0; }