[数据结构与算法]Codeforces Round #741 div.2 A-D题解

视频讲解：TBD

A. The Miracle and the Sleeper

题目大意

给定两个正整数 $l,r(1\le l\le r\le 10^9)$ ，求满足 $r\ge a\ge b\ge l$ 的最大的 $a \mod{b} $ 。

题解

若 $l$ 足够小，那么 $a$ 应该取 $r$ ， $b$ 应该取 $?\frac{r+1}{2}?$ ，答案为 $?\frac{r?1}{2}?$ 。
若 $l$ 较大，那么 $a=r,b=l$ ，答案为 $r\mathrm{m}\mathrm{o}\mathrm{d}l$ 。
分界点为 $?\frac{r+1}{2}?$ 。

参考代码

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

int main()
{
	int T,l,r;
	cin>>T;
	while(T--)
	{
		cin>>l>>r;
		if(l<=(r+1)/2)
			cout<<(r-1)/2<<endl;
		else
			cout<<r-l<<endl;
	}
}

B. Scenes From a Memory

题目大意

给定一个十进制下不包含 $0$ 的整数 $n(1\le n<10^{50})$ ，删除最多的数字，使其变为非素数。

给定数据保证有解，若有多组解则输出任意一种即可。

题解

若包含 $1,4,6,8,9$ 之一，则直接输出一位数即可。
若包含 $2,5$ 之一且不为首位，则直接输出首位与 $2$ 或 $5$ 即可。
若包含两个 $3,7$ ，则直接输出 $33$ 或 $77$ 即可。
剩余只有 $37,73,237,273,537,573$ 这几种情况。由于保证必定有解，因此不存在 $37,73$ 这两种无解情况。对于剩余四种情况，显然 $27$ 或 $57$ 合法。

因此，答案必定为二位数，可以通过上述方式分类讨论，也可以直接枚举得到。

参考代码

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

int main()
{
	int T,sum[15],pos[15],i,j,k,flag;
	char s[55];
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&k);
		scanf("%s",&s);
		memset(sum,0,sizeof(sum));
		for(i=0;i<k;i++)
		{
			sum[s[i]-'0']++;
			pos[s[i]-'0']=i;
		}
		if(sum[1])
			printf("1\n1\n");
		else if(sum[4])
			printf("1\n4\n");
		else if(sum[6])
			printf("1\n6\n");
		else if(sum[8])
			printf("1\n8\n");
		else if(sum[9])
			printf("1\n9\n");
		else if(sum[2]&&pos[2]!=0)
			printf("2\n%c2\n",s[0]);
		else if(sum[5]&&pos[5]!=0)
			printf("2\n%c5\n",s[0]);
		else if(sum[3]>1)
			printf("2\n33\n");
		else if(sum[7]>1)
			printf("2\n77\n");
		else
		{
			flag=1;
			for(i=0;i<k&&flag;i++)
			{
				for(j=i+1;j<k;j++)
				{
					if((s[i]-'0'+s[j]-'0')%3==0)
					{
						printf("2\n%c%c\n",s[i],s[j]);
						flag=0;
						break;
					}
				}
			}
		}
	}
}

C. Rings

题目大意

有一个长度为 $n(2\le n\le 2?10^4)$ 仅由01构成的字符串 $s$ 。

定义函数 $f$ 表示将字符串视为二进制数后再转为十进制数的结果，例如 $f(001010)=10$ 。

你需要找到满足以下条件的两对整数 $(l_1,r_1),(l_2,r_2)$ ：

• $1\le l_1\le n,1\le r_1\le n,r_1?l_1+1\ge ?\frac{n}{2}?$
• $1\le l_2\le n,1\le r_2\le n,r_2?l_2+1\ge ?\frac{n}{2}?$
• 存在非负整数 $k$ ，满足 $f(s[l_1:r_1])=f(s[l_2:r_2])?k$

题解

由于是二进制下截取子串，因此考虑 $k=2$ 的情况。
若 $?i\in [?\frac{n}{2}?+1,n],s[i]=0$ 则存在合法情况 $(l_1,r_1)=(1,i),(l_2,r_2)=(1,i?1),k=2$ 。

当不存在上述 $i$ 时，则表示 $s$ 后半段全为 $1$ 。
若 $s[?\frac{n}{2}?]=0$ ，则存在合法情况 $(l_1,r_1)=(?\frac{n}{2}?,n),(l_2,r_2)=(?\frac{n}{2}?+1,n),k=1$ 。
若 $s[?\frac{n}{2}?]=1$ ，则存在合法情况 $(l_1,r_1)=(?\frac{n}{2}?,n?1),(l_2,r_2)=(?\frac{n}{2}?+1,n),k=1$ 。

参考代码

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

const int MAXN=20020;
char s[MAXN];

int main()
{
	int T,n,flag,i;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		scanf("%s",s+1);
		flag=0;
		for(i=n/2+1;i<=n;i++)
		{
			if(s[i]=='0')
			{
				printf("%d %d %d %d\n",1,i,1,i-1);
				flag=1;
				break;
			}
		}
		if(!flag)
		{
			if(s[n/2]=='0')
				printf("%d %d %d %d\n",n/2,n,n/2+1,n);
			else
				printf("%d %d %d %d\n",n/2,n-1,n/2+1,n);
		}
	}
}

