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\n",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; }

?

轉載于:https://www.cnblogs.com/ditoly/p/20170319C.html

總結

以上是生活随笔為你收集整理的2017-3-19四校联考的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。