CF一如既往在深夜举行，我也一如既往在周三上午的C++课上进行了virtual participation。这次div2的题目除了E题都水的一塌糊涂，参赛时的E题最后也没有几个参赛者AC，排名又成为了手速与精准的竞争……（遗憾，如果参加了一定可以上分的吧orz）
A题：
先判断起点和终点的距离是否被每次跳的距离整除，如果不整除就到不了。再检验跳跃过程中的落点是否均合法即可。
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
int k,n;
char a[];
void solve(int st,int en)
{
if((en-st)%k!=)
{
printf("NO\n");
return ;
}
int j;
for(j=st+k;j<en;j+=k)
{
if(a[j]=='#')
{
printf("NO\n");
return;
}
}
// if(j<en)
printf("YES\n"); }
int main()
{
int i,si,ei;
scanf("%d%d",&n,&k);
scanf("%s",a);
for(i=;i<n;i++)
{
if(a[i]=='G')
ei=i;
if(a[i]=='T')
si=i;
}
if(ei<si)
swap(ei,si);
solve(si,ei);
return ;
}
B题：
根据题意，只需要想清楚最佳分配方案。根据排序不等式，即可轻松找到最佳方案。将人排序后，让从大到小的前若干个人分到人数小的城市，接下来再若干人分到人数多的城市即可得到最大值。
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
ll n,a[],ren[],i,he1=,he2=;
double an=;
int main()
{ scanf("%I64d%I64d%I64d",&n,&a[],&a[]);
if(a[]>a[])
swap(a[],a[]);
for(i=;i<n;i++)
scanf("%I64d",&ren[i]);
sort(ren,ren+n);
for(i=n-;i>=n-a[];i--)
{
he1+=ren[i];
}
for(i=n-a[]-;i>=n-a[]-a[];i--)
{
he2+=ren[i];
}
an=(1.0*he1/a[])+(1.0*he2/a[]);
printf("%.8f\n",an);
return ;
}
C题：
观察比赛场次和人数的关系，以及比赛场次何时+1即可发现这题本质上是斐波那契数列。设人x时开始变为最多比赛q场，人y时开始变为最多比赛q+1场，则人（x+y)时，前x个人可以找到比赛q场的唯一到最后的选手，后y个人可以找到比赛(q+1)场后唯一到最后的选手，这两个人可以比赛，并且会得出胜者，如果后y人中的胜者获得胜利，就构造出了最多参加（q+2)场的情况。并且可以归纳证明这是最少的人数。于是就证明了本题斐波那契数列的本质。
#include<stdio.h>
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
ll n;
ll fi(ll x)
{
if(x==)
return ;
if(x==)
return ;
else {
ll x1,x2,tem,cnt;
cnt=;x1=;x2=;
while(x1<x)
{
tem=x1;
x1=x1+x2;
x2=tem;
cnt++;
}
if(x1==x)
return cnt;
else
return cnt-;
}
}
int main()
{
scanf("%I64d",&n);
printf("%I64d\n",fi(n));
return ;
}
D题：
乍一看和素数相关，数还特别大，比较吓人。而实际上利用哥德巴赫猜想的内容即可轻松解决（虽然还没有证明为真，但这样数量级的数之前都已经用计算机验证过了）
注意到：任何一个大于2的偶数都是两个素数之和。那么对于输入的如果是偶数，2就输出1（因为本身是质数），其余就输出2（根据猜想，可以分为两个质数之和）
任何大于5的奇数都是三个素数之和。那么对于输入的如果是奇数，判断是否为质数（这里我比较懒，直接用了拉宾米勒，实际上简单的从2到根号n循环一遍就可以），是就输出1，不是的话再看（n-2)是否为质数，如果是，就可以将其分为2和（n-2)这样两个质数，那么就输出2。不然就只能根据猜想，一定可以分为3个质数，输出3。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std; //****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数
//****************************************************************
const int S=;//随机算法判定次数，S越大，判错概率越小 //计算 (a*b)%c. a,b都是long long的数，直接相乘可能溢出的
// a,b,c <2^63
long long mult_mod(long long a,long long b,long long c)
{
a%=c;
b%=c;
long long ret=;
while(b)
{
if(b&){ret+=a;ret%=c;}
a<<=;
if(a>=c)a%=c;
b>>=;
}
return ret;
} //计算 x^n %c
long long pow_mod(long long x,long long n,long long mod)//x^n%c
{
if(n==)return x%mod;
x%=mod;
long long tmp=x;
long long ret=;
while(n)
{
if(n&) ret=mult_mod(ret,tmp,mod);
tmp=mult_mod(tmp,tmp,mod);
n>>=;
}
return ret;
} //以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(long long a,long long n,long long x,long long t)
{
long long ret=pow_mod(a,x,n);
long long last=ret;
for(int i=;i<=t;i++)
{
ret=mult_mod(ret,ret,n);
if(ret==&&last!=&&last!=n-) return true;//合数
last=ret;
}
if(ret!=) return true;
return false;
} // Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false; bool Miller_Rabin(long long n)
{
if(n<)return false;
if(n==)return true;
if((n&)==) return false;//偶数
long long x=n-;
long long t=;
while((x&)==){x>>=;t++;}
for(int i=;i<S;i++)
{
long long a=rand()%(n-)+;//rand()需要stdlib.h头文件
if(check(a,n,x,t))
return false;//合数
}
return true;
}
typedef long long ll;
ll n;
int main()
{
scanf("%I64d",&n);
if(n==)
{printf("1\n");return ;}
if(n%==)
printf("2\n");
else
{
if(Miller_Rabin(n))
{
printf("1\n"); }
else
{
if(Miller_Rabin(n-))
printf("2\n");
else
printf("3\n");
} }
return ;
}
E题好难，貌似还得用到树状dp，还没有学到orz，等以后再回来填坑。（捂脸，估计看解题报告的大家其实想看的就是E题吧……）