D1+D2. Two Hundred Twenty One

题目大意

有一个长度为 $n(1\le n\le 3?10^5)$ 的仅由±组成的字符串 $s$ ，其中+可以视为 $1$ ，-可以视为 $?1$ 。字符串合法的条件是奇数位之和等于偶数位之和，即 ${\sum }_{i=1}^n(?1{)}^{i?1}{s}_i=0$ 。

有 $q(1\le q\le 3?10^5)$ 次询问，每次给定区间 $[l,r](1\le l\le r\le n)$ ，求最少需要删除多少字符，才能使得子串 $s[l,r]$ 合法。

对于Easy Version，只需输出删除数量。
对于Hard Version，还需输出删除方案。

题解

定义字符串 $s$ 的权值为 ${\sum }_{i=1}^{|s|}(?1{)}^{i?1}{s}_i$
设 $su{m}_i$ 表示子串 $s[1,i]$ 的权值。
在子串 $s[l,r]$ 中删除字符 $s_i$ ，则表示对 $s[i+1,r]$ 部分的子串权值取相反数。
由于 $su{m}_i$ 在整数上连续，因此不妨设 $f(i)$ 表示 $s[l,r]$ 删除 $s_i$ 后的权值：
$$f(i)=su{m}_{i?1}?su{m}_{l?1}?(su{m}_r?su{m}_i)$$
易得
$$f(i+1)?f(i)=su{m}_{i+1}?su{m}_{i?1}$$

因此 $f(i+1)?f(i)$ 的值必定为 $0$ 或 $\pm 2$ 。
且
$$f(l)=?su{m}_r+su{m}_l$$

$$f(r)=su{m}_{r?1}?su{m}_{l?1}=?f(l)?s_r+s_l$$

易得 $f(r)+s_r$ 与 $f(l)?s_l$ 互为相反数。
若 $f(r)\ge 2$ 则 $f(l)\le 0$ 。
若 $f(r)\le ?2$ 则 $f(l)\ge 0$ 。
若 $f(r)=0$ 则直接找到解。
$f(r)=\pm 1$ 则无解。
因此

• 当 $f(r)$ 为偶数时，由于连续函数性质，必定存在 $f(i)=0$ 。
• 当 $f(r)$ 为奇数时，无解。

对于Easy version，

• 若 $su{m}_r?su{m}_{l?1}=0$ 则不用删除字符。
• 若 $su{m}_r?su{m}_{l?1}$ 为奇数，根据 $f(i)$ 的性质，必定存在 $i$ 满足 $su{m}_r?su{m}_i=su{m}_{i?1}?su{m}_{l?1}$ ，因此删除一个字符。
• 若 $su{m}_r?su{m}_{l?1}$ 为偶数，则删除任意一个字符（例如 $s_l$ ）后即可转化为前一种问题。因此删除两个字符。

对于Hard version，
我们需要寻找满足 $su{m}_r?su{m}_i=su{m}_{i?1}?su{m}_{l?1}$ 的 $i$ ，将式子变化为：
$$su{m}_r+su{m}_{l?1}=su{m}_i+su{m}_{i?1}$$

因此可以将每个 $i$ 放入 $su{m}_i+su{m}_{i?1}$ 的桶中统计，由于必定有解，因此查找时直接在对应桶中二分查找 $[l,r]$ 区间内的 $i$ 即可。

注意 $su{m}_i+su{m}_{i?1}$ 可能为负，因此需要加偏移量 $B=2n$ 。

参考代码

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

const int MAXN=300300;
const int B=MAXN<<1;
char s[MAXN];
int sum[MAXN];
vector<int> vec[MAXN<<2];

int main()
{
	int T,n,q,i,l,r,dif,x,id;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&q);
		scanf("%s",s+1);
		for(i=B-2*n;i<=B+2*n;i++)
			vec[i].clear();
		for(i=1;i<=n;i++)
		{
			if(i&1)
				sum[i]=sum[i-1]+(s[i]=='+'?1:-1);
			else
				sum[i]=sum[i-1]-(s[i]=='+'?1:-1);
			vec[sum[i]+sum[i-1]+B].push_back(i);
		}
		while(q--)
		{
			scanf("%d%d",&l,&r);
			dif=sum[r]-sum[l-1];
			if(dif==0)
				printf("0\n");
			else
			{
				if(dif%2)
					printf("1\n");
				else
				{
					printf("2\n");
					printf("%d ",l);
					l++;
				}
				x=sum[r]+sum[l-1]+B;
				id=lower_bound(vec[x].begin(),vec[x].end(),l)-vec[x].begin();
				printf("%d\n",vec[x][id]);
			}
		}
	}
}

E. Rescue Niwen!

题目大意

TBD

题解

参考代码

F. Tubular Bells

题目大意

TBD

题解

参考代码