algorithm 题集二 (16.04.30)

algorithm 题集二 (16.04.30)

继上一篇博文讲，有一类题不像上一篇博文的题那样简单但接触后感觉不难，这类题单独做了一个题集二。

POJ 2229 Sumsets

​​ 大意：求解一个数字分解成2的幂的方案数 7: 1) 1+1+1+1+1+1+1 2) 1+1+1+1+1+2 3) 1+1+1+2+2 4) 1+1+1+4 5) 1+2+2+2 6) 1+2+4 分析：注意看第一列，容易知道6和7的分解数一样，即奇数和小于它的最大偶数的一样。 再看第四行，看出来前四种方案都是4或者说5的分解，再将 5) 1+2+2+2 6) 1+2+4 看成 5) 1+1+1 6) 1+2 即3或者说2的分解。 前四种分解是n-2的分解 后两种是n>>1的分解 所以dp[n]=dp[n-2]+dp[n>>1]

#include #include using namespace std;const int mod=1e9;const int N=1e6+10; // 试了试极限，5e8超内存/*int get(int n){ // 栈溢出 if(n==1 || n==0) return 1; return (get(n-2)+get(n>>1))%mod;}*/int dp[N];int main(){ dp[0]=dp[1]=1; for(int i=2;i>1])%mod; } int n; while(cin>>n){ printf("%d\n",dp[n]); } return 0;}

nefu 355 合成陨石

nefu 355 合成陨石 ​​​ fz大学化学系的学生们最近发现了一种奇怪的陨石，这些陨石通过化学反应合成，会放出惊人的破坏力量。为了储存方便，化学系的学生们决定把这些陨石碎块合成一个大的陨石块。每一次合并，可以把两个陨石合成一个，放出的破坏能量是两个陨石的质量之和，而新产生的陨石质量是这两个陨石的质量之和。 为了将这次试验的破坏效果减少到最低，他们想请你帮忙，计算一下可以达到的最小破坏能量值。 分析：优先队列

#include #include #include #include using namespace std;int main(){ int n,a; while(cin>>n){ priority_queue,greater > que; for(int i=0;i

nefu 831 统计good

​​ 给你一些英文单词，你能统计出good有多少个吗？ sample_input 2 i am a good boy! goof good good dood good sample_output 1 3 分析：借助强大的C++字符流string, stringstream。

#include #include #include #include using namespace std;int main(){ int t; string line,word; cin>>t; getchar(); while(t--){ getline(cin,line); int len=line.length(); for(int i=0;i>word) if(word=="good") ans++; printf("%d\n",ans); } return 0;}

nyist 412 Same binary weight

​​ 大意：给出一个数字，其权重是二进制表示的1的个数。求解最小的数字，它大于给定的数字，且权重相同。

分析：使用STL的bitset解决二进制问题很便利。为保证权重不变，只需把原来的1变化位置，即进位和退位。比如：12 —— 1100 ——> 10001 45 —— 101101 ——>110011

#include #include #include using namespace std;typedef long long LL;int main(){ LL n; while(~scanf("%lld",&n)){ bitset<64> bit(n); //for(int i=0;i<35;i++) cout<=0 && bit[i]==0){ zero=i; break; } } bit[zero]=1; bit[one]=0; int sum=0; for(int i=0;i

POJ 3748 位操作

​​ 大意：假设你工作在一个32位的机器上，你需要将某一个外设寄存器的第X位设置成0(最低位为第0位，最高位为第31位)，将第Y位开始的连续三位设置成110（从高位到低位的顺序），而其他位保持不变。对给定的寄存器值R，及X，Y，编程计算更改后的寄存器值R。

#include #include using namespace std;int main(){ int n,x,y; while(~scanf("%x,%d,%d",&n,&x,&y)){ int p=1; p=~(p<

POj 1284 Primitive Roots

​​ 大意：求出N内的原根的个数。 关于原根： gimod p≠gjmod p, 其中i≠j且i,j在1至(p-1)之间，则g为p的原根。 分析： 相关定理： 1)所有的奇素数都是有原根的 2)一个数n有原根，那么他有phi(phi(n))个模n不同余的原根(n是否是素数都可用) 3)一个素数有原根，则有phi(n-1)个原根 第二条就是解决问题的关键

nyist 19 擅长排列的小明

​​ 大意：求出n个数字中m个数字的组合的全排列情况 例如： 4 2 12 13 14 21 23 24 31 32 34 41 42 43

分析：使用C++里的next_permutation()写出所有的全排列情况，输出前m数字即可。

