当前位置：首页 > news >正文

AtCoder Beginner Contest 272「ABCDE」

news 来源：原创 2024/4/25 23:18:48

AtCoder Beginner Contest 272

A - Integer Sum

题目描述：

输入n个数字，求数字和

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        m += x;
    }
    cout << m << endl;
}

int main(){
    io;
    work();
    return 0;
}

B - Everyone is Friends

题目描述：

给出m场演出，以及每场演出的参加人员，如果存在任意两个人没有一起参加过演出，则输出No，否则是Yes

思路：

暴力计算即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
bool tr[105][105];

void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> k;
        vector<int>v;
        for(int j = 1; j <= k; ++j){
            cin >> x;
            v.push_back(x);
        }
        for(int j = 0; j < v.size(); ++j){
            for(int p = 0; p < v.size(); ++p){
                tr[v[j]][v[p]] = tr[v[p]][v[j]] = 1;
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= i; ++j){
            if(i != j && !tr[i][j]){
                cout << "No\n";
                return;
            }
        }
    }
    cout << "Yes\n";
}

int main(){
    io;
    work();
    return 0;
}

C - Max Even

题目描述：

给n个数字，让你任意挑两个不同的数字，使得数字之和最大，问最大可以是多少

思路：

奇偶分开，奇+奇=偶偶+偶=偶，所以找大最大的两个奇数和最大的两个偶数求最大值就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
ll x;

void work(){
    cin >> n;
    vector<ll>odd,even;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        if(x % 2)odd.push_back(x);
        else even.push_back(x);
    }
    sort(odd.begin(), odd.end());
    sort(even.begin(), even.end());
    ll ans = -1;
    if(odd.size() > 1)ans = max(ans, odd.back() + odd[(int)odd.size() - 2]);
    if(even.size() > 1)ans = max(ans, even.back() + even[(int)even.size() - 2]);
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

D - Root M Leaper

题目描述：

给定n*n的方格矩阵，你每一步都只能到达与你当前点距离为 $\sqrt{m}$ 的点，你需要输出一个n*n的方格矩阵，每个点(i,j)的需要输出从(1,1)到(i,j)的最短步数

思路：

bfs

假设当前在(i,j)，到达(p,q)，需要满足： $p-i)^2+(q-j)^2=m$

枚举m等于哪两个平方数的和，然后可以往八个方向跑，暴力bfs即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y;
int tr[405][405];
vector<pii>v;

bool judge(int x, int y){
   if(x < 1 || x > n || y > n || y < 1)return false;
   if(tr[x][y]!=inf)return false;
   return true;
}

void bfs(){
   queue<pii>q;
   q.push(m_p(1, 1));
   while(!q.empty()){
       auto [x, y] = q.front();q.pop();
//        cout << x << ' ' << y << endl;
       for(auto [dx, dy] : v){
           int xx = x + dx;
           int yy = y + dy;
//            cout << xx << ' ' << yy << ' ' << judge(xx, yy) << endl;
           if(!judge(xx, yy))continue;
           tr[xx][yy] = min(tr[xx][yy], tr[x][y] + 1);
           q.push(m_p(xx, yy));
       }
   }
}

void work(){
   cin >> n >> m;
   mem(tr, inf);
   tr[1][1] = 0;
   for(int i = 1; i <= 1000; ++i){
       x = i;
       y = sqrt(m - x*x);
       if(y*y == m - x*x){
//            cout << x << ' ' << y << endl;
           v.push_back(m_p(x, y));
           v.push_back(m_p(-x, y));
           v.push_back(m_p(x, -y));
           v.push_back(m_p(-x, -y));
           v.push_back(m_p(y, -x));
           v.push_back(m_p(-y, x));
           v.push_back(m_p(-y, -x));
           v.push_back(m_p(y, x));
       }
   }
   bfs();
   for(int i = 1; i <= n; ++i){
       for(int j = 1; j <= n; ++j){
           if(tr[i][j] == inf)cout << -1 << ' ';
           else cout << tr[i][j] << ' ';
       }
       cout << endl;
   }
}


int main(){
   io;
   work();
   return 0;
}

E - Add and Mex

题目描述：

n个数，m轮，每轮都会给第i个元素a[i]加上i，输出每一轮最小未出现的非负数

思路：

不难发现答案的最大不会超过n,最极端的情况是当前轮结束后剩下的数字是0 1 2 3 4...n-1,此时答案就是n

所以我们可以考虑开一个大小为n+1的vector，记做tr，记录当i等于a中未出现的最小的非负数时的所有可能的轮数，处理方法是对每个a[i]，假设0<=a[i]+k*i<=n，就在tr[a[i]+k*i]中push一个k

我们从tr[0]跑到tr[n],维护一个集合表示1-m中当前还没确定答案的所有的数，对于tr[i]，我们找出还没确定答案的且出现在tr[i]中的数字id，则ans[id]=i

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
vector<int>tr[MAX];
int ans[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        int num = x >= 0 ? 0 : (-x + i - 1) / i;
        if(x < 0)x = (x%i+i)%i;
        while(x <= 2e5){
            tr[x].push_back(num);
            x += i;
            ++num;
        }
    }
    set<int>s;
    for(int i = 1; i <= m; ++i)s.insert(i);
    for(int i = 0; i <= 2e5; ++i){
        set<int>ss;
        for(auto x : tr[i])ss.insert(x);
        for(auto x : s){
            if(!ss.count(x))ans[x] = i;
        }
        set<int>fuck;
        for(auto x : ss){
            if(s.count(x))fuck.insert(x);
        }
        s = fuck;
        if(s.size() == 0)break;
    }
    for(int i = 1; i <= m; ++i)cout << ans[i] << endl;
}


int main(){
    io;
    work();
    return 0;
}