Codeforces Round #545 Div1 题解

2024-03-28 21:06:34

Codeforces Round #545 Div1 题解

A-Skyscrapers

题意

​ 给定一个 \(n∗m\) 的网格，每个格子里都有一个数，对于任意一行和任意一列，要求把这 \(n+m−1\) 个数重新用正整数编号，并且对于这一行，数与数之间的大小关系不变，对于这一列同理。求出任意一行和任意一列编号使用的最大编号的最小值。

题解

​ 首先对于每一行每一列单独离散化，记录每个位置在离散化之后的值，合并之后取较大的，剩下部分顺次编号即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,r[N],l[N],a[N][N],b[N][N],c[N][N];
int s[N],top;

int main()
{
        scanf( "%d%d",&n,&m );
        for ( int i=1; i<=n; i++ )
         for (  int  j = 1; j<=m; j++ )
                scanf( "%d",&a[i][j] );
        
        for ( int i=1; i<=n; i++ )
        {
                top=0;
                for ( int j=1; j<=m; j++ )
                        s[++top]=a[i][j];
                sort( s+1,s+1+top ); top=unique(s+1,s+1+top)-s-1;
                for ( int j=1; j<=m; j++ )
                        b[i][j]=lower_bound( s+1,s+1+top,a[i][j] )-s;
                r[i]=top;
        }
        for ( int i=1; i<=m; i++ )
        {
                top=0;
                for ( int j=1; j<=n; j++ )
                        s[++top]=a[j][i];
                sort( s+1,s+1+top ); top=unique(s+1,s+1+top)-s-1;
                for ( int j=1; j<=n; j++ )
                        c[j][i]=lower_bound( s+1,s+1+top,a[j][i] )-s;
                l[i]=top;
        }

        for ( int i=1; i<=n; i++,printf("\n") )
         for ( int j=1; j<=m; j++ )
         {
                 int ans1=max( r[i],max( l[j],b[i][j]+l[j]-c[i][j] ) );
                 int ans2=max( r[i],max( l[j],c[i][j]+r[i]-b[i][j] ) );
                 printf( "%d ",max( ans1,ans2 ) );
         }
}

B-Camp Schedule

题意

​ 给定两个 \(01\) 串 \(S\) 和 \(T\) ，把 \(S\) 打乱，使得 \(T\) 在其中出现次数最多。

题解

​ 对于 \(T\) 跑 \(KMP\) ,然后先建一次 \(T\) ，每次跳到 \(next\) 接着往后放即可

Code

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
char ch[N];
int n,m,nxt[N];

int main()
{
        scanf( "%s",ch+1 );
        for ( int i=1,l=strlen(ch+1); i<=l; i++ )
                if ( ch[i]=='0' ) n++;
                else m++;
        
        scanf( "%s",ch+1 ); int len=strlen(ch+1); nxt[1]=0;
        for ( int i=2; i<=len; i++ )
        {
                int tmp=nxt[i-1];
                while ( tmp && ch[tmp+1]!=ch[i] ) tmp=nxt[tmp];
                if ( !tmp )
                {
                        if ( ch[1]==ch[i] ) nxt[i]=1;
                        else nxt[i]=0;
                }
                else nxt[i]=tmp+1;
        }
        
        bool flag=1;
        for ( int i=1; i<=len; i++ )
                if ( ch[i]=='0' )
                {
                        if ( !n )  { flag=0; break; }
                        n--; printf( "0" );
                }
                else 
                {
                        if ( !m ) { flag=0; break; }
                        m--; printf( "1" );
                }
        while ( (n || m ) && flag )
        {
                for ( int i=nxt[len]+1; i<=len; i++ )
                        if ( ch[i]=='0' )
                        {
                                if ( !n )  { flag=0; break; }
                                n--; printf( "0" );
                        }
                        else 
                        {
                                if ( !m ) { flag=0; break; }
                                m--; printf( "1" );
                        }
        }
        while ( n-- ) printf( "0" );
        while ( m-- ) printf( "1" );
}

C-Museums Tour

题意

​ 给定一张 \(n\) 点的有向图，每个点有博物馆并给定每周开放状态，一周的长度为 \(d\) 天，在某一周的第一天从 \(1\) 出发，每条边边权为 \(1\) ，途中不能逗留，问最多可以访问几个博物馆。

题解

​ 首先根据时间拆点， \((i,j)\) 就是当前在城市 \(i\) ，星期 \(j\) ,对于原图 \(u\to v\),连边 \((u,i)\to (v,i \mod d+1)\)

