单词博弈 http://hero.pongo.cn/OnlineCompiler/Index?ID=168&ExamID=163

Caculator.java

import java.util.Date;
import java.util.HashMap;
import java.util.Map;


public class Caculator {
	public static Map<String,Integer> result = new HashMap<String, Integer>();
	public static boolean isAddString(String in){
		int length = in.length();
		for(int i=0;i<length-1;i++){
			char a = in.charAt(i);
			char b = in.charAt(i+1);
			if(a>=b){
				return false;
			}
		}
		return true;
	}
	/**
	 * 对现有字符串in player以最聪明的方式去拿，最终结果
	 * @param in
	 * @param player
	 * @return
	 */
	public static int whenGetOneChar(String in,int player){
		int length=in.length();
		for(int i=0;i<length;i++){
			String newIn = in.substring(0,i)+in.substring(i+1);
			if(isAddString(newIn)){
				return 1;
			}else{
				int isEnimyCanWin;
				Integer oldWinResult = result.get(newIn);
				if(oldWinResult!=null){
					isEnimyCanWin = oldWinResult;
				}else{
					isEnimyCanWin = whenGetOneChar(newIn, -player);
					result.put(newIn, isEnimyCanWin);
				}
				if(isEnimyCanWin==0){//说明对方一定会输
					return 1;
				}
			}
		}
		return 0;
	}
	public static int who(String in){
		return whenGetOneChar(in,1);
	}
	public static void main(String[] args) {
		long start = new Date().getTime();
		System.out.println(Caculator.who("asdfsdffgdsbsda"));
		long end = new Date().getTime();
		System.out.println(end-start);
	}
}

howmany.cpp

#include <iostream>
#include <map>
using namespace std;

class Test
{
public:
    static int blist[10000];
    static int ilist[10000];
    static int nlist[10000];
    static int glist[10000];
    static int bi;
    static int st;
    static int ii;
    static int ni;
    static int gi;

    static map<int, int> result1;
    static map<int, int> result2;
    static map<int, int> result3;
    static map<int, int> result4;

    static void scan(string src)
    {
        int s = 0, e = src.length(), i = 0;
        bi = 0;
        ii = 0;
        ni = 0;
        gi = 0;
        for(i = 0; i < e; i++)
        {
            if(src[i] == 'b')
            {
                s = i;
                break;
            }
        }
        for(i = e - 1; i > s; i--)
        {
            if(src[i] == 'g')
            {
                e = i;
                break;
            }
        }
        for(i = s; i <= e; i++)
        {
            switch(src[i])
            {
            case 'b':
                blist[bi++] = i;
                break;
            case 'i':
                ilist[ii++] = i;
                break;
            case 'n':
                nlist[ni++] = i;
                break;
            case 'g':
                glist[gi++] = i;
                break;
            }
        }
    }

    static void print()
    {
        for(int i = 0; i < bi; i++)
        {
            cout<<blist[i]<<" ";
        }
        cout<<endl;
        for(int i = 0; i < ii; i++)
        {
            cout<<ilist[i]<<" ";
        }
        cout<<endl;
        for(int i = 0; i < ni; i++)
        {
            cout<<nlist[i]<<" ";
        }
        cout<<endl;
        for(int i = 0; i < gi; i++)
        {
            cout<<glist[i]<<" ";
        }
        cout<<endl<<"=========="<<endl;
    }

    static int count()
    {
        int i, j, k, l, c = 0;
        for(i = bi - 1; i >= 0; i--)
        {
            for(j = ii - 1; j >= 0; j--)
            {
                if(blist[i] > ilist[j])
                {
                    break;
                }
                for(k = ni - 1; k >= 0; k--)
                {
                    if(ilist[j] > nlist[k])
                    {
                        break;
                    }
                    for(l = gi - 1; l >= 0; l--)
                    {
                        if(nlist[k] > glist[l])
                        {
                            break;
                        }
                        //cout<<blist[i]<<" "<<ilist[j]<<" "<<nlist[k]<<" "<<glist[l]<<endl;
                        c++;
                    }
                }
            }
        }
        return c;
    }

