社区讨论

WA13/50求条

ffeiyangyang
AT_abc300_f [ABC300F] More Holidays参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhjry4xi
此快照首次捕获于
2025/11/04 07:31
4 个月前
此快照最后确认于
2025/11/04 07:31
4 个月前
查看原帖
RT 以下是对您代码中变量名的详细解释，这些解释基于代码的逻辑和命名习惯：
全局变量 n: 表示输入字符串 a 的长度。 m: 表示字符串 a 需要被重复的次数以形成新字符串。 k: 表示在新字符串中可以替换的 'x' 的数量，以将其变为 'o'。 tot: 表示字符串 a 中 'x' 的总数。 ans: 用于存储最终答案的变量，即最长的连续 'o' 子串的长度。 l: 用于计算当前位置之前的连续 'o' 的数量（前缀和的一种形式）。 p: 在此代码中未使用。 q[10000002]: 存储每个 'x' 位置之前连续 'o' 的数量。 e[10000002]: 存储 'x' 在字符串 a 中的位置。 t: 表示 'x' 在字符串 a 中的总数（与 tot 相同，但命名不一致，可能会导致混淆）。 tt: 在此代码中未使用。 maxn: 用于存储当前找到的最长连续 'o' 子串的长度（在局部处理中）。 maxx: 在处理过程中，用于临时存储当前窗口内连续 'o' 的数量。 双端队列 deque qq: 一个双端队列，用于存储当前考虑的 'x' 的位置，以便在需要时快速添加或移除元素。 字符数组 char a[100000002]: 存储输入的字符串，以及为了处理 m > 1 的情况而重复的部分。 函数 work0()
这个函数专门处理 m = 1 的情况，即不需要重复字符串 a。它使用一个双端队列 qq 来维护一个滑动窗口，该窗口包含可以替换的 'x' 的位置。变量 maxx 用于跟踪当前窗口内连续 'o' 的最大数量，而 maxn 用于存储整个过程中的最大值。
主函数 main() 读取输入值 n, m, k。 读取字符串 a，并同时计算每个 'x' 位置之前的连续 'o' 的数量（存储在 q 中）和 'x' 的位置（存储在 e 中）。 为了处理 m > 1 的情况，将字符串 a 复制并附加到其自身之后。 如果 tot * m < k，即即使替换所有 'x' 也不足以满足 k 的要求，则直接输出 n * m（因为整个字符串都可以被视为 'o'）。 计算并减去完整周期中可以替换的 'x' 数量对答案的贡献。 根据 m 的值，调用不同的逻辑来处理 m = 1 和 m > 1 的情况。 注意事项 变量 t 和 tot 都表示 'x' 的总数，这种命名不一致可能会导致混淆。 在处理 m > 1 的情况时，代码中存在一些逻辑上的复杂性，特别是关于双端队列 qq 的操作，以及如何在字符串的末尾处理循环。 代码中有一些未使用的变量（如 p 和 tt），应该被移除以提高代码的可读性。 在处理字符串复制和附加时，应该确保不会超出数组 a 的边界，尽管在这个特定情况下由于 n 的大小限制和内存分配，这种情况不太可能发生。
CPP
#include<iostream>
#include<cstring>
#include<queue>
#include<stdio.h>
using namespace std;
long long n,m,k,tot,ans,l,p,q[10000002],e[10000002],t,tt;//e[] 出现x的位置 
long long maxn=-21474836,maxx;
deque <int> qq;
char a[100000002];//q[] 出现x时出现o的次数 即前缀和 
void work0()//m=1情况 
{
	for(int i=1;i<=t/2;i++)
	{
//		cout<<i<<" "<<maxx<<endl;
		qq.push_front(i); 
		k--;
		maxx=maxx+q[e[i]];
		maxn=max(maxn,maxx);
		maxx++;
		if(k<0)
		{
			maxx=maxx-q[e[qq.back()]]-1;
			qq.pop_back();
			qq.push_front(i); 
			k++;
		}
	}
	cout<<maxn;
	
}
int main()
{
	scanf("%lld %lld %lld",&n,&m,&k);
	for(int i=0;i<=n;i++)
	{
		scanf("%c",&a[i]);
//		cout<<a[i]<<" "<<i<<" ";
		if(a[i]=='o') l++;
		if(a[i]=='x') 
		{
			tot++;
			q[i]=l;
			e[++t]=i;
			l=0;
//			cout<<i<<"11111";
		}
	}
	for(int i=n+1;i<=2*n;i++)
	{
		a[i]=a[i-n];
		q[i]=q[i-n];
		if(a[i]=='x')
		e[++t]=i;
	}
	q[e[n+1]]=l+q[e[1]];
//	for(int i=1;i<=2*n;i++)
//	{
//		cout<<a[i]<<" ";
//	}
	if(tot*m<k)
	{
		std::cout<<n*m;
		return 0;
	}
	ans=n*(k/tot-1);
	if(k<tot)
	{
		work0();
		return 0;
	}
	k%=tot;
	k+=tot;
//	cout<<t<<" ";
	l=0;
	maxx=0;
	if(m!=1)
	{
		for(int i=n;i>=1;i--)
		{
			if(a[i]=='x')
			{
				qq.push_front(i);
				k--;
			}
		}
		maxx+=n;
		maxn=maxx;
		for(int i=1;i<=n;i++)
		{
			if(a[i]=='x')
			{
				k--;
				maxx=maxx+q[i];
				qq.push_front(i);
				maxn=max(maxn,maxx);
				maxx++;
//				cout<<i+n<<" "<<maxx<<" "<<endl; 
				if(k<0)
				{
					int u=qq.back();
					qq.pop_back();
					if(qq.back()>n) break;
					qq.push_back(u); 
					maxx=maxx-(q[qq.back()]+1);
					qq.pop_back();
					k++;
				}
			}
		}
		cout<<maxn+ans;
	}
	else
	{
		work0(); 
		return 0;
	}
//	for(int i=1;i<=t;i++)
//	{
//		l++;
//		qq.push(i);
//		max+=q[e[i]];
//		if(l>k)
//		{
//			maxqq.pop()
//		}
//	}
	
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...