问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

输入一个字符串str,从串str的第k个字符开始取n个字符存为子串str1,不足n个则取到串尾。

发布网友 发布时间:2022-04-12 14:39

我来回答

2个回答

懂视网 时间:2022-04-12 19:00

Time Limit: 10000ms Case Time Limit: 1000ms Memory Limit: 256MB Description Consider a string set that each of them consists of {0, 1} only. All strings in the set have the same number of 0s and 1s. Write a program to find and output the K


Time Limit: 10000ms
Case Time Limit: 1000ms
Memory Limit: 256MB

Description

Consider a string set that each of them consists of {0, 1} only. All strings in the set have the same number of 0s and 1s. Write a program to find and output the K-th string according to the dictionary order. If s?uch a string doesn’t exist, or the input is not valid, please output “Impossible”. For example, if we have two ‘0’s and two ‘1’s, we will have a set with 6 different strings, {0011, 0101, 0110, 1001, 1010, 1100}, and the 4th string is 1001.


Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10000), the number of test cases, followed by the input data for each test case.
Each test case is 3 integers separated by blank space: N, M(2 <= N + M <= 33 and N , M >= 0), K(1 <= K <= 1000000000). N stands for the number of ‘0’s, M stands for the number of ‘1’s, and K stands for the K-th of string in the set that needs to be printed as output.

Output
For each case, print exactly one line. If the string exists, please print it, otherwise print “Impossible”.

Sample In
3
2 2 2
2 2 7
4 7 47

Sample Out
0101
Impossible
01010111011


题目解析:

题意是所有n个0和m个1,然后组合排列,并按照从小到大的顺序排列,找到第k个二进制表示并输出。

好,我们可以组合一下排列,然后按照从小到大的十进制数据顺序来排列,然后查找第k个数据,最后转换为二进制输出。不过这样工作量挺大,我们组合排列的时候也要用二进制来排列。那么我们怎么去排列?先试着将题目中的例子,看看能不能找到什么规律。(接下来我们会看到,数学是很美妙的东西,等分析透彻了再动手写,代码会很简单)


排列组合我们写成Cmn。对于两个0,两个1来说:0011, 0101, 0110, 1001, 1010, 1100。

第一类:第一个数据为0011,最小,对应n个零+m个1;

第二类:第二个数据和第三个数据的时候,最高位的1增加,最低位的0降低,这时一个0一个1有两种组合(c21)

第三类:第四个到第六个数据,最高位1再提高一位至二进制的最高位,这时后面两个0和一个1有三种组合(c32)


同样我们可以通过两个0和三个1来组合成十个数:00111,01011,01101,01110,10011,10101,10110,11001,11010,11100

第一类:n个零+m个1——00111

第二类:最高位1进一位,后面m-1个1和1个0全排列——01011,01101,01110(c31)

第三类:最高位1再进一位,后面m-1个1和2个0全排列——10011,10101,10110,11001,11010,11100(c42)


通过这两个例子我们可以看到如下规律:

1+c(m-1+1)1+c(m-1+2)1+...+c(m-1+i)i+...+c(m-1+n)n

也就是最高位1不断提高,0的个数不断增加,组合数自然也不断增加。

通过展开组合数,第i个c(m-1+i)i和c(m-1+i-1)(i+1)的关系是:c(m-1+i+1)(i+1) = c(m-1+i)i * (m-1+i+1) / (i+1);


通过上述分析,不难看出,这里可以利用递归的形式,让1不断提高,直到所有的组合数超过k为止,必然k在c(m-1+i)i 中出现,那么可以确定n-i个0在最开始,紧接着是1,最后是i个零和m-1个1的组合!再递归的确定剩余的0和1的关系即可!但有一点需要注意,如果恰好1+...+c(m-1+i)i == k;那么就可以确定i个零在最后,m-1个1在前面。


代码如下:

#include 
#include 



int FindKthString(int arr[],int n,int m,int k);

