526互联

Codeforces Round 910 (Div. 2)

发布时间 2023-11-24 10:35:02作者: 空気力学の詩

Preface

这场其实挺早之前就写完代码了，但一直没时间写博客（玩云顶新赛季玩的）

感觉F其实不难但为什么就是想不出来呢，感觉后面的题就是很难突破的说

A. Milica and String

分类讨论+枚举即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,n,k,sfx[N]; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%s",&n,&k,s+1),sfx[n+1]=0,i=n;i>=1;--i) sfx[i]=sfx[i+1]+(s[i]=='B');
		if (sfx[1]==k) { puts("0"); continue; } puts("1");
		if (sfx[1]<k)
		{
			for (i=1;i<=n;++i) if (i+sfx[i+1]==k) { printf("%d B\n",i); break; }
		} else
		{
			for (i=1;i<=n;++i) if (sfx[i+1]==k) { printf("%d A\n",i); break; }
		}
	}
	return 0;
}

B. Milena and Admirer

从后往前贪心地确定，在优先满足当前分裂次数最少的前提下，尽可能最大化分裂后最靠前的数

稍微推一下式子会发现，设当前数为\(x\)，下一个数的限制是\(y\)，则\(ans+=\lceil\frac{x}{y}\rceil-1,y=\lfloor\frac{x}{\lceil\frac{x}{y}\rceil}\rfloor\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		LL ans=0; int lst=a[n]; for (i=n-1;i>=1;--i)
		ans+=(a[i]+lst-1)/lst-1,lst=a[i]/((a[i]+lst-1)/lst);
		printf("%lld\n",ans);
	}
	return 0;
}

C. Colorful Grid

小清新构造题，令\(s=n-1+m-1\)，先判掉\(s>k\)的无解情况，同时发现若\(k-s\)是奇数也显然无解

那么剩下的就是根据\(k-s\)对\(4\)取模后的结果来分类讨论了，我们可以用如下的方式来构造前\(3\times 3\)的边

这样我们从\((1,1)\)到\((3,3)\)后可以走出任意一条长\(4m/4m+2\)的合法路径，然后再从\((3,3)\)走到\((n,m)\)即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=20;
int t,n,m,k,h[N][N],l[N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d%d",&n,&m,&k); int s=n-1+m-1;
		if (s>k||(k-s)%2==1) { puts("NO"); continue; }
		for (i=1;i<=n;++i) for (j=1;j<m;++j) h[i][j]=1;
		for (i=1;i<n;++i) for (j=1;j<=m;++j) l[i][j]=1;
		h[1][1]=h[1][2]=h[2][1]=h[2][2]=l[2][2]=l[2][3]=1;
		l[1][1]=l[1][2]=l[1][3]=h[3][2]=0;
		int lst=(k-s)%4==2?1:0; puts("YES");
		for (i=3;i<n;++i) lst^=1,l[i][3]=lst;
		for (j=3;j<m;++j) lst^=1,h[n][j]=lst;
		for (i=1;i<=n;++i) for (j=1;j<m;++j) printf("%c%c",h[i][j]?'R':'B'," \n"[j==m-1]);
		for (i=1;i<n;++i) for (j=1;j<=m;++j) printf("%c%c",l[i][j]?'R':'B'," \n"[j==m]);
	}
	return 0;
}

D. Absolute Beauty

要推清楚各种情况的话需要的精力比较多，后面实现就很简单了

这里给出一种解决绝对值问题的通用思路，即分类讨论所有项的符号，最后统一取\(\max\)

列出所有情况后会发现可能让答案变大的情形只有当选中\((i,j)\)，满足\(\max(a_i,b_i)<\min(a_j,b_j)\)，或者\(\max(a_j,b_j)<\min(a_i,b_i)\)的情形

以第一种情况为例，直接扫一遍维护\(\max(a_i,b_i)\)的最小值即可，总复杂度\(O(n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N],b[N];
inline int solve(void)
{
	int mi=1e9,ret=0; for (RI i=1;i<=n;++i)
	ret=max(ret,min(a[i],b[i])-mi),mi=min(mi,max(a[i],b[i])); return ret;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; LL sum=0; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		for (i=1;i<=n;++i) scanf("%d",&b[i]),sum+=abs(a[i]-b[i]);
		int dlt=solve(); reverse(a+1,a+n+1); reverse(b+1,b+n+1);
		dlt=max(dlt,solve()); printf("%lld\n",sum+2LL*dlt);
	}
	return 0;
}

E. Sofia and Strings

想到关键就很简单的一个题

