hzwer出的BZOJ大赛，ACM赛制，AC:4/5，D题看了题解才发现把最小值看成最大值想了快两个小时。
A.满汉全席
题目大意：n个菜，每种菜可以做成两种菜式中的一种，m个厨师，每个厨师选出两种菜各一种菜式，问是否有方案满足每种菜选一种做，每个厨师选的至少有一种被做到。（n<=100,m<=1000，T组询问，T<=50）
思路：2-sat裸题，每个厨师相当于一个或的关系，复杂度O(T(n+m))。
#include<cstdio> #include<cstring> 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; } #define MN 200 #define ME 2000 struct edge{int nx,t;}e[ME+5]; int n,h[MN+5],en,d[MN+5],l[MN+5],cnt,z[MN+5],inz[MN+5],zn,bn,b[MN+5]; inline void ins(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;} int get() { char c; do c=getchar();while(c!=‘m‘&&c!=‘h‘); return (c==‘m‘)*n+read(); } void tj(int x) { d[x]=l[x]=++cnt;inz[z[zn++]=x]=1; for(int i=h[x];i;i=e[i].nx) { if(!d[e[i].t])tj(e[i].t); if(inz[e[i].t]&&l[e[i].t]<l[x])l[x]=l[e[i].t]; } if(d[x]==l[x])for(++bn;z[zn]!=x;inz[z[zn]]=0)b[z[--zn]]=bn; } int main() { int T=read(),m,i,j;char c; while(T--) { n=read();m=read(); memset(h,en=0,sizeof(h)); while(m--)i=get(),j=get(),ins((i+n-1)%(n<<1)+1,j),ins((j+n-1)%(n<<1)+1,i); memset(d,cnt=0,sizeof(d));memset(l,0,sizeof(l)); memset(z,zn=0,sizeof(z));memset(inz,0,sizeof(inz));memset(b,bn=0,sizeof(b)); for(i=1;i<=n<<1;++i)if(!d[i])tj(i); for(i=1;i<=n;++i)if(b[i]==b[i+n])break; puts(i>n?"GOOD":"BAD"); } }
B.Frozen Nova 冷冻波
题目大意：有n个巫妖和m个小精灵，表示成平面上的点，k棵树，表示成平面上的圆，一个巫妖可以消灭一个小精灵当且仅当他与这个小精灵的距离不超过这个巫妖的攻击半径且巫妖与小精灵连线与树无交点，每个巫妖隔ti秒可以消灭一个小精灵，问多久能消灭所有小精灵，无解输出-1。（n,m,k<=200）
思路：预处理出第i个巫妖能否消灭第j个小精灵，攻击半径直接判，然后枚举树，即判断一条线段与圆心距离是否超过半径，用点积叉积分类计算即可。最后二分答案，网络流check，复杂度O(nmk+logAns*最大流(n+m,nm))。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define lb long double inline int read() { int x,f=1;char c; while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)f=0; for(x=c-‘0‘;(c=getchar())>=‘0‘&&c<=‘9‘;)x=(x<<3)+(x<<1)+c-‘0‘; return f?x:-x; } #define MN 200 #define eps 1e-9 #define MV 400 #define S MV+1 #define T MV+2 #define ME 50000 #define INF 0x7FFFFFFF int dcmp(lb x){return fabs(x)<eps?0:x<0?-1:1;} struct point{lb x,y;}p1[MN+5],p2[MN+5],p3[MN+5]; point operator-(point a,point b){return (point){a.x-b.x,a.y-b.y};} lb operator*(point a,point b){return a.x*b.y-a.y*b.x;} lb dot(point a,point b){return a.x*b.x+a.y*b.y;} lb length(point a){return sqrt(dot(a,a));} lb dis(point p,point a,point b) { if(dot(p-a,b-a)<0)return length(p-a); if(dot(p-b,a-b)<0)return length(p-b); return fabs((p-a)*(b-a)/length(b-a)); } struct edge{int nx,t,w;}e[ME*2+5]; int h[MV+5],en,t[MN+5],r1[MN+5],r3[MN+5],g[MN+5][MN+5],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; } 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,r-u<e[i].w?r-u:e[i].w); u+=k;e[i].w-=k;e[i^1].w+=k; if(u==r)return r; } return d[x]=0,u; } int main() { int n,m,k,i,j,l,r,mid,ans=-1,cnt; scanf("%d%d%d",&n,&m,&k); for(i=1;i<=n;++i)p1[i].x=read(),p1[i].y=read(),r1[i]=read(),t[i]=read(); for(i=1;i<=m;++i)p2[i].x=read(),p2[i].y=read(); for(i=1;i<=k;++i)p3[i].x=read(),p3[i].y=read(),r3[i]=read(); for(i=1;i<=n;++i)for(j=1;j<=m;++j) { if(dcmp(length(p1[i]-p2[j])-r1[i])>0)continue; for(l=1;l<=k;++l)if(dcmp(dis(p3[l],p1[i],p2[j])-r3[l])<=0)break; g[i][j]=l>k; } for(l=0,r=4000000;l<=r;) { mid=l+r>>1; memset(h,0,sizeof(h));en=1; for(i=1;i<=n;++i)ins(S,i,mid/t[i]+1); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(g[i][j])ins(i,j+n,1); for(i=1;i<=m;++i)ins(i+n,T,1); for(cnt=0;bfs();)cnt+=dfs(S,INF); if(cnt<m)l=mid+1;else ans=mid,r=mid-1; } printf("%d",ans); }
C.亚瑟王
题目大意：n张卡牌，进行r次游戏，每次从左到右处理，对于第i张卡牌，若这张卡牌没用过，则有pi几率使用这张牌获得di的权值并结束这轮游戏，求最后获得的权值期望，多组询问。（询问组数<=444，n<=220，r<=132）
思路：用f[i][j]表示到第i张牌还有j场游戏没结束时的权值期望，c[i][j]表示到第i张还有j场没结束的概率，t[i][j]表示第i张卡有j场经过他后，被使用的概率，则t[i][j]=t[i][j-1]+(1-t[i][j-1])*pi，c[i][j]=c[i-1][j+1]*t[i][j+1]+c[i-1][j]*(1-t[i][j])，f[i][j]=(f[i-1][j+1]+di*c[i-1][j+1])*t[i][j+1]+f[i-1][j]*(1-t[i][j])。
#include<cstdio> #include<cstring> #define MN 220 #define MR 132 double f[MN+5][MR+5],c[MN+5][MR+5]; int main() { int T,n,m,i,j,k,z;double p,s,ans; for(scanf("%d",&T);T--;) { scanf("%d%d",&n,&m); memset(f,0,sizeof(f));memset(c,0,sizeof(c));c[0][m]=1; for(i=1;i<=n;++i) { scanf("%lf%d",&p,&z); for(j=s=0;j<=m;++j,s+=(1-s)*p) { if(j)f[i][j-1]+=(f[i-1][j]+z*c[i-1][j])*s,c[i][j-1]+=c[i-1][j]*s; f[i][j]+=f[i-1][j]*(1-s);c[i][j]+=c[i-1][j]*(1-s); } } for(i=ans=0;i<=m;++i)ans+=f[n][i]; printf("%.10lf\n",ans); } }
原文：http://www.cnblogs.com/ditoly/p/20170317C.html