A:题目：http://codeforces.com/contest/735/problem/A
题意：出发点G，终点T，每次只能走k步，#不能走，问能否到达终点
思路：暴力
1 #include <stdio.h> 2 #include <string.h> 3 char str[110]; 4 void YES(){ 5 printf("YES "); 6 } 7 void NO(){ 8 printf("NO "); 9 } 10 void solve(int n,int k){ 11 int st,ed; 12 for(int i=1;i<=n;i++){scanf(" %c",&str[i]);if(str[i]=='G') st=i;else if(str[i]=='T') ed=i;} 13 if(st<ed){ 14 while(st<=ed){ 15 st+=k; 16 if(st>n) { 17 NO(); 18 return ; 19 } 20 if(st==ed){ 21 YES(); 22 return ; 23 } 24 if(str[st]=='#'){ 25 NO(); 26 return ; 27 } 28 } 29 NO(); 30 } 31 else if(st>ed){ 32 while(st>=ed){ 33 st-=k; 34 if(st<1){ 35 NO(); 36 return ; 37 } 38 if(st==ed){ 39 YES(); 40 return ; 41 } 42 if(str[st]=='#'){ 43 NO(); 44 return ; 45 } 46 } 47 NO(); 48 } 49 50 } 51 int main(){ 52 int n,k; 53 while(scanf("%d %d",&n,&k)!=EOF){ 54 solve(n,k); 55 } 56 }
B：题目：http://codeforces.com/contest/735/problem/B
题意：有n个值，分成两部分分别有n1,n2个，求两部分的平均值之和的最大值
思路：sum1/n1+sum2/n2 要尽量大，肯定排序从大往小选
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=1e5+10; 7 int a[maxn]; 8 bool cmp(int a,int b){ 9 return a>b; 10 } 11 int main(){ 12 int n,n1,n2; 13 while(scanf("%d %d %d",&n,&n1,&n2)!=EOF){ 14 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 15 sort(a+1,a+1+n,cmp); 16 int x=min(n1,n2); 17 int y=max(n1,n2); 18 long long sum1=0,sum2=0; 19 for(int i=1;i<=x;i++) sum1+=a[i]; 20 for(int i=x+1;i<=x+y;i++) sum2+=a[i]; 21 double ans=0; 22 ans=sum1/(x*1.0)+sum2/(y*1.0); 23 printf("%.7f ",ans); 24 } 25 return 0; 26 }
C：题目：http://codeforces.com/contest/735/problem/C
题意：两个人能比赛的条件为两个人之前打过比赛场数的差值不超过1，问胜者最多能打多少场比赛
思路：递推，假设打n场所需要的最少人数是a[n]，那么要打n+1场比赛，那么在打了n场的基础上，最少需要一个打了n-1场比赛的人才能打，所以要打n+1场比赛所需要的最少人数是a[n+1]=a[n]+a[n-1]，即a[n+2]=a[n+1]+a[n]，a[1]=1,a[2]=3;
1 #include <cstdio> 2 #include <cmath> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=100; 7 long long Fi[maxn]; 8 void solve() { 9 Fi[1]=2,Fi[2]=3; 10 for(int i=3;i<=1000;i++) { 11 Fi[i]=Fi[i-1]+Fi[i-2]; 12 if(Fi[i]>=(long long)1e18) { 13 break; 14 } 15 } 16 } 17 int main(){ 18 long long n; 19 solve(); 20 while(scanf("%I64d",&n)!=EOF) { 21 int pos=lower_bound(Fi+1,Fi+1+87,n)-Fi; 22 if(Fi[pos]>n) pos-=1; 23 printf("%d ",pos); 24 } 25 return 0; 26 }
D：题目：http://codeforces.com/contest/735/problem/D
题意：一个数n的最小花费为n的最大约数（除了自己本身） ，现在n可以被分成k个数，n=n1+n2+...+nk,(nk>=2)，n现在所需要的费用是k个数的费用总和，求n的最小花费
思路：很明显质数的最小费用是1，也就是看一个数能由多少个质数组成就是多少，一开始用的暴力过的，枚举前5000个数，对每个数找每次找最近的质数减掉然后再对n进行dp，dp[n]=min(dp[n-j]+dp[j],dp[n]),后来想了想好像就是哥德巴赫猜想。。
即任一大于2的偶数都可写成两个素数之和，那么当n是素数是答案是1，n是偶数或者n-2是质数，那么答案是2，其他的答案就是3（因为可以奇数可以拆为一个奇数加一个偶数，素数肯定是奇数）
1 #include <stdio.h> 2 #include <iostream> 3 #include <map> 4 using namespace std; 5 map<int,int> m; 6 bool judge(int n){ 7 for(int i=2;i*i<=n;i++){ 8 if(n%i==0) return false; 9 } 10 return true; 11 } 12 const int maxn=5000; 13 int dp[maxn]; 14 int Cal(int num){ 15 int cnt=0; 16 while(num){ 17 for(int j=num;;j--){ 18 if(judge(j)){ 19 num-=j; 20 cnt++; 21 break; 22 } 23 } 24 } 25 return cnt; 26 } 27 int main(){ 28 int n; 29 while(scanf("%d",&n)!=EOF){ 30 m[0]=0; 31 m[1]=1; 32 for(int i=2;i<=5010;i++){ 33 m[i]=Cal(i); 34 } 35 int cnt=0; 36 for(int i=n;i>=max(n-5000,2);i--){ 37 m[i]=Cal(i); 38 39 } 40 for(int i=n;i>=max(n-5000,2);i--) 41 m[n]=min(m[n],m[n-i]+m[i]); 42 printf("%d ",m[n]); 43 } 44 }
版本:
1 #include <cstdio> 2 bool judge(int n){ 3 for(int i=2;i*i<=n;i++)if(n%i==0) return false; 4 return true; 5 } 6 int main(){ 7 int n; 8 while(scanf("%d",&n)!=EOF){ 9 if(judge(n)){ 10 printf("1 "); 11 } 12 else if(judge(n-2)||n%2==0){ 13 printf("2 "); 14 } 15 else printf("3 "); 16 } 17 return 0; 18 }
E,F留坑