习题10-21二项式系数UVa1649

作者:网络    软件教程库   2020-05-19

1.题目描述:点击打开链接

2.解题思路:本题利用枚举#43;二分解决。问题的关键是选对枚举对象,因为要找c(n,k)=m,如果枚举n的话,一旦m非常大,枚举n就会十分困难。因此枚举对象应为k。根据组合数的性质易知,c(n,n/2)时是最大#20540;,c(n,1)是最小#20540;。由于固定的是k,因此n=2*k时是最小的范围,n=m是最大的范围,这样,即可通过二分法来寻找n。

本题有一个技巧,即在计算组合数时候,不必完整的计算完毕,只要发现中间已经超过了m,说明这个n肯定不是解,返回m#43;1即表示无解。

3.代码:

#define _crt_secure_no_warnings 
#includeiostream
#includealgorithm
#includestring
#includesstream
#includeset
#includevector
#includestack
#includemap
#includequeue
#includedeque
#includecstdlib
#includecstdio
#includecstring
#includecmath
#includectime
#includefunctional
using namespace std;

#define pll pairlong long,long long
#define m(a,b) make_pair(a,b)

using namespace std;
priority_queuepll, vectorpll , greaterpll  q;
long long m;
long long c(int k, long long n)
{
	int i;
	long long f = 1;
	for (i = 1; i = k; i++)
	{
		if ((f / i)(m / (n - i + 1)))//如果发现算到第i步时结果已经超过m了,说明n肯定不是解,返回一个m+1
			return m + 1;
		f *= (n - i + 1);
		f /= i;
	}
	return f;
}
void chk()
{
	long long l, r, mid, t;
	int k;
	for (k = 1; c(k, 2 * k) = m; k++)//最小的范围是c(k,2*k)
	{
		l = k * 2;
		r = m;
		while (l = r)
		{
			mid = (l + r)  1;
			t = c(k, mid);
			if (t == m)
			{
				q.push(m(mid, k));
				if (mid == k * 2) break;
				q.push(m(mid, mid - k));
				break;
			}
			else if (tm)
				l = mid + 1;
			else
				r = mid - 1;
		}
	}
}
int main()
{
	//freopen(t.txt, r, stdin);
	int n, i;
	scanf(%d, n);
	for (i = 1; i = n; i++)
	{
		cin  m;
		chk();
		if (q.size())
		{
			printf(%d\n, q.size());
			int len = q.size();
			for (int i = 0; i  len; i++)
			{
				printf((%lld,%lld)%c, q.top().first, q.top().second, i == len - 1  #39;\n#39; : #39; #39;);
				q.pop();
			}
		}
		else
			puts(0\n);
	}
	return 0;
}


习题10-21 二项式系数 uva1649

原文地址:http://blog.csdn.net/u014800748/article/details/45424285

软件教程库 原文地址:https://www.itjcku.com/9999/1091508.html

阅读全部内容


Tags:习题二项式系数

返回首页



推荐内容

mysql小技巧

selectnow(),user(),version(),database(); #最后输入\c是放弃的意思 des ...

Java学习笔记——面试常客:写出一个死锁的例子

现在的面试挺蛋疼,为了考察大家的语言掌握水平,类#20284;这样的题特别多,不过在某个角度来说确实能看出一个人对某个知 ...

UVA-10396VampireNumbers暴力+打表

题目大意:给出n,要求你输出所有符合规则的n位数 规则如下,这个n位数由两个n/2位数相乘得到,并且满足 1.这n位 ...

CF148D.Bagofmice[概率dp]

题目链接:http://codeforces.com/problemset/problem/148/d 题目大意:一袋子 ...

HDU-1846-BraveGame(巴什博弈)

题目传送:brave game 介绍: 巴什博奕(bash game): 首先我们来玩一个比较古老的报数游戏。a ...

HDU-2149-PublicSale(巴什博弈)

题目传送:public sale 思路:巴什博弈 ac代码: #include lt;cstdiogt; # ...

enum实现售卖机

首先 推荐一下google的代码风格 :https://google-styleguide.googlecode ...

批量添加用户

a、创建用户文件,因为添加的用户比较多,因此编写脚本创建一个用户文件user.txt #!/bin/ba ...

解决侧滑中ViewPager和SlidingMenu的滑动冲突

当我们在使用开源框架slidingmenu时,如果要是使用到viewpager,就会出现滑动冲突。 解决方案: }/** ...

shell打乱文件行

思路,产生一个随机数组,然后按按照数组的元素将文件中行的重新输出 1、随机数组的生成 看书的时候感觉很是简单。第 ...

编程之美2015初赛第二场AB

题目1 : 扑克牌 时间限制:2000ms 单点时限:1000ms 内存限制:256mb 描述 一副不含王的扑 ...

Java设计模式之单例模式(恶汉式和懒汉式)

/* * 单例模式: * 饿汉式:类一加载就创建对象 * 懒汉式:用的时候,才去创建对象 * 面试题:单例模式的 ...

Html简单介绍

1、html--- hypertext markup language 的缩写 --- 超文本 标记 语言. 这个技 ...

configure:error:youmustconfigureinaseparatebuilddirectory

configure glibc-2.14 时出现以下错误: [[email#160;protected] opt]# ...

kohana框架生成feed

创建feed feed::create()斱法用给定癿参数杢创建 rss戒者 atom feed。下面是可接叐癿参数。 ...

用USB安装linux

手边没有光驱,安装ubuntu可以用 linuxlive usb creator 2.9.3,在百度网盘里有的。http ...

一个复杂子查询SQL优化

select * from test.vmark vk where id in (select v.id ...

Java多线程中常见的几个问题

我们都知道,在java中要想实现多线程,有两种手段,一种是继续thread类,另外一种是实现runable接口。  1. ...

OracleDataIntegrator12c-CreatingaCollocatedAgent

http://www.oracle.com/webfolder/technetwork/tutorials/obe/fm ...

CompilingGCC5onOSX

compiling gcc 5 on os x */--> pre.src {backgro ...

查看Linux上MySQL版本信息

如果mysql是用rpm或者yum安装的,可用 #rpm -qa|grep mysql查看. 如: [[email#16 ...

《赢在测试2-中国软件测试专家访谈录》读书笔记

《赢在测试2-中国软件测试专家访谈录》读书笔记 2015-04-30 测试人物经历与观点 1.董杰 百度测试架构师 董杰 ...

Objective-C的KVC和KVO

字面意思分别是: kvc是指key value coding,键值编码。 kvo是指key value observin ...

20150502调试分析之使用gdb远程调试ARM开发板

20150502 调试分析之 使用gdb远程调试arm开发板 2015-05-02 lover雪儿 今天我们要学习 ...

限制Apache日志access.log文件大小

可以在apache的httpd.conf配置文件中配置apache自带的程序rotatelogs的功能。 rotate ...

UVa11561-GettingGold

题目:给你一个二维的地图,里面有陷阱‘t‘,金子‘g‘以及墙壁‘#‘,和普通的道路‘.‘,现在已知一个人在起点‘p‘; ...

configure:error:cannotcomputesuffixofobjectfiles:cannotcompile

centos 6.5下安装gcc-4.8.4 make的时候提示以下错误: configure: error: can ...

我读的第一本书《梦断代码》

一切都是兴趣所在,兴趣才是发展的动力,虽然我们在这个开发过程中不可否认的会遇到挫折、瓶颈,但我认为,地狱与天堂共存 ...

iOS中定时器NSTimer的使用

ios中定时器nstimer的使用 1、初始化 + (nstimer *)timerwithtimeinterval:( ...

数组遍历二叉

//任务二叉树遍历 void cmission::initmission(dword base) { cha ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com