A. Avengers, The

留坑。

 

B. Black Widow

将所有数的所有约数插入set，然后求mex。

#include
     
      using namespace std;typedef long long LL;typedef pair
      
       pi;const int mod=1e9+7;int n,i,x;set
       
        T;inline void add(int n){  for(int i=1;i<=n/i;i++)if(n%i==0){    T.insert(i);    T.insert(n/i);  }}int main(){  scanf("%d",&n);  while(n--)scanf("%d",&x),add(x);  for(i=1;;i++)if(T.find(i)==T.end())break;  printf("%d",i);  return 0;}
       
      
     

　　

C. Chitauri

海盗分金问题，倒着递推即可。

#include
     
      using namespace std;typedef pair
      
       pi;int n,k;int rep[1020];int a[1020][1020];int main(){	while(scanf("%d%d",&n,&k)!=EOF){		for(int i=1;i<=n;i++){			if(i==1){				a[i][1]=k;				continue;			}			vector
       
        V;			for(int j=1;j
        
         =1;i--){			if(a[i][i]!=-1){				for(int j=1;j<=i;j++)rep[j]=a[i][j];				break;				}			else rep[i]=-1;		}		for(int i=n;i>=1;i--)printf("%d%c",rep[i],i==1?'\n':' ');	}}
        
       
      
     

　　

D. Dr. Banner

DP，$f[i][j]$表示填了$i$层，最后一层是$j$的方案数，状态数只有$O(n)$个，转移用前缀和优化。

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

#include
     
      using namespace std;typedef long long LL;typedef pair
      
       pi;const int mod=1e9+7;int dp[2][100020];void up(int &x,int y){	x+=y;if(x>=mod)x-=mod;}int main(){	int n;	scanf("%d",&n);	int lim=n,cs=0;	dp[0][n]=1;	int ans=1;	for(;lim;lim/=2,cs^=1){		memset(dp[cs^1],0,sizeof dp[cs^1]);		for(int i=1;i<=lim;i++){			up(dp[cs^1][i/2],dp[cs][i]);		}		for(int i=lim/2;i>=1;i--){			dp[cs^1][i]=(dp[cs^1][i]+dp[cs^1][i+1])%mod;			up(ans,dp[cs^1][i]);		}	}	printf("%d\n",ans);}
      
     

　　

E. Egocentric Loki

根据题意判断是否有点介于三角形和外接圆之间即可。

#include 
     
      using namespace std ;const int MAXN = 100005 ;const double eps = 1e-8 ;int sgn ( double x ) {	return ( x > eps ) - ( x < -eps ) ;}struct P {	double x , y ;	P () {}	P ( double x , double y ) : x ( x ) , y ( y ) {}	P operator + ( const P& p ) const {		return P ( x + p.x , y + p.y ) ;	}	P operator - ( const P& p ) const {		return P ( x - p.x , y - p.y ) ;	}	double operator * ( const P& p ) const {		return x * p.y - y * p.x ;	}	P operator * ( const double& v ) const {		return P ( x * v , y * v ) ;	}	P operator / ( const double& v ) const {		return P ( x / v , y / v ) ;	}	P rot90 () {		return P ( -y , x ) ;	}	void input () {		scanf ( "%lf%lf" , &x , &y ) ;	}	double len () {		return x * x + y * y ;	}} a[MAXN][3] ;int n ;double cross ( P a , P b ) {	return a * b ;}int line_intersection ( P a , P b , P p , P q , P& o ) {	double U = cross ( p - a , q - p ) ;	double D = cross ( b - a , q - p ) ;	o = a + ( b - a ) * ( U / D ) ;	return 1 ;}int check ( P a , P b , P c , P p ) {	int t1 = sgn ( cross ( p - b , p - a ) ) ;	int t2 = sgn ( cross ( p - c , p - b ) ) ;	int t3 = sgn ( cross ( p - a , p - c ) ) ;	if ( t1 >= 0 && t2 >= 0 && t3 >= 0 ) return 1 ;	if ( t1 <= 0 && t2 <= 0 && t3 <= 0 ) return 1 ;	return 0 ;}void solve () {	for ( int i = 1 ; i <= n ; ++ i ) {		for ( int j = 0 ; j < 3 ; ++ j ) {			a[i][j].input () ;		}	}	for ( int i = 1 ; i <= n ; ++ i ) {		P x1 = ( a[i][0] + a[i][1] ) / 2 ;		P y1 = ( a[i][0] - a[i][1] ) ;		y1 = y1.rot90 () ;		y1 = y1 + x1 ;		P x2 = ( a[i][1] + a[i][2] ) / 2 ;		P y2 = ( a[i][1] - a[i][2] ) ;		y2 = y2.rot90 () ;		y2 = y2 + x2 ;		P o ;		line_intersection ( x1 , y1 , x2 , y2 , o ) ;		double r = ( o - a[i][0] ).len () ;		for ( int j = 1 ; j <= n ; ++ j ) if ( i != j ) {			for ( int k = 0 ; k < 3 ; ++ k ) {				if ( ( o - a[j][k] ).len () + eps < r ) {					if ( check ( a[i][0] , a[i][1] , a[i][2] , a[j][k] ) == 0 ) {						printf ( "NO\n" ) ;						return ;					}				}			}		}	}	printf ( "YES\n" ) ;}int main () {	while ( ~scanf ( "%d", &n ) ) solve () ;	return 0 ;}
     

　　

F. Fury

求出SCC，每个SCC可以用一个环连接，外面DAG部分贪心选边即可。

#include 
     
      using namespace std ;typedef pair < int , int > P ;const int N = 305 ;const int M = 1000005 ;P b[M] ;vector < int > G[N] , V[N] ;int n , m ;int Q[N] , t ;int S[N] , siz ;int vis[N] ;int ans ;int scc[N]; int fa[N] ;namespace BZOJ {	int i , j , x , y , d[N],g[N],g2[N],v[M],v2[M],nxt[M],nxt2[M],ed,h,t,q[N];	bitset
      
       f[N];	void add(int x,int y){d[y]++;v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}	void add2(int x,int y){v2[++ed]=y;nxt2[ed]=g2[x];g2[x]=ed;}	void solve(int n){		for(i=1;i<=n;++i)f[i][i]=1;		for(ed=0,i=h=1;i<=n;++i)if(!d[i])q[++t]=i;		while(h<=t)for(i=g[x=q[h++]];i;add2(v[i],x),i=nxt[i])if(!(--d[v[i]]))q[++t]=v[i];		for(i=1;i<=n;++i)for(j=g2[x=q[i]];j;f[x]|=f[v2[j]],j=nxt2[j]){			if(!f[x][v2[j]])b[++ans]=P(fa[v2[j]],fa[x]);		}	}}void dfs1 ( int u ) {	vis[u] = 1 ;	for ( int i = 0 ; i < G[u].size () ; ++ i ) if ( !vis[G[u][i]] ) dfs1 ( G[u][i] ) ;	Q[++ t] = u ;}void dfs2 ( int u , int f ) {	scc[u] = f ;	vis[u] = 0 ;	S[++ siz] = u ;	for ( int i = 0 ; i < V[u].size () ; ++ i ) if ( vis[V[u][i]] ) dfs2 ( V[u][i] , f ) ;}void solve () {	for ( int i = 1 ; i <= n ; ++ i ) {		G[i].clear () ;	}	for ( int i = 1 ; i <= m ; ++ i ) {		int u , v ;		scanf ( "%d%d" , &u , &v ) ;		G[u].push_back ( v ) ;		V[v].push_back ( u ) ;	}	for ( int i = 1 ; i <= n ; ++ i ) if ( !vis[i] ) dfs1 ( i ) ;	int cnt = 0 ;	ans = 0 ;	for ( int i = n ; i >= 1 ; -- i ) if ( vis[Q[i]] ) {		++ cnt ;		siz = 0 ;		fa[cnt] = Q[i] ;		dfs2 ( Q[i] , cnt ) ;		if ( siz > 1 ) {			for ( int j = 1 ; j < siz ; ++ j ) {				b[++ ans] = P ( S[j] , S[j + 1] ) ;			}			b[++ ans] = P ( S[siz] , S[1] ) ;		}	}	for ( int i = 1 ; i <= n ; ++ i ) {		//printf ( "scc[%d] = %d\n" , i , scc[i] ) ;	}	for ( int i = 1 ; i <= n ; ++ i ) {		for ( int j = 0 ; j < G[i].size () ; ++ j ) {			int v = G[i][j] ;			if ( scc[i] != scc[v] ) {				BZOJ :: add ( scc[i] , scc[v] ) ;			}		}	}	BZOJ :: solve ( cnt ) ;	printf ( "%d %d\n" , n , ans ) ;	for ( int i = 1 ; i <= ans ; ++ i ) {		printf ( "%d %d\n" , b[i].first , b[i].second ) ;	}}int main () {	while ( ~scanf ( "%d%d", &n , &m ) ) solve () ;	return 0 ;}
      
     

　　

G. Groot

猜对题意即可。

#include 
     
      using namespace std ;const int MAXN = 100005 ;char s[MAXN] ;void solve () {	int cnt = 0 ;	for ( int i = 0 ; s[i] ; ++ i ) {		if ( s[i] == '!' ) ++ cnt ;	}	if ( !cnt ) printf ( "Pfff\n" ) ;	else {		printf ( "W" ) ;		while ( cnt -- ) printf ( "o" ) ;		printf ( "w\n" ) ;	}}int main () {	while ( fgets ( s , MAXN , stdin ) ) solve () ;	return 0 ;}
     

　　

H. Heimdall

留坑。

 

I. Iron Man

留坑。

 

J. Jarvis

任意一条边$(u,v)$的增量都可以表示成$d[1][v]-d[1][u]$，高斯消元即可。

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

 

K. KSON

大模拟。

　

---

总结：

• 要尽快适应读题场。