第一题 AcWing 4873. 简单计算
一、题目
1、原题链接
4873. 简单计算
2、题目描述
给定四个整数 x1,y1,x2,y2，请你计算 max(|x1−x2|,|y1−y2|)。
输入格式
第一行包含两个整数 x1,y1。
第二行包含两个整数 x2,y2。
输出格式
一个整数，表示 max(|x1−x2|,|y1−y2|) 的值。
数据范围
前 4 个测试点满足 −10≤x1,y1,x2,y2≤10。
所有测试点满足 −109≤x1,y1,x2,y2≤109。
输入样例1：
0 0
4 5
输出样例1：
5
输入样例2：
3 4
6 1
输出样例2：
3
二、解题报告
1、思路分析
按照题意模拟即可。（注意不要将y1定义成全局变量，因为某些头文件中可能用过y1,会造成编译错误）。
2、时间复杂度
时间复杂度为O(1)
3、代码详解
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
int x1,x2,y1,y2; //注意不要将y1，定义到全局，因为某些头文件中可能用过y1,可能会造成编译错误
cin>>x1>>y1>>x2>>y2;
int ans=max(abs(x1-x2),abs(y1-y2));
cout<<ans;
return 0;
}
第二题 AcWing 4874. 约数
一、题目
1、原题链接
4874. 约数
2、题目描述
如果一个正整数的约数个数恰好为 3，则称该数为美丽数。
给定 n 个正整数 a1,a2,…,an，请你依次判断每个数是否是美丽数。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
共 n 行，其中第 i 行输出对 ai 的判断，如果 ai 是美丽数，则输出 YES，否则输出 NO。
数据范围
前 6 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤105，1≤ai≤1012。
输入样例：
3
4 5 6
输出样例：
YES
NO
NO
二、解题报告
1、思路分析
我的思路
比赛的时候试除法判定质数超时了，最后四个数据过不了，所以对试除法做了终极优化，但是今天我试了一下比赛时的试除法的代码竟然可以AC也不知道什么原因，估计比赛时评测的人太多了?所以下面只给出朴素版的判定质数代码。
（1）其实比赛时也没想到怎么优化，只是找规律，比如9是美丽数，它的三个约数是1，3，9；25也是美丽数，它的三个约数是1，5，25；49也是美丽数，它的三个约数是1，7，49。发现什么规律没有？规律就是：这些美丽数都是完全平方数，但是16是美丽数吗？显然不是，因为16的约数是1，2，4，8，16不是3个；36也不是美丽数，因为36的约数是1，2，3，4，6，9，12，18，36不是3个，所以我们又可以得到一个规律：美丽数一定是质数的完全平方。
（2）综上：我们得到美丽数就是是质数的完全平方数，按此条件依次每个数判断即可。
y总思路
思路来源：y总讲解视频
y总yyds
（1）一个结论：完全平方数的约数个数一定为奇数个，反之亦然。
（2）因为美丽数只存在3个约数，也就是1，其平方根和其本身，所以其平方根一定是质数。
（3）根据上述条件：美丽数是质数的完全平方，对每个数进行判断即可，判断质数可以利用质数筛先将1~106（因为a[i]最大1012，其平方根最大106）所有质数先筛出来，然后查表判断是否是质数。
2、时间复杂度
时间复杂度为O(n√n)
时间复杂度为O(n)
3、代码详解
我的思路
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=100010;
int n;
LL a[N]; //注意范围，开long long
//试除法判定x是否是质数
bool isPrime(int x){
if(x<2) return false;
for(int i=2;i<=x/i;i++){
if(x%i==0) return false;
}
return true;
}
//判断a是否是美丽数
bool check(LL a){ //注意开LL
LL g=sqrt(a); //注意开LL
if(g*g==a&&isPrime(g)) return true;
return false;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
bool flag=check(a[i]);
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
y总思路
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=1000010;
int n,cnt;
int primes[N]; //存储所有质数
bool st[N]; //存储每个数是否被筛掉
LL a[N]; //注意范围，需开long long
//线性筛法将1~10^6所有质数筛出来
void getPrime(int x){
st[0]=st[1]=true;
for(int i=2;i<=x;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=x/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
//判断a是否是美丽数
bool check(LL a){ //注意LL
LL g=sqrt(a); //注意LL
if(g*g==a&&!st[g]) return true;
return false;
}
int main(){
cin>>n;
getPrime(1000000);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++){
bool flag=check(a[i]);
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
第三题 AcWing 4875. 整数游戏
一、题目
1、原题链接
4875. 整数游戏
2、题目描述
Alice 和 Bob 在玩一个游戏。
首先，给定一个长度为 n 的正整数数列 a1,a2,…,an。
随后，两人轮流展开行动，由 Alice 先手行动。
当轮到一人采取行动时，如果 a1=0，则该玩家输掉游戏，否则该玩家需要：
在 [2,n] 范围内选择一个整数 i。
将 a1 的值减少 1。
交换 a1 和 ai 的值。
假设双方都采取最优策略，请你判断谁将获胜。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
每组数据输出一行结果，如果 Alice 获胜，则输出 Alice，如果 Bob 获胜，则输出 Bob。
数据范围
前 3 个测试点满足 1≤T≤10，2≤n≤3。
所有测试点满足 1≤T≤2×104，2≤n≤105，1≤ai≤109，一个测试点的所有的 n 相加之和不超过 2×105。
输入样例：
3
2
1 1
2
2 1
3
5 4 4
输出样例：
Bob
Alice
Alice
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
若第一个数为0（其余数都是大于等于1的），则先手必输。
若第一个数为1，其余的数均大于等于1。则先手操作完之后，后面的数中存在一个0，然后后手一定可以把这个0换回到第一个数，此时先手必输。
若第一个数为2，其余数均大于等于2。则先手操作完之后，后面的数中存在一个1，然后后手一定可以把这个1换回到第一个数，这样就转化到了上面的先手必输的状态，所以此时先手也是必输的。
（1）所以可以寻找规律进行假设：如果第一个数是数组中最小的数则先手必输，否则先手必胜。
（2）根据上述假设我们可以知道
先手必胜态：第一个数不是数组中最小数。
先手必败态：第一个数是数组中最小数。
即需证明：如果先手操作完之后从先手必胜态可以转化成某一个先手必败态，即后手开始操作时，总是必败，说明此时先手必胜；同理，如果先手操作完之后从先手必败态只能转化成先手必胜态，即后手开始操作时，总是必胜，则此时先手必输。
（3）对于先手必胜态，由于第一个数不是最小的，我们可以将第一个数减1之后将最小的数换到第一个数，即可以转化成某一个先手必败态；对于先手必败态，由于第一个数已经是最小的了，我们将第一个数减1之后，该数还是最小的，我们无论拿谁来与它交换，都使得第一个数不是最小数，即只能转化为先手必胜态。
（4）说明我们假设正确：如果第一个数是数组中最小的数则先手必输，否则先手必胜。据此判断先手必胜/先手必败即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int a[N];
int T,n;
int main(){
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int m=a[0]; //m存储a[]中最小的数
for(int i=0;i<n;i++) m=min(m,a[i]); //寻找a[]中最最小的数
//如果第一个数为最小数，则先手必败，否则先手必胜
if(m==a[0]) cout<<"Bob"<<endl;
else cout<<"Alice"<<endl;
}
return 0;
}
