Code Chef December Challenge 2018題解

傳送門

\(MAXEP\)

二分，不過二分的時候要注意把\(mid\)設成\(\left\lfloor{9l+r\over 10}\right\rfloor\)，這樣往右的次數不會超過\(6\)次

//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
inline char getc(){R char ch;while((ch=getchar())>'1'||ch<'0');return ch;}
int n,c,l,r,mid;
inline int query(R int x){printf("%d %d\n",1,x),fflush(stdout);return getc()-'0';}
int main(){scanf("%d%d",&n,&c),l=1,r=n;while(l<r){mid=(9*l+r)/10;query(mid)?(puts("2"),fflush(stdout),r=mid):l=mid+1;}printf("%d %d\n",3,l),fflush(stdout);return 0;
}

\(INTXOR\)

具體的……看代碼好了……

//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
int read(){R int res,f=1;R char ch;while((ch=getchar())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getchar())>='0'&&ch<='9';res=res*10+ch-'0');return res*f;
}
const int N=5e4+5;
int n,p,x1,x2,x3,x,xx,a[N];
int query(int i,int j,int k){printf("%d %d %d %d\n",1,i,j,k);fflush(stdout);return read();}
int main(){for(int T=read();T;--T){n=read();x1=query(1,2,3),x2=query(1,2,4),xx=x1^x2;x=query(3,4,5),a[5]=x^xx,x=query(3,4,6),a[6]=x^xx;fp(i,7,n)x=query(i-2,i-1,i),a[i]=x^a[i-2]^a[i-1];x=query(1,5,n),a[1]=x^a[5]^a[n],x=query(2,n-1,n),a[2]=x^a[n-1]^a[n];a[3]=x1^a[1]^a[2],a[4]=x2^a[1]^a[2];printf("%d ",2);fp(i,1,n)printf("%d%c",a[i]," \n"[i==n]);fflush(stdout);read();}return 0;
}

\(EDGEDIR\)

先隨便找棵生成樹出來，如果是非樹邊隨便定向，子樹邊也無所謂，那么此時如果度數為偶數，父親邊就指出去，如果是奇數，父親邊就指向它。這樣的話最多只會有\(1\)號節點不滿足，如果不滿足就無解，否則就是一組合法解。~~證明并不會~~

//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f;
}
const int N=1e5+5;
struct eg{int v,nx;}e[N<<1];int head[N],tot=1;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;e[++tot]={u,head[v]},head[v]=tot;
}
bool ans[N],deg[N];int vis[N],n,m;
void dfs(int u,int k){vis[u]=1;go(u)if(i!=(k^1)){if(!vis[v])dfs(v,i);else if(vis[v]==1)deg[v]^=1,ans[i>>1]=i&1;}if(u!=1)deg[u]?(ans[k>>1]=k&1,deg[u]=0):(ans[k>>1]=k&1^1,deg[e[k^1].v]^=1);vis[u]=2;
//  printf("%d %d %d %d %d\n",u,deg[1],deg[2],deg[3],deg[4]);
}
int main(){
//  freopen("testdata.in","r",stdin);for(int T=read();T;--T){n=read(),m=read();for(R int i=1,u,v;i<=m;++i)u=read(),v=read(),add(u,v);dfs(1,0);if(deg[1])putchar('-'),putchar('1');else fp(i,1,m)putchar(ans[i]?'1':'0'),putchar(' ');putchar('\n');memset(head,0,(n+1)<<2),memset(vis,0,(n+1)<<2),memset(ans,0,m+1),memset(deg,0,n+1);tot=1;}
}

\(CBFEAST\)

蠢了……

先把詢問轉化一下，每個菜可以被\([c-k,c+k]\)范圍內的人看到的，每次詢問\(c\)的人能看到的最大子段和，變成了一個區間修改，單點查詢的問題。然而這樣的話還是沒法做

我們考慮如果只往后面插入的話，那么用線段樹就可以很容易地維護出最大子段和

那么我們對于從前插入和從后插入分別維護，那么都可以看做是從后插入，從線段樹維護一下就行了

代碼里是把兩個都看做從前插入了

