首页 > 代码库 > XIII Open Cup named after E.V. Pankratiev. GP of Azov Sea
XIII Open Cup named after E.V. Pankratiev. GP of Azov Sea
A. Freestyle
如果逆序对为$0$，那么先手必败。
因为每次只能翻转长度为$4k+2$和$4k+3$的区间，所以每次操作之后逆序对的奇偶性一定会发生改变。
因此如果逆序对个数为偶数，则先手必败。
#include<stdio.h>#include<algorithm>#include<math.h>#include<string.h>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<time.h>#include<assert.h>#include<iostream>using namespace std;typedef long long LL;typedef pair<int,int>pi;int a[233];int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",a+i); int tot=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(a[i]<a[j])tot^=1; } } puts(tot?"First":"Second"); return 0;}
B. Checkout lines
从后往前贪心构造。
#include <bits/stdc++.h>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<cstdio>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;k++)a[j][k+st[i]]=s[k]-‘0‘; } m+=x; } for(i=1;i<=m;i++)f[i]=1,g[i]=m,w[i]=0; for(i=1;i<=n;i++){ for(k=1;k<=num;k++)f[k]=en[k],g[k]=st[k]; for(j=i;j<=n;j++){ cnt=FL0=GL0=GL1=FL1=FR0=GR0=GR1=FR1=0; for(k=1;k<=num;k++){ for(x=st[k];x<=en[k];x++)if(a[j][x])break; if(f[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)g[k]=x+1; if(f[k]==en[k]){cnt+=en[k]-st[k]+1;continue;} up(FL0,GL0,FL1,GL1,f[k]-st[k]+1,k); up(FR0,GR0,FR1,GR1,en[k]-g[k]+1,k); } if(GL0!=GR0)uans((j-i+1)*(cnt+FL0+FR0),i,j,GR0,GL0);else{ uans((j-i+1)*(cnt+FL0+FR1),i,j,GR1,GL0); uans((j-i+1)*(cnt+FL1+FR0),i,j,GR0,GL1); } } } ext(LEFT); for(i=UP;i<=UP;i++){ for(k=1;k<=num;k++)f[k]=en[k],g[k]=st[k]; for(j=i;j<=n;j++){ cnt=FL0=GL0=GL1=FL1=FR0=GR0=GR1=FR1=0; for(k=1;k<=num;k++){ for(x=st[k];x<=en[k];x++)if(a[j][x])break; if(f[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)g[k]=x+1; if(f[k]==en[k]&&j==DOWN)ext(k); } } } ext(RIGHT); for(i=1;i<=num;i++)ext(i); m=0; for(i=1;i<=num;i++){ printf("%d%c",seq[i],i<num?‘ ‘:‘\n‘); for(j=1;j<=n;j++)for(k=st[seq[i]];k<=en[seq[i]];k++)b[j][m+k-st[seq[i]]+1]=a[j][k]; m+=en[seq[i]]-st[seq[i]]+1; } for(i=1;i<=m;i++)f[i]=1,g[i]=m,w[i]=0; ans=-1; for(i=1;i<=n;i++){ for(GL=j=1;j<=m;j++)if(!b[i][j]){ w[j]++; if(GL>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<g[j])g[j]=GR; uans(w[j]*(g[j]-f[j]+1),i-w[j]+1,f[j],i,g[j]); }else GR=j-1; } printf("%d %d %d %d",UP,DOWN,LEFT,RIGHT);}}namespace NBIG{int st[M],en[M],f[M],g[M],w[M];char a[N][M],b[N][M],s[M];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;k++)a[j][k+st[i]]=s[k]-‘0‘; } m+=x; } for(i=1;i<=m;i++)f[i]=1,g[i]=m,w[i]=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++)if(a[i][j])w[j]=0;else w[j]++; for(j=1;j<=m;j++)if(w[j]){ cnt=FL0=GL0=GL1=FL1=FR0=GR0=GR1=FR1=0; for(k=1;k<=num;k++){ for(x=st[k];x<=en[k];x++)if(w[x]<w[j])break; f[k]=x-1; for(x=en[k];x>=st[k];x--)if(w[x]<w[j])break; g[k]=x+1; if(f[k]==en[k]){cnt+=en[k]-st[k]+1;continue;} up(FL0,GL0,FL1,GL1,f[k]-st[k]+1,k); up(FR0,GR0,FR1,GR1,en[k]-g[k]+1,k); } if(GL0!=GR0)uans(w[j]*(cnt+FL0+FR0),i,j,GR0,GL0);else{ uans(w[j]*(cnt+FL0+FR1),i,j,GR1,GL0); uans(w[j]*(cnt+FL1+FR0),i,j,GR0,GL1); } } } ext(LEFT); for(i=1;i<=n;i++){ for(j=1;j<=m;j++)if(a[i][j])w[j]=0;else w[j]++; for(j=1;j<=m;j++)if(w[j]){ cnt=FL0=GL0=GL1=FL1=FR0=GR0=GR1=FR1=0; for(k=1;k<=num;k++){ for(x=st[k];x<=en[k];x++)if(w[x]<w[j])break; f[k]=x-1; for(x=en[k];x>=st[k];x--)if(w[x]<w[j])break; g[k]=x+1; if(f[k]==en[k])if(i==UP&&j==DOWN)ext(k); } } } ext(RIGHT); for(i=1;i<=num;i++)ext(i); m=0; for(i=1;i<=num;i++){ printf("%d%c",seq[i],i<num?‘ ‘:‘\n‘); for(j=1;j<=n;j++)for(k=st[seq[i]];k<=en[seq[i]];k++)b[j][m+k-st[seq[i]]+1]=a[j][k]; m+=en[seq[i]]-st[seq[i]]+1; } for(i=1;i<=m;i++)f[i]=1,g[i]=m,w[i]=0; ans=-1; for(i=1;i<=n;i++){ for(GL=j=1;j<=m;j++)if(!b[i][j]){ w[j]++; if(GL>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<g[j])g[j]=GR; uans(w[j]*(g[j]-f[j]+1),i-w[j]+1,f[j],i,g[j]); }else GR=j-1; } printf("%d %d %d %d",UP,DOWN,LEFT,RIGHT);}}int main(){ scanf("%d%d",&num,&n); uans(0,1,n,0,0); if(n<=315)NSMALL::solve();else NBIG::solve(); return 0;}
D. Apres-ski
打表即可发现规律。
#include<stdio.h>#include<algorithm>#include<math.h>#include<string.h>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<time.h>#include<assert.h>#include<iostream>using namespace std;typedef long long LL;typedef pair<int,int>pi;LL a[4];/*int dp[2][10][10][10];int dfs(int cur,int t1,int t2,int t3){ int &t=dp[cur][t1][t2][t3]; if(t>=0)return t;}*/int main(){ int n; while(scanf("%d",&n)!=EOF){ int res=0; for(int i=0;i<n;i++){ scanf("%lld",a+i); if(a[i]&1)res^=1; } sort(a,a+3); if(n<=2){ puts((!res)?"2":"1"); } else{ if(res&1){ puts("1"); } else{ if((a[0]&1)&&(a[0]+1==a[1]))puts("1"); else if((a[1]&1)&&(a[1]+1==a[2]))puts("1"); else puts("2"); } } } return 0;}
E. Land in Krasnaya Polyana
留坑。
F. Transfer
对于每个人求出他留在车上的概率，这等于他睡着的概率$+$他醒着的概率$+1-$他下车了并且没被叫回来的概率。
每个人下车了并且没被叫回来的概率可以用两次树形DP求出，时间复杂度$O(n)$。
#include<stdio.h>#include<algorithm>#include<math.h>#include<string.h>#include<string>#include<vector>#include<set>#include<map>#include<queue>#include<time.h>#include<assert.h>#include<iostream>using namespace std;typedef long long LL;typedef pair<int,int>pi;const int Maxn=50020;int n;int pa[Maxn],pb[Maxn],pc[Maxn];double ans;double dp1[Maxn],dp2[Maxn],val1[Maxn];vector<int>G[Maxn];void dfs1(int u,int p){ for(int i=0;i<G[u].size();i++){ int v=G[u][i];if(v==p)continue; dfs1(v,u); } dp1[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i];if(v==p)continue; dp1[u]*=(1.0-dp1[v]); } dp1[u]=1.0-dp1[u]; val1[u]=dp1[u]; dp1[u]=(pb[u]/100.0)+dp1[u]*(pc[u]/100.0);}double pre[Maxn],suf[Maxn];void dfs2(int u,int p){ //printf("u=%d val1=%.12f\n",u,val1[u]); ans+=(1-(1.0-dp2[u])*(1.0-val1[u]))*(pc[u]/100.0); pre[0]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i];if(v==p){pre[i+1]=pre[i];continue;} pre[i+1]=pre[i]*(1.0-dp1[v]); } suf[G[u].size()]=1; for(int i=G[u].size()-1;i>=0;i--){ int v=G[u][i];if(v==p){suf[i]=suf[i+1];continue;} suf[i]=suf[i+1]*(1.0-dp1[v]); } for(int i=0;i<G[u].size();i++){ int v=G[u][i];if(v==p)continue; dp2[v]=pb[u]/100.0+ pc[u]/100.0* (1.0-pre[i]*suf[i+1]*(1.0-dp2[u])); } for(int i=0;i<G[u].size();i++){ int v=G[u][i];if(v==p)continue; dfs2(v,u); }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d%d",pa+i,pb+i,pc+i),ans+=(pa[i]+pb[i])/100.0; //printf("ans=%.2f\n",ans); for(int i=1;i<n;i++){ int u,v;scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs1(1,0); dfs2(1,0); //for(int i=1;i<=n;i++)printf("%.12f ",dp2[i]);puts(""); printf("%.12f\n",n-ans); return 0;}
G. Building ski lifts
不断重复贪心配对即可。
#include <bits/stdc++.h>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
留坑。
XIII Open Cup named after E.V. Pankratiev. GP of Azov Sea
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。