​ 对这个图求 \(SCC\) ，统计每个里面有多少不同的博物馆。然后找一条从 \(1\) 开始的最长链即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int head[N],head2[N];
struct edge
{
	int nxt,ver,val;
}e1[N<<1],e2[N*2*50];
int tot,tot2,cnt,n,m,d,gcd,g[N],f[N][55],pre[N][55],deg[N],val[N],c[N];
int dfn[N],low[N],num,top,sta[N];
char v[N][55];
bool vis[N],ins[N];
vector<int> scc[N];

void add( int x,int y )
{
	tot++; e1[tot]=(edge){ head[x],y,0 }; head[x]=tot;
}

void add2( int x,int y,int z )
{
	tot2++; e2[tot2]=(edge){ head2[x],y,z }; head2[x]=tot2; deg[y]++;
}

void solve( int x,int p )
{
	val[x]=p; vis[x]=1;
	for ( int i=head[x]; i; i=e1[i].nxt )
	{
		int y=e1[i].ver;
		if ( c[y]!=cnt ) continue;
		if ( !vis[y] ) solve(y,p+1);
		else gcd=__gcd( gcd,abs(p+1-val[y]) );
	}
}

void tarjan( int x )
{
	dfn[x]=low[x]=++num; sta[++top]=x; ins[x]=1;
	for ( int i=head[x]; i; i=e1[i].nxt )
		if ( !dfn[e1[i].ver] ) tarjan( e1[i].ver ),low[x]=min( low[x],low[e1[i].ver] );
		else if ( ins[e1[i].ver] ) low[x]=min( low[x],dfn[e1[i].ver] );
	if ( dfn[x]==low[x] )
	{
		cnt++; int y;
		do
		{
			y=sta[top--]; ins[y]=0; c[y]=cnt; scc[cnt].push_back(y);
		}while ( x!=y );
		gcd=d; solve( x,0 ); g[cnt]=gcd;
		for ( int i=0; i<gcd; i++ )
		 for ( int j=0; j<scc[cnt].size(); j++ )
		  for ( int k=i; k<d; k+=gcd )
		  	if ( v[scc[cnt][j]][k]=='1' ) 
		  	{
		  		v[scc[cnt][j]][i]='1'; break;
			}
		for ( int i=0; i<gcd; i++ )
		 for ( int j=0; j<scc[cnt].size(); j++ )
		 	if ( v[scc[cnt][j]][(val[scc[cnt][j]]+i)%gcd]=='1' ) pre[cnt][i]++;
	}
}

void dp()
{
	int ans=0; memset( f,-0x3f,sizeof(f) );
	f[c[1]][0]=pre[c[1]][0]; queue<int> q;
	for ( int i=1; i<=cnt; i++ )
		if ( !deg[i] ) q.push(i);
	while ( !q.empty() )
	{
		int x=q.front(); q.pop();
		for ( int i=head2[x]; i; i=e2[i].nxt )
		{
			int y=e2[i].ver; deg[y]--;
			if ( deg[y]==0 ) q.push(y);
		}
		for ( int i=head2[x]; i; i=e2[i].nxt )
		 for ( int j=0; j<d; j++ )
		 {
		 	int y=e2[i].ver,z=e2[i].val;
		 	f[y][(z+j)%d]=max( f[y][(z+j)%d],f[x][j]+pre[y][(z+j)%g[y]] );
		 }
		for ( int i=0; i<d; i++ )
			ans=max( ans,f[x][i] );
	}
	printf( "%d",ans );
}

int main()
{
	scanf( "%d%d%d",&n,&m,&d );
	for ( int i=1,u,v; i<=m; i++ )
		scanf( "%d%d",&u,&v ),add( u,v );
	for ( int i=1; i<=n; i++ )
		scanf( "%s",v[i] );
	
	for ( int i=1; i<=n; i++ )
		if ( !dfn[i] ) tarjan( i );
	for ( int j=1; j<=n; j++ )
	 for ( int i=head[j]; i; i=e1[i].nxt )
	 {
	 	int y=e1[i].ver;
	 	if ( c[j]==c[y] ) continue;
	 	int d2=__gcd(g[c[j]],g[c[y]] );
	 	int d1=(val[j]-val[y]+1+d)%d;
	 	for ( int k=d1%d2; k<d; k+=d2 )
	 		add2( c[j],c[y],k );
	 }
	 
	dp();
}

D-Cooperative Game （交互题）

题意

​ 有一张图是由一个长度为 \(t\) 的链和一个大小为 \(c\) 的环中间连上一条边组成的。假如这条边连接的是链的右端点，和环上的 \(T\) 点。令链的左端点是 \(S\) 。
​ 现在在 \(S\) 处有 \(10\) 个棋子，编号 \(0−9\)，每次你可以让任意数量的棋子向出边方向走一步，交互库会返回若干个集合，每一个集合内的棋子都在同一个位置上，并且这个位置上的所有棋子都在这个集合中。
​ 现在你既不知道 \(t\) 也不知道 \(c\) 。你需要使用不超过 \(3(t+c)\) 次操作使得所有棋子都移动到T位置上并且返回交互库done。

