算法也太难了吧

用户名：17306366773

访问量：12661

签　名：

我口袋只剩玫瑰一片，此行又山高路远

等　　级
排　　名	431
经　　验	4918
参赛次数	0
文章发表	41
年　　龄	0
在职情况	学生
学　　校	天津工业大学
专　　业

　　自我简介：

TA的其他文章

思维题-解谜游戏
浏览：167

蓝桥杯2019年第十届国赛真题-最长子序列
浏览：118

bfs-大胖子走迷宫
浏览：236

你可能喜欢

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

记忆化搜索-取球博弈

　　作者: 算法也太难了吧　　　　发表时间：2022-03-26 15:06:03 浏览：321　|　评论：0　

原题链接：蓝桥杯2016年第七届真题-取球博弈

dfs搜索每种可能走法，vis数组存出现过的场面防止重复递归
存在对手输则自己赢，不存在则查看是否可能出现平局，若两者情况都没有就必败
注意每次递归交换操作对象
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n[5],vis[1000][2][2];
int dfs(int x,int f,int s){
  if(vis[x][f%2][s%2]!=2){
    return vis[x][f%2][s%2];
  }
  if(x<n[1]){
    if((f%2==1)&&(s%2==0)){
      return 1;
    } else if((f%2==0)&&(s%2==1)){
      return -1;
    } else {
      return 0;
    }
  }
  int res;
  bool p=false;    //记录是否出现平局
  for(int i=1;i<=3;i++){
    if(x-n[i]>=0){
      res=dfs(x-n[i],s,f+n[i]);
      if(res==-1){
        vis[x][f%2][s%2]=1;
        return 1;
      }
      if(res==0){
        p=true;
      }
    }
  }
  if(p){
    vis[x][f%2][s%2]=0;
    return 0;
  }
  vis[x][f%2][s%2]=-1;
  return -1;
}
int main()
{
  cin>>n[1]>>n[2]>>n[3];
  sort(n+1,n+4);
  for(int i=1;i<=5;i++){
    int x;
    cin>>x;
    for(int i=0;i<=x;i++){
      vis[i][0][0]=2;
      vis[i][0][1]=2;
      vis[i][1][0]=2;
      vis[i][1][1]=2;
    }
    int ans=dfs(x,0,0);
    if(ans==1){
      cout<<"+"<<" ";
    } else if(ans==0){
      cout<<"0"<<" ";
    } else if(ans==-1){
      cout<<"-"<<" ";
    }
  }
  return 0;
}

```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

算法也太难了吧

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

人民币问题（C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

记忆化搜索-取球博弈

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

1124题解

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

分解质因数（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

算法也太难了吧

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

人民币问题 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

记忆化搜索-取球博弈

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （Java代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

1124题解

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

分解质因数 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

人民币问题（C语言代码）

　　评论区

分解质因数（C++代码）