带分数

题目描述

100 100100 可以表示为带分数的形式：

100 = 3 + 69258 714 100 = 3 + \frac{69258}{714}100=3+

714

69258

。

还可以表示为：100 = 82 + 3546 197 100 = 82 + \frac{3546}{197}100=82+

197

3546

。

注意特征：带分数中，数字 1 11 ~ 9 99 分别出现且只出现一次（不包含 0 00）。

类似这样的带分数，100 100100 有 11 1111 种表示法。

输入格式

从标准输入读入一个正整数 N ( N < 1 0 6 ) N(N<10^6)N(N<10

6

)。

输出格式

程序输出数字 N NN 用数码 1 11 ~ 9 99 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

样例 #1

样例输入 #1

100

1

样例输出 #1

11

1

样例 #2

样例输入 #2

105

1

样例输出 #2

6

1

提示

原题时限 3 秒, 64M。蓝桥杯 2013 年第四届省赛

题意分析

由于 1∼∼9 数字范围超小，所以我们可以直接暴力求解。

怎么暴力呢？

当然是全排列啊！

用全排列枚举每一种可能，再用约束条件去判断一下即可

亮代码

#include

using namespace std;

int book[9]={1,2,3,4,5,6,7,8,9};

vector a;

int to_num(int l,int r) //使数组中的数字变成数

{

int ans=0;

for(int i=l;i<=r;i++)

 ans=ans*10+book[i];

return ans;

}

int main()

{

int n;

cin>>n;

int ans=0;

do

{

 for(int i=0;i<10;i++)

 {

  int num=0;

  num=to_num(0,i);

  for(int j=i+1;j<8;j++)

   if(num+to_num(i+1,j)/to_num(j+1,8)==n&&to_num(i+1,j)%to_num(j+1,8)==0)//约束条件判断

    ans++;

 }

}

while(next_permutation(book,book+9)); //全排列函数

cout<

return 0;

}







【用法总结】C++ STL中 next_permutation函数的用法




题目 1004: [递归]母牛的故事




时间限制: 1s 内存限制: 128MB 提交: 131134 解决: 40146

题目描述

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

输入格式

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0

n=0表示输入数据的结束，不做处理。

输出格式

对于每个测试实例，输出在第n年的时候母牛的数量。

每个输出占一行。




样例输入

2

4

5

0

样例输出

2

4

6




迭代法：




先给出用迭代法的代码，因为它长




#include

using namespace std;

int main()

{

   int n, i;

   int f1, f2, f3, fn;

   while (cin >> n && n != 0)  //输入 n 的值，且 n 不等于0，则进入，否则退出

   {

       f1 = 1;

       f2 = 2;

       f3 = 3;

       if (n == 1)

           cout << f1 << endl;

       else if (n == 2)

           cout << f2 << endl;

       else if (n == 3)

           cout << f3 << endl;

       else

       {

           for (i = 4; i <= n; i++)

           {

               fn = f3 + f1;  

               //把该年迭代为一年前,一年前迭代为两年前，依次类推

               f1 = f2;  //f1代表 3 年前

               f2 = f3;  //f2代表 2 年前

               f3 = fn;  //f3代表 1 年前

           }

           cout << fn << endl;  //fn

       }

   }

   return 0;

}










数组：




最后给出用数组的，用数组相对来说会好一点，因为迭代一次，然后就可以输出了。上面那个代码每输入一个数都需要重新迭代，数量大且多的话，花费的时间会比较多。




#include

using namespace std;

int main()

{

   int n, i;

   int f[55] = { 0,1,2,3 };  //f[0]=0,f[1]=1,f[2]=2,f[3]=3

   for (i = 4; i < 55; i++)

       f[i] = f[i - 1] + f[i - 3];

   while (cin >> n && n != 0)  //输入 n 的值，且 n 不等于0，则进入，否则退出

   {

       cout << f[n] << endl;

   }

   return 0;

}







