ACGO挑战赛题解#16
2025-03-24 21:39:34
发布于：浙江
竞赛评价
我想说的是：不愧是挑战赛啊，这难度差不多有个CSP六级半的水平啊。特别是最后两题，基本上和CSP-J的题目没有区别了，当然这可难不住小编。CSP-J都二等奖了还会怕个DFS和BFS？好吧，我T6没做出来
总之：在本届挑战中，每道题都不白给，大家好好看好好学。我们——走曲~~
T1 循环太好用辣
从题目看出这道题明摆着让我们用循环枚举的方式解题。题目给我们一个x，让我们找出所有的{i,j,k,z,p}并且满足8i+6j+4k+2z+p=x最主要的是0≤i,j,k,z≤100，所以直接无脑四重循环就可以了
什么？你问我为啥是四重循环，p要怎么办？我们可以定义p=x-8×i-6×j-4×k-2×z 然后判断p是否大于0就可以了（我代码就不注释了，绝对不是因为我懒）
#include <iostream>
using namespace std;
int main() {
int x;
cin>>x;
for(int i=0;i<=100;i++){
for(int j=0;j<=100;j++){
for(int k=0;k<=100;k++){
for(int z=0;z<=100;z++){
int p=x-8*i-6*j-4*k-2*z;
if(p>=0){
cout<<i<<" "<<j<<" "<<k<<" "<<z<<" "<<p<<endl;
}
}
}
}
}
return 0;
}
T2 小特的素数训练
还是考察大家对素数的判断与数字的拆位昂。素数懂的都懂：除了本身和1没有别的数能将它整除。拆位的话——把n不断地取余十整除十就可以了。这题也没什么好讲的，上代码吧：
#include <iostream>
using namespace std;
bool zhishu(int n){//质数判断
for (int i=2;i*i<=n;i++){
if (n%i==0){
return 0;
}
}
return 1;
}
int SUM(int n){
int sum=0;
while(n>0){//n的拆位与累加，结果记为sum
sum+=n%10;
n/= 10;
}
return sum;
}
int main() {
int n,ans=0;cin>>n;
for (int i=2;i<=n;i++){//1不是质数
if (zhishu(i)){
ans+=SUM(i);
ans%=1093;//加减后取模是不影响结果的，乘除后取模，嗯，看会不会WA就完事了
}
}
cout<<ans<<endl;
return 0;
}
T3战术训练方案
先评价一下这道题：读得懂水题，读不懂WA
这道题的意思就是让我们找出A和B的最大公因数的所有因数。最大公因数想必大家都打过好几次代码了，但是99%的人都不知道有个函数可以直接求出最大公因数，那就是——__gcd(a,b)
食用方法：a和b是你要求最大公因数的数字，而当你打出了n=__gcd(a,b)时，那么恭喜你，你已经掌握了gcd的用法
然后就是求出最大公因数的所有约数，小编这里直接暴力枚举了，反正也不会超时。
#include<bits/stdc++.h>
using namespace std;
vector<int> find(int n){
vector<int> yingshu;
for (int i=1;i*i<=n;i++){
if (n%i==0){
yingshu.push_back(i);
if (i!=n/i){
yingshu.push_back(n / i);
}
}
}
sort(yingshu.begin(),yingshu.end());
return yingshu;
}
int main() {
int a,b;cin >>a>>b;
int n= __gcd(a,b);
vector<int> ans=find(n);
for (int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}
T4直角兔兔
这道题目也是考察了我们对小学数学的掌握情况啊，像这种判断直角的题目也是勾股定理秒了好吧。什么？你居然不知道勾股定理？
long long xa=(x[a]-x[b])*(x[a]-x[b]),ya=(y[a]-y[b])*(y[a]-y[b]);
long long xb=(x[a]-x[c])*(x[a]-x[c]),yb=(y[a]-y[c])*(y[a]-y[c]);
long long xc=(x[b]-x[c])*(x[b]-x[c]),yc=(y[b]-y[c])*(y[b]-y[c]);
现在会了吧。接下来就是三重循环遍历每一个点就可以了，也没什么好讲的。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
long long x[1510],y[1510];
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}int ans=0;
for(int a=1;a<=n;a++){
for(int b=a+1;b<=n;b++){
for(int c=b+1;c<=n;c++){
long long xa=(x[a]-x[b])*(x[a]-x[b]),ya=(y[a]-y[b])*(y[a]-y[b]);
long long xb=(x[a]-x[c])*(x[a]-x[c]),yb=(y[a]-y[c])*(y[a]-y[c]);
long long xc=(x[b]-x[c])*(x[b]-x[c]),yc=(y[b]-y[c])*(y[b]-y[c]);
if(xa+ya+xb+yb==xc+yc||xc+yc+xb+yb==xa+ya||xa+ya+xc+yc==xb+yb){
ans++;
}
}
}
}
cout<<ans<<endl;
return 0;
}
更多题解我会发在A Crowd of MC Lovers中，有需要的小伙伴可以加我团队。先说一下，本人T6没能AC，也不是我能力不行，测了好几次，每次都是TLE，我也是醉了。所以是哪个有点大病的人发明了时间超限啊！！！！！
如果上面的题解对你有帮助的话，希望你可以给小编一个大大的关注，大伙的关注就是小编持续更新的最大动力。当然如果大伙对我的题解有什么异议或不解，可以直接私聊我，我也会尽可能地满足宝子们的要求。最后感谢您的耐心观看，我们下期再见~~
有帮助，赞一个