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