国庆刷题笔记

出场题目一:P1217 [USACO1.5]回文质数 Prime Palindromes

1. cin和cout

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
int a;

cin>>a;
scanf("%d",&a);
//这两句话输入的结果完全相同。

cout<<a<<endl;
printf("%d\n",a);
//这两句话输出的内容完全相同。

//ps: scanf和printf效率会略高于cin和cout,在数据量不大的时候没有区别。

return 0;
}

2.布尔型

1
2
bool a;
//a=true(1) or a=false(0)

3.定义函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isPal(int x)	//定义判断回文数的函数
{
int xx=x,y=0; //备份x
while(xx>0)
{
int x1=xx%10;
y=y*10+x1;
xx=xx/10;
}
return x==y; //x=y时返回真,反之返回假
}

bool isPrime(int x)
{
// for(int i=2;i<x;i++) if(x%i==0) return false;
// for(int i=2;i*i<=x;i++) if(x%i==0) return false;
for(int i=2;i<=sqrt(x);i++) if(x%i==0) return false;
/*
如果一个数是合数,那它最小的因子一定小于等于其平方根。
注意sqrt()函数需要调用<math.h>。注释掉的第二行代码是不调用sqrt()的办法。
*/
return true;
}

4.求一个数的位数

1
2
3
4
5
6
7
8
9
10
11
int GetDigit(int x)
{
int n=0;
while(x>0)
{
n++;
x=x/10;
}
return n;
}
//不需要什么注释。

5.素数筛

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
/*
算法1:从2开始将其倍数都标为合数。然后从下一个没被标记的数开始重复此过程。
缺点:有的数会被筛好几次,例如231=3*7*11。

算法2:创建一个存储素数的数组,如果一个新数不能被所有小于它的素数整除,那它就是一个素数,将其加入这个数组。
*/

bool isPrime(int x, int Prime[], int nP)
{
for(int i=0; i<nP; i++)
if(x%Prime[i]==0)
return false;
return true;
}

//......
int main()
{
int f[N]={0}; // 假设2...N都是素数 f[i]=0表示i是素数 f[i]=1表示i不是素数
for(int i=2; i<N/2; i++)
{
if(f[i]==1) continue;
// 筛除每个i的倍数
for(int k=2; i*k<N ;k++)
f[i*k]=1; // 2的倍数不是素数
}
int Prime[1230],nP=0;
for(i=2; i<N; i++)
if(f[i]==0)
{
Prime[nP]=i; nP++;
}

//......

return 0;
}

*6.生成回文数的一种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//此处选取王琼老师代码的一段,在确定位数的情况下枚举每一位的可能情况。

for(x1=1; x1<=9; x1++) // 7位整数 1百万...1千万-1
for(int x2=0; x2<=9; x2++)
for(int x3=0; x3<=9; x3++)
for(int x4=0; x4<=9; x4++)
{
int x=x1*1000+x2*100+x3*10+x4*1;
int y=x3*100+x2*10+x1*1;
x=x*1000+y;
if(x<a) continue;
if(x>b) return 0;
if(isPrime(x, Prime, nP)==true)
cout<<x<<endl;
}

出场题目二:P2615 [NOIP2015 提高组] 神奇的幻方

1.使得代码简洁的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define N 40	//用N代替100000等大数或者题目数据上限,使得接下来的代码简洁
void Output(int a[N][N],int n) //混搭函数、变量名大小写,避免占用保留字
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++) cout<<a[i][j]<<' ';
cout<<endl;
}
}
//打印a数组中i行j列的内容

int main()
{
int a[N][N]={0}; //初始化数组,将其中所有项化为0(虽然默认是0)

//......

Output(a,n);
}

2.怎么做模拟题

模拟,意为“它怎么说,你怎么做”。照着题干描述实现程序即可。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!