//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f;
}
inline int getop(){R char ch;while((ch=getc())>'9'||ch<'0');return ch-'0';}
char sr[1<<21],z[20];int K=-1,Z=0;
inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}
void print(R int x){if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;while(z[++Z]=x%10+48,x/=10);while(sr[++K]=z[Z],--Z);sr[++K]='\n';
}
const int N=2e5+5,M=(N<<6)+5,base=1e9;
inline int max(R int x,R int y){return x>y?x:y;}
struct tr{int l,r,s,v;inline tr(){}inline tr(R int ll,R int rr,R int ss,R int vv):l(ll),r(rr),s(ss),v(vv){}inline tr operator +(const tr &b)const{return tr(max(l,s+b.l),max(r+b.s,b.r),s+b.s,max(v,max(b.v,r+b.l)));}inline tr operator +(const int &b)const{return tr(max(l,s+b),max(r+b,0),s+b,max(v,r+b));}inline void clr(){l=r=s=v=0;}
};
struct node;typedef node* ptr;
struct node{ptr lc,rc;tr s;inline node();
}e[M];int tot;
inline node::node(){lc=rc=e;}
struct tree{inline tree(){rt=e+(++tot);}tr res;ptr rt;void pd(ptr p){if(p->lc==e)p->lc=e+(++tot);if(p->rc==e)p->rc=e+(++tot);p->lc->s=p->lc->s+p->s,p->rc->s=p->rc->s+p->s,p->s.clr();}void update(ptr p,int l,int r,int ql,int qr,int x){if(ql<=l&&qr>=r)return p->s=p->s+x,void();int mid=(l+r)>>1;pd(p);if(ql<=mid)update(p->lc,l,mid,ql,qr,x);if(qr>mid)update(p->rc,mid+1,r,ql,qr,x);}void query(ptr p,int l,int r,int x){if(p==e||l==r)return res=p->s,void();int mid=(l+r)>>1;pd(p);x<=mid?query(p->lc,l,mid,x):query(p->rc,mid+1,r,x);}
}t[2];
int q,k,ans,op,c,d;
int main(){
//  freopen("testdata.in","r",stdin);q=read(),k=read();while(q--){op=getop(),c=read()^ans;if(op==3){t[0].query(t[0].rt,1,base,c),t[1].query(t[1].rt,1,base,c);print(ans=max(t[0].res.l+t[1].res.l,max(t[0].res.v,t[1].res.v)));}else d=read(),t[op-1].update(t[op-1].rt,1,base,max(1,c-k),min(base,c+k),d);}return Ot(),0;
}

\(BICONT\)

不難看出要計算的就是方案數。對于一條邊\((u,v)\)，如果兩個點不在同一個~~不知道是點雙還是邊雙就當它是邊雙好了的~~雙連通分量里，也就意味著\(u\)所在的子樹和\(v\)所在的子樹之間的點沒有邊相連，我們稱之為這條邊斷開了。那么，如果整張圖里有\(i\)個邊雙，那么有\(i-1\)條邊是斷開的

我們考慮容斥和樹形\(dp\)，設\(f_{u,j,k}\)表示\(u\)的子樹中至少有\(j\)條邊是斷開的，且和\(i\)通過沒有斷開的邊相連的點數為\(k\)的方案數。對于轉移，子樹\(f_{v,j,k}\)，如果\((u,v)\)斷開，那么和\(v\)相連的那\(k\)個點之間可以隨意連邊，不過原來樹上就有的\(k-1\)條邊必須連，方案數要額外乘上一個\(2^{(k-1)(k-2)\over 2}\)。不斷的話轉移顯然。我們枚舉\(u\)的\(j,k\)和\(v\)的\(j,k\)，理論復雜度\(O(n^5)\)，實際跑得飛快

然后處理出\(p_i\)表示至少斷了\(i\)條邊的方案數，容斥原理減一減就可以得到恰好斷了\(i\)條邊的方案數了

//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=205,P=1e9+7;
inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R int y){R int res=1;for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;return res;
}
struct eg{int v,nx;}e[N<<1];int head[N],tot;
inline void Add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
int f[N][N][N],sz[N],bin[N*N],tmp[N][N],p[N],fac[N],ifac[N],n;
inline int calc(R int x){return (x-1)*(x-2)>>1;}
inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
void dfs(int u,int fa){sz[u]=1,f[u][0][1]=1;go(u)if(v!=fa){dfs(v,u);memset(tmp,0,sizeof(tmp));fp(i,0,sz[u]-1)fp(j,1,sz[u])if(f[u][i][j]){fp(k,0,sz[v]-1)fp(l,1,sz[v])if(f[v][k][l]){upd(tmp[i+k+1][j],1ll*f[u][i][j]*f[v][k][l]%P*bin[calc(l)]%P);upd(tmp[i+k][j+l],1ll*f[u][i][j]*f[v][k][l]%P);}}sz[u]+=sz[v];fp(i,0,sz[u]-1)fp(j,1,sz[u])f[u][i][j]=tmp[i][j];}
}
int main(){
//  freopen("testdata.in","r",stdin);scanf("%d",&n);bin[0]=1;fp(i,1,n*n)bin[i]=mul(bin[i-1],2);fac[0]=ifac[0]=1;fp(i,1,n)fac[i]=mul(fac[i-1],i);ifac[n]=ksm(fac[n],P-2);fd(i,n-1,1)ifac[i]=mul(ifac[i+1],i+1);for(R int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),Add(u,v),Add(v,u);dfs(1,0);fp(i,0,sz[1]-1)fp(j,1,sz[1])upd(p[i],mul(f[1][i][j],bin[calc(j)]));fd(i,n-1,0)fp(j,i+1,n-1)p[i]=dec(p[i],mul(p[j],C(j,i)));fp(i,0,n-1)printf("%d%c",p[i]," \n"[i==n-1]);return 0;
}

