DHUOJ 基础 52 53 54

序列作者: ZhuKai时间限制: 2s章节: 一维数组问题描述明明的爸爸经常用做游戏的方法启发明明对数学的兴趣。有一次明明爸爸准备了许多盒子和球他要和明明做一个放球的游戏。游戏如下要将k个小球依次装入到若干个盒子中去可以使用的盒子数不限。小球装入盒子的规则如下1第一个盒子不能为空。2依次装入各个盒子的球数必须严格递增。例如当k8时装入方法有125或134。3装入的盒子数尽可能多。4所有相邻盒子的球数之差的绝对值之和最小。如上例中装入法125则差的绝对值之和为(2-1)(5-2)4。装入法134则差的绝对值之和为(3-1)(4-3)3。因此应该采用后一种装法。明明明白了规则以后就兴致盎然地玩起了游戏。起先明明玩得很有劲每次都能顺利的找出最佳的装小球的方法。但是随着小球数量的增多装小球的方法也就变得越来越多明明就需要花更多的时间才能找到最佳的装球方法这使得明明有些犯难了。于是明明想到了你他想请你帮他写一个程序他把小球的数量告诉你而你的程序用来计算装小球的方法。明明的问题可以归结为告诉你小球的数量k然后通过程序计算出盒子装小球的最佳方法。输入说明你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据每组测试数据仅占一行每行有一个整数k1 ≤k ≤10000即小球的个数。每组测试数据与其后一组测试数据之间没有任何空行第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。输出说明对于每一组测试数据你写的程序要求计算出一组相应的运算结果并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一串整数即表示依次放入各个盒子里的小球的个数每两个数字之间用一个‘,’分隔。每组运算结果单独占一行其行首和行尾都没有任何空格或其他任何字符每组运算结果与其后一组运算结果之间没有任何空行或其他任何字符第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他任何字符。 注通常显示屏为标准输出设备。个人总结1、自己没想出来数论拆分类型要让拆分后的数的个数最多核心原则是尽可能先取最小的连续正整数1,2,3,...因为小数字能堆砌更多个数若取完连续小数字后还有剩余值再将剩余值从最后一个数开始从后往前依次加 1保证所有数仍互不相同。代码#include bits/stdc.h using namespace std; int main(){ int n; while(cinn){ int end1,count0; int arr[200]{0}; while(nend){ nn-end; arr[count]end; end; } int kcount; count--; for(int i0;in;i){ arr[count--]; } coutarr[0]; for(int i1;ik;i){ cout,arr[i]; } coutendl; } }双重回文数作者: 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 kn,re0; while(n0){ rere*basen%base; nn/base; } if(rek) return 1; else return 0; } int countmirror(int n){ int count0; for(int i2;i10;i){ if(ismirror(n,i)){ count; if(count1) return 1; } } return 0; } int main(){ int n,s; cinns; int findcount0; for(int is1;findcountn;i){ if(countmirror(i)){ coutiendl; findcount; } } }等差数列作者: xxx时间限制: 1s章节: 一维数组问题描述一个等差数列是一个能表示成a, ab, a2b,..., anb (n0,1,2,3,...) 在这个问题中a是一个非负的整数b是正整数。写一个程序来找出在双平方数集合S中长度为n的等差数列。双平方数集合是所有能表示成p2q2的数的集合。输入说明第一行: N(3 N25),要找的等差数列的长度。 第二行: M(1 M250),搜索双平方数的上界0 p,q M。输出说明如果没有找到数列,输出NONE。如果找到了输出一行或多行, 每行由两个整数组成:a,b 这些行应该先按b排序再按a排序(均为升序)。将不会有多于10,000个等差数列。个人总结1、先用数组存储然后先循环b再循环a2、一开始使用的是for(int ka,x0;km*m*2xn;kb){ if(arr[k]0){ flag0; 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; cinnm; int arr[125001]{0}; for(int i0;im;i){ for(int j0;jm;j){ arr[i*ij*j]1; } } int mark0; for(int b1;bm*m;b){ for(int a0;a(n-1)*bm*m*2;a){ if(arr[a]0) continue;//剪枝 int flag1; for(int k1;kn;k){ int curak*b; // 第k项a1b、a2b...a(n-1)b if(arr[cur]0){ flag0; break; } } if(flag1){ couta bendl; mark1; } } } if(mark0) coutNONEendl; }