甚至总和也是两个玩家的游戏，在c＃中。 [英] Even sums is a game for two players, in c#.

问题描述

甚至总和也是两个玩家的游戏。给予玩家一系列N个正整数并轮流轮流。在每个回合中，玩家选择非空切片（连续元素的子序列），使得该切片中的值的总和是偶数，然后移除切片并连接序列的其余部分。第一个无法进行合法移动的玩家输掉比赛。



你对对手玩这个游戏你想知道你是否能赢，假设两个你和你的对手发挥得最好。你先移动。



写一个函数：



class解决方案{public string solution（int []一个）;在给定由N个整数组成的零索引数组A的情况下，返回一个格式为X，Y的字符串，其中X和Y分别为，


假设你有一个获胜策略，你应该在第一步中为了获胜而删除的切片的第一个和最后一个位置（包括）。如果存在多个这样的获胜切片，则该函数应该返回具有最小值X的那个。如果存在多个具有最小值X的切片，则该函数应该返回最短的。如果您没有获胜策略，该功能应返回NO SOLUTION。



例如，给定以下数组：

A [0] = 4

A [1] = 5

A [2] = 3

A [3] = 7

A [4] = 2



函数应返回1,2。在从位置1到2移除切片（具有5 + 3 = 8的偶数和）之后，剩余的阵列是[4,7,2]。然后对手将能够移除第一个元素（偶数为4）或最后一个元素（偶数为2）。之后你可以做一个只包含[7]的数组的移动，这样你的对手就不会有合法的举动而会输掉。其中一个可能的游戏如下图所示：



注意删除切片2,3（偶数为3 + 7 = 10）也是一个胜利的举动，但切片1,2的X值较小。



对于以下数组：

A [0 ] = 2

A [1] = 5

A [2] = 4



函数应该返回NO SOLUTION，因为没有策略可以保证您获胜。



假设：



N是[1..100,000]范围内的整数;

数组A的每个元素都是[1..1,000,000,000]范围内的整数。



复杂性：



预期最坏情况时间复杂度为O（N）;

预期最坏情况空间复杂度为O（N），超出输入存储空间（不包括输入参数所需的存储空间）。



输入数组的元素可以修改。



什么我试过了：

 public static int solution（int [] A）
 {
 / /使用.NET 4.5（Mono）在C＃6.0中编写代码
 int [] forw = new int [A.Length]; 
 int [] rewi = new int [A.Length]; 
 
 bool isAllNeg = true; 
 
 for（int i = 1; i< A.Length; i ++）
 {
 forw [i] = Math.Max（0，forw [i  -  1] + A [i]）; 
 if（A [i]> 0&& isAllNeg）
 isAllNeg = false; 
 
} 
 
 if（isAllNeg）
 {
 return 0; 
} 
 
 for（int i = A.Length  -  2; i> = 0; i--）
 {
 rewi [i] = Math。 Max（0，rewi [i + 1] + A [i]）; 
} 
 
 int maxsum = 0; 
 for（int i = 1; i< A.Length  -  1; i ++）
 {
 maxsum = Math.Max（maxsum，forw [i  -  1] + rewi [i + 1]）; 
} 
 
返回maxsum; 
} 

编译错误：无法将int巧妙地转换为字符串。



可以任何一个PLZ帮助我



谢谢

解决方案

错误不是在该代码中：它可能在代码中调用它。

从Visual Studio开始，双击错误列表窗格中的错误消息。

那将带您到有问题的行，并将错误部分用红色加下划线。

仔细查看该行，并且在尝试组合整数和字符串时应该相当明显。如果这是您想要做的，那么您将需要一个显式转换，因此对整数值使用ToString方法。

我使用javascript获得解决方案，请参考下面的代码，
 
 Javascript代码：
 
函数len（obj）{
 if（obj instanceof Array || typeof obj ===& amp; quot; string& amp; quot;）
 return obj.length; 
 else {
 var count = 0; 
 for（var i in obj）{
 if（obj.hasOwnProperty（i））
 count ++; 
} 
返回计数; 
} 
} 
 
功能检查（开始，结束）{
 if（start& amp; gt; end）{
 res =& amp;＃39; NO SOLUTION& amp;＃39 ;; 
} 
 else {
 res = start.toString（）+& amp; amp; amp; amp; amp; amp;＃39; + end.toString（）; 
} 
 
返回res; 
} 
 
函数trans（strr）{
 if（strr ==& amp;＃39; NO SOLUTION& amp;＃39;）{
 return [1，-1] 
} 
 else {
a = strr.split（& amp; amp;＃39;，& amp;＃39;）; 
} 
 
返回[parseInt（a [0]），parseInt（a [1]）]; 
} 
 
函数解（A）{
 odd_list = []; 
 for（var ind = 0; ind& amp; lt; A.length; ind ++）
 {
 if（A [ind]％2 == 1）{
 odd_list .push（parseInt函数（IND））; 
} 
} 
 
 if（len（odd_list）％2 == 0）{
 return check（0，len（A） -  1）; 
} 
 
 tempList = odd_list; 
 odd_list = []; 
 
 odd_list.push（-1）; 
 
 for（var i = 0; i& amp; lt; tempList.length; i ++）{
 odd_list.push（tempList [i]）; 
} 
 
 odd_list.push（len（A））; 
 
 var res_cand = []; 
 count = odd_list [1]; 
 second_count = len（A） -  1  -  odd_list [odd_list.length-2]; 
 first_count = odd_list [2]  -  odd_list [1]  -  1; 
 
 if（second_count& amp; gt; = count）{
 res_cand.push（trans（check（odd_list [1] + 1，len（A） -  1  -  count）） ）; 
} 
 
 if（first_count& amp; gt; = count）{
 res_cand.push（trans（check（odd_list [1] + count + 1，len（A） ） -  1）））
} 
 
 twosum = first_count + second_count; 
 
 if（second_count& amp; lt; count& amp; amp; amp; amp; count& amp; lt; = twosum）{
 res_cand.push（trans （check（odd_list [1] +（first_count  - （count  -  second_count））+ 1，odd_list [odd_list.length-2]）））; 
} 
 
 count = len（A） -  1  -  odd_list [odd_list.length-2]; 
 first_count = odd_list [1]; 
 second_count = odd_list [odd_list.length-2]  -  odd_list [odd_list.length-3]  -  1; 
 
 if（first_count& amp; gt; = count）{
 res_cand.push（trans（check（count，odd_list [odd_list.length-2]  -  1）））; 
} 
 
 if（second_count& amp; gt; = count）{
 res_cand.push（trans（check（0，odd_list [odd_list.length-2]  -  count -  1）））
} 
 
 twosum = first_count + second_count; 
 
 if（second_count& amp; lt; count& amp; amp; amp; amp; count& amp; lt; = twosum）{
 res_cand.push（trans （check-count-second_count，odd_list [odd_list.length-3]）））
} 
 
 cur = [-1，-2]; 
 
 res_cand = res_cand.sort（sortFunction）; 
 
 for（var i = res_cand.length-1; i& amp; gt; = 0; i--）{
 var row = res_cand [i]; 
 if（row [0]！== -1）{
 cur = row; 
} 
} 
 
返回支票（cur [0]，cur [1]）; 
} 
 
函数sortFunction（a，b）{
 if（a [0] === b [0]）{
 return 0; 
} 
 else {
 return（a [0]& amp; lt; b [0]）？ -1：1; 
} 
} 
 
您可以在下面的小提琴链接中获得答案
 
 https://jsfiddle.net/3ed1kuoj/</pre> 

Even sums is a game for two players. Players are given a sequence of N positive integers and take turns alternately. In each turn, a player chooses a non-empty slice (a subsequence of consecutive elements) such that the sum of values in this slice is even, then removes the slice and concatenates the remaining parts of the sequence. The first player who is unable to make a legal move loses the game.

You play this game against your opponent and you want to know if you can win, assuming both you and your opponent play optimally. You move first.

Write a function:

class Solution { public string solution(int[] A); }

that, given a zero-indexed array A consisting of N integers, returns a string of format "X,Y" where X and Y are, respectively, the first and last positions (inclusive) of the slice that you should remove on your first move in order to win, assuming you have a winning strategy. If there is more than one such winning slice, the function should return the one with the smallest value of X. If there is more than one slice with the smallest value of X, the function should return the shortest. If you do not have a winning strategy, the function should return "NO SOLUTION".

For example, given the following array:
A[0] = 4
A[1] = 5
A[2] = 3
A[3] = 7
A[4] = 2

the function should return "1,2". After removing a slice from positions 1 to 2 (with an even sum of 5 + 3 = 8), the remaining array is [4, 7, 2]. Then the opponent will be able to remove the first element (of even sum 4) or the last element (of even sum 2). Afterwards you can make a move that leaves the array containing just [7], so your opponent will not have a legal move and will lose. One of possible games is shown on the following picture:

Note that removing slice "2,3" (with an even sum of 3 + 7 = 10) is also a winning move, but slice "1,2" has a smaller value of X.

For the following array:
A[0] = 2
A[1] = 5
A[2] = 4

the function should return "NO SOLUTION", since there is no strategy that guarantees you a win.

Assume that:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

What I have tried:

public static int solution(int[] A)
        {
            // write your code in C# 6.0 with .NET 4.5 (Mono)
            int[] forw = new int[A.Length];
            int[] rewi = new int[A.Length];

            bool isAllNeg = true;

            for (int i = 1; i < A.Length; i++)
            {
                forw[i] = Math.Max(0, forw[i - 1] + A[i]);
                if (A[i] > 0 && isAllNeg)
                    isAllNeg = false;

            }

            if (isAllNeg)
            {
                return 0;
            }

            for (int i = A.Length - 2; i >= 0; i--)
            {
                rewi[i] = Math.Max(0, rewi[i + 1] + A[i]);
            }

            int maxsum = 0;
            for (int i = 1; i < A.Length - 1; i++)
            {
                maxsum = Math.Max(maxsum, forw[i - 1] + rewi[i + 1]);
            }

            return maxsum;
        }

compilation error: can not implicityly convert int to string.

can any one plz help me

Thanks

解决方案

The error isn't in that code: it's possibly in the code that calls it.
Start with Visual studio, and double click on the error message in the "Error List" pane.
That will take you to the line that has the problem, and will underline the error part in red.
Look closely at the line, and it should be fairly obvious where you are trying to combine integers and strings. If that is what you want to do, then you will need an explicit conversion, so use the ToString method on the integer value.

I got solution using javascript , please refer below code,

Javascript Code :

    function len(obj){
    if(obj instanceof Array || typeof obj === "string")
        return obj.length;
    else {
        var count = 0;
        for(var i in obj){
            if(obj.hasOwnProperty(i))
            count++;
        }
        return count;
    }
    }
    
    function check(start, end) {
    if (start > end) {
        res = 'NO SOLUTION';
    }
    else {
        res = start.toString() + ',' + end.toString();
    }

    return res;
    }

    function trans(strr){
    if (strr =='NO SOLUTION') {
        return [1, -1]
    }
    else {
       a = strr.split(',');
    }
        
    return [parseInt(a[0]), parseInt(a[1])];
    }

    function solution(A){
    odd_list = [];
    for(var ind=0; ind<A.length; ind++)
    {
        if(A[ind]%2==1) {
            odd_list.push(parseInt(ind));    
        }
    }
    
    if (len(odd_list)%2 == 0) {
        return check(0, len(A) - 1);
    }
        
     tempList = odd_list;
     odd_list = [];
     
     odd_list.push(-1);
     
     for(var i=0; i< tempList.length; i++) {
         odd_list.push(tempList[i]);
     }
         
     odd_list.push(len(A));
        
     var res_cand = [];
     count = odd_list[1];
     second_count = len(A) - 1 - odd_list[odd_list.length-2];
     first_count = odd_list[2]- odd_list[1] - 1;
     
     if (second_count >= count) {
        res_cand.push(trans(check(odd_list[1] + 1 , len(A) - 1 - count ))); 
     }
        
     if (first_count >= count) {
        res_cand.push(trans(check(odd_list[1] + count + 1, len(A) - 1))) 
     }
          
    twosum = first_count + second_count;
    
    if (second_count < count && count <= twosum) {
        res_cand.push(trans(check(odd_list[1] + (first_count - (count -     second_count )) + 1, odd_list[odd_list.length-2] )));
    }
    
    count = len(A) - 1 - odd_list[odd_list.length-2];
    first_count = odd_list[1];
    second_count = odd_list[odd_list.length-2] - odd_list[odd_list.length-3] - 1;
    
    if(first_count >= count) {
        res_cand.push(trans(check( count, odd_list[odd_list.length-2] - 1 )));
    }

    if (second_count >= count) {
        res_cand.push(trans(check( 0, odd_list[odd_list.length-2] - count - 1)))
    }
        
    twosum = first_count + second_count;
    
    if(second_count < count && count <= twosum) {
        res_cand.push(trans(check(count-second_count, odd_list[odd_list.length-3])))
    }
        
    cur = [-1, -2];
    
    res_cand =  res_cand.sort(sortFunction);
    
    for(var i= res_cand.length-1 ; i >= 0 ; i--) {
          var row = res_cand[i]; 
          if(row[0] !== -1) {
            cur = row;  
          }
    }
    
    return check(cur[0], cur[1]);
    }

    function sortFunction(a, b) {
    if (a[0] === b[0]) {
        return 0;
    }
    else {
        return (a[0] < b[0]) ? -1 : 1;
    }
    }

You can get the answer in below fiddle link

https://jsfiddle.net/3ed1kuoj/</pre>

这篇关于甚至总和也是两个玩家的游戏，在c＃中。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！