Educational Codeforces Round 118 div.2 A-E题解_d. mex sequences

视频讲解：咕了 ，推荐看wls的视频题解 。

A. Long Comparison

题目大意

有两个数，它们都用同一种格式表示：一个正整数 $x(1\le x\le 10^6)$ ，后面附加 $p(0\le p\le 10^6)$ 个 $0$ 。
现在给定两个数，求他们的大小比较关系。

题解

由于 $1\le x\le 10^6$ ，因此若 $p$ 相差超过 $6$ ，则直接比较 $p$ 的大小。反之在 $p1,p2$ 都减去 $\min (p1,p2)$ 后，还原处原数进行比较。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
	int T;
	ll x1,x2,p1,p2;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld%lld%lld",&x1,&p1,&x2,&p2);
		if(p1+6<p2)
			puts("<");
		else if(p1>p2+6)
			puts(">");
		else
		{
			x1*=pow(10,max(0ll,p1-p2));
			x2*=pow(10,max(0ll,p2-p1));
			if(x1>x2)
				puts(">");
			else if(x1==x2)
				puts("=");
			else
				puts("<");
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

B. Absent Remainder

题目大意

给定长度为 $n(2\le n\le 2\cdot 10^5)$ 的互不相同的正整数序列 $a_1,a_2,...,a_n(1\le a_i\le 10^6)$ ，求 $\lfloor \frac{n}{2}\rfloor$ 对不同的正整数 对 $x,y$ ，满足以下条件：

• $x\ne y$ ；
• $x$ 和 $y$ 都在 $a$ 中出现；
• $x\mathrm{m}\mathrm{o}\mathrm{d}y$ 不在 $a$ 中出现；

注意，某些 $x$ 或 $y$ 可以属于不同对。
如果有多组解，输出任意一组即可。可以证明至少存在一个解。

题解

对 $a$ 从小到大排序后，易得 $a_i\mathrm{m}\mathrm{o}\mathrm{d}{a}_1<a_1$ ，即不在 $a$ 中出现。因此直接构造 $\lfloor \frac{n}{2}\rfloor$ 对 $(a_i,a_1)$ 即可，注意 $i>1$ 。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAXN=200200;
int a[MAXN];

int main()
{
	int T;
	int n,i;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		sort(a+1,a+n+1);
		for(i=2;i<=n/2+1;i++)
		{
			printf("%d %d\n",a[i],a[1]);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

C. Poisoned Dagger

题目大意

Monocarp在玩一个电脑游戏。在游戏种，他的角色必须杀死一条龙。战斗会持续 $100^{500}$ 秒，期间Monocarp会用毒匕首攻击龙 $n(1\le n\le 100)$ 次。第 $i$ 次攻击在战斗开始后第 $a_i(1\le a_i\le 10^9,a_i<a_{i+1})$ 秒发生。毒匕首本身不会对龙造成伤害，但会对龙施加中毒效果，在接下来 $k$ 秒内每秒造成 $1$ 点伤害（从龙被匕首刺伤的同一秒开始）。如果龙已经中毒，则会刷新持续时间。

已知龙有 $h(1\le h\le 10^{18})$ 点生命，如果在战斗中队龙造成至少 $h$ 点伤害，则会成功杀死这条龙。求杀死这条龙的情况下， $k$ 的最小值。

题解

二分答案，对于每个答案以 $O(n)$ 复杂度进行模拟。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAXN=110;
ll n,h,a[MAXN];

bool check(ll x)
{
	ll last=h-x;
	for(int i=1;i<=n;i++)
		last-=min(x,a[i]-a[i-1]);
	if(last<=0)
		return true;
	else
		return false;
}

int main()
{
	int T,i;
	ll lef,rig,mid;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld",&n,&h);
		for(i=1;i<=n;i++)
			scanf("%lld",&a[i]);
		a[0]=a[1];
		lef=1,rig=h;
		while(lef<=rig)
		{
			mid=(lef+rig)>>1;
			if(check(mid))
				rig=mid-1;
			else
				lef=mid+1;
		}
		printf("%lld\n",lef);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

D. MEX Sequences

题目大意

如果一个整数序列 $x_1,x_2,...,x_k$ 满足 $\forall i(1\le i\le k)$ ， $|x_i-MEX(x_1,x_2,...,x_i)|\le 1$ ，则称其为MEX正确。其中 $MEX(x_1,...,x_k)$ 表示不属于集合 $x_1,...,x_k$ 的最小非负整数。

现在给定一个长度为 $n(1\le n\le 5\cdot 10^5)$ 大小的非负整数序列 $a$ ，求其非空MEX正确的子序列有多少个，答案对 $998244353$ 取模。

题解

考虑合法子序列，只存在以下两种可能：

1. 不下降序列，即 $0...1...2...3...4...$
2. 前面是不下降序列，后面是在 $x$ 和 $x+2$ 间反复，即 $0...x...(x+2)...x...(x+2)...$

从左到右遍历序列，设

• $f_x$ 表示之前的序列中属于第一种情况的 $MEX$ 值为 $x$ 的子序列方案数；
• $g_x$ 表示之前的序列中属于第二种情况的 $MEX$ 值为 $x$ 的子序列方案数；

若当前遍历到 $a_i$ ，则以 $a_i$ 结尾的合法子序列对答案的贡献有以下几项：

• $MEX=a_i+1$ 的贡献 $f_{a_i}+f_{a_i+1}+g_{a_i+1}$ ；
• $MEX=a_i-1$ 的贡献 $f_{a_i-1}+g_{a_i-1}$ ；

添加以 $a_i$ 结尾的子序列贡献后， $f_x,g_x$ 有以下变化：

• $f_{a_i+1}+=f_{a_i+1}+f_{a_i}$
• $g_{a_i+1}+=g_{a_i+1}$
• $g_{a_i-1}+=g_{a_i-1}+f_{a_i-1}$

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAXN=500500;
const ll mod=998244353;
int a[MAXN];
ll f[MAXN],g[MAXN];

int main()
{
	int T,n,i;
	ll ans;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		memset(f,0,sizeof(ll)*(n+10));
		memset(g,0,sizeof(ll)*(n+10));
		f[0]=1;
		ans=0;
		for(i=1;i<=n;i++)
		{
			ans+=f[a[i]]+f[a[i]+1]+g[a[i]+1];
			f[a[i]+1]=(f[a[i]+1]*2ll+f[a[i]])%mod;
			if(a[i])
			{
				ans+=g[a[i]-1]+f[a[i]-1]%mod;
				g[a[i]-1]=(g[a[i]-1]*2ll+f[a[i]-1])%mod;
			}
			ans%=mod;
			g[a[i]+1]=g[a[i]+1]*2ll%mod;
		}
		printf("%lld\n",ans);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

E. Crazy Robot

题目大意

有一个 $n\ast m(1\le n,m\le 10^6,n\cdot m\le 10^6)$ 大小的网格，每个单元格是空的或被阻塞的。其中有个空的单元格内有一个实验室。超出网格边界的其他单元格都是被阻塞的。

有一个机器人从实验室中逃出，处于某个空的单元格中。你可以命令其向上下左右四个方向之一移动到相邻的单元格，但机器人不会听从指令，它会选择一个与命令方向不同的其他方向，且该方向上的单元格是空的。如果存在，则其会移动到那个方向，否则什么都不做。

现在希望机器人回到实验室。对于每个单元格，判断其能否被迫回到实验室。被迫是指，在机器人每一步后，都可以向其发送一个命令，无论机器人选择什么不同方向，最终都会回到实验室。

题解

对于一个格子来说，若其周围都是 ‘+’ 或 ‘L’ ，只有最多一个相邻格子是 ‘.’ ，则该格子也是 ‘+’ 。
当一个格子变为 ‘+’ 后，其周围格子也可能变成 ‘+’ 。
因此，采用BFS实现即可（不怕 $10^6$ 爆栈也可以用dfs）。

参考代码

#include <bits/stdc++.h>
typedef long long ll;
#define mkp make_pair
#define pii pair<int,int>
using namespace std;

const int MAXN=1000100;
const int g[2][4]={{-1,1,0,0},{0,0,-1,1}};
char mz[MAXN];
queue<pii> q;

int main()
{
	int T,n,m,x,y,i,j,nx,ny,d;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
			{
				scanf(" %c",&mz[i*m+j]);
				if(mz[i*m+j]=='L')
					q.push(mkp(i,j));
			}
		while(!q.empty())
		{
			pii now=q.front();
			q.pop();
			for(i=0;i<4;i++)
			{
				x=now.first+g[0][i];
				y=now.second+g[1][i];
				if(x>=0&&x<n&&y>=0&&y<m
					&&mz[x*m+y]=='.')
				{
					d=0;
					for(j=0;j<4;j++)
					{
						nx=x+g[0][j];
						ny=y+g[1][j];
						if(nx>=0&&nx<n&&ny>=0&&ny<m
							&&mz[nx*m+ny]=='.')
							d++;
					}
					if(d<=1)
					{
						mz[x*m+y]='+';
						q.push(mkp(x,y));
					}
				}
			}
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
				printf("%c",mz[i*m+j]);
			puts("");
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

F. Tree Coloring

题目大意

给定一棵包含 $n(2\le n\le 250000)$ 个节点的有根树，编号从 $1$ 到 $n$ ，根节点为 $1$ 号节点。

现在需要将所有节点染为 $1$ 到 $n$ 共 $n$ 种颜色，每种颜色恰好对应一个节点。设 $c_i$ 为节点 $i$ 的颜色， $p_i$ 是节点 $i$ 的父亲。如果不存在 $k(1<k\le n)$ 满足 $c_k=c_{p_k}-1$ ，则称该染色方案为漂亮的。

求所有漂亮的染色方案数，答案对 $998244353$ 取模。

题解

TBD

参考代码

1