AtCoder Beginner Contest (ABC) 313 D-E

Tasks - AtCoder Beginner Contest 313

PS:当时看到D过的比E多就一直在考虑D，但还没做出来，其实个人感觉E比D简单。

D - Odd or Even

交互题。有n个数，最多可以询问n次然后要求判断出这n个数的奇偶性。每次可以询问数组里任意k个元素的和是不是奇数

一开始想到的是高斯消元，n次总能组成一个异或方程组嘛，不过n是1000，n^3会炸。

目前来说，我只是理解了算法的正确性，至于如何从题目中推导出来，，，有待思维能力的进一步提高吧。。

大体思路就是先通过k+1次询问确定前k+1个数的值，然后选择k-1个已知值再分别与[k+2,n]的任意一个组合成k各值，通过一次询问得到该值。总共询问(k+1)+(n-(k+1))=n次

所以，具体看代码吧

#include<iostream>
using namespace std;
int n,a[1005],k,tmp;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=k+1;i++)
	{
		cout<<"? ";
		for(int j=1;j<=k+1;j++)
		{
			if(i==j)continue;//此时要计算除了i以外是不是奇数
			cout<<j<<' ';
		}
		cout<<endl;
		cin>>a[i];//除了i前k项和是不是奇数
		tmp^=a[i];//最后的tmp是前k+1项的和是不是奇数。
	}
	//如果前k+1项和为偶数，那么如果a[i]是奇数，那么sum-a[i]也是奇数，即读入的就是正确的
	//如果前k+1项和为奇数，如果a[i]为奇数，那么sum-a[i]为偶数，若a[i]为偶数，则sum-a[i]为奇数，此时是相反的
	for(int i=1;i<=k+1;i++)a[i]^=tmp;
	//此时已经通过询问k+1次 k个数的和 获得了前k+1个数
	//那么接下来选取k-1个数再加一个[k+2,n]里面数的和询问n-k-1次即可，总共询问n次
	tmp=0;
	for(int i=1;i<k;i++)tmp^=a[i];
	for(int i=k+2;i<=n;i++)
	{
		cout<<"? "<<i<<' ';
		for(int j=1;j<k;j++)
		cout<<j<<' ';
		cout<<endl;
		cin>>a[i];
		a[i]^=tmp;
		//如果前k-1项为偶数，那么加上第i项后的奇偶性就是第i项的奇偶性
		//如果前k-1项为奇数，那么加上第i项后的奇偶性取反就第i项奇偶性
	}
	cout<<"! ";
	for(int i=1;i<=n;i++)
	cout<<a[i]<<' ';
	return 0;
}

E - Duplicate

给一个由10进制数字组成的字符串，每次操作会得到一个新字符串，s[i]会变成s[i+1]个s[i]，就像xyz->(y个x)(z个y)

问多少次可以只剩下一个字符串，如果不能输出-1

我们其实可以写个暴力程序推一推规律。

先考虑不能的情况。每次操作相当于牺牲掉最后一个数让序列中其它的数增殖，如何保证这种增殖最终会走向减少呢？每个数每次的增殖数量取决于它后面的数。如果后面的数是1相当于不增殖xy->x，否则数量会增加xy->xxxxx...xxx，此时增殖的这一堆(xx.....xxx)中。如果x是大于1的，意味着这个序列将会一直增殖下去。综上就是只要存在两个相邻的数都大于1就无法减少到1

接下来就是怎么找每次操作的规律。

既然已经能缩减到1，那么原序列就是一个一堆1里随便找几个空插入大于1的序列。因为如果后面是1的话一次操作实际是不增殖的，我们可以把连续的1存起来，那么现在序列就像.....1x1y1z.........

考虑到每次去掉最后的数，那我们从后往前推。

如果后面的数是1，那么一直到后面的数被干掉，当前数（一个大于1的数或者是一堆1）都不会增殖，那么去掉当前的数操作数++

如果后面的数不是1，那么一直到后面的数被干掉，当前数（一定是一堆1，不是的结果上面已经排除掉了）会增殖当前操作数次，每次是增加后面数-1个。那么此时有(原来1的个数+t*（后面的数-1）)个1，要干掉这一堆1，操作数+=增殖后1的总数量。

不断重复以上的操作，剩下一个即可。

当然有些情况需要特判，例如全1串，只有一个数的，等等。

我在代码里干脆就把最后一个必不能增殖的不管它是不是1单独放一起，然后是算全部干掉的操作数，最后输出这个-1即可。

#include<iostream>
#include<vector>
#define int long long
using namespace std;
string s;
const int mod=998244353;
int n,a[1000005];
vector<int>c,b;
signed main()
{
	cin>>n>>s;
	for(int i=0;i<s.length();i++)
		a[i+1]=s[i]-'0';
	for(int i=1;i<n;i++)
	{
		if(a[i]>=2&&a[i+1]>=2)
		{
			cout<<-1;
			return 0;
		}
	}
	b.push_back(a[1]);
	c.push_back(1);
	for(int i=2;i<n;i++)
	{
		if(a[i]==b[b.size()-1])
		{
			c[c.size()-1]++;
		}
		else
		{
			b.push_back(a[i]);
			c.push_back(1);
		}
	}
	b.push_back(a[n]);
	c.push_back(1);
	int d=b.size()-2,t=1;//先把末尾的干掉
	for(int i=d;i>=0;i--)
	{
		if(b[i]!=1)
		{
			t++;//消除当前非1数
			t%=mod;
		}
		else
		{
			int tp=c[i]+t*(b[i+1]-1)%mod;//先增殖再消除
			t+=(tp);
			t%=mod;
		}
	}
	t--;//现在的是全部干掉后的答案，保留一个的话操作数-1即可
	cout<<t;
	return 0;
}