首页 > 其他分享 >Toyota Programming Contest 2024#2（AtCoder Beginner Contest 341）

Toyota Programming Contest 2024#2（AtCoder Beginner Contest 341）

时间：2024-02-20 23:44:39浏览次数：27  
标签：AtCoder return Beginner Contest int ll long using define

Toyota Programming Contest 2024#2（AtCoder Beginner Contest 341）

A - Print 341

代码:

#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>>;

void solve()
{
    int n;
    cin >> n;
    int cur = 1;
    for (int i = 1; i <= 2 * n + 1; i++)
    {
        cout << cur;
        cur ^= 1;
    }
}

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

B - Foreign Exchange

代码:

#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>>;

void solve()
{
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    vector<ll> s(n + 1), t(n + 1);
    for (int i = 1; i < n; i++)
    {
        cin >> s[i] >> t[i];
        ll k = a[i] / s[i];
        a[i + 1] += k * t[i];
    }
    cout << a[n] << endl;
}

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

C - Takahashi Gets Lost

代码：

#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>>;

void solve()
{
    int n, m, l;
    cin >> n >> m >> l;
    string s;
    cin >> s;
    vector<string> g(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> g[i];
        g[i] = ' ' + g[i];
    }
    auto bfs = [&](int a, int b) -> bool
    {
        for (auto c : s)
        {
            if (c == 'L')
            {
                b--;
            }
            else if (c == 'R')
            {
                b++;
            }
            else if (c == 'U')
            {
                a--;
            }
            else
            {
                a++;
            }
            if (g[a][b] != '.' || a < 1 || b < 1 || a > n || b > m)
            {
                return false;
            }
        }
        return true;
    };
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (g[i][j] == '.')
            {
                if (bfs(i, j))
                {
                    cnt++;
                }
            }
        }
    }
    cout << cnt << endl;
}

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

D - Only one of two

解题思路：

假设答案为\(x\)。

那么\(x\)内\(a的倍数 + b的倍数 - ab的倍数= k\)。如果\(x\)变大，\(a的倍数 + b的倍数 - ab的倍数 \geq k\)，反之，小于等于。

代码:

#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>>;

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}

