文档章节

[NBOJ0031][Nim-B* Sum]

小弘
 小弘
发布于 2012/10/13 23:19
字数 824
阅读 116
收藏 0
[题目要求]

http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show_problem.php?problem_id=31

[题目涉及的相关理论与算法]
1,博弈论中的NIM游戏。虽然题目中求的Nim和是Nim游戏中的策略,但是和游戏本身关系不大,相当于实现游戏中一个算法。开始不理解的时候觉得很深奥,但是看过一些介绍之后有了初步的了解就好多了。
推荐一个介绍:http://blog.csdn.net/qiankun1993/article/details/6765688,这里面比较详细了介绍了Nim游戏。
2,进制转换的相关运算,这个应该属于基本功。
3,理解“异或运算”实质是在二进制下的不进位加法。本题中出现的运算针对的是B进制下。

[题目中需要注意的地方]
觉得有两点值得一说吧,一个是两个B进制下的数进行运算时要注意对准位。数组存的是逆序的结果。就是a[0]存的是最低位的。
还有一个是,额。。在最后算回十进制数时,我的算法是在循环内多乘了一个B,结果要除以B,但是就是这一个多乘,造成提交时的结果溢出了。。到最后慢慢比较后才发现。。所以千万留神,将结果改成用long long型就AC了。最好的解决办法就是改一下循环体的构造,不多乘那一下。。。这也说明系统测试时的数据真的很大。。都是边缘啊= =。

[思路过程]
开始没太看明白,后来看过介绍之后,对这个博弈论中的经典问题有了了解。知道了Nim和的定义和求法。后面就比较好办了。顺序就是先将两个数转换为相应的进制,然后按位进行不进位加法。得到的结果再转换为十进制输出。

[代码]

#include<iostream>
using namespace std;
int const L = 21;	//因为位数最多的情况就是2进制,而2000000对应的2进制不超过21位。所以设L为21.
void casesolve()
{
	int result[L];
	int X[L];
	int Y[L];
	int n,b,x,y;
	memset(X,0,sizeof(X));
	memset(Y,0,sizeof(Y));
	memset(result,0,sizeof(result));
	cin>>n>>b>>x>>y;
	int i=0;	//辅助的参数。
	int max=0;	//使用max来记录两个转换后的进制数最高的位数,当然这里说的“位数”是B进制下的分组数。
	while(x != 0)	//将x转换为b进制。
	{
		X[i++] = x % b;
		x = x/b;
	}
	max = i;	//此时max记录下x的最高位。
	i=0;	
	while(y != 0)	//同理处理y
	{
		Y[i++] = y % b;
		y = y/b ;
	}
	if(i > max) max =i;//比较x和y哪一个位数高。
	i=0;
	while(i != max)		//这一步是将两个B进制下进行不进位加法。用到了max。
	{
		result[i] = (X[i] + Y[i]) % b;
		i++;
	}
	int sum = 0;
	i=max;
	while((i--) >= 1 )
	{
		sum = sum * b;			//注意这两步骤的顺序。这里是对进制转换的基本算法。
		sum = sum+result[i];	
	}
	cout<<n<<" "<<sum<<endl;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);	
	int t;
	cin>>t;
	while((t--) > 0)
	{
		casesolve();
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

[尾声]
做这道题的时候顺便了解了一点点博弈论中的知识,觉得奥妙无穷啊。今天总算遇到的都是不太讨厌的题目! 还不错~

 

© 著作权归作者所有

小弘
粉丝 12
博文 25
码字总数 24359
作品 0
海淀
私信 提问
VB6 调用 Nim 生成的 DLL

关于 Nim Nim 是德国人 开发的编程语言,最初叫 Nimrod。Nim 有下面几个特点: 强制缩进语法 AST 操控 编译到 C 静态编译 .exe 或 dll 指针 gc Nim 的标准库还可以,一些常用的算法、网络库都...

彩色的铅笔盒
2016/10/26
106
0
Nim如何与C/C++/Objc互动

header pragma(头文件指示): Compile pragma(编译指示): 直接让nim文件使用c/c++代码文件, 编译的时候会先编译.c文件成.o然后链接让nim也能使用其内容. --- Link pragma(连接指示): 直接链接...

路中鸟
2015/07/20
620
0
如何使用lldb/gdb调试Nim程序

一般用nim写程序基本都用echo, repr等命令简单调试, 相信大家也会需要高级调试的时候, 所以在这里介绍如何使用lldb或gdb调试nim程序. 首先输入代码保存test.nim. 然后打开终端. 代码里的变量...

路中鸟
2015/11/25
748
0
决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
2018/02/09
0
0
Nim各种pragma使用方法

Pragmas(编译指示) 编译指示"{."为开始, ".}"为结束, ","号为分隔符, 例如{.cdecl, importc.} deprecated pragma (弃用(分解?)指示) deprecated指示用来标记为弃用. 也可以在声明时使用, 需要......

路中鸟
2015/07/24
514
0

没有更多内容

加载失败,请刷新页面

加载更多

最简单的获取相机拍照的图片

  import android.content.Intent;import android.graphics.Bitmap;import android.os.Bundle;import android.os.Environment;import android.provider.MediaStore;import andr......

MrLins
37分钟前
4
0
说好不哭!数据可视化深度干货,前端开发下一个涨薪点在这里~

随着互联网在各行各业的影响不断深入,数据规模越来越大,各企业也越来越重视数据的价值。作为一家专业的数据智能公司,个推从消息推送服务起家,经过多年的持续耕耘,积累沉淀了海量数据,在...

个推
39分钟前
7
0
第三方支付-返回与回调注意事项

不管是支付宝,微信,还是其它第三方支付,第四方支付,支付机构服务商只要涉及到钱的交易都要进行如下校验,全部成功了才视为成功订单 1.http请求是否成功 2.校验商户号 3.校验订单号及状态...

Shingfi
42分钟前
4
0
简述Java内存分配和回收策略以及Minor GC 和 Major GC(Full GC)

内存分配: 1. 栈区:栈可分为Java虚拟机和本地方法栈 2. 堆区:堆被所有线程共享,在虚拟机启动时创建,是唯一的目的是存放对象实例,是gc的主要区域。通常可分为两个区块年轻代和年老代。更...

DustinChan
47分钟前
6
0
Excel插入批注:可在批注插入文字、形状、图片

1.批注一直显示:审阅选项卡-------->勾选显示批注选项: 2.插入批注快捷键:Shift+F2 组合键 3.在批注中插入图片:鼠标右键点击批注框的小圆点【重点不可以在批注文本框内点击】----->调出批...

东方墨天
今天
6
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部