A. Altitude

从小到大加入每个数，用set查找前驱和后继即可。

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

#include 
     
      using namespace std ;const int Maxn=100020,Inf=1e9;typedef pair
      
       pi;int n;int a[Maxn];vector
       
        V;set
        
         S;int ans,rep1,rep2,rep3;int caldis(int x,int y){	return y>x?(y-x):(y+n-x);}void ask(int loc){	if(!S.size())return ;	set
         
          ::iterator it=S.lower_bound(loc);	set
          
           ::iterator it2=it; for(int i=0;i<2;i++){ if(it2==S.begin()){it2=S.end();it2--;} else it2--; } int ret1=Inf,ret2=Inf,cs1,cs2; for(int i=0;i<5;i++){ int t1=caldis(*it2,loc); int t2=caldis(loc,*it2); if(t1
          
         
        
       
      
     

　　

B. Blocking Buffer

观察发现$\gcd(r,w)$都是可以达到的，于是欧几里得求一下即可。

#include 
     
      using namespace std ;const int Maxn=200020,Inf=1e9;typedef pair
      
       pi;typedef long long LL;bool solve(LL l,LL A,LL B){	if(l-B>=A-1)return 0;	LL gc=__gcd(A,B);	LL tmp=(l-B)/gc*gc;	while(tmp<=l-B)tmp+=gc;	if(tmp
       
        >l>>A>>B){	/*	set
        
         S;	LL cur=0;	bool flag=1;	S.insert(0);	while(1){		if(cur>l-B&&cur
         
          =A){			cur%=A;		}		else{			cur=(l-cur)/B*B+cur;		}		if(S.find(cur)!=S.end()){break;}	}	puts(flag?"OK":"DEADLOCK");	*/	puts(solve(l,A,B)?"DEADLOCK":"OK");	}	return 0 ;}
         
        
       
      
     

　　

C. Catch Me If You Can

留坑。

 

D. Demolition Time

留坑。

 

E. Economy Printing

将数字从小到大排序，那么第$i$个数要么自己作为开头，要么和$i-2$连接，要么和$i-1$连接，设$f[i][j][k]$表示考虑了前$i$个数，第$i-1$个数用操作$j$，第$i$个数用操作$k$时的最小串长，然后DP即可。

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

#include 
     
      using namespace std ;typedef pair < int , int > pii ;#define clr( a , x ) memset ( a , x, sizeof a )const int MAXN = 200005 ;const int INF = 0x3f3f3f3f ;int n ;int len[MAXN] ;int a[MAXN] ;int dp[MAXN][4][4] ;int f[MAXN] ;pii p[MAXN][4][4] ;int vis[MAXN] ;int calc ( int x ) {	int t = 0 ;	while ( x ) {		t ++ ;		x /= 10 ;	}	return t ;}void dfs ( int n , int x , int y ) {	if ( n == 1 ) return ;	int nx = p[n][x][y].first ;	int ny = x ;	f[n] = p[n][x][y].second ;	dfs ( n - 1 , nx , ny ) ;}int dfs2 ( int x ) {	vis[x] = 1 ;	if ( f[x] == 0 ) return x ;	return dfs2 ( f[x] ) ;}	void solve () {	for ( int i = 1 ; i <= n ; ++ i ) {		scanf ( "%d" , &a[i] ) ;	}	sort ( a + 1 , a + n + 1 ) ;	for ( int i = 1 ; i <= n ; ++ i ) {		len[i] = calc ( a[i] ) ;	}	clr ( f , 0 ) ;	clr ( p , 0 ) ;	clr ( dp , INF ) ;	dp[0][0][0] = 0 ;	for ( int i = 1 ; i <= n ; ++ i ) {		for ( int j = 0 ; j < 4 ; ++ j ) {			for ( int k = 0 ; k < 4 ; ++ k ) if ( dp[i - 1][j][k] != INF ) {				for ( int l = 0 ; l < 4 ; ++ l ) {					int tmp = dp[i - 1][j][k] + 1 + len[i] ;					if ( l ) tmp = tmp + 1 + len[i] ;					if ( l == 1 && a[i] % 2 == 0 ) continue ;					if ( l == 2 && a[i] % 2 == 1 ) continue ;					if ( dp[i][k][l] > tmp ) {						dp[i][k][l] = tmp ;						p[i][k][l] = pii ( j , 0 ) ;					}				}				if ( j == 1 || j == 2 ) {					if ( i > 2 && a[i] - a[i - 2] == 2 ) {						int tmp = dp[i - 1][j][k] + len[i] - len[i - 2] ;						if ( dp[i][k][j] > tmp ) {							dp[i][k][j] = tmp ;							p[i][k][j] = pii ( j , i - 2 ) ;						}					}				}				if ( k == 1 || k == 2 ) {					if ( i > 1 && a[i] - a[i - 1] == 2 ) {						int tmp = dp[i - 1][j][k] + len[i] - len[i - 1] ;						if ( dp[i][k][k] > tmp ) {							dp[i][k][k] = tmp ;							p[i][k][k] = pii ( j , i - 1 ) ;						}					}				}				if ( k == 3 ) {					if ( i > 1 && a[i] - a[i - 1] == 1 ) {						int tmp = dp[i - 1][j][k] + len[i] - len[i - 1] ;						if ( dp[i][k][k] > tmp ) {							dp[i][k][k] = tmp ;							p[i][k][k] = pii ( j , i - 1 ) ;						}					}				}			}		}	}	int ans = INF , x = -1 , y = -1 ;	for ( int i = 0 ; i < 4 ; ++ i ) {		for ( int j = 0 ; j < 4 ; ++ j ) {			if ( dp[n][i][j] < ans ) {				ans = dp[n][i][j] ;				x = i ;				y = j ;			}		}	}	dfs ( n , x , y ) ;	//printf ( "%d\n" , ans - 1 ) ;	clr ( vis , 0 ) ;	int flag = 0 ;	for ( int i = n ; i >= 1 ; -- i ) if ( !vis[i] ) {		int L = dfs2 ( i ) ;		if ( flag ) putchar ( ',' ) ;		flag = 1 ;		if ( L == i ) printf ( "%d" , a[i] ) ;		else {			printf ( "%d" , a[L] ) ;			if ( a[i] - a[f[i]] == 2 ) {				if ( a[i] % 2 == 0 ) putchar ( '%' ) ;				else putchar ( '#' ) ;			} else putchar ( '-' ) ;			printf ( "%d" , a[i] ) ;		}	}	puts ( "" ) ;}int main () {	while ( ~scanf ( "%d" , &n ) ) solve () ;	return 0 ;}
     

　　

F. Format

枚举有没有"^"符号，然后将字符分成三类：可选可不选、必须要选、必须不能选。

设$f[i]$表示处理完字典序最小的$i$个字符时的最短串长以及对应串长的字典序最小串，然后枚举往前延伸到哪里转移。

需要注意的是，如果全部字符都出现了，那么答案应该是%[^!]，需要特判。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef pair
          
           P;const int N=300;int n,i,j,v[N];char s[222222];P ans(N,""),f[N];inline bool check(char x){ if(x==' ')return 1; if(x>='0'&&x<='9')return 1; if(x>='a'&&x<='z')return 1; if(x>='A'&&x<='Z')return 1; return 0;}void dp(){ for(i=32;i<=126;i++){ f[i]=P(N,""); if(v[i]==0||v[i]==2){ P t=f[i-1]; f[i]=t; } if(v[i]==0||v[i]==1){ for(j=i;j>=32;j--){ if(v[j]==2)break; P t=f[j-1]; if(j==i){ t.first++; t.second.push_back(char(i)); }else if(j+1==i){ t.first+=2; t.second.push_back(char(j)); t.second.push_back(char(i)); }else{ t.first+=3; t.second.push_back(char(j)); t.second+="-"; t.second.push_back(char(i)); } f[i]=min(f[i],t); } } }}int main(){ fgets(s,111111,stdin); n=strlen(s); //0 : can choose and can not choose //1 : must choose //2 : mustn't choose for(i=32;i<=126;i++)v[i]=0; for(i=0;i
           
            1)ans=min(ans,f[126]);else ans=min(ans,P(2,"%[^!")); ans.second+="]"; cout<
            
             <
            
           
          
         
        
       
      
     

　　

G. Great Guest Gathering

分成$n$轮构造即可。

#include 
     
      using namespace std ;int n ;void solve () {	printf ( "%d %d %d\n" , 1 , 1 , 0 ) ;	for ( int i = 1 ; i < n ; ++ i ) {		for ( int j = i + 2 ; j <= n ; ++ j ) {			printf ( "%d %d %d\n" , j , j , i ) ;			printf ( "%d %d %d\n" , i , i , j ) ;		}		printf ( "%d %d %d\n" , i + 1 , i + 1 , i ) ;	}	for ( int i = n - 1 ; i >= 2 ; -- i ) {		printf ( "%d %d %d\n" , i , i , i + 1 ) ;	}	printf ( "%d %d %d\n" , 0 , 1 , 2 ) ;}int main () {	while ( ~scanf ( "%d" , &n ) ) solve () ;	return 0 ;}
     

　　

H. Hockey Cup

按题意模拟即可。

#include 
     
      using namespace std ;const int Maxn=200020,Inf=1e9;typedef pair
      
       pi;typedef long long LL;map
       
        Mp;string ts[]={"Russia","Sweden","Finland","NA"};int res[4][4][3];int sc[4][6];int g[4][4];int cmpop;bool cmp(int a,int b){	return sc[a][cmpop]>sc[b][cmpop];}void solve(vector
        
         &v,int ty){	if(v.size()<=2){		if(v.size()==1)return ;		if(v.size()==2){			if(!g[v[0]][v[1]])swap(v[0],v[1]);		}		return ;	}	cmpop=ty;	sort(v.begin(),v.end(),cmp);	vector
         
          rv;	for(int i=0,j;i
          

tmp; for(j=i;j