比赛传送门：
Contest Problem List (hdu.edu.cn)
1006）GCD Game
题目翻译：爱丽丝和鲍勃正在玩游戏。 他们轮流操作。有n个数字，a1，a2，…，an。每次，玩家分 3 步进行游戏。 1.任意选择一个数字ai。 2.任意选择另一个数x(1≤x<ai)。 3. 用 gcd(ai,x) 替换数字 ai。
这里，gcd(u,v) 指的是 u 和 v 的最大公约数。 当玩家不能移动时，他/她就输掉了游戏。爱丽丝先走，她让你告诉她，如果两个玩家都有最佳策略，谁将赢得比赛。
样例：
2
1
1
1
2输出：
Bob
Alice题目分析：每次的操作都分为三步，要将其转化为自己的一个因数，那么对于某一个数字而言，它最多可操作的次数就取决于自己有多少个质因数（质数为1，合数不等比如4，可以变为2，再把2变为1，可操作两次，8可操作三次，其他同理）。因此，我们可以联想的典型的NIM函数，每个数字都可以看成一堆石子，质因数的个数可以看成是石子的数量。
解题思路：首先对数据范围之内的数字进行预处理，求出所有的数的质因数的个数，直接一个一个分解会T，这里我们采用欧拉筛（在筛的过程当中记录质因数个数），预处理完毕之后，直接采用NIM函数的结论：当a1^a2^a3^…..^an≠0的时候先手必胜，否则后手必胜。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+10;
int n,m,a,cnt;
int num[N];//存每个数字的质因数个数
int prime[N];//记录素数
bool f[N];//判断过程当中的标记数组
//经典欧拉筛 稍微改动
void find_prime(int n){
for(int i=2;i<=n;i++){
if(!f[i])prime[+cnt]=i,num[i]=1;//质数的质因数为1
for(int j=1;j<=cnt&&i*prime[i]<=n;j++){
f[i*prime[j]]=true;
num[i*prime[j]]=num[i]+1;//记录质因子的个数
if(i%prime[i]==0)break;
}
}
}
int main(){
find_prime((int)1e7);//预处理
int t;
cin>>t;
while(t--){
cin>>n;
cin>>a;
int ans=num[a];//第一个数单独输入
//nim结论
for(int i=2;i<=n;i++){
cin>>a;
ans^=num[a];
}
if(ans)cout<<"Alice"<<endl;
else cout<<"Bob"<<endl;
}
return 0;
} 1003）Ink on paper
题目翻译：鲍勃不小心把几滴墨水洒在了纸上。第 i 滴墨水的初始位置是 (xi,yi)，每秒向外扩展 0.5 厘米，显示一个圆圈。 好奇的鲍勃想知道所有墨水连接起来需要多长时间。为了方便输出，请输出时间的平方。
样例输入：
2
3
0 0
1 1
0 1
5
1 1
4 5
1 4
2 6
3 10输出：
1
17分析：任意两滴墨水都会同时扩散，我们要找所有的墨水连成一整块所花费的时间，可以将每滴墨水看成一个点，之间的距离看做边权，那么我们要求的便是把所有的点形成联通块所需的时间，其中因为所有的点是同时开始扩散的，所以，最长的时间取决于所有联通过程当中花费时间最大的两个点。转化为了最小生成树问题，直接套板子（prim算法）即可。
代码：
#include <bits/stdc++.h>
using namespace std;
// t组数据 n个点 记录坐标 最远距离
//将该点加入集合的距离 标记数组 两点之间多条路径去取更短
long long t,n,x[5005],y[5005],ans,dis[5005],vis[5005],mind;
//两点之间的距离
long long distance(int i,int j){
return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%dll",&n);
for(int i=1;i<=n;i++)scanf("%lld %lld",&x[i],&y[i]);
ans=0;
memset(dis,0x7f,sizeof(dis));//初始化
memset(vis,0,sizeof(vis));
int u;
dis[1]=0;//将1作为起点开始
//经典板子
for(int i=1;i<=n;i++){
mind=0x7fffff;
for(int j=1;j<=n;j++)
//没有访问过 且距离更小 选择该点
if(!vis[j]&&dis[j]<mind)mind=dis[j],u=j;
vis[u]=1;//标记已经访问
ans=max(ans,dis[u]);//更新最大值
//优化通过这个点可以使得路径更短的点
for(int j=1;j<=n;j++)
if(!vis[j])dis[j]=min(dis[j],distance(i,j));
}
printf("%lld\n",ans);
}
return 0;
}
参考：
杭电第八场 题解_Frank_Star的博客-CSDN博客
有什么问题还请大家指出 ^–^