int main(void)
{
 int n,m,k;

 while(1){
 printf("
please input n,m,k:");
 scanf("%d %d %d",&n,&m,&k);
 int *arr = (int *)malloc((n+m) * sizeof(int));
 int result = FindKthString(arr,n,m,k);
 if(!result)
  printf("impossible");
 else{
  for(int i = 0;i < n+m;++i)
  printf("%d",arr[i]);
 }
 free(arr);
 }
 return 0;
}

int FindKthString(int arr[],int n,int m,int k)
{
 int temp=1,sum=1;
 int i;

 if(k <= 0) //传入k不合法
 return 0;

 if(k == 1){ //当k为第一个值的时候,直接返回说要结果:所有的1在末尾
 for(int i = 0;i < n+m;++i){ //n个零,m个一
  if(i= k) //必须加等号,证明i个0在末尾的时候查找成功。
  break;
 sum += temp;
 }
 if(i>n)
 return 0;
 //--i; 这句话不能要,必须在i个零里面才能匹配

 for(int j = 0;j < n+m; ++j){ //将数据分成n-i个0,接着是1,然后i个零,最后m-1个1
 if(j < n-i)
  arr[j] = 0;
 else if(j == n-i)
  arr[j] = 1;
 else if(j < n+1)
  arr[j] = 0;
 else
  arr[j] = 1;
 }
 arr = arr+n-i+1; //调整指针,指向最高位1后面的地方
 if(sum+temp == k){ //如果正好为k,那么最末的i位全为0
 for(int j = 0;j < m+i-1;++j){
  if(j < m-1)
  arr[j] = 1;
  else
  arr[j] = 0;
 }
 return 1;
 }

 int result = FindKthString(arr,i,m-1,k-sum); //递归进行求解
 if(!result)
 return 0;
 return 1;
}


总结:通过这个题可以看出来,数学是多么的美妙,那么复杂的问题,通过一个表达式就给解决了。代码也很简单!碰到问题,尽量导出表达式。









热心网友 时间:2022-04-12 16:08

for(p=str;p<=str+a+b;p++){
if(p>=str+a&&p<=str+a+b-1) printf("%c",*p);
}
声明声明:本网页内容为用户发布,旨在传播知识,不代表本网认同其观点,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。E-MAIL:11247931@qq.com
高考560分能上211大学吗? - 知乎 河北高考多少分能上211大学 河北2023高考211分数线是多少? 考560分能上211大学吗河北 刀剑英雄合王者武器多少费用 刀剑英雄帝辰王者现在什么价位 2021年度工程施工合同范本 2021承包转让简单的合同范本 2021医院食堂承包合同范本 div+css+js实现菜单的收缩与展开 调用数据库内容的时候为什么内容字段... 山地自行车该怎么选择 如何挑选山地自行车 幼儿园园长资格证需要修够多少学分 如何选择合适的山地自行车 qq小程序朋友心里话都是匿名吗 怎样选择一辆质量好,价格不贵的山地自行车? 黑枸杞怎么吃补肾阳虚 服用方法很关键 被冻结,解冻不成功怎么办? 我的被冻结 解冻不了? 学生党,一加7pro和努比亚Z20买哪个好? 被冻结,解冻不成功怎么办? C语言编程:将字符串中第k个字符开始的连续n个字符复制到另一个字符串中 求解答大帝!!!! 电影内容有太空飞船进行空间跳跃的电影有哪些 一部美国电影 男主角在星际飞行的飞船上早醒了几十年,无聊中把女主角弄醒了 关於一部很老的宇宙飞船的电影 求一部关于飞船的科幻电影 求一部太空飞船类科幻电影的名字,里面主角一直认为飞船在太空,最后发现飞船是在水里面。 谁知道2004年以前的所有关于飞船的科幻电影呀。我在找一部没有看完的电影。希望大家帮忙! 求一部关于美国太空飞船的电影! 求一部关于宇宙飞船的电影 市民就餐时扫了下微信二维码 ,几百个好友收到群发广告,扫码后,广告便发出去了。 微信扫码的群发的软件现在能用的是哪一个百分被微侠的时光都跑路了! 智讯快客微信扫码群发软件怎么用? 请各位提供几篇最新短篇英文故事(300字左右).哪些网站或杂志上有此类文章? 以感恩为主题500字左右的英文作文,初中的! 关于&quot;启动&quot;的问题,知道的进 局域网共享? Wii的事情 常用的doc命令有什么 C语言编程,编写函数去除字符串 S 从第 k 个字符开始的 n 个字符。 溜肉段用什么淀粉最脆 做溜肉段汤汁可以用马铃薯淀粉吗? 做溜肉段/锅包肉的淀粉用什么的最好?? 做溜肉段/锅包肉的淀粉用什么的最好? 什么是特殊医学用途配方食品实行何种管理制度 特殊医学用途配方食品有哪些 到底该如何分辨特殊医学用途配方食品和普通食品之间的区别? 使用索尼T300数码相机的小窍门? 什么营业执照可以进特殊医学药品奶粉 爱优诺特殊医学奶粉的作用