AtCoder Beginner Contest 272(D,E)
D
这个题最主要的是需要找出有哪些移动的距离
对于题目给出的\(m\),我们的移动过程可以是\((i-ii)^2 +(j-jj)^2=m\)
这样的话,我们可以对\(m\)分解成两个平方数\(a\)和\(b\),然后对于这个\(a\)和\(b\)的分配,一共有\(8\)种方向,(没有规定\(a\)一定是\(x\)方向上的,也没有规定只能往前走)
然后就\(bfs\)即可
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=400+10;
#define int long long
int n,m;
int dis[maxn][maxn];
bool vis[maxn][maxn];
int dx[maxn];
int dy[maxn];
int cnt;
void get()
{
for(int i=0;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(i*i+j*j==m)
{
dx[++cnt]=i,dy[cnt]=j;
dx[++cnt]=i,dy[cnt]=-j;
dx[++cnt]=-i,dy[cnt]=j;
dx[++cnt]=-i,dy[cnt]=-j;
dx[++cnt]=j,dy[cnt]=i;
dx[++cnt]=j,dy[cnt]=-i;
dx[++cnt]=-j,dy[cnt]=i;
dx[++cnt]=-j,dy[cnt]=-i;
}
}
}
return ;
}
void bfs()
{
queue<pair<int,int>>q;
q.push({1,1});
vis[1][1]=true;
while (!q.empty())
{
int x=q.front().first;
int y=q.front().second;
q.pop();
for (int d=1;d<=cnt;d++)
{
int tx=x+dx[d];
int ty=y+dy[d];
if (tx>n||ty>n||tx<=0||ty<=0) continue;
if (vis[tx][ty]) continue;
vis[tx][ty]=true;
dis[tx][ty]=dis[x][y]+1;
q.push({tx,ty});
}
}
return ;
}
signed main ()
{
cin>>n>>m;
get();
memset(dis,-1,sizeof(dis));
dis[1][1]=0;
vis[1][1]=true;
bfs();
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
cout<<dis[i][j]<<" ";
}
cout<<'\n';
}
system ("pause");
return 0;
}
E
这个题呢就是给你\(n\)个数,我们会进行\(m\)轮操作,每一轮操作\(a_i\)都会变成\(a_i+i\),对于每一轮操作后得到的\(n\)个数,我们需要知道这\(n\)个数的\(mex\)
对于\(mex\),我们可以知道负数是对\(mex\)有任何影响的,还有大于\(n\)的数也一定是没有影响的(要想\(mex\)是\(n+1\),至少需要\(n+1\)个数
那么对于每一个数,我们需要记录的就只能是小于等于\(n\)的非负数
求\(mex\)的过程,就是一一判断\(1\)到\(mex-1\)这一段之间的数是否存在,我们直接用\(map\)表示第\(x\)次操作后有哪些数字存在
那么对于那些小于\(0\)的数,我们首先要找到他大于等于\(0\)的最小操作,然后再一个一个操作地记录
然后具体的就看代码吧
#include <iostream>
#include <algorithm>
#include <map>
#include <algorithm>
using namespace std;
const int maxn=2e5+10;
#define int long long
int n,m;
int a[maxn];
map<int,bool>vis[maxn];
signed main ()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>a[i];
int tim=0;
if (a[i]<0)
{
int now=-1*a[i];
int k=now/i+(now%i!=0);//>=0需要的次数
tim=k-1;
}
for (int j=tim+1;j<=m&&(a[i]+i*j)<=n;j++)
{
vis[j][a[i]+i*j]=true;
}
}
for (int i=1;i<=m;i++)
{
for (int j=0;j<=n;j++)
{
if (!vis[i][j])
{
cout<<j<<"\n";
break;
}
}
}
system ("pause");
return 0;
}
F
不会写
标签:AtCoder,Beginner,int,long,272,maxn,include,mex,dis From: https://www.cnblogs.com/righting/p/17203140.html