首页 > 其他分享 >AtCoder Beginner Contest 339

AtCoder Beginner Contest 339

时间:2024-02-20 17:36:03浏览次数:26  
标签:AtCoder 339 Beginner int res long Ai tie define




B - Langton's Takahashi

难度: ⭐⭐

题目大意

给定一个n * m的网格, 并且每一行和每一列都是首尾相连的, 每行的最后一个格子再往右就是这行的第一个格子, 第一个格子向左就是最后一个格子; 列也同理; 默认每个格子初始为白色; 小莫位于(1, 1), 方向朝上;
当小莫位于某个格子时, 如果当前单元格是白色,则将其重新涂成黑色,前进方向顺时针旋转90度,然后沿着他面对的方向向前移动一个单元格。如果是黑色,则将当前单元格重新涂成白色,逆时针旋转90度,然后沿着他所面对的方向向前移动一个单元格。
将上述步骤进行k次, 打印最后格子的颜色分布, '.'表示白色, '#'为黑色;

解题思路

模拟就行, 没啥好说的;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, res;
int g[110][110];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
signed main(){
    int k;
    cin >> n >> m >> k;
    int a = 1, b = 1, d = -1;
    while(k--){
        if(g[a][b]){
            g[a][b] = 0;
            d = (d - 1 + 4) % 4;
            a += dx[d], b += dy[d];
        }
        else{
            g[a][b] = 1;
            d = (d + 1) % 4;
            a += dx[d], b += dy[d];
        }
        if(a > n) a = 1;
        else if(a < 1) a = n;
        if(b > m) b = 1;
        else if(b < 1) b = m;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(g[i][j]) cout << '#';
            else cout << '.';
        }
        cout << endl;
    }
    return 0;   
}




C - Perfect Bus

难度: ⭐⭐

题目大意

给定一个公交车n个站牌的上下车情况, 这期间车上的人数始终不能小于0, 请问满足条件的最小的初始人数是多少;

解题思路

很简单, 只需要当人数小于0的时候把人数补到0即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, res;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int a;
        cin >> a;
        res += a;
        if(res < 0){
            res = 0;
        }
    }
    cout << res;
    return 0;   
}




D - Synchronized Players

难度: ⭐⭐⭐

题目大意

在一个n * n的网格中有两名玩家, 每次我们可以选择上下左右中的一个方向, 两人都朝这个方向前进一格; 如果某人面前是障碍物或者边界则这名玩家不移动; 请问最少进行多少次可以让两名玩家同时位于同一个格子; 无解则输出-1;

解题思路

由于没有什么规律, 所以bfs打暴力即可; 因为数据很小, 所以可以开一个四维数组来去重, 以便判断是否有解;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, res;
int xa, ya, xb, yb;
char g[100][100];
bool st[62][62][62][62];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
struct node{
    int xa, ya, xb, yb;
    int num;
};
bool check(int x, int y){
    if(x >= 1 && x <= n && y >= 1 && y <= n && g[x][y] != '#'){
        return true;
    }
    else return false;
}
int bfs(){
    queue<node> q;
    q.push({xa, ya, xb, yb, 0});
    while(q.size()){
        auto t = q.front();
        q.pop();
        if(t.xa == t.xb && t.ya == t.yb){
            return t.num;
        }
        for(int i = 0; i < 4; i++){
            int x1 = t.xa + dx[i], y1 =t.ya + dy[i];
            int x2 = t.xb + dx[i], y2 =t.yb + dy[i];
            if(!check(x1, y1)){
                x1 = t.xa, y1 = t.ya;
            }
            if(!check(x2, y2)){
                x2 = t.xb, y2 = t.yb;
            }
            if(!st[x1][y1][x2][y2]) {
                q.push({x1, y1, x2, y2, t.num + 1});
                st[x1][y1][x2][y2] = true;
            }
        }
    }
    return -1;
}
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> g[i][j];
            if(g[i][j] == 'P'){
                if(xa) xb = i, yb = j;
                else xa = i, ya = j;
            }
        }
    }
    cout << bfs();
    return 0;   
}




E - Smooth Subsequence

难度: ⭐⭐⭐

题目大意

给定一个长度为n的数组A, 求其满足条件的子序列的最大长度是多少;
要求该子序列相邻的数之间差距不能超过m;

解题思路

我一开始想的是用dp, 并且根据题意对于每个数肯定是能接就接; 如果当前进行到了Ai, Ai要接在以(Ai - m, Ai + m)其中一个数结尾的子序列后面, 假设把所有满足条件的子序列后面都接上Ai, 我们发现其实只需要保留其中最长的一个子序列就行, 因为他们都是以Ai, 是等效的; 所以我们可以用线段树来维护以x结尾的子序列的最大长度; 对于Ai就只需要从(Ai - m, Ai + m)中找出最大值即可; 所以其实也用不到dp;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 5e5 + 10, mod = 998244353, inf = 1e18;
typedef pair<int, int> PII;
int n, m, res;
int p[N];
struct node{
    int l, r;
    int maxn;
}tr[4 * N];
void pushup(int u){
    tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}
