DHUOJ 基础 52 53 54

序列

作者: ZhuKai

时间限制: 2s

章节: 一维数组

问题描述

明明的爸爸经常用做游戏的方法启发明明对数学的兴趣。有一次，明明爸爸准备了许多盒子和球，他要和明明做一个放球的游戏。

游戏如下：要将k个小球依次装入到若干个盒子中去（可以使用的盒子数不限）。

小球装入盒子的规则如下：

1）第一个盒子不能为空。

2）依次装入各个盒子的球数必须严格递增。例如：当k=8时，装入方法有1，2，5或1，3，4。

3）装入的盒子数尽可能多。

4）所有相邻盒子的球数之差的绝对值之和最小。

如上例中：装入法1，2，5，则差的绝对值之和为(2-1)+(5-2)=4。装入法1，3，4，则差的绝对值之和为(3-1)+(4-3)=3。因此应该采用后一种装法。

明明明白了规则以后，就兴致盎然地玩起了游戏。起先明明玩得很有劲，每次都能顺利的找出最佳的装小球的方法。但是随着小球数量的增多，装小球的方法也就变得越来越多，明明就需要花更多的时间才能找到最佳的装球方法，这使得明明有些犯难了。于是明明想到了你，他想请你帮他写一个程序，他把小球的数量告诉你，而你的程序用来计算装小球的方法。

明明的问题可以归结为：告诉你小球的数量k，然后通过程序计算出盒子装小球的最佳方法。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅占一行，每行有一个整数k（1 ≤k ≤10000），即小球的个数。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一串整数，即表示依次放入各个盒子里的小球的个数，每两个数字之间用一个‘,’分隔。每组运算结果单独占一行，其行首和行尾都没有任何空格或其他任何字符，每组运算结果与其后一组运算结果之间没有任何空行或其他任何字符，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他任何字符。 注：通常，显示屏为标准输出设备。

个人总结

1、自己没想出来，数论拆分类型：

要让拆分后的数的个数最多，核心原则是：尽可能先取最小的连续正整数（1,2,3,...），因为小数字能堆砌更多个数；若取完连续小数字后还有剩余值，再将剩余值从最后一个数开始，从后往前依次加 1（保证所有数仍互不相同）。

代码

#include <bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ int end=1,count=0; int arr[200]={0}; while(n>=end){ n=n-end; arr[count++]=end; end++; } int k=count; count--; for(int i=0;i<n;i++){ arr[count--]++; } cout<<arr[0]; for(int i=1;i<k;i++){ cout<<","<<arr[i]; } cout<<endl; } }

双重回文数

作者: xxx

时间限制: 1s

章节: 一维数组

问题描述

如果一个数从左往右读和从右往左读都是一样，那么这个数就叫做回文数。例如，12321就是一个回文数，而77778就不是。当然，回文数的首和尾都应是非零的，因此0220就不是回文数。事实上，有一些数（如21），在十进制时不是回文数，但在其它进制（如二进制时为10101）时就是回文数。 编一个程序，从文件读入两个十进制数 N (1<= N <= 15) S (0 <S <10000) 然后找出前N个满足大于S且在两种或两种以上进制（二进制至十进制）上是回文数的十进制数，输出到文件上。 本问题的解决方案不需要使用大于4字节的整型变量。

输入说明

只有一行，用空格隔开的两个数N和S。

输出说明

N行, 每行一个满足上述要求的数，并按从小到大的顺序输出。

个人总结

1、建立正确的函数

代码

#include <bits/stdc++.h> using namespace std; int ismirror(int n,int base){ int k=n,re=0; while(n>0){ re=re*base+n%base; n=n/base; } if(re==k) return 1; else return 0; } int countmirror(int n){ int count=0; for(int i=2;i<=10;i++){ if(ismirror(n,i)){ count++; if(count>1) return 1; } } return 0; } int main(){ int n,s; cin>>n>>s; int findcount=0; for(int i=s+1;findcount<n;i++){ if(countmirror(i)){ cout<<i<<endl; findcount++; } } }

等差数列

作者: xxx

时间限制: 1s

章节: 一维数组

问题描述

一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...) 在这个问题中a是一个非负的整数，b是正整数。

写一个程序来找出在双平方数集合S中长度为n的等差数列。双平方数集合是所有能表示成p2＋q2的数的集合。

输入说明

第一行: N(3<= N<=25),要找的等差数列的长度。 第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。

输出说明

如果没有找到数列,输出`NONE'。

如果找到了，输出一行或多行, 每行由两个整数组成:a,b 这些行应该先按b排序再按a排序(均为升序)。

将不会有多于10,000个等差数列。

个人总结

1、先用数组存储，然后先循环b再循环a

2、一开始使用的是

for(int k=a,x=0;k<=m*m*2&&x<n;k+=b){ if(arr[k]==0){ flag=0; break; } }

问题在于没有x++会导致死循环

3、更高效的核心代码如下，这样可以不需要两个标记

bool isFind = false; // 从b先开始，题目要求b先排序 for (int b = 1; b <= m * m; b++) { for (int a = 0; a <= m * m; a++) { int i; // 判断前n个是否为双平方 for (i = 0; i < n; i++) { if (arr[a + i * b] == 0) break; } if (i == n) { isFind = true; cout << a << " " << b << endl; } } } if (!isFind) cout << "NONE" << endl;

代码

#include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; int arr[125001]={0}; for(int i=0;i<=m;i++){ for(int j=0;j<=m;j++){ arr[i*i+j*j]=1; } } int mark=0; for(int b=1;b<=m*m;b++){ for(int a=0;a+(n-1)*b<=m*m*2;a++){ if(arr[a]==0) continue;//剪枝 int flag=1; for(int k=1;k<n;k++){ int cur=a+k*b; // 第k项：a+1b、a+2b...a+(n-1)b if(arr[cur]==0){ flag=0; break; } } if(flag==1){ cout<<a<<" "<<b<<endl; mark=1; } } } if(mark==0) cout<<"NONE"<<endl; }