当前位置：首页 > news >正文

OJ53 54 55

news 2026/8/30 16:07:16

双重回文数

作者: xxx

时间限制: 1s

章节: 一维数组

问题描述

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

输入说明

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

输出说明

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

总结

对于需要在头插入内容的变量，可以全部先在尾部插入后再做逆置，这样的话时间复杂度会小很多。

#include <iostream> #include <string> #include <algorithm> using namespace std; string shi_change_qt(int n,int jinzhi){ string s=""; while(n>0){ int yushu=n%jinzhi; // s.insert(0,(char)('0'+yushu));//再次提醒一位数字转为char从ascii码角度出发 s.push_back((char)('0' + yushu)); // 始终插在末尾，复杂度 O(1) n=n/jinzhi; } reverse(s.begin(), s.end()); // 循环结束后，统一反转字符串 return s; } int pdhuiwen(string n){ int length=n.length(); for(int i=0;i<length;i++){ if(n[i]!=n[length-1-i]) return 0; } return 1; } int main(){ int N,S; cin>>N>>S; int num=S+1; while(N>0){ int count=0; if(pdhuiwen(to_string(num))) count++; for(int i=2;i<10;i++){ string a=shi_change_qt(num,i); if(pdhuiwen(a)) count++; if(count>=2) break; } if(count>=2) { N--; cout<<num<<endl; } num++; } }

等差数列

作者: 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个等差数列。

总结

预处理：先用一个布尔数组 is_bisquare[2 * M * M + 1] 标记哪些数是双平方数。这比每次去算 p^2+q^2 快得多。
枚举顺序：为了方便输出，你可以外层循环枚举公差 b，内层循环枚举首项 a

#include <iostream> #include <cmath> #include <vector> using namespace std; int main(){ int N,M; cin>>N>>M; bool is_bisquare[125001]={false}; for(int p=0;p<=M;p++){ for(int q=p;q<=M;q++){ int num=p*p+q*q; is_bisquare[num]=true; } } int sumcount=0; for(int b=1;b<=(2*M*M)/(N-1);b++){ for(int a=0;a<M*M;a++){ int count=0; while(count!=N){ if(is_bisquare[a+count*b]) count++; else break; } if(count==N) { cout<<a<<" "<<b<<endl; sumcount++; } } } if(sumcount==0) cout<<"NONE"; }

人见人爱A-B

作者: xxx

时间限制: 1s

章节: 一维数组

问题描述

A和B是两个集合，A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）呵呵，很简单吧？

输入说明

输入数据包含T个测试实例。

首先输入数字T，然后输入T组测试数据，每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间由一个空格隔开.

输出说明

针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.

总结

由于set底层是红黑树，对于it指向的节点需要用*来获取具体数值，it仅仅是个指针

#include <iostream> #include <set> using namespace std; int main(){ int T,n,m; cin>>T; while(T--){ cin>>n>>m; set<int> s; s.clear(); while(n--){ int num; cin>>num; s.insert(num); } while(m--){ int num; cin>>num; if(s.count(num)) s.erase(num); } if(s.empty()) { cout<<"NULL"<<endl; continue; } for(auto it=s.begin();it!=s.end();it++){//由于set底层是红黑树，对于it指向的节点需要用*来获取具体数值，it仅仅是个指针 cout<<*it<<" "; } cout<<endl; } }