void build(int u, int l, int r){
    tr[u] = {l, r, 0};
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int x, int num){
    if(tr[u].l == tr[u]. r && tr[u].l == x){
        if(num > tr[u].maxn){
            tr[u].maxn = num;
        }
    }
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, num);
        else modify(u << 1 | 1, x, num);
        pushup(u);
    }
}
int query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r){
        return tr[u].maxn;
    }
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if(l <= mid) res = max(res, query(u << 1, l, r));
        if(r > mid) res = max(res, query(u << 1 | 1, l, r));
        return res;
    }
}
signed main(){
    cin >> n >> m;
    int k = 0;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
        k = max(k ,p[i]);
    }
    build(1, 1, k);
    for(int i = 1; i <= n; i++){
        int maxn = query(1, max(0ll, p[i] - m), min(k, p[i] + m));
        modify(1, p[i], maxn + 1);
    }
    cout << query(1, 1, k);
    return 0;   
}




F - Product Equality

难度: ⭐⭐⭐

题目大意

给定一个长度为n的数组A, 找出满足条件的三元组(i, j, k)的数量: 1 <= i, j, k <= n, 并且 Ai * Aj = Ak;

解题思路

要求很简单, 但是本题的难点在于Ai的范围是101000; 可以用python的大数来做, 如果用c++的话就只能靠哈希来赌了; 为了提高概率这里我们用双哈希; 也就是对于每个Ai, 我们用两个数对其取模, 用这两个数的二元组来代表这个数; 当然不放心的话也可以再多几层哈希;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 5e5 + 10, mod = 998244353, inf = 1000000993;
typedef pair<int, int> PII;
int n, m, res;
int p[2][N];
map<PII, int> mp;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < s.size(); j++){
            p[0][i] = (p[0][i] * 10 + (s[j] - '0')) % mod;
            p[1][i] = (p[1][i] * 10 + (s[j] - '0')) % inf;
        }
        mp[{p[0][i], p[1][i]}]++;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            res += mp[{p[0][i] * p[0][j] % mod, p[1][i] * p[1][j] % inf}];
        }
    }
    cout << res;
    return 0;   
}

标签:AtCoder,339,Beginner,int,res,long,Ai,tie,define
From: https://www.cnblogs.com/mostimali/p/18023627

相关文章

  • [2024 AtCoder 比赛历程]
    2024.1.20ABC337-G题目大意:给定一棵树,对于树上的每个点$u$,定义$f[u]$表示满足点$w$在点$u$到点$v$的路径中,且$w>v$的点对$(w,v)$的数量。$u$可以等于$w$。解法:比赛时先考虑将一个点钦定为$w$时,该点对其他点的贡献。发现对于一个点,它可以通过它的一个子树内......
  • AtCoder Beginner Contest 341
    AtCoderBeginnerContest341做得太慢了,原因BC题意很难懂,而且一开始AtCoderBetter加载不出来,不好翻译(先用10min做的AB。其中B好几次读错题。看C发现题面这么长压根看不懂,先看小清新D。发现一眼出思路,二分很快写完了。后来调二分边界用了很长时间,实际上此时已经......
  • Toyota Programming Contest 2024#2(AtCoder Beginner Contest 341)(菜小白)
    A-Print341思路:给你一个整数N有N个0和N+1个1组成 01交替输出1 解法:输出10最后输出最后剩余的1即可Code:#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intN;cin>>N......
  • AtCoder Grand Contest 012 E Camel and Oases
    洛谷传送门AtCoder传送门容易发现跳跃次数为\(O(\logV)\)。考虑对于跳跃\(k\)次后的限制\(\left\lfloor\frac{V}{2^k}\right\rfloor\),对每个点预处理出不再跳跃能到达的最左和最右的点\([l_{k,i},r_{k,i}]\)。于是问题变成了,从第\(i\)个区间集选择一个区间\([a_i,......
  • AtCoder Beginner Contest 340 题解
    AtCoderBeginnerContest340题解去我的洛谷博客里看这篇文章!A-ArithmeticProgression模拟即可。//2024/2/11PikachuQAQ#include<iostream>usingnamespacestd;inta,b,d;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>......
  • AtCoder Beginner Contest 340 题解
    AtCoderBeginnerContest340题解去我的洛谷博客里看这篇文章!A-ArithmeticProgression模拟即可。//2024/2/11PikachuQAQ#include<iostream>usingnamespacestd;inta,b,d;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>......
  • KAJIMA CORPORATION CONTEST 2024(AtCoder Beginner Contest 340)
    KAJIMACORPORATIONCONTEST2024(AtCoderBeginnerContest340)A-ArithmeticProgression代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__int128......
  • 1339. 分裂二叉树的最大乘积
    这道题关键突破点就是先算出节点总和,然后找到一颗子树总和最接近总和的一半。乘积最大基本就是先要求总和,然后找到最接近总和一半。关键就是这一步,找到最适合子树的和。点击查看代码if(abs(2*cur-sum)<abs(2*best-sum)){best=cur;}完整代码:点击查看......
  • Atcoder ABC340(A-D)
    A题题意:给出一个首项为A,尾项为B,公差为D的算数序列,要求输出符合条件的序列思路:只需要从首项开始每次加上公差输出即可代码:#include<bits/stdc++.h>#defineiosios::sync_with_stdio(false);cin.tie(0);cout.tie(0)usingnamespacestd;intadd(intx,inty){returnx......
  • AtCoder Beginner Contest 340 考试总结
    前言可惜的是我是VP的,却打得相对较好(服了。得分明细:ABCDEFGTotal√√√√√√×2625改题明细:ABCDEFG√√√√√√×第一次打AT,发挥还可以。A.ArithmeticProgressionProblem打印一个包含第一项\(A\),最后一项\(B\)......