    static int count2()
    {
        result1.clear();
        result2.clear();
        result3.clear();
        result4.clear();
        int i, c = 0, call = 0;
        map<int, int>::iterator mit;
        for(i = 0; i < gi; i++)
        {
            result1[glist[i]] = 1;
        }
        for(i = 0; i < ni; i++)
        {
            for (mit = result1.begin( ); mit != result1.end( ); mit++ )
            {
                if(nlist[i] > mit->first)
                {
                    continue;
                }

                if(result2.find(nlist[i]) == result2.end())
                {
                    c = mit->second;
                }
                else
                {
                    c = result2[nlist[i]] + mit->second;
                }
                result2[nlist[i]] = c;
            }
        }
        for(i = 0; i < ii; i++)
        {
            for (mit = result2.begin( ); mit != result2.end( ); mit++ )
            {
                if(ilist[i] > mit->first)
                {
                    continue;
                }

                if(result3.find(ilist[i]) == result3.end())
                {
                    c = mit->second;
                }
                else
                {
                    c = result3[ilist[i]] + mit->second;
                }
                result3[ilist[i]] = c;
            }
        }
        for(i = 0; i < bi; i++)
        {
            for (mit = result3.begin( ); mit != result3.end( ); mit++ )
            {
                if(blist[i] > mit->first)
                {
                    continue;
                }

                if(result4.find(blist[i]) == result4.end())
                {
                    c = mit->second;
                }
                else
                {
                    c = result4[blist[i]] + mit->second;
                }
                result4[blist[i]] = c;
            }
        }
        for (mit = result4.begin( ); mit != result4.end( ); mit++ )
        {
            call += mit->second;
        }
        return call;
    }

    static int howmany (string s)
    {
        scan(s);
        return count2();
    }
};

int Test::bi;
int Test::ii;
int Test::blist[10000];
int Test::ilist[10000];
int Test::nlist[10000];
int Test::glist[10000];
int Test::st;
int Test::ni;
int Test::gi;

map<int, int> Test::result1;
map<int, int> Test::result2;
map<int, int> Test::result3;
map<int, int> Test::result4;

int main()
{
    cout<<Test::howmany("iinbinbingiinbinbingiinbinbiniinbinbiiinbinbingiinbinbingiinbinbiniinbinbi")<<endl;
}

wk.c

#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

const int	N = 20 + 5;
int		dp[32768 + 10];

int getlen( int x )
{
	return( (int) (log( x + 0.5 ) / log( 2.0 ) ) );
}


int judge( char *word, int num )
{
	int	i, index;
	char	last = 0;
	for ( i = num; i > 0; i -= (-i & i) )
	{
		index = getlen( -i & i );
		if ( last == 0 )
			last = word[index];
		else if ( last >= word[index] )
			return(0);
		else last = word[index];
	}
	return(1);
}


int cal( char *word, int num )
{
	int	i;
	int	flag[17];
	if ( dp[num] + 1 )
		return(dp[num]);
	if ( judge( word, num ) )
		return(dp[num] = 0);
	for ( i = 0; i < 17; i++ )
		flag[i] = 0;
	for ( i = num; i > 0; i -= (-i & i) )
		flag[cal( word, num - (-i & i) )] = 1;
	for ( i = 0; i < 17; i++ )
		if ( flag[i] != 1 )
			return(dp[num] = i);
}


int who( char *word )
{
	int i, n, maxn;
	n	= strlen( word );
	maxn	= 1 << n;
	if ( judge( word, maxn - 1 ) )
		return(0);
	for ( i = 0; i < maxn; i++ )
		dp[i] = -1;
	for ( i = 1; i < maxn; i++ )
		cal( word, i );
	/* for(i=0;i<maxn;i++)printf("%d,%d\n",i,dp[i]); */
	return(dp[maxn - 1] != 0);
}


int main()
{
	printf( "%d", who( "aaa" ) );
}

WordGame.cpp

#include <stdio.h>
#include <iostream>
#include <string>
#include <list>

using namespace std;
class Test {
public:
    static int who (string word)
    {
        return go(word.c_str()) ? 1 : 0;
    }
    
    static bool go(const char in[])
    {
        int len = getLen(in);
        list<char*> children;
        for (int i = 0; i < len; i++) {
            char *nin = copyChars(in, i);
            if(isAdd(nin)){
                return true;
            }
            children.push_back(nin);
        }
        list<char *>::iterator it;
        for (it = children.begin(); it != children.end(); ++it)
        {
            char *child = *it;
            // 对方有一次没成功，自己就赢了
            if(!go(child))
            {
                return true;
            }
        }
        return false;
    }
 
