塔里木油田公司档案馆网站建设研究,wordpress主页404,临沂网站域名,一个人做网站可以做什么Description小明比较喜欢研究各种各样的数字#xff0c;有一天他发现了一类数#xff0c;并将这些数命名为“小明数”#xff0c;下面是“小明数”的定义#xff1a;
数字的二进制由连续的k个1和连续的k-1个0组成。
比如#xff1a;
1#xff08;二进制为#xff1a;1有一天他发现了一类数并将这些数命名为“小明数”下面是“小明数”的定义
数字的二进制由连续的k个1和连续的k-1个0组成。
比如
1二进制为1k1
6二进制为110k2
120二进制为1111000k4
496二进制为111110000k5
现在给你一个数字n求他所有的因子里最大的“小明数”。Input第1行一个数T表示后面用作输入测试的数的数量。1 T 10^5)
第2 - T 1行每行1个数n。1 n 10^5)Output共T行每行对应每个测试用例的结果Sample Input 1 2
3
992Sample Output 11
496思路刚开始没算好时间复杂度所以直接暴力在main函数里面
#includeiostream
#includecstring
using namespace std;int a[100];
int b[100];
int huansuan(int n,int a[]) {int p0;//一共p位数 while(n) {a[p]n1;n1;p;}
// for(int i p-1; i0; i--) {
// couta[i];
// }
// coutendl;return p;
}
bool ok(int x) {if(x1) return true;int p huansuan(x,b);int cnt00;for(int i 0; ip; i) {if(b[i]0) cnt0;else break;}if(cnt0*21!p) return false;//因为这里要考虑到cnt00的情况也就是想到了x1的情况了 for(int i cnt0; ip; i) {if(b[i]!1) return false;}return true;}
int main()
{int n,t;cint;while(t--) {memset(a,0,sizeof(a));cinn;huansuan(n,a);for(int i n-1; i0; i--) {if(ok(i)) {printf(%d\n,i); break;}}}return 0 ;}
而且没加上是因子的判断很失败、、
TLE之后发现打表刚开始的打表也是失败的
//超时做法
#includeiostream
#includecstring
using namespace std;int a[100];
int b[100];
int db[100005];int huansuan(int n,int a[]) {int p0;//一共p位数 while(n) {a[p]n1;n1;p;}
// for(int i p-1; i0; i--) {
// couta[i];
// }
// coutendl;return p;
}
bool ok(int x) {if(x1) return true;int p huansuan(x,b);int cnt00;for(int i 0; ip; i) {if(b[i]0) cnt0;else break;}if(cnt0*21!p) return false;//因为这里要考虑到cnt00的情况也就是自然想到x1的情况了 for(int i cnt0; ip; i) {if(b[i]!1) return false;}return true;}
void dabiao() {db[1]db[2]1;for(int i 2; i10005; i) {memset(a,0,sizeof(a));memset(b,0,sizeof(b));huansuan(i,a);for(int j i-1; jdb[i]; j--) {//这样并不能简化运算复杂度甚至更高了不像筛法求素数一样因为这个不是记忆化if(ok(j)) { //也就是你虽然k那层for循环更新了db值但并不一定是最终结果所以意义不大 db[i]j; //建议在看一看线性时间筛法求素数中是怎么降低时间复杂度的那才是真正的记忆化for(int k idb[i]; k10005; kdb[i]) {//你这个记忆化卵用没有只是先找到了较优解并非最优解所以此处无意义。 db[k]db[i]; // 只有A*算法类似的才需要较优解其余情况需要记忆的是最优解才有意义。 }break;}}}}
int main()
{int n,t;scanf(%d,t);dabiao(); while(t--) {scanf(%d,n);printf(%d\n,db[n]);}return 0 ;}
依旧TLE并且比时间复杂度略高于直接双层forps:其实直接双层for时间复杂度也是o(n^2)虽然内层不是1~100005但是取平均去掉系数依旧是o(n^2)
下面是思考后的打表
#includeiostream
#includecstring
using namespace std;
int db[10];
int cnt0;
void dabiao() {db[0]1;cnt;db[1]6;cnt;//cnt2;int n6;int tmp1,tmp2;while(n100005) {tmp1n2;ndb[cnt]tmp1( 1cnt );//需要加括号
// coutdb[cnt]endl;cnt;}}
int main()
{int n,t;scanf(%d,t);dabiao();
// for(int i 0; icnt; i) {
// printf(%d\n,db[i]);
// }while(t--) {scanf(%d,n);if(n1) {printf(1\n);continue;} for(int i cnt-2; i0; i--) {//小细节需要-1不然就爆零了 if( ndb[i] (n%db[i]0)) {printf(%d\n,db[i]);break;}}}return 0 ;} /*
1
6
28
120
496
2016
8128
32640
130816*/24ms运行时间、、、还有一点要注意的是因子的定义eg : 6是6的因子所以ndb[i]
等号不能拉下很气、、
总结先看题啊算一算时间复杂度这题数据量1e5所以不打表就至少1e10肯定TLE所以打表是肯定的了再审题发现不需要像第一版那样去遍历1e5来找符合小明数的而应该根据题目小明数的特点直接位运算得到若干个小明数即你可以直接找出这些小明数并且一共就不多就8个那为什么还要遍历求呢直接算把次就好了啊或者直接提前算好然后再数组里直接赋值初始化极好极好。
另附网络版用快速幂做的但是个人感觉没有必要#include iostream
#include cstdio
#include cstring
#include string
using namespace std;
int a[100000];
int cnt 0;
int q_pow(int a,int b){ int ans 1; while(b){ if(b1) ans * a; b 1; a * a; } return ans;
}
void getnum(){ int t 1; int num; do{ int tmp 2 * t - 2; int tmp2 t; num 0; while(tmp2){ num q_pow(2,tmp); tmp2--; tmp--; } if(num 100000) a[cnt] num; t; }while(num 100000);
}
int main(){ getnum(); for(int i 0; icnt; i) {couta[i]endl;} int t,n; scanf(%d,t); while(t--){ scanf(%d,n); for(int i cnt-1; i 0; i--){ if(n % a[i] 0){ printf(%d\n,a[i]); break; } } } return 0;
}
/*
1
6
28
120
496
2016
8128
32640
*/
