总结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++){
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)
{
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);
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 有可能会有溢出问题。