    static char *copyChars(const char src[], int except) 
    {
        int len = getLen(src);
        char *dst = new char[len - 1];
        for(int i = 0; i < except; i++)
        {
            dst[i] = src[i];
        }
        for(int i = except + 1; i < len; i++)
        {
            dst[i - 1] = src[i];
        }
        return dst;
    }
 
    static bool isAdd(const char in[]) 
    {
        int len = getLen(in);
        for (int i = 0; i < len - 1; i++) {
            if (in[i] >= in[i + 1]) {
                return false;
            }
        }
        return true;
    }

    static int getLen(const char array[])
    {
        int len = (sizeof(array) / sizeof(array[0]));
        return len;
    }
};
//start 提示：自动阅卷起始唯一标识，请勿删除或增加。
int main()
{   
    cout<<Test::who("Test")<<endl;   
} 
//end //提示：自动阅卷结束唯一标识，请勿删除或增加。

WordGame.java

/**
 * 单词游戏
 * @author gudh
 * @date 2013-12-20
 */
public class WordGame {
 
	public static void main(String[] args) {
		long s = System.currentTimeMillis();
		System.out.println(who("jaldfkkgdkjfsdf"));
		long t = System.currentTimeMillis() - s;
		System.out.println("Use time:" + t);
		System.out.println("Go times:" + times);
	}
	// 计算进入go的次数
	static long times = 0;
	
	public static int who(String in) {
		// 预处理，对相邻的仅保留一个
		char[] arrs = in.toCharArray();
		int len = arrs.length;
		StringBuffer sb = new StringBuffer();
		char lastC = '\0';
		for(int i = 0; i < len; i++){
			if(arrs[i] != lastC){
				sb.append(arrs[i]);
				lastC = arrs[i];
			}
		}
		arrs = sb.toString().toCharArray();
		int res = (len - arrs.length) % 2;
		if(isAdd(arrs)){
			// 如果已经单调，则需要进行原始判断
			return go(in.toCharArray()) ? 1 : 0;
		}
		// 否则可以在去重的基础上判断
		return go(arrs) ? 1 - res  : res;
	}
 
	/**
	 * 递归算法，当前go的人具有严格优先权
	 * @param in
	 * @return
	 */
	public static boolean go(char[] in) {
		//times++;
		int len = in.length;
		char[][] children = new char[len][];
		int j = 0;
		for (int i = 0; i < len; i++) {
			char[] nin = copyChars(in, i);
			if(isAdd(nin)){
				return true;
			}
			children[j++] = nin;
		}
		for(int i = 0; i < j; i++){
			char[] child = children[i];
			// 对方只要有一次没成功，自己就赢了
			if(!go(child)){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 从src中获取一个除第except个字符的拷贝
	 * @param src
	 * @param except
	 * @return
	 */
	public static char[] copyChars(char src[], int except) {
		int len = src.length;
		char dst[] = new char[len - 1];
		for(int i = 0; i < except; i++){
			dst[i] = src[i];
		}
		for(int i = except + 1; i < len; i++){
			dst[i - 1] = src[i];
		}
		return dst;
	}
 
	/**
	 * 判断是否是严格单调增
	 * @param in
	 * @return
	 */
	public static boolean isAdd(char[] in) {
		int len = in.length;
		for (int i = 0; i < len - 1; i++) {
			if (in[i] >= in[i + 1]) {
				return false;
			}
		}
		return true;
	}
}

题目

题目详情:
本第一次在线编程大赛由文思海辉冠名，题目如下：
甲乙两个人用一个英语单词玩游戏。两个人轮流进行，每个人每次从中删掉任意一个字母，如果剩余的字母序列是严格单调递增的（按字典序a < b < c <....<z)，则这个人胜利。两个人都足够聪明（即如果有赢的方案，都不会选输的方案 ），甲先开始，问他能赢么？
输入： 一连串英文小写字母，长度不超过15,保证最开始的状态不是一个严格单增的序列。
输出：1表示甲可以赢，0表示甲不能赢。
例如: 输入 bad， 则甲可以删掉b或者a,剩余的是ad或者bd，他就赢了，输出1。
又如: 输入 aaa， 则甲只能删掉1个a，乙删掉一个a,剩余1个a，乙获胜，输出0。

函数头部：
C：int who (char * word);
C++：int who (string word);
Java：public static int who(String in);
C# ：public static  int who(string word);

不错不错