首页 > 代码库 > cf#382div2
cf#382div2
A.
题意：字符串长度n,每次可向左向右跳k个格子。要求不能在障碍物处停留（‘#’），可以在空地处停留（‘ . ’）。给出字符串，从G开始，问能不能到达T。
分析：直接从G处开始向两边搜，如果能到T则输出YES，如果到达边界或到障碍物#停止搜索。、
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; char s[105]; int main() { int n,k,po; bool flag=0; scanf("%d%d",&n,&k); for(int i=0;i<n;i++) { cin>>s[i]; if(s[i]==‘G‘) po=i; } for(int i=po;i>=0;i-=k) { if(s[i]==‘T‘) { flag=1; break; } else if(s[i]==‘#‘) break; } for(int i=po;i<n;i+=k) { if(s[i]==‘T‘) { flag=1; break; } else if(s[i]==‘#‘) break; } if(flag) puts("YES\n"); else puts("NO\n"); return 0; }
B.
题意：给出n个数，从中选择n1和n2个数（不重复选择），分别求n1个数和n2个数的平均数，要求这两个平均数和最大，求平均数之和。
分析：首先给n个数排序，根据题目要求肯定选择的是n个数中前n1+n2个最大的数，然后假如n1<n2,则先选择n1个最大的数相加（sum1）求平均数(sum1/n1)，剩下的n2个数相加（sum2）求平均数(sum2/n2)。其结果最大。(原理即：用最少的数来平分最大的数，最后得到的平均数才是最大的，而题目中sum1+sum2的和是一定的）
即：求max(sum1/n1+sum2/n2)==max((sum1*n2+sum2*n1)/(n1*n2))==max(sum1*n2+sum2*n1)，因为，大的数与大的数相乘，分母才会更大；又假设的n2>n1,所以sum1越大越好，分母的值才会越大，得到的结果才会越大。
得到结论后的代码：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int num[100005]; int cmp(int a,int b) { return a>b; } int main() { int n,a,b; scanf("%d%d%d",&n,&a,&b); if(a>b)swap(a,b); for(int i=0;i<n;i++) scanf("%d",num+i); sort(num,num+n,cmp); double s1=0,s2=0; for(int i=0;i<a+b;i++) { if(i<a) s1+=num[i]; else s2+=num[i]; } printf("%.8lf\n",s1/a+s2/b); return 0; }
得到结论前的推导公式代码：/过程容易TLE...半天没看出来==max((sum1*(n2-n1)+(sum1+sum2)*n1)/(n1*n2))
如果(n2>n1),从n1+n2个数中取n1个最小的数之和，反之取n1个最大的数之和。
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; int num[100005]; int cmp(int a,int b) { return a>b; } int main() { int n,a,b; long long s=0; scanf("%d%d%d",&n,&a,&b); for(int i=0;i<n;i++) scanf("%d",num+i); sort(num,num+n,cmp); for(int i=0;i<a+b;i++) s+=num[i]; //cout<<s<<endl; double ans=0; long long sum=0; if(b>a) { for(int i=0;i<a;i++) sum+=num[i]; } else { for(int i=b;i<a+b;i++) sum+=num[i]; } ans=(1.0*(ll)s*(ll)a+(ll)sum*(ll)(b-a))/((ll)a*(ll)b);//过程爆int printf("%.8lf\n",ans); return 0; }
C.
题意：给出参赛人数N，问冠军最多能赢多少场比赛
分析：设f(n)为打n场比赛至少需要的人数，则题目即求：当f(n)==N时，n的最大值。根据分析可知f(n)是斐波那契数
具体分析(待补...
https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define ll long long ll f(ll n) { ll a=2,b=3; ll cnt=1; while(b<=n) { a=a+b; b=a+b; cnt++; } if(a>n) return cnt*2-2; else return cnt*2-1; } int main() { ll n; while(cin>>n) { ll ans=f(n); cout<<ans<<endl; } return 0; }
D.
题意：年收入是N，那么需要缴税额是N的最大因子。为了偷税可以把N拆成K个数，但是拆成的数不能为1，因为这样会被税务局发现。找出最小税额。
分析：如果N是素数，税费自然为1，那么把N拆成K个素数之和即可。K当然越小越好，那自然要求拆成的素数越大越好，假设哥德巴赫猜想成立，同时拆成的数不能为1，那么事实上K最大也就是3。
哥德巴赫猜想：任何大于2的偶数能够拆成两个素数相加得到。
素数：1
非素数且为偶数：2
非素数且为奇数：2（n-2为素数时）/ 3(n-2不为素数时)
很明显只能通过奇数==奇数+偶数得来，然而偶数中素数只有2，所以当偶数为2时，而n-2为素数，答案为2，否则偶数就至少由两个素数组成。而根据奇数的哥德巴赫猜想：任一大于5的整数都可写成三个质数之和。答案最大为3 。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define ll long long bool isprime(ll n) { bool f=1; for(int i=2;i<=sqrt(n);i++) { if(n%i==0) f=0; } return f; } int main() { ll n; int ans; bool flag; cin>>n; flag=isprime(n); if(flag) ans=1; else if(n%2==0) ans=2; else if(n%2!=0&&isprime(n-2)) ans=2; else ans=3; cout<<ans<<endl; return 0; }
cf#382div2