German Collegiate Programming Contest 2018（GCPC）
目录
Gym - 102021D：Down the Pyramid
Gym - 102021E ：Expired License
Gym - 102021F ：Fighting Monsters
Gym - 102021I： It’s Time for a Montage
题目链接：http://codeforces.com/gym/102021
Gym - 102021B: Battle Royale
题意：平面内有一个大圆，大圆里面有两个点（我假设A和B）和一个小圆，这个小圆在A，B之间。问从A到B的最短距离。（小圆和AB两点永远在大圆里面，并且AB两点不在小圆里面，并且走小圆的边缘也是允许的）
思路：示意图如下图所示，分析可知最短距离就是L1+L2+L3的值，其中L1,L2是三角形的弦，L3是圆的一段弧长。L1,L2好求，通过勾股定理即可，求L3时要用到弧长公式“ L=R*θ”（θ为弧度制）。所以求角度a2时，要求出其中的大角和两边的小角，相减即可得到a2。求出da求三个角度a1,a2,a3时，要用到acos(number)函数求角度（number为余弦值），最后即可求出L3的弧长。（自己做的是前面分析出图都很简单，就是求角度时不知道可以用这个函数，卡了半天）
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
int x1,y1,x2,y2,x0,y0,r0,x,y,r;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
scanf("%d%d%d",&x,&y,&r);
scanf("%d%d%d",&x0,&y0,&r0);
double len1=sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0));
double len2=sqrt((x2-x0)*(x2-x0)+(y2-y0)*(y2-y0));
double len=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
double ans1=sqrt(len1*len1-r0*r0);//弦L1
double ans2=sqrt(len2*len2-r0*r0);//弦L2
//ang为圆心角
double ang=acos((len1*len1+len2*len2-len*len)/(2*len1*len2));///加括号！！！
ang=ang-acos(r0/len1)-acos(r0/len2);
double ans=ans1+ans2+r0*ang;
printf("%.10lf\n",ans);
return 0;
}小总结：1、就是求角函数 acos(number)其中number为余弦值，acos()所求的值为弧度制。2、用到除号“/”当分母有多项时一定记得加括号！！这些小细节真的很重要，有时候这些细节忘了一旦程序报错了很难找出自己哪错了。所以要重视这些细节。
Gym - 102021D：Down the Pyramid
题意：给你一层数，让你求出它下面的一层数，上面的每一个数都是下层相邻两个数的和。（就像图中的数字金字塔一样）。问你下面一层有多少种满足的方案。
思路：假设给出的值为，a1,a2,a3,a3...，假设下面的第一个数b0=x，那么可以推得第二个数b1=a1-x，第三个数就是a2-(a1-x)，以此类推。其中bo...bn要满足的条件就是每一项都大于等于零。所以就可推得关于x 的不等式，所以就可以求出x的一个最小的范围，所以就可求出方案数。
其实这个思路一开始也没懂，但是在草稿纸上写了一下就突然明白了，
b1=a1-x>=0
b2=a2-(a1-x)>=0,
b3=a3-(a2-(a1-x))>=0
...
所以可知是一个递推公式：x=a[i]-x;每一项的x都要满足>=0
当下标为奇数时，取上界最小的一个，当下标为偶数时，取下界最大的一个（还不懂就在草稿纸上写出几个不等式就知道怎么回事了）
（这题比赛的时候没做出来，当时感觉这道题跟之前做过的一道熄灯问题很像，都是有一种连带，枚举局部就能得到整体的解。所以比赛的时候我一直在想可不可以枚举第一个数，然后判断最后一个数是否满足条件。显然看数据就知道我错了，这道题也是想了半天，后来看了其他队的做法，和网上的做法，不得不服，脑子真是个好东西可惜我没有。）
#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxn 1000050
using namespace std;
int a[maxn];
int n;
int main()
{
ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
while(cin>>n)
{
for(int i=1;i<=n;i++)
cin>>a[i];
int low=0, high=a[1];
int x=0;
for(int i=1;i<=n;i++)
{
x=a[i]-x;
if(i%2)//奇数
{
high=min(high,x);//取上界的最小
}
else
{
low=max(low,-x);//取下界额最大
}
}
if(low>high)
cout<<0<<endl;
else
cout<<high-low+1<<endl;//区间中满足条件的方案数
}
return 0;
}Gym - 102021E ：Expired License
题意：给你一对浮点数，让你判断这对浮点数的比值能否用一对素数的比值所表示，如果可以就输出两个素数。
分析：首先将所给数乘以100000并四舍五入，然后两数在除以他们的最大公因子判断是否为素数。其中里面包含一种特殊情况，就是当两数相等时，直接输出2,2
（一开始的判断素数的思路是每次都判断一次，但是这样一直过不了，直到预处理存下所有素数再判断才过了）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define maxn 10000050
using namespace std;
bool isPrime[maxn];
int n;
int gcd(int a,int b)
{
return a%b?gcd(b,a%b):b;
}
//bool checksushu(int x)
//{
// for(int i=2;i<x;i++)
// if(x%i==0)
// return false;
// return true;
//}
void init()
{
for(int i=2;i<=maxn;i++)
isPrime[i]=true;
for(int i=2;i<=maxn;i++)
{
if(isPrime[i])
{
for(int j=2*i;j<=maxn;j+=i)
isPrime[j]=false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
init();
int t;
double a,b;
cin>>t;
while(t--)
{
cin>>a>>b;
a=round(a*100000);
b=round(b*100000);
int num=gcd(a,b);
a/=num;
b/=num;
int x=a,y=b;
if(x==y)
cout<<2<<" "<<2<<endl;
else
{
if(isPrime[x]&&isPrime[y])
cout<<x<<" "<<y<<endl;
else
cout<<"impossible"<<endl;
}
}
return 0;
}
Gym - 102021F ：Fighting Monsters
题意：给定N个怪兽，问能否选出两个怪兽，使得他们相互攻击，最后活着的怪兽剩1滴血，死的怪兽的血为零或者为负数。
分析：通过分析可知，满足条件的最后两怪兽的血量一定是 1和0，（假设如果最后是-1,1的话，那么这个-1怪兽肯定是被能力值为1的怪兽所攻击的，那么它们上一个状态的血量就一定是0,1，所以不会出现-1,1 的情况，所以1，-2、1,-3,的更不可能出现了）。所以通过最后的血量1,0网上推可能的数字对时，可以发现规律就是斐波那契数列相邻的两个数。所以问题就变成求相邻的两个斐波那契数就可以了。
（这题比赛的时候其实已经想出来思路了，但是敲代码的时候一直很着急，越着急越不过导致我心态炸了，这以后千万要注意，比赛保持一个好的心态非常重要！）
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
const int maxn = 1e8+50;
const int maxx=100050;
using namespace std;
struct node
{
int x,num;//x表示下标，num表示能力值
}m[maxx];
struct rule
{
bool operator()(const node &a1,const node &a2)
{
return a1.num<a2.num;
}
};
int n;
int b[1000];
int k;
int s[maxx];
void feibo()//首先预处理先存好斐波那契数
{
b[0]=1;
b[1]=1;
k=2;
while(1)
{
b[k] = b[k-1]+b[k-2];
if(b[k]>=maxn)
break;
k++;
}
}
int main()
{
feibo();
while(cin>>n)
{
for(int i=1;i<=n;i++)
{
cin>>m[i].num;
m[i].x=i;
}
sort(m+1,m+n+1,rule());//按照能力值排序
for(int i=1;i<=n;i++)
s[i]=m[i].num;
int flag=0;
int i,j;
int pp;
for(i=1;i<n;i++)
{
int p=lower_bound(b,b+k,m[i].num)-b;//判断这个数是不是斐波那契数
if(b[p]!=m[i].num)
continue;
else
{//如果是的话，就查找他相邻的斐波那契数
pp=lower_bound(s+i+1,s+n+1,b[p+1])-s;
if(s[pp]==b[p+1])
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag)
cout<<m[i].x<<" "<<m[pp].x<<endl;
else
cout<<"impossible"<<endl;
}
return 0;
}
Gym - 102021I： It’s Time for a Montage
题意：一队英雄和一队怪物按照优先级排队打架，看优先级最高的英雄能否获胜。规定如果英雄和怪物的能力值相同，那么就看优先级较低的下一对的结果。每训练一天可以使所有英雄的能力值都提高1，问要使英雄获胜最少训练多少天。
分析：这个题其实是一道水题，直接暴力就行。最低训练天数就是第一个敌人和英雄的差值。再看后面的英雄有没有比所对的敌人强的，如果有直接输出，如果没有在此能力值基础上加一输出即可。
（这道题其实很水就是题意读了半天才读懂）
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1050];
int b[1050];
int n;
int main()
{
ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
cin>>b[i];
int d=b[0]-a[0];
int flag=0;
if(d<0)
cout<<0<<endl;
else
{
int p,i;
for(p=d;p<=1000;p++)
{
for(i=0;i<n;i++)
{
if(a[i]+p<b[i])
break;
else if(a[i]+p==b[i])
continue;
else
{
flag=1;
break;
}
}
if(i==n)
{
flag=1;
break;
}
if(flag==1)
break;
}
cout<<p<<endl;
}
}
return 0;
}
Gym - 102021L： Logic Puzzle
题意：扫雷问题，给你周围雷的个数，让你标出雷区中的雷。（这题是在雷区外又加了一圈，雷区只是里面的h行w列）
分析： 这题是引入其他博客的思路：
不同的是这题中自己位置上的雷也会计算在内。一行一行地解决，从雷区的第一个位置开始，看左上角的位置的雷的数目，如果不为0，就把这个点标记上雷，并将自己和周围的位置全部减去1。
最后如果全部位置在处理完毕之后都为0，就代表存在合法的解。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int h,w;
int a[110][110];
int dx[9]={1,-1,0,0,1,1,-1,-1,0};
int dy[9]={0,0,-1,1,-1,1,-1,1,0};
int b[110][110];
int main()
{
ios::sync_with_stdio(false);
cin>>h>>w;
memset(b,0,sizeof(b));
for(int i=0;i<h+2;i++)
for(int j=0;j<w+2;j++)
cin>>a[i][j];
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
if(a[i-1][j-1])
{
b[i][j]=1;
for(int k=0;k<9;k++)
{
int nx=i+dx[k];
int ny=j+dy[k];
a[nx][ny]--;
}
}
}
}
int flag=1;
for(int i=0;i<h+2;i++)
{
for(int j=0;j<w+2;j++)
if(a[i][j]!=0)
{
flag=0;
cout<<"impossible"<<endl;
break;
}
if(flag==0)
break;
}
if(flag==1)
{
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
if(b[i][j])
cout<<"X";
else
cout<<".";
}
cout<<endl;
}
}
return 0;
}
（这篇博客应该是我写的最长的一篇了，攒了好几道题的题解没写就打算一起写一块。还有几道题也可以做还没有做，做出来的话再补上题解）