A. Within Arm's Reach

留坑。

 

B. Bribing Eve

枚举经过$1$号点的所有直线，统计直线右侧的点数，旋转卡壳即可。

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

#include
     
      #include
      
       #include
       
        using namespace std;const int N=2000010;const double eps=1e-7;int _,n,i,x,y,at_center,X,Y,j,m,inarea,online,ansmin,ansmax;struct P{  int x,y,z;  double o;  P(){}  P(int _x,int _y,int _z){    x=_x,y=_y;    z=_z;    o=atan2(y,x);  }}a[N],b[N];int s[N];inline bool cmp(const P&a,const P&b){return a.o
        
         =0)j++;    //printf("%d %d %d\n",b[i].x,b[i].y,b[i].z);    if(b[i].x<0||b[i].y>0)continue;    inarea=s[j]-s[i-1];    online=b[i].z;    if(i
        
       
      
     

　　

C. Candle Box

模拟。

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

　　

D. Dinner Bet

$f[i][j][k]$表示有$i$个仅属于第一个人的数字被选中，$j$个仅属于第二个人的数字被选中，$k$个属于两个人的数字被选中的期望次数。

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

　　

E. Passwords

建立AC自动机，$f[i][j][x][y][z]$表示串长为$i$，目前走到了$j$这个点，小写字母/大写字母/数字是否出现的方案数。

#include
     
      #include
      
       const int N=1010,P=1000003;int A,B,tot,son[N][26],fail[N],q[N],ban[N],ans,i,j,x,y,z,t,o;int n;char s[N];int f[22][N][2][2][2];//lower upper digitinline void up(int&x,int y){  x+=y;  if(x>=P)x-=P;}void insert(){  scanf("%s",s);  for(int l=strlen(s),x=0,i=0,w;i
      
     

　　

F. Performance Review

按权值排序之后树状数组维护dfs序即可。

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=100010;int n,i,x,a[N],b[N],q[N],g[N],nxt[N],root,j,st[N],en[N],dfn;int flag[N];ll bit[N],ans[N];inline bool cmp(int x,int y){return a[x]
       
        0)add(x,i);else root=i;  }  for(i=1;i<=n;i++)if(!flag[i])dfs(i);  for(i=1;i<=n;i++)q[i]=i;  sort(q+1,q+n+1,cmp);  for(i=1;i<=n;i=j){    for(j=i;j<=n&&a[q[i]]==a[q[j]];j++)ans[q[j]]=ask(en[q[j]])-ask(st[q[j]]-1);    for(j=i;j<=n&&a[q[i]]==a[q[j]];j++)modify(st[q[j]],b[q[j]]);  }  for(i=1;i<=n;i++)printf("%I64d\n",ans[i]);}
       
      
     

　　

G. Cairo Corridor

找出与四个边界都连通的连通块，然后枚举连通块里每个点，如果它不是割点，且去掉它之后剩余部分依旧与四个边界都连通，则无解。

