A. Avengers, The

留坑。

?

B. Black Widow

將所有數的所有約數插入set，然后求mex。

#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int>pi; const int mod=1e9+7; int n,i,x; set<int>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<bits/stdc++.h> using namespace std; typedef pair<int,int>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<pi>V;for(int j=1;j<i;j++){V.push_back(pi(a[i-1][j]+1,-j));}sort(V.begin(),V.end());int ned=i/2,sum=0;if(i%2==0)ned--;for(int j=0;j<ned;j++){sum+=V[j].first;}if(k<sum){a[i][i]=-1;for(int j=1;j<i;j++)a[i][j]=a[i-1][j];} else{for(int j=1;j<=i;j++)a[i][j]=0;a[i][i]=k-sum;for(int j=0;j<ned;j++){a[i][-V[j].second]=V[j].first;}}}for(int i=n;i>=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<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int>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 <bits/stdc++.h> 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 <bits/stdc++.h> 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<N>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 <bits/stdc++.h> 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

大模擬。

　

---

總結：

• 要盡快適應讀題場。

?

轉載于:https://www.cnblogs.com/clrs97/p/6034511.html

總結

以上是生活随笔為你收集整理的XVI Open Cup named after E.V. Pankratiev. GP of Ekaterinburg的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。