首页 > 其他分享 >AtCoder Beginner Contest 272(D,E)

AtCoder Beginner Contest 272(D,E)

时间:2023-03-10 14:14:26浏览次数:74  
标签:AtCoder Beginner int long 272 maxn include mex dis

AtCoder Beginner Contest 272(D,E)

D

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

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

相关文章

  • 272. 最长公共上升子序列
    题目来源acwing题目难度3星算法标签dp+优化参考程序#include<iostream>usingnamespacestd;constintN=3005;intn;inta[N],b[N];//dp[i][j]表......
  • AtCoder Beginner Contest 292-C D E
    C.FourVariables从正整数中,找出合适的ABCD,使得这个式子成立\(AB+CD=N\)。可以看到,A与B是相互关联的,C与D是相互关联的,所以我们可以在小于N的正整数中,找寻可以相加的两个......
  • Atcoder-ABC291 "Teleporter and Closed off" 动态DP版
    题目地址题意:在一个DAG图中,点i只有最多m条出边连向i+1~i+m(m<=10),边权均为1。对于\(k\in[2,n-1]\),依次输出当点k被删除时1到n的最短路。分析:标准做法无非就是预......
  • 容斥定理 AtCoder——FizzBuzz Sum Hard
    题目传送门ProblemStatementFindthesumofintegersbetween 1 and N(inclusive)thatarenotmultiplesof Aor B.Constraints1≤N,A,B≤109 Allvalue......
  • AtCoder Beginner Contest 292
    A-CAPSLOCK#include<bits/stdc++.h>usingnamespacestd;int32_tmain(){strings;cin>>s;for(autoi:s)cout<<char(i-'a'+......
  • AtCoder Beginner Contest 292
    《E-Transitivity》   这道题首先要看一下自己有没有理解错题意:      问:点2和点3之间要连边吗? 答案是不需......
  • AtCoder Regular Contest 131(A,B,C)
    AtCoderRegularContest131(A,B,C)AA这个大意就是很容易做出来,只是有一点要注意,对于第二个字符串,如果小于\(2\),那么比如\(1\),,这些可能是进位形成的,所以我们需要补一......
  • AtCoder Beginner Contest 292
    A-CAPSLOCK(abc292a)题目大意给定一个小写字母串,将其转换成大写字母。解题思路调库,或者按照ascii码转换即可。神奇的代码#include<bits/stdc++.h>usingname......
  • AtCoder Beginner Contest 252
    AtCoderBeginnerContest252D题意在数组中形如\(1\leqi<j<k\leqn\)使得\(a_i,a_j,a_k\)互不相同,求共有多少组满足条件思路它的数据范围\(1\leqa_i\leq2*10^5\)......
  • AtCoder Beginner Contest 251
    AtCoderBeginnerContest251D给定一个1e6范围内的数n,要你构造出一个数组,对于1~n中的任何一个数都能用数组中最多三个数的和加起来。这题真的是很好的一道思维题,想了我......