A. Alien Sunset

暴力枚举答案即可。

#include
     
      int n,i,mx;struct P{	int h,r,t;	bool night(int x){		x%=h;		if(r<=t)return x<=r||x>=t;		return x<=r&&x>=t;	}	}a[50];inline bool check(int x){	for(int i=0;i
      
       mx)mx=a[i].h;	}	for(i=0;i<1825*mx;i++)if(check(i))return printf("%d",i),0;	puts("impossible");}
      
     

　　

B. Breaking Biscuits

等价于选择一对距离最小的平行线夹住所有点。

枚举一条边，计算两侧所有点到这条直线的距离的最大值即可。

时间复杂度$O(n^3)$。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=111;struct P{	int x,y;	P(){}	P(int _x,int _y){x=_x,y=_y;}	P operator-(P b){return P(x-b.x,y-b.y);}	double len(){return hypot(x,y);}}a[N];int n,i,j,k;double cross(P a,P b){return a.x*b.y-a.y*b.x;}double dist(P p,P a,P b){	return cross(p-a,b-a)/(b-a).len();}int main(){	scanf("%d",&n);	for(i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);	double ans=1e100;	a[n+1]=a[1];	for(i=1;i<=n;i++)for(j=1;j
       
      
     

　　

C. Cued In

按题意模拟即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

D. Deranging Hat

求出最终位置，然后贪心置换即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

E. Education

按人数从大到小考虑，每次选择满足条件的最便宜的房子。

#include
     
      #include
      
       using namespace std;const int N=5010;int n,m,i,a[N],b[N],c[N],q[N],ans[N];bool cmp(int x,int y){return a[x]
       
        >1;	for(int i=1;i<=m;i++)if(b[i]>=x){		if(c[i]
       
      
     

　　

F. Flipping Coins

$f[i][j]$表示还需要操作$i$次，目前有$j$枚硬币朝上时的最大期望正面向上的硬币数。

时间复杂度$O(nk)$。

#include
     
      #include
      
       using namespace std;const int N=444;double f[N][N],ans;int n,m,i,j;int main(){	scanf("%d%d",&n,&m);	for(i=1;i<=n;i++)f[0][i]=i;	for(i=1;i<=m;i++)for(j=0;j<=n;j++){		if(j)f[i][j]=(f[i-1][j]+f[i-1][j-1])/2;		if(j
      
     

　　

G. GentleBots

设估价函数为两点到终点的曼哈顿距离之和，每次选取使得估价函数最优的方向走，若不能走，则随机抖动。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int dx[7]={1,-1,0,0,0,0,0},		  dy[7]={0,0,-1,1,0,0,0},		  dz[7]={0,0,0,0,1,-1,0};struct P{	int x,y,z;	void read(){		scanf("%d%d%d",&x,&y,&z);	}	int dis(P b){		return abs(x-b.x)+abs(y-b.y)+abs(z-b.z);	}	void write(){		printf("(%d %d %d)",x,y,z);	}	P(){}	P(int _x,int _y,int _z){x=_x,y=_y,z=_z;}	P apply(int d){		return P(x+dx[d],y+dy[d],z+dz[d]);	}}A,B,C,D;//A->B C->Dint main(){	A.read();	B.read();	C.read();	D.read();	while(1){		A.write();		putchar(' ');		C.write();		puts("");		int pre=A.dis(B)+C.dis(D);		if(!pre)return 0;		int best=~0U>>1;		int I=0,J=0;		for(int i=0;i<7;i++)for(int j=0;j<7;j++){			P NA=A.apply(i),NC=C.apply(j);			if(!NA.dis(C))continue;			if(!NA.dis(NC))continue;			if(!NC.dis(A))continue;			if(!NC.dis(NA))continue;			int now=NA.dis(B)+NC.dis(D);			if(now
         
          =pre){			while(1){				int i=rand()%7,j=rand()%7;				P NA=A.apply(i),NC=C.apply(j);				if(!NA.dis(C))continue;				if(!NA.dis(NC))continue;				if(!NC.dis(A))continue;				if(!NC.dis(NA))continue;				I=i,J=j;				break;			}		}		A=A.apply(I);		C=C.apply(J);	}}
         
        
       
      
     

　　

H. Hiker Safety

能走就走，用队列维护所有可能走的人，时间复杂度$O(n^2)$。

#include
     
      const int N=10010;int B,m,i,n,d[N],a[N],pos[N],r;int h,t,x,q[10000000];int cnt,fin[3333333];inline int abs(int x){return x>0?x:-x;}inline bool check(int x){	if(pos[x]==m)return 0;	int pre=x-1,nxt=x+1;	if(nxt>r)nxt=0;	if(pre){		if(abs(d[pos[x]+1]-d[pos[pre]])>B)return 0;		if(abs(d[pos[x]+1]-d[pos[pre]])
      
       B)return 0;		if(abs(d[pos[x]+1]-d[pos[nxt]])
       
        %d\n",x);	pos[x]++;	fin[++cnt]=x;	while(r&&pos[r]==m)r--;	if(x>1)q[++t]=x-1;	if(x
        
         d[i+1])while(1);	scanf("%d",&n);	for(i=1;i<=n;i++){		scanf("%d%d",&a[i],&pos[i]);	}	for(i=1;i<=n;i++){		if(pos[i]
        
       
      
     

　　

I. I Work All Day

按题意模拟即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

J. Just A Minim

按题意模拟即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

K. Knightsbridge Rises

拆点求最大流。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

L. Lounge Lizards

将所有点到原点的方向向量约分后分组，每组按距离从小到大排序，然后求LIS。

时间复杂度$O(n\log n)$。

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=1000010;int n,i,j,k,m,f[N],ans;struct P{int x,y,h;ll w;}a[N],O;ll sqr(ll x){return x*x;}int gcd(int a,int b){return b?gcd(b,a%b):a;}inline bool cmp(const P&a,const P&b){	if(a.x!=b.x)return a.x
       
        f[m]){		f[++m]=x;		return;	}	int l=1,r=m,mid,t;	while(l<=r){		mid=(l+r)>>1;		if(f[mid]>=x)r=(t=mid)-1;else l=mid+1;	}	f[t]=x;}int main(){	scanf("%d%d",&O.x,&O.y);	scanf("%d",&n);	for(i=1;i<=n;i++){		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].h);		a[i].x-=O.x;		a[i].y-=O.y;		a[i].w=sqr(a[i].x)+sqr(a[i].y);		//sgn gcd		int d=gcd(abs(a[i].x),abs(a[i].y));		a[i].x/=d,a[i].y/=d;		//printf("%d %d %lld\n",a[i].x,a[i].y,a[i].w);	}	sort(a+1,a+n+1,cmp);	for(i=1;i<=n;i=j){		for(j=i;j<=n&&a[i].x==a[j].x&&a[i].y==a[j].y;j++);		m=0;		for(k=i;k