首页 > 其他分享 >Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339)

Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339)

时间：2024-02-06 17:22:55浏览次数：41  
标签：AtCoder 339 Contest int ll long pair using define

Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339)

A - TLD

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 1010;
const int mod = 1e9 + 7;

void solve()
{
    string s;
    cin >> s;
    int idx = 0;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        char c = s[i];
        if (c == '.')
        {
            idx = i;
        }
    }
    cout << s.substr(idx + 1) << endl;
}

int main()
{

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

B - Langton's Takahashi

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 110;
char g[N][N];

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            g[i][j] = '.';
        }
    }
    int x = 1;
    int y = 1;
    int f = 0;
    while (k--)
    {
        // cout << x << ' ' << y << endl;
        if (g[x][y] == '.')
        {
            g[x][y] = '#';
            f += 1;
            f += 4;
            f %= 4;
            if (f == 0)
            {
                x = ((x - 1) - 1) % n;
                x += n;
                x %= n;
                x += 1;
            }
            else if (f == 1)
            {
                y = y % m;
                y += m;
                y %= m;
                y += 1;
            }
            else if (f == 2)
            {
                x = ((x - 1) + 1) % n;
                x += n;
                x %= n;
                x += 1;
            }
            else
            {
                y = (y - 2) % m;
                y += m;
                y %= m;
                y += 1;
            }
        }
        else
        {
            g[x][y] = '.';
            f -= 1;
            f += 4;
            f %= 4;
            if (f == 0)
            {
                x = ((x - 1) - 1) % n;
                x += n;
                x %= n;
                x += 1;
            }
            else if (f == 1)
            {
                y = y % m;
                y += m;
                y %= m;
                y += 1;
            }
            else if (f == 2)
            {
                x = ((x - 1) + 1) % n;
                x += n;
                x %= n;
                x += 1;
            }
            else
            {
                y = (y - 2) % m;
                y += m;
                y %= m;
                y += 1;
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << g[i][j];
        }
        cout << endl;
    }
}

int main()
{

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

C - Perfect Bus

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 110;
char g[N][N];

void solve()
{
    ll n;
    cin >> n;
    ll cur = 0;
    ll t = 1e18;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cur += x;
        t = min(t, cur);
    }
    if (t >= 0)
    {
        cout << cur << endl;
    }
    else
    {
        cout << cur - t << endl;
    }
}

int main()
{

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

D - Synchronized Players

解题思路:

\(bfs\)搜索，枚举两位棋手从开始位置移动的每一种情况，最多\(60^4\)个位置对。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 65;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int dist[N][N][N][N];
bool vis[N][N][N][N];

struct node
{
    pii a;
    pii b;
};

void solve()
{
    int n;
    cin >> n;
    vector<string> g(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> g[i];
        g[i] = ' ' + g[i];
    }
    vector<pii> st;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (g[i][j] == 'P')
            {
                st.push_back({i, j});
            }
        }
    }
    memset(dist, 0x3f, sizeof dist);
    queue<node> q;
    q.push((node){{st[0].fi, st[0].se}, {st[1].fi, st[1].se}});
    dist[st[0].fi][st[0].se][st[1].fi][st[1].se] = 0;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        int x1 = t.a.fi;
        int y1 = t.a.se;
        int x2 = t.b.fi;
        int y2 = t.b.se;
        if (vis[x1][y1][x2][y2])
        {
            continue;
        }
        vis[x1][y1][x2][y2] = true;
        for (int i = 0; i < 4; i++)
        {
            int nx1 = max(1, min(x1 + dx[i], n));
            int ny1 = max(1, min(y1 + dy[i], n));
            int nx2 = max(1, min(x2 + dx[i], n));
            int ny2 = max(1, min(y2 + dy[i], n));
            if (g[nx1][ny1] == '#')
            {
                nx1 -= dx[i];
                ny1 -= dy[i];
            }
            if (g[nx2][ny2] == '#')
            {
                nx2 -= dx[i];
                ny2 -= dy[i];
            }
            dist[nx1][ny1][nx2][ny2] = min(dist[nx1][ny1][nx2][ny2], dist[x1][y1][x2][y2] + 1);
            q.push({{nx1, ny1}, {nx2, ny2}});
        }
    }
    ll ans = 1e18;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            ans = min(ans, (ll)dist[i][j][i][j]);
        }
    }
    if (ans >= 1e9)
    {
        ans = -1;
    }
    cout << ans << endl;
}