#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 = 300005 ;const int mod = 13 ;const int INF = 0x3f3f3f3f ;struct Node {	int x , y , v ;	Node () {}	Node ( int x , int y , int v ) : x ( x ) , y ( y ) , v ( v ) {}} ;vector < int > G[MAXN] , now ;int dfn[MAXN] , low[MAXN] , dfs_clock ;int cut[MAXN] ;int vis[MAXN] ;int S[MAXN] , top ;int a[255][255] , b[255][255] ;int idx[255][255][2] , cnt ;Node is[MAXN] ;int num[4] ;//l r u dint p[MAXN] ;int n , m ;void tarjan ( int u , int pre ) {	int v ;	low[u] = dfn[u] = ++ dfs_clock ;	S[top ++] = u ;	int son = 0 , pre_cnt = 0 ;	for ( int i = 0 ; i < G[u].size () ; ++ i ) {		v = G[u][i] ;		if ( v == pre && pre_cnt == 0 ) {			pre_cnt ++ ;			continue ;		}		if ( !dfn[v] ) {			++ son ;			tarjan ( v , u ) ;			if ( low[u] > low[v] ) low[u] = low[v] ;			if ( u != pre && low[v] >= dfn[u] ) cut[u] = 1 ;		} else low[u] = min ( low[u] , dfn[v] ) ;	}	if ( u == pre && son > 1 ) cut[u] = 1 ;	-- top ;}int F ( int x ) {	return p[x] == x ? x : ( p[x] = F ( p[x] ) ) ;}void add ( int x , int y ) {	if ( is[x].v ) {		if ( b[is[x].x][is[x].y] ) return ;	} else {		if ( a[is[x].x][is[x].y] ) return ;	}	if ( is[y].v ) {		if ( b[is[y].x][is[y].y] ) return ;	} else {		if ( a[is[y].x][is[y].y] ) return ;	}	p[F ( x )] = F ( y ) ;	G[x].push_back ( y ) ;}void dfs ( int u , int f ) {	vis[u] = 1 ;	now.push_back ( u ) ;	for ( int i = 0 ; i < G[u].size () ; ++ i ) {		int v = G[u][i] ;		if ( v == f ) continue ;		if ( vis[v] ) continue ;		dfs ( v , u ) ;	}}int addval ( int x , int y , int v , int f ) {	if ( ( x + y ) % 2 == 0 ) {		if ( v == 0 && y == 1 ) num[0] += f ;		if ( v == 1 && y == m ) num[1] += f ;		if ( x == 1 ) num[2] += f ;		if ( x == n ) num[3] += f ;	} else {		if ( y == 1 ) num[0] += f ;		if ( y == m ) num[1] += f ;		if ( v == 0 && x == 1 ) num[2] += f ;		if ( v == 1 && x == n ) num[3] += f ;	}}int can_del ( int o ) {	int x = is[o].x , y = is[o].y , v = is[o].v , ok = 1 ;	addval ( x , y , v , -1 ) ;	if ( !num[0] || !num[1] || !num[2] || !num[3] ) ok = 0 ;	addval ( x , y , v , 1 ) ;	return ok ;}void solve () {	cnt = 0 ;	scanf ( "%d%d" , &n , &m ) ;	for ( int i = 1 ; i <= n ; ++ i ) {		for ( int j = 1 ; j <= m ; ++ j ) {			scanf ( "%1d%1d" , &a[i][j] , &b[i][j] ) ;			idx[i][j][0] = ++ cnt ;			is[cnt] = Node ( i , j , 0 ) ;			idx[i][j][1] = ++ cnt ;			is[cnt] = Node ( i , j , 1 ) ;		}	}	for ( int i = 1 ; i <= cnt ; ++ i ) {		G[i].clear () ;	}	for ( int i = 1 ; i <= cnt ; ++ i ) {		p[i] = i ;	}	for ( int i =  1 ; i <= n ; ++ i ) {		for ( int j = 1 ; j <= m ; ++ j ) {			add ( idx[i][j][0] , idx[i][j][1] ) ;			add ( idx[i][j][1] , idx[i][j][0] ) ;			if ( ( i + j ) % 2 == 0 ) {				if ( i < n ) add ( idx[i][j][0] , idx[i + 1][j][0] ) ;				if ( i > 1 ) add ( idx[i][j][0] , idx[i - 1][j][1] ) ;				if ( j > 1 ) add ( idx[i][j][0] , idx[i][j - 1][0] ) ;				if ( j > 1 ) add ( idx[i][j][0] , idx[i][j - 1][1] ) ;				if ( i < n ) add ( idx[i][j][1] , idx[i + 1][j][0] ) ;				if ( i > 1 ) add ( idx[i][j][1] , idx[i - 1][j][1] ) ;				if ( j < m ) add ( idx[i][j][1] , idx[i][j + 1][0] ) ;				if ( j < m ) add ( idx[i][j][1] , idx[i][j + 1][1] ) ;			} else {				if ( j < m ) add ( idx[i][j][0] , idx[i][j + 1][0] ) ;				if ( j > 1 ) add ( idx[i][j][0] , idx[i][j - 1][1] ) ;				if ( i > 1 ) add ( idx[i][j][0] , idx[i - 1][j][0] ) ;				if ( i > 1 ) add ( idx[i][j][0] , idx[i - 1][j][1] ) ;				if ( j < m ) add ( idx[i][j][1] , idx[i][j + 1][0] ) ;				if ( j > 1 ) add ( idx[i][j][1] , idx[i][j - 1][1] ) ;				if ( i < n ) add ( idx[i][j][1] , idx[i + 1][j][0] ) ;				if ( i < n ) add ( idx[i][j][1] , idx[i + 1][j][1] ) ;			}		}	}	clr ( dfn , 0 ) ;	clr ( low , 0 ) ;	clr ( cut , 0 ) ;	top = dfs_clock = 0 ;	for ( int i = 1 ; i <= cnt ; ++ i ) if ( !dfn[i] ) {		tarjan ( i , i ) ;	}	int ans = -1 ;	clr ( vis , 0 ) ;	for ( int i = 1 ; i <= cnt ; ++ i ) if ( F ( i ) == i ) {		if ( is[i].v ) {			if ( b[is[i].x][is[i].y] ) continue ;		} else {			if ( a[is[i].x][is[i].y] ) continue ;		}		now.clear () ;		clr ( num , 0 ) ;		dfs ( i , i ) ;		for ( int j = 0 ; j < now.size () ; ++ j ) {			int x = is[now[j]].x , y = is[now[j]].y , v = is[now[j]].v ;			addval ( x , y , v , 1 ) ;		}		if ( !num[0] || !num[1] || !num[2] || !num[3] ) continue ;		int ok = 1 ;		for ( int j = 0 ; j < now.size () ; ++ j ) {			if ( !cut[now[j]] ) {				if ( can_del ( now[j] ) ) {					ok = 0 ;					//break ;				}			}		}		if ( ok ) ans = max ( ans , ( int ) now.size () ) ;	}	if ( ans == -1 ) printf ( "NO MINIMAL CORRIDOR\n" ) ;	else printf ( "%d\n" , ans ) ;}int main () {	int T = 0 ;	scanf ( "%d" , &T ) ;	for ( int i = 1 ; i <= T ; ++ i ) {		//printf ( "Case #%d:\n" , i ) ;		solve () ;	}	if ( T ) return 0 ;	//while ( ~scanf ( "%d%d%d%d" , &n , &s , &t , &m ) ) solve () ;	return 0 ;}
     

　　

