首页 > 其他分享 >ABC339

ABC339

时间:2024-02-03 23:55:46浏览次数:26  
标签:ABC339 dist ps int res rep id

T1:TLD

模拟

代码实现
s = input()
a = s.split('.')
print(a[-1])

T2:Langton's Takahashi

模拟

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vector<string> s(h, string(w, '.'));
    
    int i = 0, j = 0, v = 0;
    rep(ti, n) {
        if (s[i][j] == '.') {
            s[i][j] = '#';
            v += 1;
        }
        else {
            s[i][j] = '.';
            v += 3;
        }
        v %= 4;
        i += di[v]; j += dj[v];
        i = (i+h)%h; 
        j = (j+w)%w; 
    }
    
    rep(i, h) cout << s[i] << '\n';
    
    return 0;
}

T3:Perfect Bus

先假设初始人数为 \(0\),然后求一遍到每一站为止的人数,找到其中最小的负数 \(x\),然后将初始人数改成 \(-x\) 就能满足题目要求

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    ll y = 0, l = 0;
    rep(i, n) {
        y += a[i];
        l = min(l, y);
    }
    
    ll ans = y+(-l);
    cout << ans << '\n';
    
    return 0;
}

T4:Synchronized Players

维护两个玩家当前所在的点作为状态跑bfs即可

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;
using vp = vector<P>;

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

int main() {
    int n;
    cin >> n;
    
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    
    vector<P> ps;
    rep(i, n)rep(j, n) {
        if (s[i][j] == 'P') ps.emplace_back(i, j);
    }
    
    auto to_i = [&](vp ps) {
        int res = 0;
        res = res*n + ps[0].first;
        res = res*n + ps[0].second;
        res = res*n + ps[1].first;
        res = res*n + ps[1].second;
        return res;
    };
    auto to_ps = [&](int id) {
        vp ps(2);
        ps[1].second = id%n; id /= n;
        ps[1].first = id%n; id /= n;
        ps[0].second = id%n; id /= n;
        ps[0].first = id%n; id /= n;
        return ps;
    };
    
    int m = n*n*n*n;
    const int INF = 1001001001;
    vector<int> dist(m, INF);
    queue<int> q;
    int sid = to_i(ps);
    dist[sid] = 0;
    q.push(sid);
    while (q.size()) {
        int id = q.front(); q.pop();
        int d = dist[id];
        vp ps = to_ps(id);
        rep(v, 4) {
            vp nps;
            for (auto [i, j] : ps) {
                int ni = i+di[v], nj = j+dj[v];
                if (ni < 0 or nj < 0 or ni >= n or nj >= n or s[ni][nj] == '#') {
                    ni = i; nj = j;
                }
                nps.emplace_back(ni, nj);
            }
            int nid = to_i(nps);
            if (dist[nid] != INF) continue;
            dist[nid] = d+1;
            q.push(nid);
        }
    }
    
    int ans = INF;
    rep(id, m) {
        vp ps = to_ps(id); 
        int d = dist[id];
        if (ps[0] == ps[1]) ans = min(ans, d);
    }
    
    if (ans == INF) ans = -1;
    cout << ans << '\n';
    
    return 0;
}

标签:ABC339,dist,ps,int,res,rep,id
From: https://www.cnblogs.com/Melville/p/18005425

相关文章

  • ABC339总结
    ABC339Url:https://atcoder.jp/contests/abc339Time:1h30minComplete_time:2hB模拟,但是我考场上交了三次没过。因为我计算转移的时候把n,m写反了。x=(x+dx[dir]+m)%m;y=(y+dy[dir]+n)%n;x,y是坐标,dir是方向。我想错了,将x想成是横向移动了。下次要注意画图,不......
  • ABC339_g Smaller Sum 题解
    题目链接:Atcoder或者洛谷比价朴素的题,首先有暴力的想法就是树套树或者分块。这两种就不再赘述,这里来正式提提主xi树(应该不能打出来这玩意)的本质而不再停留在板题找第\(k\)大上。对于可差性问题和传统问题不同,我们对于可差性问题往往都有更好的优化方案。例如对于树类问......
  • ABC339
    题解不应该流露出太多感情,对吧。E建议评黄。首先我们可以想到暴力dp。定义\(dp_i\)为以\(a_i\)为结尾满足题目意思的最长序列的长度。很明显,时间复杂度为\(O(n^2)\)不可通过本题。我们发现一个序列以\(a_i\)为结尾,那么上一位绝对是以\(a_i-k\)到\(a_i+k\)中的......
  • ABC339 题解
    AK了。A-TLD给出一个字符串\(s\),输出最后一个.后面的内容。\(|s|\le100\)。\(\text{2sec/1024MB}\)。按照题意模拟即可,时空复杂度均为\(\mathcal{O}(|s|)\)。ACCodeB-Langton'sTakahashi给出\(H\timesW\)的网格。初始你在\((1,1)\),方向......
  • ABC339 题解(A~G)
    A从后向前找到第一个.就行了。B按照题意模拟,设当前位置\(x,y\)移动方向\(dx,dy\)。那么下一步为\((x+dx,y+dy)\)设新的移动方向为\(dx',dy'\)如果顺时针旋转,则有\(dy'\gets-dx,dx'\getsdy\);如果逆时针,则有\(dx'\gets-dy,dy'\getsdx\)。C鉴定为除A以外......