算法总结-1

Author Avatar
Xzhah 3月 30, 2019
  • 在其它设备中阅读本文章

总结1

打扰了,开始刷算法了。

第一点想要总结的是如何快速获得素数,对应的题是B - T-primes

简单来说就是找只有三个因数的数,很显然除了1和他本身,剩下的因数必须是素数,而且这个素数的平方等于该数本身。

那么如何快速找到素数就是此问关键。

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
#include<stdio.h>
#include<math.h>
#include<memory.h>
typedef long long ll;
bool isPrime[1000001];
int PrimeNum[1000001];
ll current=0;
void FindPrime(){
memset(isPrime,true,sizeof(isPrime));
memset(PrimeNum,0,sizeof(PrimeNum));
isPrime[0]=isPrime[1]=false;
for(int t_num=2;t_num<=1000000;t_num++){
if(isPrime[t_num])
PrimeNum[++current]=t_num;
for(ll j=1;j<=current && t_num*PrimeNum[j]<=1000000;j++){ //相当于每个已知素数*t_num遍历下去,这样所有非素数都会被找出来。
isPrime[PrimeNum[j]*t_num]=false;
}
}
}
int main()
{
ll number;
scanf("%I64d",&number);
ll test;
FindPrime();
for(int k=0;k<number;k++)
{
scanf("%I64d",&test);
double temp=sqrt(double(test));
if (temp-ll(temp)==0) //因数只有三个的数一定是平方数,且不是1和自身的那个因数是素数。
{
if (isPrime[int(temp)])
printf("YES\n");
else printf("NO\n");
}
else printf("NO\n");
}
return 0;
}

总结2

动态规划,D - Flood Fill

大意就是给出比如1 2 3 3 3 4 5这样一串数字,选定一个数字,每次只能改变它,连着一样的数字会跟着变,请问最少多少次能变同一。此题思想是,利用递推,比如要把1 2 3变成 1 1 1,那么一定是从1 2 2+1步或者1 3 3加1步

而且最终结果一定是跟最左边或者最右边的数一样。所以我们就把每个点设为起始点和每个点变的区间长度都遍历一次,最后比较得到最小的,代码如下。

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
#include<stdio.h>
#include<memory.h>
typedef long long int;
#define min(a,b) a<b?a:b
int main(){
const int max=5002;
int true_color[5002];
int temp_color[5002];
int num;
int cur=0;
int dp[max][max];
scanf("%d",&num);
for(int i=1;i<=num;i++)
scanf("%d",&temp_color[i]);
for(int i=1;i<=num;i++)
if(temp_color[i]!=temp_color[i+1])
true_color[++cur]=temp_color[i];
memset(dp,0x7f,sizeof(dp));
for(int len=1;len<=cur;len++)
dp[len][len]=0;
for(int len=1;len<=cur;len++)
for(int start=1;start<=cur-len+1 ;start++)
{
int l=start,r=start+len-1;
if(true_color[l-1]==true_color[r+1])
dp[l-1][r+1]=min(dp[l-1][r+1],dp[l][r]+1); //两种情况,如果规划区域两边同色,+1就行,不然一步只能靠近一边
else
{
dp[l][r+1]=min(dp[l][r+1],dp[l][r]+1);
dp[l-1][r]=min(dp[l-1][r],dp[l][r]+1);
}
}
printf("%d\n",dp[1][cur]);
return 0;
}

总结3

1096c emmmmmmm感觉有时候自己在做数学题,这个是正多边形的内角知识,是一个爆破程序。

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<stdio.h>
typedef long long ll;
int main()
{
ll num;
scanf("%I64d",&num);
for(int i=1;i<=num;i++)
{
int flag=0;
float ang;
scanf("%f",&ang);
for(float n=3;n<=998244353;n++)
{
float max_ang=(n-2)*180/n;
float min_ang=90-max_ang/2;
float temp_ang=min_ang;
while(temp_ang<=max_ang)
{
if(temp_ang==ang)
{flag=1;
break;}
temp_ang+=min_ang;
}
if(flag==1)
{
printf("%d\n",int(n));
break;
}
}
}
}

总结4

能用long long 就不用Int 有可能会有溢出问题。