再 放 送
4月24日的时候我讲了这学期程序设计与算法实践的第一课,内容包括算法时间复杂度的概念,枚举与递归等。其中关于枚举这方面还是比较有意思的,从易到难总结了三道题目枚举题,其他的内容就是老生常谈了。实际上枚举算法看似简单又不能很轻易掌握,因为枚举也是有技巧与策略的。在一道具体的题目中,暴力的枚举很可能行不通,但是聪明的枚举往往能起到“四两拨千斤”的效果。
练习题目
1.素数判定
定义一个数是素数当且仅当它是一个大于1的自然数,且不含有除1和它本身以外的因数。
直接枚举2到n−1的所有数,看是否能整除n,时间复杂度O(n)。
考虑到如果n是合数,那么就能写成n=a×b(1<a,b<n)的形式。
不妨设a≤b
那么就有n=a×b≥a2
即a≤n
也就是说如果n是合数,那么就一定有一个根号范围内的因数,所以枚举上界一下子就降下来了,时间复杂度O(n)。
(题目在bnuoj上也有http://www.bnuoj.com/problem_show.php?pid=7931)
给出一个数n(1≤n≤1018) ,判断n的因数中有没有平方数。比如18有,21没有。
直观上来看,需要枚举根号范围内的正整数x,判断n是否是x2的倍数,时间复杂度O(n)。
如果n满足条件,则一定可以表示成n=ab2(b=1)的形式。
显然a,b不同时大于106。
那么我们只需要分别枚举判断即可,其中枚举a时需要看除完后是否是完全平方数,这个随便搞搞就好了,总的时间复杂度O(n31)。
很久之前写的代码了,还是不建议直接用sqrt开方(精度误差),可以开完之后比如在加减5的范围内再for一下找找:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| #include<bits/stdc++.h> using namespace std; typedef long long ll; bool square(ll x) { ll y=(ll)sqrt(x+0.5); return x==y*y; } bool squarefree(ll x) { if(square(x)) return false; for(ll i=2;i<=x/i/i;i++) { if(x%(i*i)==0) return false; if(x%i==0 && square(x/i)) return false; } return true; } int main() { int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { ll x; scanf("%lld",&x); printf("Case %d: ",cas); if(squarefree(x)) puts("Yes"); else puts("No"); } }
|
题目来源是2016 ACM-ICPC World Finals(近几年我校唯一没进总决赛的一次),当时算是第三、四道简单签到题,不过这个签到就非常有水平了。
给一个十进制数n(10≤y≤1018),和一个下届L(10≤L),找到最大的正整数B,使得n在B进制下只有0到9的数字,并且再当成十进制翻译后,要至少为L。
题意比较绕,还是需要结合样例理解一下。
直接从大到小枚举进制B,然后进制转换,验证是否符合条件,找到就退出,然而光是枚举就需要O(n),显然不行。
最简单的例子,比如不管n多大,只要下届是10,答案就可以是n进制。
观察到一个数由更大的进制表示时,位数是越来越短的。具体来说
比如n=a0+a1B+a2B2+a3B3+…
发现当B>106时,B3>1018,也就是说当枚举到B>106时,表示出来的长度不会超过3位。又因为每一位必须是0到9的数字(不能有ABCDEF这样的),那么我直接一个三层循环枚举表示后的结果,最后解一个关于B的一元二次方程n=a0+a1B+a2B2就非常trivial了。
最后把这两种枚举方式得到的答案取最大值即可,总的时间复杂度O(n31)。
代码写的稍微有点难看,训练的时候以为中间爆long long了,实际是别的地方的问题:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,L; int len; int d[30]; int getlen(ll x) { int ans=0; while(x) { ++ans; x/=10; } return ans; } bool ok(ll n,ll l,ll B) { int cnt=0; while(n) { if(n%B>=10) return false; d[cnt++]=n%B; n/=B; } ll now=0; for(int i=cnt-1; i>=0; --i) now=now*10+d[i]; return now>=l; }
int main() { scanf("%I64d%I64d",&n,&L); len=getlen(L);
ll ans=10; for(ll B=2000000; B>=10; --B) if(ok(n,L,B)) { ans=B; break; } for(int i=0; i<10; ++i) for(int j=0; j<10; ++j) for(int k=0; k<10; ++k) if(i*100+j*10+k>=L) { if(i==0 && j==0) assert(false); ll l=0,r=n,mid; while(l<r) { mid=(l+r+1)/2; if(i*mid+j<=(n-k)/mid) l=mid; else r=mid-1; } if(l>=10 && (n-k)%l==0 && (n-k)/l==i*l+j) ans=max(ans,l); } printf("%I64d\n",ans); }
|