int main()
{

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

E - Smooth Subsequence

解题思路:

线段树优化\(dp\)。

\(dp[i]:以第i个数为结尾的最长合法序列\)。

对于\(a[i]\)，我们能将结尾数字为\([a[i] - d,a[i] + d]\)的序列和其拼接。

也就是说我们要找到结尾在\([a_i-d,a_i+d]\)这个区间上的最大\(dp\)值，区间查询，单点修改。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 5e5 + 10;
int n, d;
int maxv[N * 4];
int a[N];
int dp[N];

void pushup(int u)
{
    maxv[u] = max(maxv[u << 1], maxv[u << 1 | 1]);
}

void modify(int u, int l, int r, int x, int val)
{
    if (l == r)
    {
        maxv[u] = max(maxv[u], val);
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
    {
        modify(u << 1, l, mid, x, val);
    }
    else
    {
        modify(u << 1 | 1, mid + 1, r, x, val);
    }
    pushup(u);
}

int query(int u, int l, int r, int nl, int nr)
{
    if (l >= nl && r <= nr)
    {
        return maxv[u];
    }
    int res = 0;
    int mid = l + r >> 1;
    if (nl <= mid)
    {
        res = max(res, query(u << 1, l, mid, nl, nr));
    }
    if (nr > mid)
    {
        res = max(res, query(u << 1 | 1, mid + 1, r, nl, nr));
    }
    return res;
}

void solve()
{
    cin >> n >> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int ans = 0;
    int m = N - 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i] = query(1, 1, m, max(1, a[i] - d), min(500000, a[i] + d)) + 1;
        ans = max(ans, dp[i]);
        modify(1, 1, m, a[i], dp[i]);
    }
    cout << ans << endl;
}

int main()
{

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

F - Product Equality

解题思路:

哈希乱搞。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int m1 = 1e9 + 7;
const int m2 = 13331;
const int m3 = 1145141;
const int N = 1010;
ll a[N];
ll b[N];
ll d[N];

void solve()
{
    int n;
    cin >> n;
    map<piii, int> q;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (auto c : s)
        {
            a[i] = (a[i] * 10 + (c - '0')) % m1;
            b[i] = (b[i] * 10 + (c - '0')) % m2;
            d[i] = (d[i] * 10 + (c - '0')) % m3;
        }
        q[{a[i], {b[i], d[i]}}]++;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            ll t1 = a[i] * a[j] % m1;
            ll t2 = b[i] * b[j] % m2;
            ll t3 = d[i] * d[j] % m3;
            ans += q[{t1, {t2, t3}}];
        }
    }
    cout << ans << endl;
}

int main()
{

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

G - Smaller Sum

解题思路:

动态开点 + 主席树。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
const int N = 2e5 + 10;
ll s[N * 65];
int a[N];
int root[N];
int idx = 0;
int ls[N * 65], rs[N * 65];
void insert(auto &pre, auto &cur, int l, int r, int val)
{
    cur = ++idx;
    s[cur] = s[pre] + val;
    if (l == r)
    {
        return;
    }
    int mid = l + r >> 1;
    if (val <= mid)
    {
        rs[cur] = rs[pre];
        insert(ls[pre], ls[cur], l, mid, val);
    }
    else
    {
        ls[cur] = ls[pre];
        insert(rs[pre], rs[cur], mid + 1, r, val);
    }
}

ll query(int pre, int u, int l, int r, int nl, int nr)
{
    if (l >= nl && r <= nr)
    {
        return s[u] - s[pre];
    }
    int mid = l + r >> 1;
    ll res = 0;
    if (nl <= mid)
    {
        res += query(ls[pre], ls[u], l, mid, nl, nr);
    }
    if (nr > mid)
    {
        res += query(rs[pre], rs[u], mid + 1, r, nl, nr);
    }
    return res;
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        insert(root[i - 1], root[i], 0, 1e9, a[i]);
    }
    int q;
    cin >> q;
    ll ans = 0;
    while (q--)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        ll l = a ^ ans;
        ll r = b ^ ans;
        ll x = c ^ ans;
        ans = query(root[l - 1], root[r], 0, 1e9, 0, x);
        printf("%lld\n", ans);
    }
}

