【NOIP2012模拟8.7】JZOJ2020年8月8日提高组T1 奶牛编号
2024-09-27 00:00:16
【NOIP2012模拟8.7】JZOJ2020年8月8日提高组T1 奶牛编号
题目
作为一个神秘的电脑高手,Farmer John 用二进制数字标识他的奶牛。
然而,他有点迷信,标识奶牛用的二进制数字,必须只含有K位“1” (1 <= K <= 10)。 当然,每个标识数字的首位必须为“1”。
FJ按递增的顺序,安排标识数字,开始是最小可行的标识数字(由“1”组成的一个K位数)。
不幸的是,他没有记录下标识数字。请帮他计算,第N个标识数字 (1 <= N <= 10^7)。
题解
题意
求第\(n\)小的合法的数
合法:该数在二进制下有且仅有\(k\)个位置为1,最高位一定为1
分析
尝试去构造这个第\(n\)小的数
可以想到利用组合数
首先先确定长度
然后再判断方案数与组合数的大小,选择填0还是1
Code
#include<cstdio>
#define mx 10000000
using namespace std;
int n,k,i,j,s,cc,l,x,c[3005][3005];
int C(int x,int y)
{
if (x==y||y==0) return 1;
if (y==x-1||y==1) return x;
return c[x][y];
}
int main()
{
scanf("%d%d",&n,&k);
if (k==1)
{
printf("1");
for (i=1;i<n;i++)
printf("0");
return 0;
}
c[0][0]=1;
for (i=1;i<3000;i++)
{
c[i][0]=c[i][i]=1;
for (j=1;j<i;j++)
{
c[i][j]=c[i-1][j]+c[i-1][j-1];
if (c[i][j]>mx) c[i][j]=mx;
}
}
s=0;
i=k-1;
j=0;
while (s<n)
{
s+=C(i,j);
i++;
j++;
}
n-=s-C(i-1,j-1);
printf("1");
l=i-1;
x=j-1;
while (l)
{
if (x&&n<=C(l-1,x-1))
{
printf("0");
x--;
}
else
{
printf("1");
if (x) n-=C(l-1,x-1);
}
l--;
}
return 0;
}
最新文章
- 设置 Unix,Linux环境下的NLS_LANG
- No.2 CAS之SPNEGO+LDAP认证配置
- HDU 3342 Legal or Not(判断是否存在环)
- vs xamarin android SharedPreferences
- Protocol Buffer多态
- [转载]《C++0x漫谈》系列之:多线程内存模型
- pycharm快捷键大全
- 「译」如何正确学习JavaScript
- 使用CURL发彩信,短信和进行多线程
- UVA 10795 - A Different Task(递归)
- 什么是Solr搜索
- linux文件相关的命令
- 在CentOS 7.3 中安装 NVIDIA GT730 显卡驱动
- [C++] const与指针的关系
- ACM练习中关于LCS的题目
- PHP的move_uploaded_file()出错解决
- Why I don&#39;t want use JPA anymore
- java中int和Integer比较大小
- R的常用命令
- &ldquo;图片+标签&rdquo;的社交玩法已经被验证?nice 宣布获得新一轮3600万美元融资【转载+整理】
热门文章
- 简单Emacs配置
- Java入门(5)
- 关于Java中泛型、反射和注解的扫盲篇
- Jmeter(二十六) - 从入门到精通 - 搭建开源论坛JForum(详解教程)
- JavaScript的原型对象prototype、原型属性__proto__、原型链和constructor
- CORS跨域请求:前后端分离
- 2012年游戏软件开发独立本科段01B0815自考科目教材
- 软件工程作业--ATM自助银行服务系统
- 还不懂Docker?一个故事安排的明明白白!
- pip install 一个本地包时提示error: Microsoft Visual C++ 14.0 is required.