博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
分析build2011 ACM-ICPC世界总决赛试题分析4-7
阅读量：7257 次
发布时间：2019-06-29

本文共 8185 字，大约阅读时间需要 27 分钟。

最近使用开发的过程中出现了一个小问题，顺便记录一下原因和方法--分析build

    4

#include
    
     const int MaxN=41;const int MOD=3214567;int N,Must,Can;int C[MaxN*3][MaxN*3];int W[MaxN*3][MaxN*3];int Cost,Answer,Upper,A,B;char Map[MaxN][MaxN];#define fo(i,a,b) for(int i=a;i<=b;i++)#define AddEdge(u,v,f,c) C[u][v]=f,W[u][v]=c,W[v][u]=-c#define IncFlow(u,v,df) C[u][v]+=dfvoid Init(){	fo(i,1,N)	{		scanf("\n");		fo(j,1,N)			scanf("%c",&Map[i][j]);	}}void Build(int temp){	fo(i,1,3*N)		fo(j,1,N*3)		C[i][j]=W[i][j]=0;	Must=0,Can=0;	fo(i,1,N)		fo(j,1,N)	{		char r;		r=Map[i][j];		if(r=='C')		{			Must++;			AddEdge(i,j+N,1,-10000);		}		else if(r=='.')		{			Can++;			AddEdge(i,j+N,1,-1);		}	}	fo(i,1,N)	{		AddEdge(i+N+N,i,temp,0);		AddEdge(i+N,i+N+N,10000000,0);	}}int sp[MaxN*3],app[MaxN*3],Q[MOD],Last[MaxN*3],app0[MaxN*3];bool inQ[MaxN*3];bool FindCir(){	fo(i,1,3*N)		sp[i]=0,app[i]=0,Q[i]=i,inQ[i]=true;	for(int L=1,R=3*N+1;L!=R;)	{		app[Q[L]]++;		fo(i,1,3*N)			if(C[Q[L]][i]>0&&sp[i]>sp[Q[L]]+W[Q[L]][i])			{				sp[i]=sp[Q[L]]+W[Q[L]][i];				Last[i]=Q[L];				if(!inQ[i])				{					inQ[i]=true;					Q[R]=i;					R=(R+1==MOD?0:R+1);				}			}			if(app[Q[L]]>3*N)			{				int p;				fo(i,1,3*N)					app0[i]=0;				for(int i=Q[L];;i=Last[i])				{					app0[i]++;					if(app0[i]==2)					{						p=i;						break;					}				}				for(int i=p;;i=Last[i])				{					C[Last[i]][i]--;					C[i][Last[i]]++;					Cost+=W[Last[i]][i];					if(Last[i]==p)						break;				}				return true;			}			inQ[Q[L]]=false;			L=(L+1==MOD?0:L+1);	}	return false;}void Solve(){	Answer=-1;	Upper=(int)(Must*A/B);	Build(Upper);	Cost=0;	if(Can==N*N&&N*N*A>=N*B)	{		printf("%d\n",N*N);		return;	}	fo(i,Must,Must+Can)	{		if(i!=0&&B>A*N)			continue;		if(i>0)		{			fo(j,1,N)				IncFlow(j+N+N,j,(int)(i*A/B)-Upper);			Upper=(int)(i*A/B);		}		while(FindCir());		if(int(-Cost/10000)!=Must)			continue;		if((int)(-Cost/10000)+(-Cost%10000)>=i)		{			Answer=(int)(-Cost/10000)+(-Cost%10000);			i=Answer;		}	}	if(Answer==-1)		puts("impossible");	else		printf("%d\n",Answer-Must);}int main(){	int Test=0;	while(3==scanf("%d%d%d",&N,&A,&B)&&(N||A||B))	{		Init();		printf("Case %d: ",Test);		Solve();	}	return 0;}

    5

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define MP make_pairconst int MaxN=500009;int dx,dy,N,Q,d;int X[MaxN],Y[MaxN];int Sum[2020][2020];void Init(){	for(int i=1;i<=N;i++)		cin>>X[i]>>Y[i];}void Inc(int _x1,int _y1,int _x2,int _y2){	int x1=_x1+_y1+10;	int y1=_y1-_x1+1010;	int x2=_x2+_y2+10;	int y2=_y2-_x2+1010;	if(x1<10)		x1=9;	if(y1<10)		y1=9;	if(x2>2010)		x2=2010;	if(y2>2010)		y2=2010;	Sum[x2][y2]++;	Sum[x1-1][y1-1]++;	Sum[x1-1][y2]--;	Sum[x2][y1-1]--;}int FindAns(int _x,int _y){	int x=_x+_y+10;	int y=_y-_x+1010;	return Sum[x][y];}void Adjust(){	for(int i=2010;i>=0;i--)		for(int j=2010;j>=0;j--)			Sum[i][j]=Sum[i][j+1]+Sum[i+1][j]+Sum[i][j]-Sum[i+1][j+1];	pair
         
          
           >Ans=MP(100,MP(-1,-1)); for(int i=1;i<=dx;i++) for(int j=1;j<=dy;j++) if(MP(-FindAns(i,j),MP(j,i))
           
            >d; for(int x=0;x<=2011;x++) for(int y=0;y<=2011;y++) Sum[x][y]=0; for(int j=1;j<=N;j++) Inc(X[j],Y[j]-d,X[j],Y[j]+d); Adjust(); }}int main(){ int Case=0; while(cin>>dx>>dy>>N>>Q&&(dx||dy||N||Q)) { Init(); cout<<"Case "<<++Case<<":\n"; Solve(); }}

    

    6

    每日一道理
