寒假训练七之暴力枚举~

2019-11-06 06:03:53

字体：大中小

来源：转载

供稿：网友

丹青楼

PRoblem:A

Time Limit:1000ms

Memory Limit:65536K

Description 在NEFU校园内，有一栋丹青楼，总共有17 777 777 777层，编号从- 8 888 888 888 到8 888 888 888。尤其是，这里有0层，即在-1层与1层之间。有一个观点存在于NEFU学生心中，那就是数字‘8’是幸运数字。而且，如果一个整数里面至少包含一个数字‘8’那么这个整数就是幸运的，即在这楼层考试，你就肯定不会挂科。例如，8，-180，808这些都是幸运数字，42，-10这些不是。那么，你即将在丹青楼参加一场考试，考场楼层让你选。你现在在a层，你需要找一个最小的正整数b,你往上再走b层就可以到达为幸运数字的楼层，从而确保这场考试不挂。

Input 输入为一个整数，即题干中所描述的a(-10^9<=a<=10^9)

Output 输出只有一行，即所要求的b。

Sample Input 179 -1 18 Sample Output 1 9 10

代码

#include <iostream>#include<stdio.h>#include<cmath>using namespace std;int main(){ int a,y,i; while(cin>>a) { for(i=a+1;; i++) { int flag=0; int k=abs(i); while(k!=0) { int s=k%10; k=k/10; if(s==8) { flag=1; break; } } if(flag==1) break; } int k1=abs(i-a); cout<<k1<<endl; } return 0;}

数学题

Problem:B

Time Limit:1000ms

Memory Limit:65536K

Description 由于参加数学考试时你没有选对幸运楼层，数学肯定是挂了，现在你开始为开学前补考做准备。现在你遇到了一个数学题，对于下面的这个方程，你要求出x(0 < x < 10^9)的所有整数解 x=b*S(x)^a+c 其中a,b,c是给定的值，函数S(x)求得是整数x上的所有数字之和。现在，需要你来解决这道题。

Input 输入只有一行，分别为题干中描述的a,b,c(1<=a<=5, 1<=b<=10000,-10000<=c<=10000)

Output 输出有两行，第一行为n，表示你找到了n组解，第二行为n个整数，即你找到的对于上述方程的n个解，且以升序排列。每个解都严格大于0且小于10^9。

Sample Input 3 2 8 1 2 -18 2 2 -1

Sample Output 3 10 2008 13726 0 4 1 31 337 967

代码

#include <iostream>#include<stdio.h>#include<cmath>#include<algorithm>using namespace std;int main(){ int a,b,c; int s[1000]; int j,len,h,sum1,i,d; while(cin>>a>>b>>c) { for(i=1,j=0,sum1=0; i<=81; i++) { for(d=0,h=1; d<a; d++) h*=i; int x=b*h+c; int k=x; int sum=0; while(x!=0) { sum+=x%10; x=x/10; } if(sum==i) { sum1++; s[j]=k; j++; len=j; } } cout<<sum1<<endl; if(sum1!=0) { sort(s,s+len); cout<<s[0]; for(j=1; j<len; j++) cout<<" "<<s[j]; cout<<endl; } } return 0;}

素数问题

Problem:C

Time Limit:1000ms

Memory Limit:65536K

Description 现在给你一个正整数n(n<=10000),问你有多少组(p1,p2,p3)满足p1<=p2<=p3，p1,p2,p3都是素数，且p1+p2+p3=n

Input 输入只有一行，为n(n<=10000)

Output 输出也只有一行，即所问有多少组(p1,p2,p3)

Sample Input 3 9 Sample Output 0 2

代码

这道题之前会写…..然后过了几个星期后居然又忘记咋写了…orz.. 写错是因为时间超时，我的想法一开始很简单就是把1-n的素数全部存到数组中，然后三个循环把和为n的情况求出来…. 但是吧，这样是超时的…..3个循环花费的时间貌似有点多呀。。然后我看了其他题又想到了另一种想法，就是用两层循环，n减去那两个数，得到p3,判断p3是不是质数，但是判断它是不是质数的时候是在那两重循环里的，所以时间花的很多，因此也行不通。。。。

#include<iostream>#include <stdio.h>#include <math.h>#include<string.h>#include<algorithm>using namespace std;int main(){ int n,i,j,len; int a[10000],b[10000]; while(cin>>n) { memset(b,0,sizeof(b)); for(int x=2,i=0; x<=n; x++) { if(x==2||x==3) { a[i]=x; i++; len=i; b[x]=1; } else { for(j=2; j<x; j++) { if(x%j==0) break; } if(j>=x) { a[i]=x; i++; len=i; b[x]=1; } } } int sum=0; for(int k1=0; k1<len; k1++) for(int k2=0; k2<len; k2++) { int k3=n-a[k1]-a[k2]; if(a[k1]<=a[k2]&&a[k1]<=k3&&a[k2]<=k3) { if(b[k3]==1) sum++; } } cout<<sum<<endl; }}

上一篇：二．指针的定义及运算

下一篇：洛谷 P1111 修复公路