Topic Details
A and B two people to play games with an English word . Two people take turns , each person each from arbitrarily delete a letter, if the rest of the letter sequence is strictly monotonically increasing ( lexicographical ordering a
Input: a series of English lowercase letters, no longer than 15 to ensure that the state is not the beginning of a strictly monotone increasing sequence.
output: 1 means A can win , 0 A can not win.
For example : Input bad, then A can be removed b or a, or the remainder of the ad bd, he won, output 1.
Another example : Enter aaa, then A can only delete an a, b delete an a, remaining an a, B wins, the output is 0.
function head :
C: int who (const char * word);
C + +: int who (string word);
Java: public static int who (String in);
C #: public static int who (string word);
------ Solution ------------------------------------ --------
I looked at , not the algorithm, no idea
------ Solution ----------------- ---------------------------
feel undirected graph should be used to represent letters remove all conflict is equivalent to a letter Are there strategies to remove a node can certainly win
------ Solution diagram based -------------------------- ------------------
top, looked nothing thinking.
------ Solution ---------------------------------------- ----
paste my code , great God help us to see where wrong. . .
line with the idea that generations of reverse right.
public class Test {
public static void main(String[] args) {
String string="vgwgpkxxkqmnx";
System.out.println(who(string));
}
public static int who(String word){
String word2=word;
int maxIndex;//逆序最大数
int count=0;//count为奇数甲操作，count为偶数乙操作
while(maxCount(word2)>0){
//System.out.println(word2);
maxIndex=maxCount(word2);
word2=word2.substring(0,maxIndex)+word2.substring(maxIndex+1,word2.length());
count++;
}
return count%2;
}
private static int maxCount(String in){
int[] a=new int[in.length()];
int max=0;
int maxIndex=0;
char[] chs=in.toCharArray();
for(int i=0;i<in.length()-1;i++)
for(int j=i+1;j<in.length();j++){
if(chs[i]>=chs[j]){
a[i]++;
a[j]++;
}
}
for(int i=0;i<a.length;i++){
//System.out.print(a[i]+" ");
if(a[i]>max){
max=a[i];
maxIndex=i;
}
}
//System.out.println();
return maxIndex;
}
}
------ For reference only ---------------------------------- -----
------ For reference only ---------------------------------------
put down no idea
------ For reference only ------------------------------- --------
you forgot to say a and B are the subject of strategic priorities for the elimination of more disordered nodes can speed up the algorithm , but by choice unordered pairs AB fewer letters or letters to win orderly " a and B are smart enough " water on deep
------ For reference only ----------- ----------------------------
you forgot to say a and B are the subject of strategic priorities eliminate more unordered pairs of nodes can speed up the algorithm, but a and B are unordered pairs by selecting letters or less orderly letters to win the " a and B are smart enough " on deep water
That I can Oh it. . .
------ For reference only ----- ----------------------------------
1, first calculate the number of reverse all the letters and other letters
2, a deletion of the maximum number of reverse
3, B to delete the fewest number of reverse
4, if the remaining number of letters in reverse order are all 0 , and the remaining number is greater than 1, then A wins
5, if the remaining letters of less than or equal to 1 , then B wins
This idea can it
------ For reference only ------------------------------ ---------
nobody does it do ?
------ For reference only -------------------------------------- -
you forgot to say a and B are the subject of strategic priorities for the elimination of more disordered nodes can speed up the algorithm , but a and B are unordered pairs by selecting letters or less ordered letters to win the " a and B are smart enough " on deep water
That I can Oh it. . .
Such things are the default , unless your idea of a very fast hardware , and then also into their company it
------ For reference only ---------- -----------------------------
input string : abcdcabghwhgaha, string length : 15, 6 degrees of disorder
recursively remove the string abcdcabghwhgaha, the degree of disorder is 6, game progress , step 1
input string : abcdcabghwhgaha, remove a character, get a list of strings : [bcdcabghwhgaha, acdcabghwhgaha, abdcabghwhgaha, abccabghwhgaha, abcdabghwhgaha, abcdcbghwhgaha, abcdcaghwhgaha, abcdcabhwhgaha, abcdcabgwhgaha, abcdcabghhgaha, abcdcabghwgaha, abcdcabghwhaha, abcdcabghwhgha, abcdcabghwhgaa, abcdcabghwhgah]
string bcdcabghwhgaha disorder is 6 , the details : DisordeDegree [index = 0, str = bcdcabghwhgaha, disordeDegree = 6]
string acdcabghwhgaha disorder is 6 , the details : DisordeDegree [index = 1, str = acdcabghwhgaha, disordeDegree = 6]
string abdcabghwhgaha disorder is 6 , the details : DisordeDegree [index = 2, str = abdcabghwhgaha, disordeDegree = 6]
string abccabghwhgaha disorder is 6 , the details : DisordeDegree [index = 3, str = abccabghwhgaha, disordeDegree = 6]
string abcdabghwhgaha disorder is 5 , the details : DisordeDegree [index = 4, str = abcdabghwhgaha, disordeDegree = 5]
string abcdcbghwhgaha disorder is 6 , the details : DisordeDegree [index = 5, str = abcdcbghwhgaha, disordeDegree = 6]
string abcdcaghwhgaha disorder is 6 , the details : DisordeDegree [index = 6, str = abcdcaghwhgaha, disordeDegree = 6]
string abcdcabhwhgaha disorder is 6 , the details : DisordeDegree [index = 7, str = abcdcabhwhgaha, disordeDegree = 6]
string abcdcabgwhgaha disorder is 6 , the details : DisordeDegree [index = 8, str = abcdcabgwhgaha, disordeDegree = 6]
string abcdcabghhgaha disorder is 6 , the details : DisordeDegree [index = 9, str = abcdcabghhgaha, disordeDegree = 6]
string abcdcabghwgaha disorder is 5 , the details : DisordeDegree [index = 10, str = abcdcabghwgaha, disordeDegree = 5]
string abcdcabghwhaha disorder is 5 , the details : DisordeDegree [index = 11, str = abcdcabghwhaha, disordeDegree = 5]
string abcdcabghwhgha disorder is 5 , the details : DisordeDegree [index = 12, str = abcdcabghwhgha, disordeDegree = 5]
string abcdcabghwhgaa disorder is 6 , the details : DisordeDegree [index = 13, str = abcdcabghwhgaa, disordeDegree = 6]
string abcdcabghwhgah disorder is 5 , the details : DisordeDegree [index = 14, str = abcdcabghwhgah, disordeDegree = 5]
list of strings obtained after removing one string and returns a string as the minimum degree of disorder : [DisordeDegree [index = 4, str = abcdabghwhgaha, disordeDegree = 5], DisordeDegree ; [index = 10, str = abcdcabghwgaha, disordeDegree = 5], DisordeDegree [index = 11, str = abcdcabghwhaha, disordeDegree = 5], DisordeDegree [index = 12, str = abcdcabghwhgha, disordeDegree = 5], DisordeDegree [index = 14, str = abcdcabghwhgah, disordeDegree = 5]]
removed after a character string abcdcabghwhgaha returns the minimum degree of disorder string is not strictly increasing string : [DisordeDegree [index = 4, str = abcdabghwhgaha, disordeDegree = 5], DisordeDegree [index = 10, str = abcdcabghwgaha, disordeDegree = 5], DisordeDegree [index = 11, str = abcdcabghwhaha, disordeDegree = 5], DisordeDegree [index = 12, str = abcdcabghwhgha, disordeDegree = 5], DisordeDegree [index = 14, str = abcdcabghwhgah, disordeDegree = 5]]
removed after a string abcdcabghwhgaha character , returns the string is not a minimum degree of disorder strictly increasing string to remove the string : DisordeDegree [index = 4, str = abcdabghwhgaha, disordeDegree = 5 ]
removed after a string abcdabghwhgaha character , returns the string minimum degree of disorder string is not strictly increasing , remove string result : abcdabghwhgaha
recursively remove the string abcdabghwhgaha, the disorder is 5 , the game progress , step 2
input string : abcdabghwhgaha, remove a character, get a list of strings : [bcdabghwhgaha, acdabghwhgaha, abdabghwhgaha, abcabghwhgaha, abcdbghwhgaha, abcdaghwhgaha, abcdabhwhgaha, abcdabgwhgaha, abcdabghhgaha, abcdabghwgaha, abcdabghwhaha, abcdabghwhgha, abcdabghwhgaa, abcdabghwhgah]
string bcdabghwhgaha disorder is 5 , the details : DisordeDegree [index = 0, str = bcdabghwhgaha, disordeDegree = 5]
string acdabghwhgaha disorder is 5 , the details : DisordeDegree [index = 1, str = acdabghwhgaha, disordeDegree = 5]
string abdabghwhgaha disorder is 5 , the details : DisordeDegree [index = 2, str = abdabghwhgaha, disordeDegree = 5]
string abcabghwhgaha disorder is 5 , the details : DisordeDegree [index = 3, str = abcabghwhgaha, disordeDegree = 5]
string abcdbghwhgaha disorder is 5 , the details : DisordeDegree [index = 4, str = abcdbghwhgaha, disordeDegree = 5]
string abcdaghwhgaha disorder is 5 , the details : DisordeDegree [index = 5, str = abcdaghwhgaha, disordeDegree = 5]
string abcdabhwhgaha disorder is 5 , the details : DisordeDegree [index = 6, str = abcdabhwhgaha, disordeDegree = 5]
string abcdabgwhgaha disorder is 5 , the details : DisordeDegree [index = 7, str = abcdabgwhgaha, disordeDegree = 5]
string abcdabghhgaha disorder is 5 , the details : DisordeDegree [index = 8, str = abcdabghhgaha, disordeDegree = 5]
string abcdabghwgaha disorder is 4 , the details : DisordeDegree [index = 9, str = abcdabghwgaha, disordeDegree = 4]
string abcdabghwhaha disorder is 4 , the details : DisordeDegree [index = 10, str = abcdabghwhaha, disordeDegree = 4]
string abcdabghwhgha disorder is 4 , the details : DisordeDegree [index = 11, str = abcdabghwhgha, disordeDegree = 4]
string abcdabghwhgaa disorder is 5 , the details : DisordeDegree [index = 12, str = abcdabghwhgaa, disordeDegree = 5]
string abcdabghwhgah disorder is 4 , the details : DisordeDegree [index = 13, str = abcdabghwhgah, disordeDegree = 4]
list of strings obtained after removing one string and returns a string as the minimum degree of disorder : [DisordeDegree [index = 9, str = abcdabghwgaha, disordeDegree = 4], DisordeDegree ; [index = 10, str = abcdabghwhaha, disordeDegree = 4], DisordeDegree [index = 11, str = abcdabghwhgha, disordeDegree = 4], DisordeDegree [index = 13, str = abcdabghwhgah, disordeDegree = 4]]
removed after a character string abcdabghwhgaha returns the minimum degree of disorder string is not strictly increasing string : [DisordeDegree [index = 9, str = abcdabghwgaha, disordeDegree = 4], DisordeDegree [index = 10, str = abcdabghwhaha, disordeDegree = 4], DisordeDegree [index = 11, str = abcdabghwhgha, disordeDegree = 4], DisordeDegree [index = 13, str = abcdabghwhgah, disordeDegree = 4]]
removed after a string abcdabghwhgaha character , returns the string is not a minimum degree of disorder strictly increasing string to remove the string : DisordeDegree [index = 9, str = abcdabghwgaha, disordeDegree = 4 ]
removed after a string abcdabghwgaha character , returns the string minimum degree of disorder string is not strictly increasing , remove string result : abcdabghwgaha
recursively remove the string abcdabghwgaha, the disorder is 4 , game progress , step 3
input string : abcdabghwgaha, remove a character, get a list of strings : [bcdabghwgaha, acdabghwgaha, abdabghwgaha, abcabghwgaha, abcdbghwgaha, abcdaghwgaha, abcdabhwgaha, abcdabgwgaha, abcdabghgaha, abcdabghwaha, abcdabghwgha, abcdabghwgaa, abcdabghwgah]
string bcdabghwgaha disorder is 4 , the details : DisordeDegree [index = 0, str = bcdabghwgaha, disordeDegree = 4]
string acdabghwgaha disorder is 4 , the details : DisordeDegree [index = 1, str = acdabghwgaha, disordeDegree = 4]
string abdabghwgaha disorder is 4 , the details : DisordeDegree [index = 2, str = abdabghwgaha, disordeDegree = 4]
string abcabghwgaha disorder is 4 , the details : DisordeDegree [index = 3, str = abcabghwgaha, disordeDegree = 4]
string abcdbghwgaha disorder is 4 , the details : DisordeDegree [index = 4, str = abcdbghwgaha, disordeDegree = 4]
string abcdaghwgaha disorder is 4 , the details : DisordeDegree [index = 5, str = abcdaghwgaha, disordeDegree = 4]
string abcdabhwgaha disorder is 4 , the details : DisordeDegree [index = 6, str = abcdabhwgaha, disordeDegree = 4]
string abcdabgwgaha disorder is 4 , the details : DisordeDegree [index = 7, str = abcdabgwgaha, disordeDegree = 4]
string abcdabghgaha disorder is 4 , the details : DisordeDegree [index = 8, str = abcdabghgaha, disordeDegree = 4]
string abcdabghwaha the disorder is 3, the details : DisordeDegree [index = 9, str = abcdabghwaha, disordeDegree = 3]
string abcdabghwgha the disorder is 3, the details : DisordeDegree [index = 10, str = abcdabghwgha, disordeDegree = 3]
string abcdabghwgaa disorder is 4 , the details : DisordeDegree [index = 11, str = abcdabghwgaa, disordeDegree = 4]
string abcdabghwgah the disorder is 3, the details : DisordeDegree [index = 12, str = abcdabghwgah, disordeDegree = 3]
list of strings obtained after removing one string and returns a string as the minimum degree of disorder : [DisordeDegree [index = 9, str = abcdabghwaha, disordeDegree = 3], DisordeDegree ; [index = 10, str = abcdabghwgha, disordeDegree = 3], DisordeDegree [index = 12, str = abcdabghwgah, disordeDegree = 3]]
removed after a character string abcdabghwgaha returns the minimum degree of disorder string is not strictly increasing string : [DisordeDegree [index = 9, str = abcdabghwaha, disordeDegree = 3], DisordeDegree [index = 10, str = abcdabghwgha, disordeDegree = 3], DisordeDegree [index = 12, str = abcdabghwgah, disordeDegree = 3]]
removed after a string abcdabghwgaha character , returns the string is not a minimum degree of disorder strictly increasing string to remove the string : DisordeDegree [index = 9, str = abcdabghwaha, disordeDegree = 3 ]
removed after a string abcdabghwaha character , returns the string minimum degree of disorder string is not strictly increasing , remove string result : abcdabghwaha
......
recursively remove the string wah, is a disorder of the game progress , step 13
input string : wah, remove a character, get a list of strings : [ah, wh, wa]
string ah disorder is 0 , the details : DisordeDegree [index = 0, str = ah, disordeDegree = 0]
string wh disorder is 1 , the details : DisordeDegree [index = 1, str = wh, disordeDegree = 1]
string wa disorder is 1 , the details : DisordeDegree [index = 2, str = wa, disordeDegree = 1]
list of strings obtained after removing one string and returns a string minimum degree of disorder is : [DisordeDegree [index = 0, str = ah, disordeDegree = 0]]
removed after a character string wah , returns the minimum degree of disorder of the string is strictly increasing string: 0
input string : abcdcabghwhgaha, the result is a game
------ For reference only ---------------------------------- -----
------ For reference only ---------------------------------- -----
------ For reference only ---------------------------------------
This question should be a core algorithm used in the project . . . Thousands of pieces to buy , Evans will earn too , to do with the individual words at least a week , not worth the price . . .
没有评论:
发表评论