生命，是一场漫长的棋局。这盘棋没有猎猎西风，没有四起狼烟，只有在取舍和进退中抉择。只有像棋中的小卒那样，勇往直前，毫不退缩沿着沟沟坎坎的人生之路，艰难而执着的求索，前进，才会谱写人生最壮丽的强者之歌。 
#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define MP make_pair#define PB push_backtypedef long long LL;const LL INF=100000000000000000LL;const int MaxN=100009;int N;LL Dollar,Day;LL D[MaxN],P[MaxN],R[MaxN],G[MaxN];LL U[MaxN],F[MaxN];vector
           
            
             > Set;LL Area(pair
             
              p0,pair
              
               p1,pair
               
                p2){ double ret=(double)(p1.first-p0.first)/1000000000.000*(p2.second-p0.second) - (double)(p2.first-p0.first)/1000000000.000*(p1.second-p0.second); if(ret>=0.000000001) return -1; else return 0;}void Insert(LL x0,LL y0){ int d; if(Set.empty()) { d=0; Set.PB(MP(x0,y0)); } else if(Set[Set.size()-1].first
                
                 =x0) r=mid; else l=mid+1; } d=l; Set.insert(Set.begin()+1,MP(x0,y0)); } if(d!=0&&d!=Set.size()-1) { if(Area(Set[d-1],Set[d],Set[d+1])>=0) { Set.erase(Set.begin()+d); return; } } if(d!=0&&Set[d].first==Set[d-1].first&&Set[d].second<=Set[d-1].second) { Set.erase(Set.begin()+d); return; } if(d!=Set.size()-1&&Set[d].first==Set[d+1].first&&Set[d].second<=Set[d+1].second) { Set.erase(Set.begin()+d); return; } if(d==1&&Set[d].first==Set[d-1].first) { d--; Set.erase(Set.begin()+d); } if(d==Set.size()-2&&Set[d].first==Set[d+1].first) Set.erase(Set.begin()+d+1); while(d>1&&Area(Set[d-2],Set[d-1],Set[d])>=0) { d--; Set.erase(Set.begin()+d); } while(d+2<=Set.size()-1&&Area(Set[d],Set[d+1],Set[d+2])>=0) Set.erase(Set.begin()+d+1); }pair
                 
                   Find(LL k){ if(Set.size()==1) return Set[0]; if(double(Set[1].second-Set[0].second)/(Set[1].first-Set[0].first)<=(double)k) return Set[0]; int l=1,r=Set.size()-1; while(l
                  
                   >D[i]>>P[i]>>R[i]>>G[i]; Qsort(1,N); P[N+1]=R[N+1]=G[N+1]=0; D[N+1]=Day+1; P[0]=R[0]=G[0]=D[0]=0; F[0]=Dollar; U[0]=Dollar; Insert(0,U[0]);}void Solve(){ for(int i=1;i<=N+1;i++) { pair
                   
                     kp=Find(-D[i]); F[i]=kp.first*D[i]+kp.second; U[i]=F[i]-G[i]*D[i]-G[i]-P[i]+R[i]; if(F[i]>=P[i]) Insert(G[i],U[i]); } cout<
                    
                     <<"\n";}int main(){ int Case=0; while(cin>>N>>Dollar>>Day&&(N||Dollar||Day)) { Init(); cout<<"Case "<<++Case<<": "; Solve(); } return 0;}

    7

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MaxN=509;const double Pi=acos(-1.0);int N;double A[MaxN],Sum[MaxN][MaxN],Max[MaxN][MaxN],S[MaxN][MaxN];double F[MaxN][MaxN];double fmax(double a,double b){ return a>b?a:b;}double MaxAreaOf(int s,int t){ double L=Max[s][t]/2.000; double x=(Max[s][t]-1.000)/2.000; double R=fmax(Max[s][t]/(2.000*sin(Pi/(t-s+1))),(4.000*x>=1.000?((x*x)/sqrt(4.000*x-1.000)):0.000)); double SL,SR; while(true) { SL=0.000; for(int k=s;k<=t;k++) SL+=sqrt(L*L-(A[k]/2.000)*(A[k]/2.000))*(A[k]/2.000); SR=0.000; for(int k=s;k<=t;k++) SR+=sqrt(R*R-(A[k]/2.000)*(A[k]/2.000))*(A[k]/2.000); if(SL+0.00001>SR) break; double Mid=(L+R)/2.000; double deg=0.000; for(int k=s;k<=t;k++) deg+=2*asin(A[k]/2.000/Mid); if(deg-2*asin(Max[s][t]/2.000/Mid)<=Pi) { deg-=2*asin(Max[s][t]/2.000/Mid); deg+=2*Pi-2*asin(Max[s][t]/2.000/Mid); if(deg<2*Pi) L=Mid; else R=Mid; } else { if(deg<2*Pi) R=Mid; else L=Mid; } } L=(L+R)/2.000; double deg=0.000; for(int k=s;k<=t;k++) deg+=2*asin(A[k]/2.000/L); L=(L+R)/2.000; double Ret=0.000; for(int k=s;k<=t;k++) Ret+=sqrt(L*L-(A[k]/2.000)*(A[k]/2.000))*(A[k]/2.000); Ret-=sqrt(L*L-(Max[s][t]/2.000)*(Max[s][t]/2.000))*(Max[s][t]/2.000); if(deg-2*asin(Max[s][t]/2.000/L)<=Pi) Ret-=sqrt(L*L-(Max[s][t]/2.000)*(Max[s][t]/2.000))*(Max[s][t]/2.000); else Ret+=sqrt(L*L-(Max[s][t]/2.000)*(Max[s][t]/2.000))*(Max[s][t]/2.000); return Ret;}void Init(){ for(int i=1;i<=N;i++) cin>>A[i]; for(int i=1;i<=N;i++) Sum[i][i]=A[i]; for(int i=1;i<=N;i++) Max[i][i]=A[i]; for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++) { Sum[i][j]=Sum[i][j-1]+A[j]; Max[i][j]=fmax(Max[i][j-1],A[j]); } for(int i=1;i<=N;i++) for(int j=i;j<=N;j++) { if(i-1>=1) { if(A[i]*2>A[i-1]&&A[i-1]*2>A[i]) { S[i][j]=0.000; continue; } } if(j+1<=N) { if(A[j]*2>A[j+1]&&A[j+1]*2>A[j]) { S[i][j]=0.000; continue; } } if(i-3>=1) { if(A[i-1]+A[i-2]>A[i-3]&&A[i-3]+A[i-2]>A[i-1]&&A[i-1]+A[i-3]>A[i-2]) { S[i][j]=0.000; continue; } } if(j+3<=N) { if(A[j+1]+A[j+2]>A[j+3]&&A[j+3]+A[j+2]>A[j+1]&&A[j+1]+A[j+3]>A[j+2]) { S[i][j]=0.000; continue; } } if(Max[i][j]*2>=Sum[i][j]) S[i][j]=0.000; else S[i][j]=MaxAreaOf(i,j); }}void Solve(){ for(int len=1;len<=N;len++) for(int i=1;i+len-1<=N;i++) { int j=i+len-1; F[i][j]=S[i][j]; for(int k=i;k
          
           >N&&N) { Init(); cout<<"Case "<<++Case<<": "; Solve(); } return 0;}

文章结束给大家分享下程序员的一些笑话语录： Google事件并不像国内主流媒体普遍误导的那样，它仅仅是中国Z府和美国公司、中国文化和美国文化甚至中国人和美国人之间的关系，是民族主义和帝国主义之间的关系；更重要的是，它就是Z府和公司之间的关系，是权力管制和市场自由之间的关系。从这个意义上说，过度管制下的受害者，主要是国内的企业。Google可以抽身而去，国内的企业只能祈望特区。www.ishuo.cn

--------------------------------- 原创文章 By

分析和build
---------------------------------

转载地址：http://xepdm.baihongyu.com/

你可能感兴趣的文章
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-02-13 23:14:01   当前IP: 3.145.167.199   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我