Educational Codeforces Round 135 (Rated for Div. 2)

A. Colored Balls: Revisited

题目链接：Problem - A - Codeforces

 样例输入：

3
3
1 1 1
1
9
2
4 7

样例输出：

3
1
2

题意：一个袋子里面有n种颜色的球，第i种颜色的球的数目为ai,球的总数目是奇数，每次操作我们可以一次拿出两个颜色不同的球，问最后剩余的球的颜色可能是什么？输出任意一种答案即可。

分析：我们直接输出颜色数量最多的那个球的颜色即可，因为我们可以在剩余的n-1种颜色的球中进行操作，直至n-1种颜色只剩下一种颜色，那么再将这一种颜色与数目最多的那一种球进行操作，那么颜色数目最多的球一定会有剩余，所以我们可以直接输出颜色数量最多的那个球的颜色。

细节见代码：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int mxid=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]>a[mxid]) mxid=i;
		}
		printf("%d\n",mxid);
	}
	return 0;
} 

B. Best Permutation

题目链接：Problem - B - Codeforces

 样例输入：

3
4
5
6

样例输出：

2 1 3 4
1 2 3 4 5
4 5 1 2 3 6

题意：给定一个n的全排列p1,p2,……,pn,有一个初始值x=0,用x对全排列进行一次操作可以得到一个值，操作规则是先让x与p1比较，如果x

分析：通过简单分析可以发现一个结论，最终的值是不可能超过n+n-1的，原因很简单，就是如果一个数x小于pi，那么x=x+p1，首先x用前n-2个数操作后使得x=0，最后再对n-1操作得到n-1，然后对n操作得到n+n-1,下面来说一下如何对前n-2个数操作使得x为0，其实很简单，对于n-2是偶数的情况，我们相邻两个数为一组，每组先对大的数操作即可，对于n-2是奇数的情况，我们把前三个数分为一组，按照1，3，2的顺序操作，这样操作后得到的结果为0，后面的数就是偶数个，再按照两两分组先与大的操作即可。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=1e5+10;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		if(n&1)
		{
			printf("1");
			for(int i=2;i<=n-2;i++)
				printf(" %d",i^1);
			printf(" %d %d\n",n-1,n);
		}
		else
		{
			for(int i=1;i<=n-2;i++)
				if(i&1) printf("%d ",i+1);
				else printf("%d ",i-1);
			printf("%d %d\n",n-1,n);
		}
	} 
	return 0;
}

C. Digital Logarithm

题目链接：Problem - C - Codeforces

样例输入：

4
1
1
1000
4
1 2 3 4
3 1 4 2
3
2 9 3
1 100 9
10
75019 709259 5 611271314 9024533 81871864 9 3 6 4865
9503 2 371245467 6 7 37376159 8 364036498 52295554 169

样例输出：

2
0
2
18

题意：定义f(x)表示x这个字符串的位数，一开始给定两个字符数组a和b，然后我们需要对两个字符数组中的字符串进行操作，每次操作可以把一个x变为f(x),问至少需要多少次操作才能使得字符数组a和字符数组b相等，这里的相等就是说对字符数组a和字符数组b排序后相等即可。

分析：这个题直接贪心求解即可，首先不难想到的一点是对于一开始a和b就相等的元素我们直接令其匹配即可，匹配结束后剩余的元素都是无法匹配的了，我们把元素>=10的进行一次操作使其变为1~9,因为题目中给出字符串的长度都是小于等于9的，那为什么不把1~9的字符串也直接操作一次令其等于1呢？其实这个很容易想，就是说比如a数组中有一个3没有匹配，b数组中有一个666没有匹配，666>=10，我们通过一次操作把666变为3，那么就可以将二者匹配，所以只需要一次操作，3这种一位数是有可能与大数经过一次操作后的数相等的，所以我们没有必要急着把他进行操作，经过上述两次操作后所有的数都变为1~9了，我们再进行匹配，匹配完后剩余的数如果不经过操作则一定不可能成功匹配，所以我们还需要对其进行匹配，但是1是没必要进行操作的，因为1操作后还是1，我们只需要对2~9的数进行操作即可。最后一次操作一定能把所有的数化为1，那么一定可以全部匹配

有一个坑点一定要注意就是我们要用map记录每一个数出现的次数而不能用unordered_map,codeforce是卡unordered_map的，所以这一点一定要注意。

