XIII Open Cup named after E.V. Pankratiev. GP of Azov Sea

时间：2021-07-23 14:34:53

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

建立二分图，将行放左边，列放右边，中间连$n\times m$条边，权值为$c[i][j]$，一共有$n+m$个点，而我们要选出$n+m$条边，因此答案就是最小生成环套外向森林。

类似最小生成树Kruskal算法，贪心选小的边，能加就加，用并查集维护每个连通块是否多了一条边。

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

#include<cstdio>

#include<algorithm>

const int N=1000010;

int n,m,i,j,z,x,y,cnt,f[N],v[N];long long ans;

struct E{int x,y,z;E(){}E(int _x,int _y,int _z){x=_x,y=_y,z=_z;}}e[N];

inline bool cmp(const E&a,const E&b){return a.z<b.z;}

int F(int x){return f[x]==x?x:f[x]=F(f[x]);}

int main(){

  scanf("%d%d",&n,&m);

  for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&z),e[++cnt]=E(i,j+n,z);

  std::sort(e+1,e+cnt+1,cmp);

  for(i=1;i<=n+m;i++)f[i]=i;

  for(i=1;i<=cnt;i++){

    x=F(e[i].x),y=F(e[i].y);

    if(v[x]&&v[y])continue;

    if(x!=y)v[y]|=v[x],f[f[x]]=f[y];else v[x]=1;

    ans+=e[i].z;

  }

  return printf("%lld",ans),0;

}

　　

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

留坑。

相关文章