博客

Alice和Bob正在玩一个基于字符串的游戏，一开始，Alice和Bob分别拥有一个等长的字符串S1和S2，且这两个字符串只包含小写字母。 在每个回合中，Alice和Bob

必须

分别选择自己的字符串的某一个位置并把这个位置上的字母改变为其他小写字母。 经过P个回合后，他们的得分分别等于自己的字符串中出现最多的字母出现的次数。 最终得分高者获胜，如果两人得分相等，则为平局。 现在你知道了初始的两个字符串S1、S2和回合数P，如果两人都以最优策略游戏，请问最后谁能获胜或者结果是平局。

输入

第一行是一个数T(1≤T≤100000)，表示样例的个数。 然后每个样例第一行两个数字，分别是字符串长度N和回合数P，(1≤N≤100,0≤P≤109)。 接下来两行是两个字符串S1,S2，分别是Alice和Bob的初始字符串。

输出

对于每个样例，输出一行。如果Alice能获胜，输出”Alice”，如果结果是平局，输出”Draw”,否则输出”Bob”。

样例输入

4
6 2
xxxttu
xxttuu
6 5
xxxttu
xxttuu
6 3
xtuxtu
xxttuu
4 0
alic
ebob

样例输出

Alice
Draw
Draw
Bob

思路分析：这道题的下手点就是要代入，代入其中一个人，想着你要赢应该怎么做。

#include <stdio.h>
#include <iostream>
#include<cstring>
using namespace::std;
int main()
{
	int k;
	scanf("%d", &k);
	while (k--)
	{
		/*因为不可能进行模拟，因为变的哪个字符都不同
	我们应该做的就是才用极值的方法进行放缩
	为什么会这样想？因为假如我是ALICE,我和bob回合数都是一样的
	那么如果我要想赢，就必须想尽办法得到最高分，也就是说
	我们只需要对最高分就行比较，只要alice最高分大于bob最高分
	那么alice就一定赢
	我是不是就应该打好我手中的牌？利用
	我这个字符串中最多的字符，然后在规定的回合数内把这个最多的字符的优势扩到最大
	因此，我们的思路是首先找到哪个字母出现的次数最多
	*/
		int n, p;//n为字符总数,p为回合数
		scanf(" %d %d", &n, &p);
		char s1[101];
		char s2[101];
		int a[30]={0}, b[30]={0};//用来记录每个字符串中每个字符出现的个数
		int  countalicemax = 0, countbobmax = 0;//用来记录两个字符串中的极大值
	
		scanf("%s", s1);
		scanf("%s", s2);
		
	
		for (int i = 0; i < n; i++) {
			a[s1[i] - 'a']++;//记录各个字母出现的次数
			if (a[s1[i] - 'a'] > countalicemax) {
				countalicemax = a[s1[i] - 'a'];
			}
			
			b[s2[i] - 'a']++;
			if (b[s2[i] - 'a'] > countbobmax) {
				countbobmax = b[s2[i] - 'a'];
			}

		}
		int scorealice = 0, scorebob = 0;
		//注意一下特殊情况
		if (countalicemax == n) {//如果说全部字母都相同
			if (p == 1) {//只有一个回合
				scorealice = n - 1;//因为字符全部相同，而又必须要变动字符，
				//那么就必须把总分-1
			}
			else
				scorealice = n;//这个地方就相当有难度了,只要回合数不为1且全部字符相同
		//那么总有办法变回原来的形态，也就是说你要赢，就必须想尽办法得到最高分
		}
		
		
		else   if (p >= n - countalicemax) //当回合数>剩余的字符长度
			{
			scorealice = n;//因为回合数超了后，我们就可以变回最高分的状态
			}
		else {
			scorealice = p + countalicemax;
		}
			if (countbobmax == n) {//如果说全部字母都相同
				if (p == 1) {//只有一个回合
					scorebob = n - 1;//因为字符全部相同，而又必须要变动字符，
					//那么就必须把总分-1
				}
				else {
					scorebob = n;//这个地方就相当有难度了,只要回合数不为1且全部字符相同
			//那么总有办法变回原来的形态，也就是说你要赢，就必须想尽办法得到最高分
				}
			}
			else if (p >= n - countbobmax) //当回合数>剩余的字符长度
			{
				scorebob = n;//因为回合数超了后，我们就可以变回最高分的状态
			}
			else scorebob = p + countbobmax;

		
			 if (scorealice > scorebob)
			{
				printf("Alice\n");
			}
			else if (scorealice < scorebob) {
				printf("Bob\n");
			}
			else
			 {
				 printf("Draw\n");
			 } 
			 
	 
		 
		    
	}

}