Educational Codeforces Round 94 简要题解

A.String Similarity

题目链接

构造题。

我们观察到，长度为 $2n-1$ 的串只有 $n$ 个长度为 $n$ 的子串。

不难想到让构造出的串每一位与这n个串中的不同位分别相等。

方便构造，可以取第一个串的第一位，第二个的第二位……

那么对应到原串，构造出的串的第 $k$ 位为原串的第 $2k-1$ 位。

Code

B.RPG Protagonist

题目链接

阴间题。没有二分，递推等高级算法，纯枚举+模拟。

我们可以枚举第一个人选$s$的个数。

那么他剩余的空间肯定用来选$w$。

设第一个人选完后剩下的$s$和$w$的个数分别为 $cs,cw$。

那么问题转化成了第二个人在 $cs,cw$ 中选的最大个数。

简单贪心，先考虑最小体积的，再放最大的。

模拟即可。

为了方便，我们可以在枚举前确定 $w$ 和 $s$ 的大小关系，然后枚举较小者。

Code

C.Binary String Reconstruction

题目链接

根据逻辑运算，在s中为0的位置i，原串中i-x，i+x必定为0。（若存在）

那么可以根据这一性质，先把 $0$ 的位置前后+，-x的位置确定。

再枚举 $1$ 的位置，若前后都是0，那么无解。

如果有解，那么把未确定的部分都赋值为1，一定是一个解的方案。

Code

D.Zigzags

题目链接

我们可以先枚举第一个区间 $[i,j]$ ，保证 $a_i=a_j$ 。

那么问题转化成在 $(i,j)$ 和 $(j,n]$ 间，相等的数字对数。

我们可以预处理出在 $[1,j]$ 和 $[1,n]$ 间，相等的数字对数 $s[j][n]$

若要提取给定区间，可以运用差分思想减去 $s[i][n]$ 和 $s[j-1][j]$ 。

相当于去除了 $[1,i]$ 和 $[1,j]$ 对答案的贡献。

根据容斥，还要加上 $s[i][j]$ 。

受到P6006的启发，这就是一个二维前缀和。

那么我们就可以 $O(1)$ 回答了。

记得开longlong。

Code

E.Clear the multiset

题目链接

贪心+分治。

每次进行一次操作后，原问题都转化成了一个新的子问题，可以分治解决。

如果只有第一种方式，那么我们贪心选择能选的最大数字和宽度。

这样做一定比其他方式更优或不劣。

找到最大的连通区域，减去最大数字后递归求解。

再考虑第二种方式，对于任意一个区间操作次数均为 $r-l+1$ 。

将两者取min，就得到了当前问题的最优解法。

得到了子问题的最优方案，便可以归并求得最终答案。

l=r时为边界，如果非0则操作次数为1，否则为0.

Code:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
int n;
int h[5009];

inline int solve(int l,int r,int H)
{
	if(l==r) return h[l]?1:0;
	int minn=0x7f7f7f7f,res=0;
	for(int i=l;i<=r;i++) minn=min(minn,h[i]);
	res+=minn-H;
	int p;
	for(int i=l;i<=r;i=p+1)
	{
		p=i;
		if(h[i]==minn) continue;
		for(int j=i+1;j<=r;j++)
		{
			if(h[j]==minn) break;
			p=j;
		}
		res+=solve(i,p,minn);
	} 
	return min(res,r-l+1);
}

signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
	printf("%lld\n",solve(1,n,0));
	return 0;
}