H. Pascal's Hyper-Pyramids

等价于找$D$个非负整数$x_1,x_2,...,x_D$，且和为$H-1$，答案为$\frac{(H-1)!}{x_1!x_2!...x_D!}$。

考虑爆搜，加上$x_i\leq x_{i+1}$以及可行性剪枝即可，计算答案可以分解质因数。

#include
     
      #include
      
       using namespace std;typedef unsigned long long ll;const int N=35;int n,m,i,j;int p[N],v[N],tot;int f[N][N],g[N],q[N];ll po[N][N];set
       
        T;void divide(int n){  int t=n;  for(int i=0;i
        
         m)return;    q[x]=i;    dfs(x+1,i,z+i);  }}int main(){  for(i=2;i
         
          ::iterator o=T.begin();o!=T.end();o++)printf("%I64u\n",*o);}
         
        
       
      
     

　　

I. The White Rabbit Pocket Watch

在模$13$意义下高斯消元求出每条边的长度，然后floyd即可。

#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 = 1005 ;const int mod = 13 ;const int INF = 0x3f3f3f3f ;int pm ( int x , int n ) {	int res = 1 ;	while ( n ) {		if ( n & 1 ) res = res * x % mod ;		x = x * x % mod ;		n >>= 1 ;	}	return res ;}int inv[MAXN] ;int val[MAXN] ;vector < int > G[MAXN] ;pii path[MAXN] ;int d[MAXN][MAXN] ;int a[MAXN][MAXN] ;int ans[MAXN] ;int cnt ;int n , s , t , m ;void gauss ( int n , int m ) {	int r = 0 , c = 0 ;	for ( ; r < n && c < m ; ++ c ) {		int tmpr = r ;		for ( int i = r ; i < n ; ++ i ) {			if ( a[i][c] ) tmpr = i ;		}		if ( !a[tmpr][c] ) continue ;		for ( int i = c ; i <= m ; ++ i ) {			swap ( a[r][i] , a[tmpr][i] ) ;		}		for ( int i = m ; i >= c ; -- i ) {			a[r][i] = a[r][i] * inv[a[r][c]] % mod ;		}		for ( int i = 0 ; i < n ; ++ i ) if ( i != r && a[i][c] ) {			for ( int j = m ; j >= c ; -- j ) {				a[i][j] = ( a[i][j] - a[r][j] * a[i][c] % mod + mod ) % mod ;			}		}		++ r ;	}}void solve () {	cnt = 0 ;	clr ( d , -1 ) ;	clr ( a , 0 ) ;	for ( int i = 0 ; i < MAXN ; ++ i ) {		G[i].clear () ;	}	for ( int i = 0 ; i < m ; ++ i ) {		scanf ( "%d" , &val[i] ) ;		int x , u , v ;		scanf ( "%d" , &x ) ;		for ( int j = 0 ; j < x ; ++ j ) {			scanf ( "%d" , &v ) ;			if ( j ) {				if ( d[u][v] == -1 ) {					d[u][v] = d[v][u] = cnt ++ ;					path[cnt] = pii ( u , v ) ;				}				G[i].push_back ( d[u][v] ) ;			}			u = v ;		}	}	for ( int i = 0 ; i < m ; ++ i ) {		for ( int j = 0 ; j < G[i].size () ; ++ j ) {			a[i][G[i][j]] ++ ;			a[i][G[i][j]] %= mod ;		}		a[i][cnt] = val[i] ;	}	gauss ( m , cnt ) ;	/*	for ( int i = 0 ; i < m ; ++ i ) {		for ( int j = 0 ; j < cnt ; ++ j ) {			printf ( "%d " , a[i][j] ) ;		}		printf ( "|%d\n" , a[i][cnt] ) ;	}	*/	clr ( d , INF ) ;	for ( int i = 1 ; i <= cnt ; ++ i ) {		int u = path[i].first , v = path[i].second , c = a[i - 1][cnt] ;		d[u][v] = d[v][u] = c ;	}	for(int i=1;i<=n;i++)d[i][i]=0;	for ( int k = 1 ; k <= n ; ++ k ) {		for ( int i = 1 ; i <= n ; ++ i ) {			for ( int j = 1 ; j <= n ; ++ j ) {				d[i][j] = min ( d[i][j] , d[i][k] + d[k][j] ) ;			}		}	}	printf ( "%d\n" , d[s][t] ) ;}int main () {	for ( int i = 1 ; i < mod ; ++ i ) {		inv[i] = pm ( i , mod - 2 ) ;	}	int T = 0 ;	//scanf ( "%d" , &T ) ;	for ( int i = 1 ; i <= T ; ++ i ) {		//printf ( "Case #%d:\n" , i ) ;		solve () ;	}	if ( T ) return 0 ;	while ( ~scanf ( "%d%d%d%d" , &n , &s , &t , &m ) ) solve () ;	return 0 ;}
     

　　

J. Risky Lottery

留坑。

 

K. Balls and Needles

并查集判环。

#include
     
      #include