题解

（第一次做交互题啊……）

​ 首先让两个棋子移动，一个每次操作都向前走，另外一个每两次操作才向前走。当两个棋子相遇时停止。
​ 把环按照 \(T\) 点开始沿出边方向标号。
​ 设当第二个棋子位于 \(T\) ，即 \(0\) 位置时，假设第一个棋子在 \(p\) 位置。
​ 因为第一个棋子每次比第二个棋子多走一步，距离差是 \(c−p\)。
​ 所以接下来第二个棋子要移动的步数就是 \(c−p\)。所以相遇时两个棋子在 \(c−p\) 位置。
​ 因为第二个棋子到达 \(T\) 时走了 \(t\) 步，此时第一个棋子走了 \(2t\) 步，即他在环上走了 \(t\) 步，所以有 \(t\mod c=p\)，那么让 \(10\) 个棋子同时向前走，当所有棋子位于同一个点时他们就同时到达了 \(T\) 。
​ 即这里还需要走 \(t\) 步，而这 \(t\) 步等价于在环上走了 \(p\) 步，那么 \(1,2\) 两个棋子就从 \(c−p\) 走到了 \(0\) 位置。

​ 注意输出要刷缓存，可以用 cout 或者是 fflush(stdout).

Code

#include <bits/stdc++.h>
using namespace std;
char ch[20];

int read()
{
        int x; scanf( "%d",&x );
        for ( int i=1; i<=x; i++ )
                scanf( "%s",ch );
        return x;
}

int main()
{
	while ( 1 )
	{
		cout<<"next 0"<<endl; read();
		cout<<"next 0 1"<<endl;
		int tot=read();
		if ( tot==2 ) break;
	}
	while ( 1 )
	{
		cout<<"next 0 1 2 3 4 5 6 7 8 9"<<endl;
		if ( read()==1 ) break; 
	}
        cout<<"done";
}

E-Train Car Selection

题意

​ 你有一列有 \(n\) 个车厢的火车，从车头开始 \(1−n\) 编号。
​ 现在有 \(3\) 种操作，第一种是在车头位置加入 \(k\) 节车厢，第二种位置是在车尾位置加入 \(k\) 节车厢，第三种是修改每节车厢的价值。
​ 价值定义为：一开始所有车厢的价值都是 \(0\) (包括中途加入的车厢)，然后每次修改会给定 \(s,b\)，如果当前车厢是从车头开始数的第 \(i\) 节，那么它的价值就会加上 \((i−1)∗s+b\) 。
​ 在每次操作结束之后回答价值最小的车厢的编号以及其价值。如果有多个输出编号最小的那个。

题解

​ 发现每次一起加入进来的东西只需要维护左端点就好了。
​ 首先如果在前端插入一段，那么后面全部都没用了，可以直接丢掉。
​ 否则在后面插入一段，维护一下当前全局加的一次函数是什么，那么每个左端点按照车厢编号+权值可以写成一个个的点，显然只有一个上凸壳才有用，那么维护这个上凸壳就行了。

Code

#include <bits/stdc++.h>
#define ll long long
#define PI pair<ll,ll>
using namespace std;
const int N=3e5+10;
PI p[N];
int n,m,r=1;
ll k=0,b=0;

double get_k( PI a,PI b )
{
        return 1.0*(a.second-b.second)/(a.first-b.first);
}

ll calc( PI x )
{
        return k*x.first+x.second+b;
}

int main()
{
        scanf( "%d%d",&n,&m );
        p[1]=make_pair( 0,0 ); r=1;
        while ( m-- )
        {
                int opt; scanf( "%d",&opt );
                if ( opt==1 ) 
                {
                        r=1; p[1]=make_pair( 0,0 ); k=b=0;
                        int tmp; scanf( "%d",&tmp ); n+=tmp;
                }
                else if ( opt==2 )
                {
                        PI now=make_pair( n,-(n*k+b) );
                        while ( r>1 && get_k(now,p[r])<=get_k( p[r],p[r-1] ) ) r--;
                        p[++r]=now; int tmp; scanf( "%d",&tmp ); n+=tmp; 
                }
                else
                {
                        int x,y; scanf( "%d%d",&x,&y );
                        b+=x; k+=y;
                }
                while ( r>1 && calc( p[r] )>=calc( p[r-1] ) ) r--;
                printf( "%lld %lld\n",p[r].first+1,calc(p[r]) );
        }
}
上一篇：1496. Path Crossing


下一篇：洛谷P1352 没有上司的舞会（树形DP+记忆化）