int main()
{

    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

标签：AtCoder,339,Contest,int,ll,long,pair,using,define
From： https://www.cnblogs.com/value0/p/18010071

相关文章

  • P3397 地毯
    原题链接二维差分的简单应用。作为学二维差分时的练手题很不错。主要代码：#include<bits/stdc++.h>usingnamespacestd;constintN=1002;inta[N][N];intmain(){ios::sync_with_stdio(false);intn,m;cin>>n>>m;for(inti=1;i<=m;i++){in......
  • AtCoder Beginner Contest 339
    A找到最后一个点的位置，使用substr函数。B模拟，记得边界是循环的。C容易发现答案为：\[\min_p(\sum_{i=1}^{p}a_i)+\sum_{i=1}^{n}a_i\]D由于不同状态数只有\(60^4\)，容易搜索，但是我去吃饭了，所以没能快速切掉。E有一个显然的dp，然后考虑每一个\(a_i\)可以转移到\(a_j\)......
  • abc339 详解
    第一篇整场题解纪念我第一次AK的abc！A从后往前找到第一个'.'然后输出'.'到字符串结尾构成的字符串。#include<iostream>usingnamespacestd;intmain(intargc,constchar*argv[]){stringstr;cin>>str;intlen=(int)str.length();stri......
  • 2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019)
    Preface由于前两天疑似感染风寒，今天头痛+鼻塞+咽炎一条龙，硬打了4h顶不住就下班了最后过了8个题也还行，比较可惜的就是H题从中期写到结束，祁神和徐神各写了一个version也没过A.AverageRank挺有意思的一个题考虑将一个原来分数为\(x\)的人加\(1\)分后会发生什么，显然只有原来分......
  • AtCoder Beginner Contest 330
    A-CountingPasses#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingvi=vector<int>;usingi32=int32_t;usingpii=pair<int,int>;#definempmake_pairconstintinf=1e9;i32main(){intn,l;......
  • AtCoder Beginner Contest 339
    基本情况A和C出的比较快但不能说秒了还是思考了几分钟的，然后B很奇怪我样例还有一些测试点都能过，但有些测试点就是过不了...A-TLD貌似没啥说的B-Langton'sTakahashi说实话现在还是不懂我的哪里错了很不科学啊，明明很多测试点都过了啊C-PerfectBus做题时的思路：要想求......
  • ABC339 F Product Equality 题解
    QuestionABC339FProductEquality给出一个序列\(A_1,A_2,\cdots,A_N\)计算数对\((i,j,k)\)满足\(A_i\timesA_j=A_k\)的个数\(A_i\le10^{1000}\)Solution思考\(A_i\)比较小的情况如果\(A_i\le1e9\)的，暴力枚举\(i,j\)然后用\(map\)查找\(A_i\timesA_j......
  • ABC339
    T1：TLD模拟代码实现s=input()a=s.split('.')print(a[-1])T2：Langton'sTakahashi模拟代码实现#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<(n);++i)usingnamespacestd;constintdi[]={-1,0,1,0};constintd......
  • 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想成是横向移动了。下次要注意画图，不......
  • Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contes
    //这一场我感觉有了新的蜕变思考问题也变了多种，3题（✌）A-TLD思路：题目本意 Youaregivenastring S， Printthelastsubstringwhen S issplitby .s给你一个字符串输出最后的点的网址(类似)的后缀，入坑点没有，题意简单。思路方法：最后一个‘.’为停止符号，倒的字符串......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99