void solve()
{
    ll a, b, k;
    cin >> a >> b >> k;
    ll l = -1;
    ll r = 1e18;
    auto check = [&](ll mid)
    {
        ll c1 = mid / a;
        ll c2 = mid / b;
        ll c3 = mid / lcm(a, b);
        return (c1 + c2 - 2 * c3 >= k);
    };
    while (l + 1 < r)
    {
        ll mid = l + r >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    cout << r << endl;
}

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

E - Alternating String

解题思路:

维护区间端点，区间修改，区间查询，可用线段树。

代码:

#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;
bool tr[N * 4];
int lc[N * 4];
int rc[N * 4];
int laz[N * 4];
int n, q;
string s;
void pushup(int u)
{
    lc[u] = lc[u << 1];
    rc[u] = rc[u << 1 | 1];
    if (rc[u << 1] == lc[u << 1 | 1])
    {
        tr[u] = false;
    }
    else
    {
        tr[u] = true;
    }
    if (tr[u << 1] == false || tr[u << 1 | 1] == false)
    {
        tr[u] = false;
    }
}

void pushdown(int u, int l, int r)
{
    if (laz[u])
    {
        lc[u << 1] ^= laz[u];
        rc[u << 1] ^= laz[u];
        lc[u << 1 | 1] ^= laz[u];
        rc[u << 1 | 1] ^= laz[u];
        laz[u << 1] ^= laz[u];
        laz[u << 1 | 1] ^= laz[u];
        laz[u] = 0;
    }
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = true;
        rc[u] = lc[u] = s[l] - '0';
        laz[u] = 0;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int nl, int nr)
{
    if (l >= nl && r <= nr)
    {
        lc[u] ^= 1;
        rc[u] ^= 1;
        laz[u] ^= 1;
        return;
    }
    pushdown(u, l, r);
    int mid = l + r >> 1;
    if (nl <= mid)
    {
        modify(u << 1, l, mid, nl, nr);
    }
    if (nr > mid)
    {
        modify(u << 1 | 1, mid + 1, r, nl, nr);
    }
    pushup(u);
}

array<int, 3> query(int u, int l, int r, int nl, int nr)
{
    if (l >= nl && r <= nr)
    {
        return {lc[u], rc[u], tr[u]};
    }
    pushdown(u, l, r);
    int mid = l + r >> 1;
    if (nr <= mid)
    {
        return query(u << 1, l, mid, nl, nr);
    }
    if (nl > mid)
    {
        return query(u << 1 | 1, mid + 1, r, nl, nr);
    }
    auto lson = query(u << 1, l, mid, nl, nr);
    auto rson = query(u << 1 | 1, mid + 1, r, nl, nr);
    array<int, 3> res;
    if (lson[1] == rson[0])
    {
        res[2] = false;
    }
    else
    {
        res[2] = true;
    }
    if (lson[2] == 0 || rson[2] == 0)
    {
        res[2] = false;
    }
    res[0] = lson[0];
    res[1] = rson[1];
    return res;
}



void solve()
{

    cin >> n >> q;
    cin >> s;
    s = ' ' + s;
    build(1, 1, n);
    while (q--)
    {
        int c, l, r;
        cin >> c >> l >> r;
        if (c == 1)
        {
            modify(1, 1, n, l, r);
        }
        else
        {
            auto res = query(1, 1, n, l, r);
            if (res[2] == 0)
            {
                puts("No");
            }
            else
            {
                puts("Yes");
            }
        }
    }
}

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

F - Breakdown

解题思路:

棋子只能从大权值点走向小权值点，所以图是\(DAG\)。

\(dp[u][w]:点u周围结点权值和为w时，1个棋子的最大操作步数。\)

\(f[u]:点u一个棋子的最大操作步数。\)

对结点按权值升序排序。从小权值结点开始计算\(1\)个棋子的最大步数。对每个结点做一次\(01\)背包。

代码:

#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 inf = 1 << 30;
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> e(n + 1, vector<int>());
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    vector<int> a(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        a[i] = i;
    }
    auto cmp = [&](int x, int y) -> bool
    {
        return w[x] < w[y];
    };
    sort(a.begin() + 1, a.end(), cmp);
    vector<vector<ll>> dp(n + 1, vector<ll>(5010, 1));
    vector<ll> f(n + 1, 1);
    for (int i = 1; i <= n; i++)
    {
        int u = a[i];
        for (auto v : e[u])
        {
            if (w[v] >= w[u])
            {
                continue;
            }
            for (int j = w[u] - 1; j >= 0; j--)
            {
                if (w[v] <= j)
                {
                    dp[u][j] = max(dp[u][j], dp[u][j - w[v]] + f[v]);
                    f[u] = max(f[u], dp[u][j]);
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        ans += f[i] * x;
    }
    cout << ans << endl;
}

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

G - Highest Ratio

解题思路:

\(pre_i:前缀和数组。\)

\[\frac{pre_r - pre_{k - 1}}{r - k + 1} \]

我们将数组倒序，方便维护。

\[\frac{pre_i - pre_{j}}{i - j},(i > j) \]

将\((i,pre_i)\)看作二维坐标上的一个点，不难发现我们要求最大斜率。

\(i和pre_i都是升序\)，比较板子的斜率优化\(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>>;

void solve()
{
    int n;
    cin >> n;
    vector<double> a(n + 1);
    for (int i = n; i; i--)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        a[i] += a[i - 1];
    }
    vector<int> q(n + 10);
    int hh = 0;
    int tt = 0;
    q[0] = 0;
    vector<double> ans;
    for (int i = 1; i <= n; i++)
    {
        while (hh < tt && (a[i] - a[q[tt]]) * (i - q[tt - 1]) <= (a[i] - a[q[tt - 1]]) * (i - q[tt]))
        {
            tt--;
        }
        int j = q[tt];
        ans.push_back((a[i] - a[j]) / (i - j));
        q[++tt] = i;
    }
    reverse(ans.begin(), ans.end());
    for (auto x : ans)
    {
        printf("%.10lf\n", x);
    }
}

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

标签：AtCoder,return,Beginner,Contest,int,ll,long,using,define
From： https://www.cnblogs.com/value0/p/18024280

相关文章

  • AtCoder Beginner Contest 339
    B-Langton'sTakahashi难度:⭐⭐题目大意给定一个n*m的网格,并且每一行和每一列都是首尾相连的,每行的最后一个格子再往右就是这行的第一个格子,第一个格子向左就是最后一个格子;列也同理;默认每个格子初始为白色;小莫位于(1,1),方向朝上;当小莫位于某个格子......
  • USACO 2024 February Contest, Bronze Problem 1. Palindrome Game
    1.猜结论2.证明如果\(s<=9\)则\(Bessie\)必赢。如果\(s=10\)则\(Elsie\)必赢。如果\(10<s<=19\)则\(Bessie\)可以减去\(s-10\)，使自己必赢。如果\(s=20\)则\(Bessie\)无论如何减去一个回文数都会离\(10\)差一个个位数，\(Elsie\)减去这个个位......
  • CF1295F - Good Contest
    题意：\(a_i\)​是在\([l_i​,r_i]\)上均匀随机分布的整数，求\(a_{1\dotsn}\)​单调不增的概率。对\(998244353\)取模。\(2\len\le50,0\lel_i\ler_i\le998244351\)。首先可以把概率转化为总方案数在除以\(\prodr_i-l_i+1\)，考虑出朴素的dp，设\(f_{i,j}\)为$选......
  • [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......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99