考虑从左到右扫描\(t\)中的每个字符\(c\)，当我们要在\(s\)中找一个与它相同的字符匹配时，显然找最靠前的是最优的

然后考虑对于找到的位置之前的其它字符\(c'\)，如果\(c'<c\)就必须被删掉，否则可以把它移动到后面去下次再用

用\(26\)个deque模拟上述过程即可，总复杂度\(O(26\times n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m; char a[N],b[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d%s%s",&n,&m,a+1,b+1); deque <int> dq[26];
		for (i=1;i<=n;++i) dq[a[i]-'a'].push_back(i);
		bool flag=1; for (i=1;i<=m;++i)
		{
			if (dq[b[i]-'a'].empty()) { flag=0; break; }
			int pos=dq[b[i]-'a'].front(); dq[b[i]-'a'].pop_front();
			for (j=0;j<b[i]-'a';++j)
			while (!dq[j].empty()&&dq[j].front()<pos) dq[j].pop_front();
		}
		puts(flag?"YES":"NO");
	}
	return 0;
}

F. Vova Escapes the Matrix

其实一点不难的一个题，但为什么我就是想不到呢

首先对于Type1的情形，直接把所有空位填了即可；对于Type2的话就找到起点到出口的最短路，保留这上面的所有点即可

考虑Type3的情形要怎么处理，显然最后让起点刚好有\(2\)种出走方式是最优的

那么对于这种两条路径的问题，一般分析之后都会有相交的性质，这题也不例外

我们发现最后答案的构成一定形如：先从起点走到某个点，然后从该点恰好存在两条通向不同出口的路径

考虑怎么维护答案，难点在于维护后面那个东西，不过我们可以通过魔改BFS来求出到每个点的最近出口和次近出口

最后从起点出发再BFS一遍即可求出前者，最后枚举中转点即可

总复杂度\(O(n\times m)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005,INF=5e8,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
struct ifo
{
	int x,y,d;
	inline ifo(CI X=-1,CI Y=-1,CI D=INF)
	{
		x=X; y=Y; d=D;
	}
}f[N][N][2]; int t,n,m,sx,sy,f3[N][N]; char a[N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
		for (scanf("%s",a[i]+1),j=1;j<=m;++j) if (a[i][j]=='V') sx=i,sy=j;
		for (i=1;i<=n;++i) for (j=1;j<=m;++j) f[i][j][0]=f[i][j][1]=ifo(),f3[i][j]=INF;
		queue <ifo> q; for (i=1;i<=n;++i) for (j=1;j<=m;++j)
		if ((i==1||i==n||j==1||j==m)&&a[i][j]!='#')
		f[i][j][0]=ifo(i,j,0),q.push(ifo(i,j,0));
		int all=0; for (i=1;i<=n;++i) for (j=1;j<=m;++j) all+=a[i][j]=='.';
		while (!q.empty())
		{
			auto [x,y,tp]=q.front(); q.pop();
			for (i=0;i<4;++i)
			{
				int nx=x+dx[i],ny=y+dy[i];
				if (nx<1||nx>n||ny<1||ny>m||a[nx][ny]=='#') continue;
				if (f[nx][ny][0].d==INF) f[nx][ny][0]=f[x][y][tp],++f[nx][ny][0].d,q.push(ifo(nx,ny,0));
				else if ((f[nx][ny][0].x!=f[x][y][tp].x||f[nx][ny][0].y!=f[x][y][tp].y)&&f[nx][ny][1].d==INF)
				f[nx][ny][1]=f[x][y][tp],++f[nx][ny][1].d,q.push(ifo(nx,ny,1));
			}
		}
		if (f[sx][sy][0].d==INF) { printf("%d\n",all); continue; }
		if (f[sx][sy][1].d==INF) { printf("%d\n",all-f[sx][sy][0].d); continue; }
		q.push(ifo(sx,sy,f3[sx][sy]=0));
		while (!q.empty())
		{
			auto [x,y,d]=q.front(); q.pop();
			for (i=0;i<4;++i)
			{
				int nx=x+dx[i],ny=y+dy[i];
				if (nx<1||nx>n||ny<1||ny>m||a[nx][ny]=='#') continue;
				if (f3[nx][ny]==INF) q.push(ifo(nx,ny,f3[nx][ny]=d+1));
			}
		}
		int ret=INF; for (i=1;i<=n;++i) for (j=1;j<=m;++j)
		ret=min(ret,f3[i][j]+f[i][j][0].d+f[i][j][1].d);
		printf("%d\n",all-ret);
	}
	return 0;
}

Postscript

感觉好久没有按时打CF了，看来是越来越怠惰了呢