AtCoder Beginner Contest 272 - AtCoder
A-Integer Sum （赛
题目概述
求和
B-Everyone is Friends （赛
题目概述
二维数组记录相互关系即可，数据量少可用\(O(n^3)\)
C-Max Even （赛
题目概述
从非负整数数列中找出和为偶数，且和最大的两个数
解题思路
遍历数列，把偶数和奇数放入两个向量，排序后求最大两个再比大小
D-Root M Leaper （赛-补
题目概述
\(N*N\)棋盘，每步可以走长度 \(\sqrt{M}\)到达一个整格
求解到达每个位置的最短路径
解题思路
最短路径可以用\(bfs\)
\((1)\) \(1e6\)求出\(?^2+?^2=M\)
$(2) $ 利用\(re[N][N]\)记录是否走过，利用\(dx[4]={1,1,-1,-1},dy[4]={1,-1,1,-1}\) 遍历整个棋盘
注意：在同一层循环中，如果其中一个方向的位移为零，就可能出现在队列中加入完全相同的两个节点，不断迭代就会产生极大的时间浪费，因而我们需要记录\((i,j)\)是否已进入队列或者特判这种情况!!
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N=410,M=1e6+10;
int map1[N][N],re[N][N];
vector<int> x,y;
int dx[4]={1,1,-1,-1},dy[4]={1,-1,1,-1};
struct node{
int x,y,step;
};
int main()
{
#记得赋初值
memset(map1,-1,sizeof map1);
memset(re,0,sizeof re);
x.clear(),y.clear();
int n,m;
cin>>n>>m;
for(int i=0;i*i<=m;i++)
{
for(int j=0;j*j<=m;j++)
{
if(i*i+j*j==m)
{
x.push_back(i);
y.push_back(j);
x.push_back(j);
y.push_back(i);
}
}
}
queue<node> q;
node a,next,now;
#记得赋初值
map1[1][1]=0;
re[1][1]=1;
a.x=1,a.y=1,a.step=0;
q.push(a);
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=0;i<x.size();i++)
{
for(int j=0;j<4;j++)
{
next.x=now.x+dx[j]*x[i];
next.y=now.y+dy[j]*y[i];
next.step=now.step+1;
if(next.x>=1&&next.y>=1&&next.x<=n&&next.y<=n)
{
if(re[next.x][next.y]==0)
{
re[next.x][next.y]=1;
map1[next.x][next.y]=next.step;
q.push(next);
}
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<map1[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
E-Add and Mex （补
参考ABC 272E - Add and Mex（MEX，调和级数）-CSDN博客
题目概述
有一长度为\(N\)的整数数列\(A=(A_1,A_2,...,A_N)\)，对\(A\)做\(M\)次操作，一次操作为对每个\(A_i\)增\(i\)，求出每次操作后序列中未出现的最小非负整数
解题思路
\((1)\) 一个长度为\(n\)的数列，未出现的最小非负整数只可能在\([0,n]\)范围内，因而只有处在该区间的数字会对结果产生影响\(\Rightarrow\)可以使用一个\(set\)容器\(r[j]\)对第\(j\)次操作后在该范围内的数字进行记录
\((2)\) 时间复杂度分析：
由于序列每次增\(i\)，\(insert\)只会进行大约\(N+N/2+N/3+...+N/M\) \(\Rightarrow\) \(N*(1+1/2+1/3+...+1/M)\) \(\Rightarrow\)\(N*(logM)\) 次，时间复杂度为\(O(NlogM)\)
而寻找\(Mex\)的过程中\(Mex\)始终较小（因为每次都加上\(i\)，就算有一个询问中出现了\(0-n\)，加过之后下一个询问就没有了，所以一个询问中能从\(0\)开始连续的数字长度其实是很小的，那么直接从\(0\)开始枚举看哪个数不存在即可。）
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N=2*1e5+10;
const int M=2*1e6;
set<int> r[N];
int main()
{
int a,n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a;
if(a<n&&a+m*n>=0)
{
int j;
if(a>=0)
{
j=1;
}
else
{
if((-a)%i==0) j=(-a)/i;
else j=(-a)/i+1;
}
a=a+j*i;
while(a<=n&&j<=m)
{
r[j].insert(a);
j++;
a+=i;
}
}
}
for(int i=1;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(!r[i].count(j))
{
cout<<j<<endl;
break;
}
}
}
return 0;
}