题目 1084: 用筛法求之N内的素数

题目描述

用筛法求之N内的素数。

输入格式

N

输出格式

0～N的素数

样例输入

100

样例输出

2

3

5

7

11

13

17

19

23

29

31

37

41

43

47

53

59

61

67

71

73

79

83

89

97

#include

int main(){

    int prime[10000]={0};

    int i,j;

    int n;

    scanf("%d",&n);

    prime[0]=prime[1]=1;

    for(i=2;i

        if(prime[i]==0)

              for(j=2;i*j<=n;j++)

                   prime[i*j]=1;

    for(i=0;i

         if(prime[i]==0)

              printf("%d\n",i);

    return 0;

}







题目 1093: 字符逆序




题目描述

将一个字符串str的内容颠倒过来，并输出。str的长度不超过100个字符。

输入格式

输入包括一行。 第一行输入的字符串。

输出格式

输出转换好的逆序字符串。

样例输入

I am a student

样例输出

tneduts a ma I

#include

#include

int main(void)

{

   char strinput[100];

   scanf("%[^\n]", strinput); //除了换行符以外的字符全部接收

   char stroutput[100];

   int i = 0;

   int j = 0;

   int len = strlen(strinput);

   //逆序拷贝

   for (i = len - 1; i >= 0; i--)

   {

       stroutput[j++] = strinput[i];

   }

   stroutput[j] = '\0';

   printf("%s\n", stroutput);

   return 0;

}







题目 1094: 字符串的输入输出处理




时间限制: 1s 内存限制: 64MB 提交: 37388 解决: 14203

题目描述

字符串的输入输出处理。

输入格式

第一行是一个正整数N，最大为100。之后是多行字符串（行数大于N）， 每一行字符串可能含有空格，字符数不超过1000。

输出格式

先将输入中的前N行字符串（可能含有空格）原样输出，再将余下的字符串（不含有空格）以空格或回车分割依次按行输出。每行输出之间输出一个空行。

样例输入

2

www.dotcpp.com DOTCPP

A C M

D O T CPP

样例输出

www.dotcpp.com DOTCPP

A C M

D

O

T

CPP

解题思路:




（1）带空格的要用 cin.getline() 接收输入，接收完就输出。




（2）不带空格的直接用 cin 接收输入，接受完就输出。




注意事项:




输入完 N 后要用 getchar() 接收后面紧跟的回车，不然就会把这个回车视为 getline() 接收的部分，多输出两个回车，而且占用 N 中的一个。




参考代码:




// 题目 1094: 字符串的输入输出处理

#include

#include

using namespace std;

int main() {

   string str;

   int N = 0;

   cin >> N;

   getchar(); // 把 'N' 和 '\n' 一起放进缓冲区，避免多输出两个回车

   while (N-- && getline(cin, str)) {

       cout << str << endl << endl; // 输出带空格的

   }

   while (cin >> str) {

       cout << str << endl << endl; // 输出不带空格的

   }

   return 0;

}







题目 1097: 蛇行矩阵




时间限制: 1s 内存限制: 64MB 提交: 18950 解决: 12790

题目描述

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

输入格式

本题有多组数据，每组数据由一个正整数N组成。（N不大于100）

输出格式

对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。

样例输入

5




样例输出

1 3 6 10 15

2 5 9 14

4 8 13

7 12

11




#include

int  main()

{

   int n,i,j,a,b,temp;

   temp=1;

   scanf("%d",&n);

   for(i=1;i<=n;i++){           //控制行

       a=i-1+temp;              //a作为开头

       temp=a;

       b=i+1;      

       for(j=n+1-i;j>0;j--){     //控制列

           if(i!=n && j==1){ //判断一行最后一个

               a += b;

               printf("%d",a);

           }else{

               if(j==n+1-i){    //判断第一个

                   printf("%d ",a);

               }else{

                   a += b;

                   printf("%d ",a);

                   b++;

               }

           }  

       }

       printf("\n");

   }

   return 0;

}







*题目 1110: 2^k进制数




时间限制: 1s 内存限制: 128MB 提交: 4070 解决: 2066

题目描述

设r是个2^k 进制数，并满足以下条件：

（1）r至少是个2位的2^k 进制数。

（2）作为2^k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。

（3）将r转换为2进制数q后，则q的总位数不超过w。

在这里，正整数k（1≤k≤9）和w（k〈w≤30000）是事先给定的。




问：满足上述条件的不同的r共有多少个？

我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2k 进制数r。

例：设k=3，w=7。则r是个八进制数（2^3=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：

2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。

3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。

所以，满足要求的r共有36个。




输入格式

只有1行，为两个正整数，用一个空格隔开：

k w




输出格式

1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。

（提示：作为结果的正整数可能很大，但不会超过200位）




样例输入

3 7

样例输出

36




解题思路：

这是一个组合数学问题，




注意这句话：作为2^k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。




其实这是在暗示组合数，




显然r中的不会有相同的位




 如果每一位都不同，显然只有严格递增的排列是合法的

这便是组合，




将 r 转化成这种形式（设k为3） 000 000 000 000




 显然除首位外每一位的取值范围为 000 to 111(2^k-1)

 在首位为0的情况下，最多可取 w/k 位，且题目要求大于2位，

 则在首位为0的合法解有 ∑ C(2^k-1,i)(2<=i<=w/k) ，

Ps. 如果 w 模 k 等于 0 仅考虑上述情况即可。




考虑首位不为0的情况




 显然首位不为0的话，r 就有 w/k+1 位，

 除首位外还有w/k位，

 可以枚举首位的取值范围为 1 to 2^(w mod k)-1

 设首位取值为 val

 则剩下 w/k 位 取值范围为 val+1 to 2^k-1

 也就是有 2^k-1-val 个数可取

 所以首位不为0的合法解有 ∑ C(2^k-1-val,w/k)(1<=val<=2^(w mod k)-1)

所以上述两者相加便是正解（需要高精运算）




对于高精运算的处理，我看到了一个比较巧妙的方法避开了复杂的数组运算，就是把上面那些组合数的运算




都转换成了 C(2^k-1,i) ——-> C(2^k-i,i) 然后写C函数的时候不是计算C(2^k-1,i)，而是计算C(2^k-i+i-1,i)。 巧妙之处就在这里，这样可以有效的避免有溢出吧。




注意事项：

本题重要的是看懂题，然后用排列组合思考题




参考代码

#include

#include

using namespace std;

long sump( int n, int m)    //公式为C(n+m-1)(m)

{

   long sum = 1;

   for(int i = 1 ; i <= m ; i++)

       sum *= ( n + m - i );

   for( int i = 1 ; i <= m;i++)

       sum /= i;

   return sum;

}

int main()

{

   int k , w;

       cin >> k >> w;

   int part = w/k + 1;              //一共分为几段

   int max = pow( 2.0 , k);          //取不到，每部分最大取到maxt减去1，就是每一位都是1的时候

   int gao = pow( 2.0, w%k) - 1 ;          //最高位的数最大值,可以是0

    //开始计算，分两种情况，第一种，首段为0，那么后面n位数对应的个数符合c[max-1][n]

   long long sum = 0;

   //去掉最高位部分，还有至少两位数 所以i从2开始

   for(int i = 2 ;i <= part - 1; i++)

       sum += sump( max - i ,i);

     //第二种情况，首段不是0，如果首段为x，解就有C[max-1-x][w/k]    

   for(int i = 1 ; i <= gao ;i++)

       sum += sump( max - w/k - i , w/k);

       cout << sum << endl ;

       return 0;

}

以下是我用c语言写的代码，仅供参考

#include

#include

long sump(int n, int m)        //公式为C(n+m-1)(m)

{

   int i;

   long sum = 1;

   for(i = 1 ; i <= m ; i++)

       sum *= (n+m-i);

   for(i = 1 ; i <= m ; i++)

       sum /= i;

       return sum;

}

int main()

{

   int k ,w ,i ;

       scanf("%d%d",&k,&w);

   int part = w/k + 1;

   int max = pow( 2.0 , k);

   int gao = pow( 2.0, w%k)-1;

   long long sum = 0;

   for(i = 2 ; i <= part - 1;i++)

       sum += sump( max - i,i);

   for( i = 1 ; i <= gao ; i++)

       sum += sump( max - w/k - i , w/k);

       printf("%d\n",sum);

   return 0;

}







来自csdn博主 认真写博客的夏目浅石 的题目们




牛客网—倒置字符串（注释超详解




牛客网—倒置字符串（注释超详解） i like beijing.




#include

#include

void revers(char* left,char* right)

{

   //下面这个方法就是 1 2 3  4 5

   //5 与 1交换然后 依次交换  直到left==right 这不跳出while 循环了嘛，所以拿这个例子你去理解下面这个 代码

   //

while(left

{

 char temp=*right;

 *right=*left;

 *left=temp;

 left++;

 right--;

}

   //看完这个咱还回去哈..

}

//这里先打出c语言主函数部分并且注释学习.

int main()

{

char arr[100];

   //gets函数去输入.  小技巧：gets一次输入一行代码. getchar一次输入一个字符

gets(arr);

char* cur=arr;    

   //这里 用指针cur加* 去取走数组arr的第一个地址.

while(*cur)

{

 char* start = cur;

 char* end = cur;

       //这样定义start 是保存初地址，也可以理解为第一个元素的下标.

       //end 是为了遍历我的字符串对吧？目的也就是找独立的单词.

 while(*end!=' ' && *end!='\0')

 {

  end++;

 }

       //定义一个函数然后作用是为了单词转置，把俩地址传过去.好，我们去瞅瞅定义的函数吧.  向上

       //看吧

 revers(start,end-1);

       //

 if(*end!='\0')

 {

  cur=end+1;

 }

 else

 {

  cur=end;

 }

       //为下一个单词做准备

}

//打印出去

int len=strlen(arr);

revers(arr,arr+len-1);

printf("%s",arr);

return 0;




字符替换




#include

#include

int main()

{

char arr[100010];

char ch,c;

scanf("%s %c %c",&arr,&ch,&c);

int len=strlen(arr);

int i;

for(i=0;i

{

 if(arr[i]==ch)

 {

  arr[i]=c;

 }

 else continue;

}

if(len==i)

{

 printf("%s",arr);

}

return 0;

}

//注意现在注意是一行输入.这里还是需要提醒的，自己在这里卡了几次




奇偶排序




这块应该开到 21 11 11 的数组长度，防止出现未知情况溢出数据了




*#include

int main()

{

int a[20],b[10],c[10],i,j=0,k=0,t,m,n;

for(i=0;i<10;i++)

{

 scanf("%d",&a[i]);

 if(a[i]%2==0)

           b[j++]=a[i];

 if(a[i]%2==1)

           c[k++]=a[i];

}

m=j,n=k;

for(j=0;j

{

 for(i=1;i

 {

  if(b[i-1]>b[i])

               t=b[i-1],b[i-1]=b[i],b[i]=t;

 }

}

for(j=0;j

{

 for(i=1;i

 {

  if(c[i-1]>c[i])

           {

               t=c[i-1]

               c[i-1]=c[i]

               c[i]=t;

           }

 }

}

for(i=0;i

       printf("%d ",c[i]);

for(i=0;i

       printf("%d ",b[i]);

printf("%d\n",b[m-1]);

return 0;

}

//这个题思想就是开三个数组，一个用于输入，2个用来记录奇数和偶数

//然后对俩数组进行冒泡排序后打印.————简单题