Dashboard - Codeforces Round 1011 (Div. 2) - Codeforces

A. Serval and String Theory（字符串）

题意

对于字符串s,最多可以进行k次交换，是否满足s<s的翻转

思路

wa了两发，都是因为没有翻转字符串，直接比较了s[0] 和s[n-1]

• k==0,直接判断，s和reverse(s)
• k>0,只要不是只有一种元素，都可以满足

代码

void solve()
{
	int n,k=0;
	string s;
	cin>>n>>k>>s;
	string t=s;
	reverse(ALL(t));
	if(k==0&&t<=s)
	cout<<"NO\n";
	else
	{
		int f=0;
		fir(i,1,n-1)
		if(s[i]!=s[i-1]) f=1;
		if(f==0)
		cout<<"NO\n";
		else
		cout<<"YES\n";
	}
}

B. Serval and Final MEX（消除操作）

题意

对给定数组，选取任意区间替换为没有出现在区间内的最小非负整数。

输出具体操作，不需要尽量减少操作次数。

思路

明明不需要尽量减少，还非要从具体情况考虑，虽然保证了次数最小，却迎来巨大罚时。

只需要考虑将0全部消除即可。

两种方法

1. 每逢0，将其与其相邻的数字，选做一个区间，用vector存放，最后再选取剩下的所有数
2. 特判几种情况（容易漏判，不建议）

代码1

void solve()
{
	int n,s0=0,j=0;
	vector<PII> v;
	cin>>n;
	fir(i,1,n)
	{
		cin>>a[i];
	}
	fir(i,1,n)
	{
		if(a[i]==0)
		{
			int x=v.size();
			if(i!=n)
			v.push_back({i-x,i-x+1ll});
			else
			v.push_back({i-x-1ll,i-x});
			i++;
		}
	}
	cout<<v.size()+1<<"\n";
	for(auto it:v)
	cout<<it.fi<<" "<<it.se<<'\n';
	cout<<"1 "<<n-v.size()<<'\n';
}

代码2

void solve()
{
	int n,s0=0,j=0;
	cin>>n;
	fir(i,1,n)
	{
		cin>>a[i];
		if(a[i]!=0)
		j=i;
		else s0++;
	}
	if(s0==n)
	{
		cout<<"3\n1 2\n"<<"2 "<<n-1<<"\n1 2\n";
	}
	else if(s0==0)
	{
		cout<<"1\n1 "<<n<<"\n";
	}
	else
	{
		int f=0;
	 	fir(i,1,j)
	 	if(a[i]==0) f=1;
		if(j==n)
		cout<<"2\n1 "<<j-1<<"\n1 2\n";
		else if(j==1)
		cout<<"2\n"<<j+1<<" "<<n<<"\n1 2\n";
		else if(f==0)
		cout<<"2\n"<<"2 "<<n<<"\n1 2\n";
		else
		{
			if(j==2)
			cout<<"3\n1 "<<j<<"\n"<<"2 "<<n-j+1<<"\n1 2\n";
			else
			cout<<"3\n1 "<<j-1<<"\n"<<"2 "<<n-j+2<<"\n1 2\n";
		}
		 
	}
}

C. Serval and The Formula（和、异或）

给出两个正整数 $$x$$$ 和 $$$y$$$ ( $$$1\le x,y\le 10^9$$ )。

找到一个非负整数 $$k\le 10^{18}$$$ ，使得 $$$(x+k)+(y+k)=(x+k)\oplus (y+k)$$ 满足 ，或者确定这样的整数不存在。

思路

这题也算秒了，如此得心应手，还是第一次体会到

第一反应便是：
$$(x+k)+(y+k)=(x+k)\oplus (y+k)+2\times ((x+k)\&(y+k))$$
这就是一个加法和异或的性质。

由此，只需要找到一个k，使得$x\&y=0$便是正解。

假设最大的数字(mx)的2进制为n位，$2^n-mx$.

赛后发现，其实不需要$2^n$,只要是一个较大的2整数幂即可。

代码

void solve()
{
	int x,y;
	cin>>x>>y;
	if(x==y)
	cout<<"-1\n";
	else
	{
		int a=max(x,y);
		int k=pow(2,(int)log2(a)+1); 
		cout<<k-a<<'\n';
	}
}

D. 贪心

题意

一共有n个盘子，第 i 个盘子在 i 分钟才出现。每个盘子里有 k 个寿司，需要 k 分钟吃完，美味值为 $d_i$.

取下一个盘子，需要 1 分钟，k个寿司吃完才能获得美味值。

求在n分钟内可以获得的最大美味值总和。

思路

题解上的提示非常妙。

• 不要用dp
• 可以拿几盘寿司

要想美味值最大，就需要尽可能多的选择，尽可能选择最大的。

由于第 i 个盘子，在 i分钟才出现，应该从已出现的盘子中选取最大美味值。

可以拿几盘呢？

$n/(k+1)$

最后一个盘子什么最晚时候拿？

$n-(k+1)+1$

再晚就吃不完啦

举个例子

9个盘子，k=2

9 #8 7 5 #1 4 5 #2 3

按照上方，从右往左，最后两个不能选，划分。以$k+1$为步长，划分。

可以想一下，除去最后一个区间，每当经过一个区间，就可以从前面选择一个盘子，

这样一定能保证吃完，并且必须要选，因为选总比不选要优。

每一个右区间就是一个边界：

• 最晚应该在此时选择，才不会少选一个
• 最晚，所以有更多选择，使其更优

代码

const int N=1e6+10;
int a[N];
void solve()
{
	int n,k,sum=0;
	cin>>n>>k;
	fir(i,1,n)
	cin>>a[i];
	priority_queue<int> q;
	fir(i,1,n-k)
	{
		q.push(a[i]);
		if((n-k-i)%(k+1)==0)
		{
			sum+=q.top();
			q.pop();
		}
	}
	cout<<sum<<'\n';
}

E.又是一个取模

题意

给你两个数组a,b。b数组是由 a[i ]%k,产生的，当然顺序已经被打乱了

请问是否存在这样一个数字 k ，使数组满足条件，存在输出k，不存在输出-1

思路

a[i]-a[i]%k 结果是多少？

结果为 t*k（t>=0）

a[i]%k 不正是 b 数组？

sum(a)-sum(b) 又会怎么样呢？

同样是 t*k (t>=0)

---

所以如果存在 k ,那么C=sum(a)-sum(b),一定是k的非负整数倍。

计算数据范围：

C <=10^10 ,计算它的因数个数大概在10^4之内。每次判断需要 10^4 ,刚好卡过去。

int n,a[N],b[N],c[N],INF=1e9;
bool check(int k)
{
	fir(i,1,n)
	c[a[i]%k]++;
	fir(i,1,n)
	{
		c[b[i]]--;
		if(c[b[i]]<0)
		{
			fir(i,1,n)
			c[a[i]%k]=0;
			c[b[i]]=0;
			return 0;
		}
	}
	return 1;
}
void solve()
{
	int sum=0;
	cin>>n;
	fir(i,1,n)
	{
		cin>>a[i];
		sum+=a[i];
	}
	fir(i,1,n)
	{
		cin>>b[i];
		sum-=b[i];
	}
	if(sum==0)
	{
		cout<<(check(INF) ? INF:-1)<<'\n';
		return ;
	}
	for(int i=1;i*i<=sum;i++)
	{
		if(sum%i==0)
		{
			if(check(i))
			{
				cout<<i<<'\n';return;
			}
			if( check(sum/i))
			{
				cout<<sum/i<<'\n';return;
			}
		}
	}
	  cout<<"-1\n";
}