细节见代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
using namespace std;
const int N=2e5+10;
map<int,int>mp;
int a[N],b[N];
int pa[N],pb[N];
int len(int x)
{
	int t=0;
	while(x)
	{
		t++;
		x/=10;
	}
	return t;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int ans=0,n;
		for(int i=1;i<=9;i++) pa[i]=pb[i]=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			mp[a[i]]++;
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&b[i]);
			if(mp[b[i]])	mp[b[i]]--;
			else
			{
				if(b[i]>=10)
				{
					ans++;//花费一次操作将其变为其长度 
					pb[len(b[i])]++;
				}
				else
					pb[b[i]]++;
			}
		}
		for(int i=1;i<=n;i++)
			if(mp[a[i]])
			{
				mp[a[i]]--;
				if(a[i]>=10)
				{
					pa[len(a[i])]++;
					ans++;//花费一次操作将其变为其长度 
				}
				else
					pa[a[i]]++;
			}
		for(int i=2;i<=9;i++)
			ans+=abs(pb[i]-pa[i]);
		printf("%d\n",ans);
	}
	return 0;
}

D. Letter Picking

题目链接：Problem - D - Codeforces

样例输入： 

2
forces
abba

样例输出：

Alice
Draw

题意：一开始给定一个长度为偶数的字符串，Alice和Bob两个玩家进行博弈，两个玩家一开始都有一个空串，两个玩家轮流操作，每次操作都是从给定的字符串从开头或者结尾选择一个字符串加入自己字符串的开头，假设两个人都是采取最优操作，问最后谁会赢，Alice是先手，如果Alice赢则输出Alice，Bob赢则输出Bob，平局则输出Draw.

分析：之前见过很多这样的题目，一看到这种对字符串首尾操作的题目就能够想到是区间DP，设f[i][j]=1/2/3分别代表对Alice是先手且对区间i~j内的数进行操作Alice有必胜/平局/必败情况，当然，Alice肯定会选择最有利于自己的操作，所以能选择获胜绝不选择平局，所以不难想到f[i][j]的值是唯一的。

首先不难发现的一点是对于每一个字符串第一回合操作只有四种情况，就是Alice取最左边的字符，Bob取最右边的字符或者是次左边的字符，还有就是Alice取最右边的字符，Bob取最左边的字符或者是次右边的字符，其实这个题目只是需要枚举一下所有可能即可，假如现在我们对区间[l,r]进行操作，Alice取最左边的字符s[l]，那么Bob只能选择取次左边的字符s[l+1]或者最右边的字符s[r]，当然Bob肯定会选择有利于他的一个字符，那么对于Alice而言我们就需要分别讨论Alice的这两种情况并取一个最坏情况，对于Alice一开始取最右边的字符的情况讨论方法也是类似的，这里就不再赘述了，但是Alice的操作是可控的，所以我们应该贪心地选择一个对Alice有用的操作，也就是Alice一开始选择最左边字符还是最右边字符的问题，对这两个操作造成的结果取一个较优的即可。我们对Alice取最左边字符s[l]，Bob取次左边字符s[l+1]进行讨论，区间[l,r]去掉l和l+1这两个点剩余的区间就是[l+2,r]，我们需要注意的一点是区间DP的过程是从小区间到大区间，也就是说在更新大区间时小区间已经更新完了，而且对于这道题而言，我们能够发现我们是先选取边缘的字符，那么就是说越边缘的字符在我们最终两个玩家的字符串中的位置越靠后，所以真正起到决定作用的字符是位于中间的字符，也就是我们区间DP一开始更新的小区间，所以对于Alice取最左边字符s[l]，Bob取次左边字符s[l+1]这种情况，如果区间[l+2,r]的结果不是平局，那么对于之后Alice和Bob选取什么字符已经没什么作用了，直接返回[l+2,r]的结果即可，而如果区间[l+2,r]的结果是平局，那么决胜局就在于当前操作了（当然当前操作也可能是平局），我们只需要比较一下Alice和Bob选取的字符大小即可，细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=2e3+10;
char s[N];
int f[N][N];
//f[i][j]=1/2/3分别代表对区间i~j内的数进行操作Alice有必胜/平局/必败情况
int cal(int x,int y,int z)
{
	if(z!=0&&z!=2) return z;
	if(s[x]<s[y]) return 1;
	else if(s[x]>s[y]) return 3;
	else return 2;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%s",s+1);
		int n=strlen(s+1);
		for(int len=2;len<=n;len+=2)
		for(int l=1;l+len-1<=n;l++)
		{
			int r=l+len-1;
			f[l][r]=min(max(cal(l,r,f[l+1][r-1]),cal(l,l+1,f[l+2][r])),max(cal(r,l,f[l+1][r-1]),cal(r,r-1,f[l][r-2])));
		}
		if(f[1][n]==1) puts("Alice");
		else if(f[1][n]==2) puts("Draw");
		else puts("Bob");
	}
	return 0;
}