[ACGO挑战赛#16]部分题解
2025-03-26 17:31:52
发布于：广东
本人只是一个xxs，而以我的能力无法ak挑战赛，以下是我的部分题目题解
第一题：直接循环暴力枚举即可
赛时代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define si short int
#define infinity 0xffffff
using namespace std;
const int N=1e3+9;
ll x,i,j,k,z,p;
bool check()
{
return (8*i+6*j+4*k+2*z+p==x);
}
int main()
{
cin>>x;
for(i=0;i<=x;i++)
{
for(j=0;j<=x;j++)
{
for(k=0;k<=x;k++)
{
for(z=0;z<=x;z++)
{
for(p=0;p<=x;p++)
{
if(check()) cout<<i<<" "<<j<<" "<<k<<" "<<z<<" "<<p<<"\n";
}
}
}
}
}
}
第二题：我写的是埃筛（也可以是欧筛）+暴力（注意要在过程中 ，不然可能会爆空间）
赛时代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define si short int
#define infinity 0xffffff
using namespace std;
const int N=2e5+9;
bool canNum[N];
ll n,ans;
int main()
{
cin>>n;
for(ll i=2;i<=sqrt(n);i++)
{
if(!canNum[i])
{
for(ll j=2*i;j<=n;j+=i) canNum[j]=1;
}
}
ll tmp;
for(ll i=2;i<=n;i++)
{
if(!canNum[i])
{
tmp=i;
while(tmp) ans=(ans+tmp%10)%1093,tmp/=10;
}
}
cout<<ans;
}
第三题：我写的是通过（最大公因数）获取暴力的范围然后暴力枚举区间内的能不能满足 （不求会爆时间）。
赛时代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define si short int
#define infinity 0xffffff
using namespace std;
const int N=2e5+9;
int gcd(ll a,ll b)
{
if(!(a%b)) return b;
return gcd(b,a%b);
}
int main()
{
ll a,b;
cin>>a>>b;
for(ll i=1;i<=gcd(a,b);i++)
{
if(!(a%i or b%i)) cout<<i<<" ";
}
}
第四题：80tps，有两个测试点超时(
其实是我懒得优化)
我的想法是暴力枚举每三个点，再通过勾股定理判断是不是直角三角形(即就代表是直角三角形，其中表示三角形的三条边长度)。
但是值得注意的：
1.必须确保你的代码的下标（索引）成此关系：，其中表示三层循环的下标（索引），不然会重复计算三角形，（题目要求三角形的三个顶点坐标要全部不同）。
2.计算三角形的边长时要使用欧几里得距离而不是曼哈顿距离，而且不要给距离开算数平方根不然会导致精度丢失，而且计算完也要求距离的平方没必要开算数平方根（如：在计算过程中，）的算数平方根和平方可以抵消（因为算数平方根就是不小于的数平方的逆运算）。
赛时代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define si short int
using namespace std;
const int N=3e5+9;
const ll INF=0xffffff;
struct node
{
ll x,y;
}point[N];
ll n,ans;
ll getDis(ll x1,ll y1,ll x2,ll y2)
{
return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
cin>>n;
for(ll i=0;i<n;i++) cin>>point[i].x>>point[i].y;
for(ll i=0;i<n;i++)
{
for(ll j=0;j<i;j++)
{
for(ll k=0;k<j;k++)
{
ll dis1=getDis(point[i].x,point[i].y,point[j].x,point[j].y);
ll dis2=getDis(point[k].x,point[k].y,point[j].x,point[j].y);
ll dis3=getDis(point[i].x,point[i].y,point[k].x,point[k].y);
ans+=(dis1+dis2==dis3 || dis2+dis3==dis1 || dis1+dis3==dis2);
}
}
}
cout<<ans;
}
第五题：我写的有点乱，但是没有问题。
具体思路就是构建一个大小为的二维数组（此处记作）用于标记坐标为的点上是不是墙，若是为，否则为，然后在输入时将输入数字转换为二进制（注意要逆序排列而且要保留二进制的前导零！！！！！！！），存放到字符串类里再依次读取字符串内容并将其标记在里（推荐使用数组预处理的加值），最后找联通块（记得要给联通块大小排序，可以像我一样使用优先队列做）。
插一句题外话，我的代码里要将数组的值乘并依次做判断，悔不如当初应该用结构体写QAQ，现在自己都难看懂（
赛时代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define ll long long
#define si short int
#define infinity 0xffffff
using namespace std;
const int N=3e3+9;
ll n,m,ans;
bool vis[N][N];
short int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
priority_queue<ll> q;
void dfs(ll x,ll y)
{
for(short int i=0;i<4;i++)
{
ll xn=x+dx[i]*3,yn=y+dy[i]*3;
if(!(xn<0 or xn>=n*3 or yn<0 or yn>=m*3 or vis[xn][yn] or vis[x+dx[i]*2][y+dy[i]*2] or vis[x+dx[i]][y+dy[i]]))
{
vis[xn][yn]=1;
ans++;
dfs(xn,yn);
}
}
}
int main()
{
cin>>n>>m;
for(ll i=0;i<n;i++)
{
for(ll j=0;j<m;j++)
{
ll x=i*3+1,y=j*3+1;
int tmp;
string map="";
cin>>tmp;
vis[x-1][y-1]=vis[x+1][y-1]=vis[x-1][y+1]=vis[x+1][y+1]=1;
for(short int k=0;k<4;k++)
{
vis[x+dx[k]][y+dy[k]]=tmp%2,tmp/=2;
}
}
}
for(ll i=1;i<n*3;i+=3)
{
for(ll j=1;j<m*3;j+=3)
{
if(!vis[i][j])
{
vis[i][j]=1;
ans=1;
dfs(i,j);
q.push(ans);
}
}
}
while(!q.empty())
{
cout<<q.top()<<" ";
q.pop();
}
}
最后一题拿了15分也不知道我写的哪里有问题，望指正，但是应该核心没问题。
STEP1：分析题目解题方法：
因为题目保证移动的步数是正数，且是求最值，所以可以用解（我这里是用表示在点上，上一步步长为时最多可以拿可以拿几个个宝石）。
STEP2：推导适用的动态转移方程：
由于（此处指可以跳的步数，即必定等于或者等于）点可以拿到点上的宝石（即自己本身，因为可能有多种方法到达点）和个的宝石（即在点，上一步步长为的情况下向前走步后能拿到的没拿过的宝石，此处数组表示点上原有的宝石）。
STEP3：总结出动态转移方程并开始解题：
动态转移方程为
（记得要初始化点为点上的宝石数，因为跳步后会直接拿到上的宝石，并且要让其他点设为不然会有）。
赛时代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define si short int
#define infinity 0xffffff
using namespace std;
const int N=3e5+9;
const int M=201;
ll n,d;//【防忘】dp[x][l]表示在x点上可以拿y个宝石，步长为l
void setDp(vector<vector<ll> > &dp,ll x,ll l,ll k,vector<ll> &sum)//也可以写成减法形式
{
if(k<=0 || x+k>=dp.size()) return;
dp[x+k][k]=max(dp[x+k][k],dp[x][l]+sum[x+k]);
}
int main()
{
cin>>n>>d;
ll endIndex=0;
vector<ll> sum(N,0);
for(ll i=0;i<n;i++)
{
ll tmp;
cin>>tmp;
sum[tmp]++;
endIndex=max(endIndex,tmp);
}
vector<vector<ll> > dp(endIndex+1,vector<ll>(M+1,-1));
dp[d][d]=sum[d];
for(ll i=d;i<=endIndex;i++)
{
for(ll j=2;j<=M;j++)
{
setDp(dp,i,j,j+*,sum);//这里莫名其妙会被敏感词，原代码的"j+*"部分是"j+1"
setDp(dp,i,j,j,sum);
setDp(dp,i,j,j-1,sum);
}
}
ll maxn=0;
for(ll i=1;i<=endIndex;i++)
{
for(ll j=1;j<M;j++)
{
maxn=max(maxn,dp[i][j]);
}
}
cout<<maxn;
}
点个赞吧QAQ
有帮助，赞一个