Training:筛选法与预处理

HDU 1215:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22310
给出一个数字 n ( n ≤ 500000 ) ,输出n的所有因子的和 a i 。
筛法打表求出500000以内所有 a i 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
using namespace std;
const int maxn=500010;
int n,a[maxn];
int main(){
for(int i=1;i<maxn;++i)
for(int j=i+i;j<maxn;j+=i)
a[j]+=i;
int t;scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",a[n]);
}
return 0;
}

HDU 1286:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=37852
写解题报告才知道,这原来是求欧拉函数 Φ ( n ) 的题,结果数据水了,我是暴过的。 不贴自己代码了,贴个欧拉函数模板。

1
2
3
4
5
6
7
8
9
int phi[maxn]={0,1};
void phi_table (int n) {
for(int i=2;i<=n;++i)
if(!phi[i])
for(int j=i;j<=n;j+=i) {
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}

HDU 1406:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=36674
定义完数:如果一个大于1的正整数的所有因子之和等于它的本身,则称这个数是完数。输入 n u m 1 和 n u m 2
,输出两数之间完数的个数。
打表求出每个数所有因子和,判断是否为完数,求前缀和输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int a[maxn],b[maxn];
int main(){
for(int i=1;i<maxn;++i)
for(int j=i+i;j<maxn;j+=i)
a[j]+=i;
for(int i=1;i<maxn;++i)
if(a[i]==i) b[i]=b[i-1]+1;
else b[i]=b[i-1];
int t;scanf("%d",&t);
while(t--){
int l,r;scanf("%d%d",&l,&r);
if(l>r) swap(l,r);
printf("%d\n",b[r]-b[l-1]);
}
return 0;
}

HDU 2007:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32827
给定一段连续的整数,求出他们中所有偶数的平方和以及所有奇数的立方和。
打表求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2510;
int a[maxn],b[maxn];
int main(){
for(int i=1;i<maxn;++i){
a[i]=a[i-1],b[i]=b[i-1];
if(i&1) a[i]+=i*i*i;
else b[i]+=i*i;
}
int l,r;
while(~scanf("%d%d",&l,&r)){
if(l>r) swap(l,r);
printf("%d %d\n",b[r]-b[l-1],a[r]-a[l-1]);
}
return 0;
}

HDU 1425:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21604
输入 n 个数,从大到小输出前 m 大的数,数的范围 [ − 500000 , + 500000 ] 。
感觉题目原意是想让用数组统计的, n ≤ 1000000 的数据量,快排 O ( n l o g n )
应该会超时,数据水了也能过。
用数组做的,记录每个数字出现次数,从大到小遍历输出。

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
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=500010;
int a[maxn*2];
inline int Scan(){
int res=0,ch,flag=0;
if((ch=getchar())=='-') flag=1;
else if(ch>='0'&&ch<='9') res=ch-'0';
while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
return flag?-res:res;
}
void Out(int k) {
if(k<0) {putchar('-');k=-k;}
if(k>=10) Out(k/10);
putchar(k%10+'0');
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
memset(a,0,sizeof(a));
getchar();
for(int i=0;i<n;++i){
int k=Scan();
++a[k+maxn];
}
bool first=true;
for(int i=2*maxn-1;i>=0;--i){
if(!m) break;
for(int j=a[i];j>0;--j){
if(first) first=false;
else putchar(' ');
Out(i-maxn),--m;
if(!m)break;
}
}
putchar('\n');
}
return 0;
}

HDU 2039:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=32836
输入三个数,判断能否构成三角形。很简单的题,但是坑在题目并没有说是整数,所以要用double。

1
2
3
4
5
6
7
8
9
10
11
#include<cstdio>
using namespace std;
int main(){
int t;scanf("%d",&t);
while(t--){
double a,b,c;
scanf("%lf%lf%lf",&a,&b,&c);
puts(a>0&&b>0&&c>0&&a+b>c&&b+c>a&&a+c>b?"YES":"NO");
}
return 0;
}

HDU 1170:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17623
每组输入一个符号和两个整数,求他们做这种运算的结果。
简单题,但是有坑,坑在如果是除法,整除不输出无意义的零,否则输出。也就是说计算 1 ÷ 10 时,需要输出0.10而不是0.1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<cstdio>
using namespace std;
int main(){
int t;scanf("%d",&t);
while(t--){
getchar();
char c=getchar();
int a,b;scanf("%d%d",&a,&b);
if(c=='+') printf("%d",a+b);
if(c=='-') printf("%d",a-b);
if(c=='*') printf("%d",a*b);
if(c=='/'){if(a%b==0)printf("%d",a/b);else printf("%.2lf",1.0*a/b);}
putchar('\n');
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包