题目链接:uva 1548 - The Game of Master-Mind
题目大意:现在ACM公司要开发一个手游,游戏大致为猜数字,一开始给出p,c和m,p为要猜数字的个数,c为每个数字的最大上限,m为已经猜过的次数,每次猜完系统会给出相应的回复提示,所以接下来有2*m行为前m次的提示。每组提示分两行,一行是当前猜的数字分别有哪些,一行是代表说黑点个数和白点个数,所谓黑点个数即当前猜的数字有多少个与答案的位置且颜色均相同(题目中用数字代表颜色),白点则是颜色相同,位置不同的点。要注意的是黑点和白点是一一对应的,例:ans:1
1 2 guess:2 2 1,这种情况下白点个数为2,不是3,就是ans中的2只能对应guess中的一个2,而且如果是黑点的话,就不能算成是白点。现在要求说找出与答案最相近的序列,即满足先前所猜的m次的序列,并且要求字典序最小。
解题思路:dfs,不过光dfs的话,复杂度为100^10。当时因为题目中给的限定条件特别多,所以如果在过程中对黑点白点的情况进行判断,时间上是没有问题的。
但是在判断黑点和白点的时候要注意,统计时要统计黑点个数和点数总和,因为如果将黑点和白点分开计算的话会比较麻烦,因为会有说guess1:2 1,黑1,白0,这样的话ans为1 1是满足的,但是在dfs0层是,ans中的第一个1就变成了白点,如果剪枝为白点个数为0返回就错了。我的处理方法就感觉像是可以先向黑点预支一样,但是预支也有额度,如果超过现存黑点的个数也是不行的。
#include <stdio.h>
#include <string.h>
const int N = 105;
const int M = 15;
int p, c, m, b[N], w[N], ans[M];
int g[N][M], l[N][N], r[N][N];
int cnt[N], sum[N];
void init () {
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
memset(cnt, 0, sizeof(cnt));
memset(sum, 0, sizeof(sum));
scanf("%d%d%d", &p, &c, &m);
for (int i = 0; i < m; i++) {
for (int j = 0; j < p; j++) {
scanf("%d", &g[i][j]);
r[i][g[i][j]]++;
}
scanf("%d%d", &b[i], &w[i]);
}
}
inline bool judge (int x, int d) {
for (int i = 0; i < m; i++) {
if (x == g[i][d]) {
if (b[i] == cnt[i]) return false;
} else if (l[i][x] < r[i][x]) {
if (sum[i] >= w[i] + b[i]) return false;
}
}
return true;
}
inline void set (int x, int d, int flag) {
if (flag > 0) {
for (int i = 0; i < m; i++) {
if (x == g[i][d])
cnt[i]++;
if (l[i][x] < r[i][x])
sum[i]++;
l[i][x]++;
}
} else {
for (int i = 0; i < m; i++) {
if (x == g[i][d])
cnt[i]--;
l[i][x]--;
if (l[i][x] < r[i][x])
sum[i]--;
}
}
}
bool dfs (int d) {
if (d == p) {
for (int i = 0; i < m; i++)
if (cnt[i] != b[i] || sum[i] != w[i] + b[i]) return false;
return true;
}
for (int i = 1; i <= c; i++) {
if (!judge(i, d)) continue;
set(i, d, 1);
ans[d] = i;
if (dfs(d+1)) return true;
set(i, d, -1);
}
return false;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init ();
bool flag = dfs(0);
if (flag) {
printf("%d", ans[0]);
for (int i = 1; i < p; i++)
printf(" %d", ans[i]);
printf("\n");
} else
printf("You are cheating!\n");
}
return 0;
}
分享到:
相关推荐
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
yolo 剪枝_yolov3剪枝的实现_附项目源码+剪枝教程
人工智能大作业-剪枝算法五子棋+源代码+文档说明 - 小白不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载...
算法部署_对mobilev2-yolov5s进行剪枝+蒸馏_并进行NCNN+TensorRT部署_附详细流程+原理教程_优质算法部署项目实战
基于pytorch的模型剪枝+模型量化+BN合并+TRT部署(cifar数据)
This is a listing of all of the Microsoft Windows resources that the program uses. It includes the icons, bitmaps, and cursors that are stored in the RES subdirectory. This file can be directly ...
不用神经网络强化学习,只用alpha-beta剪枝和搜索实现的下象棋!我们的中国象棋使用python实现,总共2000+行代码,分为走法计算、评估函数与搜索和UI三部分,并采用历史启发算法进行优化,有着不错的效果。可以实现...
YOLOv3-手部检测-训练测试-模型剪枝-模型压缩
自己写的python决策树+随机森林,实现了预剪枝,后剪枝,并且包含了实验报告
算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整课件 32-34 剪枝 算法面试通关40讲完整...
人工智能-项目实践-模型剪枝-基于博弈树α-β剪枝搜索的五子棋AI 最近机器学习很火, 乘着这把火,我也学习了一把,但是没有直接学习深度学习,而是遵从一位老前辈,一定要把人工智能的所有方法都了解掌握了,才能...
对训练好的模型进行通道剪枝(channel pruning),分为两步进行:第一步是channel selection,采用LASSO regression来做,其实就是添加了一个L1范数来约束权重,因为L1范数可以使得权重更加稀疏,这样就可以把那些...
JS五子棋AI,源码+教程,基于Alpha-Beta剪枝算法(不是神经网络) JS五子棋AI,源码+教程,基于Alpha-Beta剪枝算法(不是神经网络) JS五子棋AI,源码+教程,基于Alpha-Beta剪枝算法(不是神经网络) JS五子棋AI,...
基于Alpha-Beta剪枝Max-Min博弈树的五子棋对战AI源码+搜索优化+Qt UI界面(含exe可执行程序).zip基于Alpha-Beta剪枝Max-Min博弈树的五子棋对战AI源码+搜索优化+Qt UI界面(含exe可执行程序).zip基于Alpha-Beta剪枝Max-...
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用!...基于α-β剪枝(Alpha-beta-pruning)的极小极大算法(Minimax-algorithm)实现的井字棋(一字棋、tic-tac-toe)游戏源码+项目说明.zip
制作一个五子棋小游戏,实现人机对战,其中电脑在进行极大值极小值搜索时需要运用α-β剪枝算法。五子棋小游戏的核心是电脑端走步的选取,使用的方法是极大极小值搜索,并且题目要求使用α-β剪枝来提高搜索效率;除...
人工智能小项目,2048棋盘游戏,Alpha-beta剪枝算法, Expectimax搜索 。 人工智能的课程作业,非常简单易懂,纯Javascript实现,运用Alpha-beta剪枝算法,
使用alpha-beta剪枝算法实现中国象棋人机对战,AI具有中级的智能,可以应对一般的象棋爱好者。