#include #include #include #include using namespace std;int n,m;char s[10]="123456789";int main(){ int t; cin>>t; while(t--){ scanf("%d%d",&n,&m); char s1[10],s2[10],s3[10]; strcpy(s1,s); s1[m]=0; printf("%s\n",s1); strcpy(s2,s); while(next_permutation(s2,s2+n)){ strcpy(s3,s2); s3[m]=0; if(strcmp(s1,s3)){ strcpy(s1,s3); printf("%s\n",s1); } } } return 0;}

51nod 1266 蚂蚁

​​只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。当蚂蚁爬到竿子的端点时就会掉落。由于竿子太细，两只蚂蚁相遇时，它们不能交错通过，只能各自反向爬 回去。对于每只蚂蚁，我们知道它距离竿子左端的距离xi，但不知道它当前的朝向。请计算各种情况当中，所有蚂蚁落下竿子所需的最短时间和最长时间。

关键： 1和2相遇，掉头后，2看做1,1看做2，这样继续前进了。

51nod 1279 扔盘子

​​6 4 3 6 2 3

盘子：2 3 5 2 4

最终有4个盘子落在井内。 分析：dp，追踪最小值

#include #include using namespace std;const int N=5e4+5;int dp[N],q[N];int main(){ //freopen("cin.txt","r",stdin); int n,m,x; while(cin>>n>>m){ for(int i=1;i<=n;i++) { scanf("%d",&x); if(i==1) dp[i]=x; else dp[i]=min(x,dp[i-1]); } for(int i=0;i0;){ if(q[ans]>dp[cur]) cur--; //卡住了，不知道是否在内部 else ans++, cur--; } printf("%d\n",ans); } return 0;}

poj 2773 Happy 2006

​​ 寻找第K个和M互质的数字： 分析：容斥原理+二分查找

#include #include using namespace std;typedef long long LL;const LL N=1e6,M=1e13*1LL;LL pri[N],cnt;bool vis[N];void getpri(LL Max){ cnt=0; for(LL i=2;i<=Max;i++){ if(!vis[i]) pri[cnt++]=i; for(LL j=0;j1) fac[top++]=num;}LL Sum(LL x){ LL g=0; for(LL i=1;i<(1LL<>1; if(Sum(mid)>=k){ ans=mid; r=mid-1; } else l=mid+1; } return ans;}int main(){ //freopen("cin.txt","r",stdin); LL m,k; getpri(N); while(~scanf("%lld%lld",&m,&k)){ solve(m); printf("%lld\n",midfind(k)); } return 0;}

CF 248B Chilly Willy

​​ 大意：求出最小能被2,3,5,7整除的N位数。 分析：四个质数的最小公倍数是210。于是N位数 210×10n−3

但是他不是最小的，最小数可以表示成：210×10n−3−210k 进一步处理成： (100+110)×10n−3−210k=10n−1+11×10n−2%210

nefu 887 循环小数化分数

​​ 分析： 对于一个循环小数，如

0.29(34)100x=29.3410000x=2934.349900x=2934−29=2905x=29059900

故求解循环部分和非循环部分的值及10^n后，按以上做差思路消除循环部分。得到X的分子和分母，化简即可。纯循环小数按上诉过程推导得到 value99⋯9n 非循环小数就不说了。

#include #include #include using namespace std;typedef long long LL;const int N=1e5+5;char str[N];LL gcd(LL a,LL b){ return b==0?a:gcd(b,a%b);}int main(){ while(~scanf("%s",str)){ int len=strlen(str); LL f1=0,f2=0,z1=1,z2=1; bool loop=0; for(int i=2;i1&&z2>1){ LL m=z1*z2-z1; LL n=f1*z2+f2-f1; LL d=gcd(n,m); printf("%lld/%lld\n",n/d,m/d); } else if(z1==1&&z2>1){ LL m=z2-1; LL d=gcd(f2,m); printf("%lld/%lld\n",f2/d,m/d); } else if(z1>1&&z2==1){ LL d=gcd(f1,z1); printf("%lld/%lld\n",f1/d,z1/d); } } return 0;}

UVA 10025 The ? 1 ? 2 ? … ? n = k problem

​​ 大意：?1?2?3……?n=k，?可以取+或-，求解最小的n 分析：设非负数的和是s1，负数的和是s2，那么有

S1+S2=kS1−S2=(n+1)n2⟶2S1=k+n(n+1)22S2=k−n(n+1)2

所以，k−n(n+1)2≤0 , 且为偶数

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。