\(BHD\)

勁啊……

非常感謝那位外國友人代碼里的注解不然我真的不知道還有一個叫做格林公式的東西……

對\(z\)這一維用辛普森去擬合，那么對于每一個\(z\)，我們需要求的就是圓環面積并，可以用類似格林公式求圓的面積并的方法去做

時間復雜度\(O(能過)\)

//minamoto
#include<bits/stdc++.h>
#define R register
#define pb push_back
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=1005;const double Pi=acos(-1.0),eps=1e-6;
typedef pair<double,int> pi;
struct Point{double x,y;inline Point(){}inline Point(R double xx,R double yy):x(xx),y(yy){}inline Point operator +(const Point &b)const{return Point(x+b.x,y+b.y);}inline Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}inline double norm(){return sqrt(x*x+y*y);}inline double ang(){return atan2(y,x);}
};
struct Cir{Point p;double r1,r2;}c[N];pi st[N];
inline double oint(R Point p,R double r,R double t1,R double t2){return r*(r*(t2-t1)+p.x*(sin(t2)-sin(t1))-p.y*(cos(t2)-cos(t1)));
}
int top,cnt,tot,n;double xi[N],yi[N],zi[N],r1[N],r2[N];
void add(R Point p1,R double r1,R Point p2,R double r2,R int d){double dis=(p1-p2).norm(),cur,ang,l,r;if(dis+r1<=r2)return cnt+=d,void();if(r1+r2<=dis||r2+dis<=r1)return;cur=(p2-p1).ang();ang=acos((dis*dis+r1*r1-r2*r2)/(2*r1*dis));l=cur-ang,r=cur+ang;if(l<-Pi)l+=2*Pi;if(r>Pi)r-=2*Pi;if(l>r)cnt+=d;st[++top]=make_pair(l,d),st[++top]=make_pair(r,-d);
}
double calc(Point p,double r,int id){top=cnt=0;fp(i,1,tot)if(i!=id)add(p,r,c[i].p,c[i].r1,1),add(p,r,c[i].p,c[i].r2,-1);st[0]=make_pair(-Pi,0),st[++top]=make_pair(Pi,0);sort(st+1,st+1+top);double res=0;for(R int i=1;i<=top;cnt+=st[i++].second)if(!cnt)res+=oint(p,r,st[i-1].first,st[i].first);return res;
}
double getF(double z){tot=0;fp(i,1,n)if(zi[i]-r2[i]<=z-eps&&zi[i]+r2[i]>=z+eps){double d=fabs(z-zi[i]),len=sqrt(r2[i]*r2[i]-d*d);c[++tot].p=Point(xi[i],yi[i]),c[tot].r1=r1[i]+len,c[tot].r2=r1[i]-len;}double res=0;fp(i,1,tot)res+=calc(c[i].p,c[i].r1,i)-calc(c[i].p,c[i].r2,i);return res;
}
inline double calc(R double fl,R double fm,R double fr,R double len){return (fl+fr+4*fm)*len/6;
}
double sol(double l,double m,double r,double fl,double fm,double fr,double s){double ml=(l+m)*0.5,mr=(m+r)*0.5;double fml=getF(ml),fmr=getF(mr);double cx=calc(fl,fml,fm,m-l),cy=calc(fm,fmr,fr,r-m);if(fabs(s-cx-cy)<eps)return s;return sol(l,ml,m,fl,fml,fm,cx)+sol(m,mr,r,fm,fmr,fr,cy);
}
inline double ask(R double l,R double r){double fl=getF(l),fr=getF(r),fm=getF((l+r)*0.5);return sol(l,(l+r)*0.5,r,fl,fm,fr,calc(fl,fm,fr,r-l));
}
vector<double>pos;double res;
int main(){
//  freopen("testdata.in","r",stdin);scanf("%d",&n);fp(i,1,n)scanf("%lf%lf%lf%lf%lf",&xi[i],&yi[i],&zi[i],&r1[i],&r2[i]);fp(i,1,n)pos.pb(zi[i]+r2[i]),pos.pb(zi[i]-r2[i]),pos.pb(zi[i]);sort(pos.begin(),pos.end());fp(i,1,pos.size()-1)res+=ask(pos[i-1],pos[i]);printf("%.10lf\n",res*0.5);return 0;
}