Question

有一个java题需要解答

甲乙两个人用一个英语单词玩游戏。两个人轮流进行，每个人每次从中删掉任意一个字母，如果剩余的字母序列是严格单调递增的（按字典序a < b < c <....<z)，则这个人胜利。两个人都足够聪明，甲先开始，问他能赢么？
输入： 一连串英文小写字母，长度不超过15,保证最开始的状态不是一个严格单增的序列。
输出：1表示甲可以赢，0表示甲不能赢。
例如: 输入 bad， 则甲可以删掉b或者a,剩余的是ad或者bd，他就赢了，输出1。
又如: 输入 aaa， 则甲只能删掉1个a，乙删掉一个a,剩余1个a，乙获胜，输出0。
函数头部：
Java：public static int who(String in);

Answer 1

足够聪明。。。这是奥数题，不是java题，挺有意思，应该有简便方法

这么久了没人提出个思路，我自己想了个思路，完全可行但是可能略微麻烦
思路：假如有n个字符，那么每两个字符直接都有一个大小关系，总共有n*(n-1)个【关系】。比如说bad,b>a,b<d,a<b,a<d,d>b,d>a这6个【关系】，其中b>a跟a<b是同一个【关系】，所以去掉后剩下b>a,b<d,a<d这三个【关】系n*(n-1)/2。因为你要的是递增，所以b>a不满足，b<d和a<d满足，所以可以认为【关系】b>a是错误的，另外两个是正确的。甲要赢，就必须达到所有【关系】是正确的，所以必须删除单个字母关联【关系】错误最多的那个字母。比如说b，有两个【关系】：b>a:错误，b<d:正确。就是说b的所有【关系】中错1对1。同理，a的【关系】b>a错误，a<d正确。a的所有【关系】中也是错1对1，而d的【关系】就是都对的。甲为了赢，就得删除相关联的【关系】错误最多的字符。这里a和b都是错1对1，而d是对2。所以a和b任意删除一个，甲就赢了。而乙则相反，应该删除对的【关系】最多的那个字符，这里就是d对2，删了乙就赢了。这就是最聪明的删除方法。

程序具体做法：建立一个【关系】的class，里面有三条属性，一是第一个字母，二是第二个字母，三是【关系】的对错。
然后你输入n个字符，就建立n*(n-1)/2个【关系】，通过循环和判断写入属性。
删除的时候自己决定下谁先删（这个随你高兴），删一个字母就删掉所有该字母相关联的【关系】。甲通过循环判断当前字母中谁的关系是错误最多的，删掉该字母和所有该字母相关的【关系】，然后乙继续，删除正确的最多的字符和所有相关【关系】。最后判断不用我说了吧

Answer 2

这跟象棋差多了,两人足够聪明的意思就是指两人看出了此问题的本质,所以能不输,肯定不会输。举个例子.1,abcfd,甲先走,肯定删f,会成abcd,甲胜。但是2,abcgfd,甲聪明就不会先删g或者f,会去找abc里面的删,谁先删了g(或f),另一个人立马删f(或g),就结束了。所以此题是定的,字符串定下,胜负就定了,关键是找出规律。
---其实我是回那个"达摩高僧"的，但以上的话我贴到评论里被评为有不合适的词语，我找了半天楞是找不出来“不合适的词语”，这百度就算算法太搓，你好歹也把我不合适的词标出来行不。。。

Answer 3

public static void main(String[] args) {
		
		String code="abcddsefg";	//单词
		code=code.replace("s", "");	//删除，这里可能有点问题，大概就是这样了，你改改就行了
		if(win(code))        //这里的判断啥的业务你也自己改改吧，总的留点啥给你做
			System.err.println("1");
		else
			System.err.println("0");
	}
	
	public static boolean win(String code){
		char[] c=code.toCharArray();
		for (int i = 0; i < c.length-1; i++) {
			if(c[i] > c[i+1])
				return false;
		}
		return true;
	}

Answer 4

我的想法是，首先应该找到最优的排序，也就是哪个排列是去掉最少的字母后能够满足递增要求，至于甲是否获胜，判断去掉的字母数就行了，如果是奇数甲获胜，偶数乙获胜。

这个题其实就是找最优排列的，找出最优排列来剩下的就很好判断了。

Answer 5

有点问题：两个人都足够聪明，并且都想赢。如果这样设计程序，变数太多了，就像下象棋，可以攻，可以防守，每一次做出决定，都有多种方案，这样对算法要求就高了，不是在这里能解决的。

我觉得可以改一下题目的方向：甲乙两人一起删字母，得到一个最长的严格单增序列。这样的话，这个题目在这里还是可以做做的。