A. Freestyle

如果逆序对为$0$，那么先手必败。

因为每次只能翻转长度为$4k+2$和$4k+3$的区间，所以每次操作之后逆序对的奇偶性一定会发生改变。

因此如果逆序对个数为偶数，则先手必败。

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

　　

B. Checkout lines

从后往前贪心构造。

#include 
     
      using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 100005 ;const int MAXE = 100005 ;int a[MAXN] ;int b[MAXN] ;int c[MAXN] ;int vis[MAXN] ;int n ;void solve () {	int ok = 0 ;	clr ( vis , 0 ) ;	for ( int i = 1 ; i <= n ; ++ i ) {		scanf ( "%d" , &a[i] ) ;	}	for ( int i = 1 ; i <= n ; ++ i ) {		scanf ( "%d" , &b[i] ) ;	}	if ( n == 1 ) {		printf ( "-1\n" ) ;		return ;	}	for ( int i = n ; i >= 1 ; -- i ) {		if ( !vis[i] ) {			if ( b[i] == a[i] ) {				ok = 1 ;				if ( i < n ) {					c[i] = c[i + 1] ;					c[i + 1] = b[i] ;					vis[i] = 1 ;				} else {					c[i - 1] = b[i] ;					vis[i - 1] = 1 ;				}			} else {				c[i] = b[i] ;				vis[i] = 1 ;			}		} else {			vis[i + 1] = 1 ;			c[i + 1] = b[i] ;		}	}	printf ( "%d\n" , ok ) ;	for ( int i = 1 ; i <= n ; ++ i ) {		i > 1 && putchar ( ' ' ) ;		printf ( "%d" , c[i] ) ;	}	puts ( "" ) ;}int main () {	while ( ~scanf ( "%d" , &n ) ) solve () ;	return 0 ;}
     

　　

C. Heli-ski

如果$n$比较大，那么$\sum$比较小。

求出每个点向上能延伸的长度，枚举每个点向上这条线段作为短板。

算出完全可选的碎片的长度之和以及不能完全选，左边右边最大次大延伸距离，更新答案。

时间复杂度$O(n\sum^2)$。

如果$n$比较小，那么暴力枚举上下边界，计算答案方法同上。

时间复杂度$O(n^2\sum)$。

总时间复杂度$O(n\sum\sqrt{n\sum})$。

最后再用悬线法找出最大全$0$矩阵即可。

#include
     
      const int N=100010,M=320;int num,n,m,i,j,k,x,cnt,FL0,GL0,GL1,FL1,FR0,GR0,GR1,FR1,GL,GR,ans=-1,UP,DOWN,LEFT,RIGHT;bool vis[N];int all,seq[N],old;inline void ext(int x){  if(x<1||x>num)return;  if(vis[x])return;  vis[x]=1;  seq[++all]=x;}inline void up(int&f0,int&g0,int&f1,int&g1,int x,int y){  if(x>f0){f1=f0;g1=g0;f0=x;g0=y;return;}  if(x>f1){f1=x;g1=y;}}inline void uans(int x,int l,int r,int a,int b){  if(ans>=x)return;  ans=x;  UP=l,DOWN=r;  LEFT=a,RIGHT=b;}namespace NSMALL{int st[N],en[N],f[N],g[N],w[N];char a[M][N],b[M][N],s[N];void solve(){  for(i=1;i<=num;i++){    scanf("%d",&x);    st[i]=m+1;    en[i]=m+x;    for(j=1;j<=n;j++){      scanf("%s",s);      for(k=0;k
      
       x-1)f[k]=x-1;        for(x=en[k];x>=st[k];x--)if(a[j][x])break;        if(g[k]
       
        x-1)f[k]=x-1;        for(x=en[k];x>=st[k];x--)if(a[j][x])break;        if(g[k]
        
         f[j])f[j]=GL;    }else w[j]=0,f[j]=1,g[j]=m,GL=j+1;    for(GR=j=m;j;j--)if(!b[i][j]){      if(GR
         
          =st[k];x--)if(w[x]
          
           =st[k];x--)if(w[x]
           
            f[j])f[j]=GL; }else w[j]=0,f[j]=1,g[j]=m,GL=j+1; for(GR=j=m;j;j--)if(!b[i][j]){ if(GR
           
          
         
        
       
      
     

　　

D. Apres-ski

打表即可发现规律。

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

　　

E. Land in Krasnaya Polyana

建立二分图，将行放左边，列放右边，中间连$n\times m$条边，权值为$c[i][j]$，一共有$n+m$个点，而我们要选出$n+m$条边，因此答案就是最小生成环套外向森林。

类似最小生成树Kruskal算法，贪心选小的边，能加就加，用并查集维护每个连通块是否多了一条边。

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

#include
     
      #include
      
       const int N=1000010;int n,m,i,j,z,x,y,cnt,f[N],v[N];long long ans;struct E{int x,y,z;E(){}E(int _x,int _y,int _z){x=_x,y=_y,z=_z;}}e[N];inline bool cmp(const E&a,const E&b){return a.z
      
     

　　

F. Transfer

对于每个人求出他留在车上的概率，这等于他睡着的概率$+$他醒着的概率$+1-$他下车了并且没被叫回来的概率。

每个人下车了并且没被叫回来的概率可以用两次树形DP求出，时间复杂度$O(n)$。

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

　　

G. Building ski lifts

不断重复贪心配对即可。

#include 
     
      using namespace std ;typedef long long LL ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 105 ;const int MAXE = 100005 ;int G[MAXN][MAXN] ;int in[MAXN] , ou[MAXN] , a[MAXN] ;pair < int , int > p[MAXN] ;int cnt ;int n , m ;void solve () {	clr ( G , 0 ) ;	for ( int i = 1 ; i <= n ; ++ i ) {		in[i] = ou[i] = 0 ;		scanf ( "%d" , &a[i] ) ;	}	for ( int i = 1 ; i <= m ; ++ i ) {		int u , v ;		scanf ( "%d%d" , &u , &v ) ;		in[v] ++ ;		ou[u] ++ ;	}	if ( n == 1 ) {		printf ( "0\n0\n" ) ;		return ;	}	int sum = 0 , num = 0 ;	while ( 1 ) {		cnt = 0 ;		for ( int i = 1 ; i <= n ; ++ i ) {			if ( !in[i] || !ou[i] ) {				p[++ cnt] = pii ( a[i] , i ) ;			}		}		sort ( p + 1 , p + cnt + 1 ) ;		for ( int i = 1 ; i < cnt ; ++ i ) {			int u = p[i].second , v = p[i + 1].second ;			G[u][v] = 1 ;			sum += p[i + 1].first - p[i].first ;			num ++ ;			in[v] ++ ;			ou[u] ++ ;		}		int ok = 1 ;		for ( int i = 1 ; i <= n ; ++ i ) {			if ( !in[i] || !ou[i] ) ok = 0 ;		}		if ( ok ) break ;	}	printf ( "%d\n%d\n" , sum , num ) ;	for ( int i = 1 ; i <= n ; ++ i ) {		for ( int j = 1 ; j <= n ; ++ j ) {			if ( G[i][j] ) printf ( "%d %d\n" , i , j ) ;		}	}}int main () {	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;	return 0 ;}
     

　　

H. The lost key

留坑。