题目链接:uva 12163 - Addition-Subtraction Game
题目大意:两个人进行游戏,对于每一局有一个无向图,给出无向图,每个节点有个K值,两人轮流操作,每次可以选中国一个含有石子的节点,将该节点的一个石子拿掉,然后选择K个有边连接的节点加上一个石子(节点可以重复选择),每个节点的子节点不会超过15个。不能操作的人视为失败。每局有n轮,给定每轮中每个节点上石子的初始值,问先手胜利还是失败。
解题思路:有向图上移动石子的组合游戏,对于没有子节点的节点SG值为0,然后对于每个节点,用记忆化的方式处理出SG值,注意因为要选中K个节点,但是子节点的个数最多为15,然后对于选中偶数次的节点可视没选,所以枚举215状态即可,并且要保证选中的个数奇偶性和K值相同。
对于每一轮给定的初始状态,计算各个子游戏的Nim和即可。
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 105;
vector<int> g[maxn];
int N, M, s[maxn], val[maxn];
inline int bitcount (int x) {
return x == 0 ? x : bitcount(x>>1) + (x&1);
}
int SG (int x) {
if (s[x] != -1)
return s[x];
map<int, int> vis;
int n = g[x].size();
if (n == 0)
return s[x] == 0;
for (int i = 0; i < (1<<n); i++) {
int bit = bitcount(i);
if (bit > val[x] || (bit&1) != (val[x]&1))
continue;
int tmp = 0;
for (int j = 0; j < n; j++) {
if (i&(1<<j))
tmp ^= SG(g[x][j]);
}
vis[tmp] = 1;
}
int ret = -1;
while (vis.count(++ret));
return s[x] = ret;
}
void init () {
scanf("%d%d", &N, &M);
for (int i = 0; i < maxn; i++)
g[i].clear();
int u, v;
for (int i = 0; i < M; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
}
for (int i = 0; i < N; i++)
scanf("%d", &val[i]);
memset(s, -1, sizeof(s));
for (int i = 0; i < N; i++)
s[i] = SG(i);
}
void solve () {
int Q;
scanf("%d", &Q);
for (int i = 1; i <= Q; i++) {
int ret = 0, x;
for (int j = 0; j < N; j++) {
scanf("%d", &x);
if (x&1)
ret ^= s[j];
}
printf("Round#%d: %s\n", i, ret ? "WINNING" : "LOSING");
}
printf("\n");
}
int main () {
int cas;
scanf("%d", &cas);
for (int k = 1; k <= cas; k++) {
init();
printf("Game#%d:\n", k);
solve();
}
return 0;
}
分享到:
相关推荐
Description: Multiband spectral subtraction as proposed by Kamath 2002. Uses adjusts the subtraction coefficient with the frequency as well as the SNR. note that the first 0.25sec of your signal is ...
Robot fish detection based on a combination method of three-frame-difference and background subtraction
ARITHMETICAL FACTS, ADDITION,SUBTRACTION AND MULTIPLICATION.IMPLICATIONS
subtraction is a very popular approach for foreground segmentation in a still scene image. In order to compensate for illumination changes, a background model updating process is generally adopted, ...
采用C语言实现了一种背景建模的方法,vibe算法,该算法性能良好且运算速度较快,该算法基于文章Vibe:a universal background subtraction algorithm for video sequences实现,具有较高的实用价值。
摘要组合游戏是指,信息完全轮流操作的双人游戏。本文将从一个游戏——k 倍动态减法游戏(k-based dynamic subtraction game)的解答出
Spectral-Subtraction-源码.rar
摘要组合游戏是指,信息完全轮流操作的双人游戏。本文将从一个游戏——k 倍动态减法游戏(k-based dynamic subtraction game)的解答出
二进制加法减法运算
保守值法matlab代码K.Sehairi_UATL_BGS_library Matlab背景减法库 最后一页更新17-03-2020 K.Sehairi_UATL_BGS_library是由Sehairi Kamal博士于2015年开发的背景扣除库。它包含30多种使用Matlab实现的背景扣除算法。...
Kamath 2002 提出的多频带频谱减法。使用根据频率和 SNR 调整减法系数。 请注意,信号的前 0.25 秒用于模拟噪声。
适用于复杂背景下的差减法!效果还行!是一个难得的程序,与大家分享哈!
利用VHDL语言编写减法器,并利用七段数码管显示。
matalab code for edege
可以进行图像的边缘检测,效果还行,具有垂直梯度图和水平梯度图
基于减法平均的优化器Subtraction-Average-Based Optimizer
令人敬畏的背景减法精选的背景扣除论文清单和相关应用资源即将举行的计算机视觉会议截止日期ACM MM- 2021年4月17日,中国成都FG- 2021年4月15日,印度焦特布尔CIKM -TBA,昆士兰州,澳大利亚WACV -TBA,通常在6月...
实现加减法 平台:eclipse3.5 tomcat5.5以上-bpel a related addition of a subtraction of the webservice and then use bpel integration and realization of addition and subtraction Platform: eclipse3.5 ...
matlab 背景开发代码BGS图书馆 背景减法库 请 fork 这个仓库: 页面更新: 01/04/2017 库版本: ...Subtraction Library}, booktitle = {IX Workshop de Visão Computacional (WVC'2013)}, address = {R