8.23【A】

1927考虑初始状态下前半边和后半边的总和差值x那么B的目标就是让这个差值尽可能接近0然后A的目标是让这个差值远离0然后还要知道当前填的这个数是在前半边还是后半边对于差值为0的必胜态往上延申就是只剩一个问号时能否通过那个问号导向差值为0还是先从正向DFS考虑初始时前后差值为a然后记录问号所在的下标数组dfs返回的应该是当前状态下能否导向差值不为0然后每层的状态就是数组和目前差值以及当前的执行人对于最底层的叶子节点对于A无论如何选都可以导向直接返回true对于B如果差值为正且最后的问号在前面那么一定为true如果差值为正问号在后面但差值大于9也一定为true否则为false对于差值为负的情况则完全对称然后是遍历与合并对每个还没确定的问号遍历从零到9如果当前是A在执棋那么只要有一个是true那就返回true否则false如果是B在执棋只要有一个false那就返回false否则true更自然的底层节点描述对比class Solution { public: bool sumGame(string num) { int nnum.size(),count0; vectorboolvis(n,false);//cur为true则为A执棋否则为B functionbool(int,int,bool)dfs[](int delta,int cnt,bool cur)-bool{ // if(cnt1){ // if(cur){return true;} // for(int i0;in;i){ // if(!vis[i]){ // if(in/2delta-9){return false;} // if(in/2delta9){return false;} // return true; // } // } // } if(cnt0){ return delta!0; } bool res; for(int i0;in;i){ if(!vis[i]){ vis[i]true; for(int j0;j9;j){ //cnt; if(in/2){resdfs(deltaj,cnt-1,!cur);} else{resdfs(delta-j,cnt-1,!cur);} if(rescur){break;} if(!res!cur){break;} } vis[i]false; if(rescur){break;} if(!res!cur){break;} } } return res; }; int tmp0,i0; for(;in/2;i){ if(num[i]!?){ vis[i]true; tmp(num[i]-0); }else{ count; } } for(;in;i){ if(num[i]!?){ vis[i]true; tmp-(num[i]-0); }else{ count; } } return dfs(tmp,count,true); } };这版 DFS 的逻辑是正确的但会超时。因为?最多可以很多DFS 枚举量爆炸。正解B的获胜条件为什么是“2 * delta 9 * (rightQ - leftQ)”即这个等式是怎么来的如果问号在两侧B自然可以抵消A的影响但也可以超过A配的数来进一步抵消差值啊而且在同侧时B为什么要选择9-x一定要配出9呢没理解