首页 > 其他分享 >KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340）

KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340）

时间：2024-02-14 19:34:27浏览次数：31  
标签：AtCoder Beginner CONTEST int ll -- while using top

KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340）

A - Arithmetic Progression

代码:

#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>>;
map<int, ll> q;

void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    while (a <= b)
    {
        cout << a << ' ';
        a += c;
    }
}

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

    return 0;
}

B - Append

代码：

#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>>;
map<int, ll> q;

void solve()
{
    int n;
    vector<int> v;
    cin >> n;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        if (a == 1)
        {
            v.push_back(b);
        }
        else
        {
            int m = v.size();
            cout << v[m - b] << endl;
        }
    }
}

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

    return 0;
}

C - Divide and Divide

解题思路:

可记忆化搜索。

除了最后一层得到\(1\)的拆分可能会有不同，前面的拆分层数都是一样的，花费总和也都是\(x\)。

最后\(x\)一定会全部拆分成\(1\)，所以，我们可以先算出倒数第二层总共会有多少个数字，此时数字不是\(1\)就是\(2\)。

然后二分得出有多少个\(2\)，这些就是最后一层的偏差，加上即可。

代码:

#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 x;
    cin >> x;
    ll ans = 0;
    int cnt = 0;
    ll l = 0;
    ll r = 0;
    ll t = x;
    while (t >= 2)
    {
        l++;
        t /= 2;
    }
    t = x;
    while (t >= 2)
    {
        r++;
        t = (t + 1) / 2;
    }
    ans = x * l;
    ll s = 1ll << l;
    l = -1;
    r = s + 1;
    while (l + 1 < r)
    {
        ll mid = l + r >> 1;
        if (mid + 2 * (s - mid) < x)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    cout << 2 * (s - l) + ans << endl;
}

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

    return 0;
}

D - Super Takahashi Bros.

解题思路:

有环，不好\(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;
const ll inf = 1ll << 60;
int e[N * 2];
int ne[N * 2];
int h[N];
ll w[N];
int idx;
ll dist[N];
bool vis[N];
int n;
void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

void dij()
{
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({dist[1], 1});
    dist[1] = 0;
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        auto u = t.se;
        vis[u] = false;
        for (int j = h[u]; ~j; j = ne[j])
        {
            int v = e[j];
            if (dist[v] > dist[u] + w[j])
            {
                dist[v] = dist[u] + w[j];
                if (!vis[v])
                {
                    q.push({dist[v], v});
                }
            }
        }
    }
}

void solve()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(i, i + 1, a);
        add(i, c, b);
        dist[i] = inf;
    }
    dist[n] = inf;
    dij();
    cout << dist[n] << endl;
}

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

    return 0;
}

E - Mancala 2

解题思路:

单点查询\(+\)区间修改\(\to\)线段树可做。

修改区间讨论下即可。

代码:

#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 t[N * 8];
ll laz[N * 8];
int n, m;

void pushup(int u)
{
    t[u] = t[u << 1] + t[u << 1 | 1];
}

void pushdown(int u)
{
    if (laz[u])
    {
        t[u << 1] += laz[u];
        t[u << 1 | 1] += laz[u];
        laz[u << 1] += laz[u];
        laz[u << 1 | 1] += laz[u];
        laz[u] = 0;
    }
}

void insert(int u, int l, int r, int nl, int nr, ll val)
{
    if (l >= nl && r <= nr)
    {
        t[u] += val;
        laz[u] += val;
        return;
    }
    pushdown(u);
    int mid = l + r >> 1;
    if (nl <= mid)
    {
        insert(u << 1, l, mid, nl, nr, val);
    }
    if (nr > mid)
    {
        insert(u << 1 | 1, mid + 1, r, nl, nr, val);
    }
    pushup(u);
}

ll query(int u, int l, int r, int v)
{

    if (l == r)
    {
        return t[u];
    }
    pushdown(u);
    int mid = l + r >> 1;
    if (v <= mid)
    {
        return query(u << 1, l, mid, v);
    }
    return query(u << 1 | 1, mid + 1, r, v);
}

void print()
{
    for (int i = 0; i < n; i++)
    {
        cout << query(1, 0, n, i) << ' ';
    }
    cout << endl;
}

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        ll x;
        cin >> x;
        insert(1, 0, n, i, i, x);
    }

    while (m--)
    {
        int b;
        cin >> b;
        ll res = query(1, 0, n, b);
        insert(1, 0, n, b, b, -res);
        ll a = res / n;
        ll c = res % n;
        if (c != 0)
        {
            ll lr = n - 1 - (b + 1) + 1;
            if (c > lr)
            {
                insert(1, 0, n, b + 1, n - 1, 1);
                insert(1, 0, n, 0, c - lr - 1, 1);
            }
            else
            {
                insert(1, 0, n, b + 1, b + 1 + c - 1, 1);
            }
        }
        insert(1, 0, n, 0, n - 1, a);
    }
    print();
}

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

    return 0;
}

F - S = 1

解题思路:

首先根据叉乘可得出\(|xy - ab | = 2\)。

扩展欧几里得可求不定方程的一组可行解。

代码:

#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 exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

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

void solve()
{
    ll a, b;
    cin >> a >> b;
    ll g = gcd(a, b);
    g = abs(g);
    if (g > 2)
    {
        puts("-1");
        return;
    }
    ll x = 0;
    ll y = 0;
    exgcd(a, -b, y, x);
    cout << x * 2 / g << ' ' << y * 2 / g << endl;
}

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

    return 0;
}

G - Leaf Color

解题思路:

对于一棵叶子结点都是同一颜色的树，我们发现，只有该颜色的结点和这些结点的公共祖先是构成这样的树的有用元素，所以可以对于每种颜色构建虚树。

\(dp[i]:选择了结点i的方案数。\)

代码：

#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 = 3e5 + 10;
const int mod = 998244353;
vector<int> e[N];
vector<int> adj[N];
int s[N];
int top;
int dfn[N];
int idx;
int n, q;
int dep[N];
int fa[N][22];
int k;
bool vis[N];
int c[N];
ll ans = 0;
ll f[N];
vector<int> color[N];

void dfs(int u, int par)
{
    fa[u][0] = par;
    dfn[u] = ++idx;
    for (auto v : e[u])
    {
        if (v == par)
        {
            continue;
        }
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

int lca(int a, int b)
{
    if (dep[a] < dep[b])
    {
        swap(a, b);
    }
    for (int i = 20; i >= 0; i--)
    {
        if (dep[fa[a][i]] >= dep[b])
        {
            a = fa[a][i];
        }
    }
    if (a == b)
    {
        return a;
    }
    for (int i = 20; i >= 0; i--)
    {
        if (fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}

bool cmp(int a, int b)
{
    return dfn[a] < dfn[b];
}

void build(vector<int> a)
{
    sort(a.begin(), a.end(), cmp);
    top = 0;
    s[++top] = 1;
    if (a[0] != 1)
    {
        s[++top] = a[0];
    }
    for (int i = 1; i < a.size(); i++)
    {
        int l = lca(s[top], a[i]);
        while (top > 1 && dep[s[top - 1]] >= dep[l])
        {
            adj[s[top - 1]].push_back(s[top]);
            top--;
        }
        if (s[top] != l)
        {
            adj[l].push_back(s[top]);
            s[top] = l;
        }
        s[++top] = a[i];
    }
    while (top)
    {
        adj[s[top - 1]].push_back(s[top]);
        top--;
    }
}

void dp(int u, int col)
{
    f[u] = 1;
    for (auto v : adj[u])
    {
        dp(v, col);
        // 这里计算全集，子树可选(f[v))，可不选(+ 1)
        f[u] = f[u] * (f[v] + 1) % mod;
    }
    ll cur = f[u];
    if (c[u] != col)
    {
        cur--;
        // 不能一个子节点都不选。
        f[u]--;
        // 对于以u为最终根节点的情况来说，不能只选择一棵子树。
        for (auto v : adj[u])
        {
            cur = ((cur - f[v]) % mod + mod) % mod;
        }
    }
    ans = ((ans + cur) % mod + mod) % mod;
    adj[u].clear();
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &c[i]);
        color[c[i]].push_back(i);
    }
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        scanf("%d %d", &a, &b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dep[1] = 1;
    dfs(1, 0);
    for (int j = 1; j <= 20; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if ((int)color[i].size() == 0)
        {
            continue;
        }
        build(color[i]);
        dp(1, i);
    }
    printf("%lld\n", ans);
}

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

    return 0;
}

标签：AtCoder,Beginner,CONTEST,int,ll,--,while,using,top
From： https://www.cnblogs.com/value0/p/18015510

相关文章

  • 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\)......
  • Atcoder Educational DP Contest 题解
    比赛链接：Atcoderr或者题单A：Frog1常规线性dp，注意到对于每个落点来说，青蛙只能由第\(i-1\)个石头或者第\(i-2\)个石头转移得到，那么我们让\(dp[i]\)为当跳到第\(i\)个石头上的最小费用。此时显然有：\[dp_i=\min(dp_{i-1}+\left|h_i-h_{i-1}\right|,dp_{i-2}+\left|h_......
  • AtCoder-abc340_f题解
    题意简述给定整数\(x,y\)，询问是否存在整数\(a,b\)，满足：\(-10^{18}\lea,b\le10^{18}\)。由\((0,0),(x,y),(a,b)\)三点构成的三角形面积为\(1\)。如果存在，输出任意一组；否则输出-1。思路先假设\(x,y,a,b\)都是正数。那么图大概是这样：此时红色三角形的面积就......
  • AtCoder Beginner Contest 340
    A-ArithmeticProgression(abc340A)题目大意给定等差数列的首项、末项、公差。输出这个等差数列。解题思路从首相依次累加公差到末项即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_std......
  • The 18th Heilongjiang Provincial Collegiate Programming Contest
    A.MagicComputer看题目猜规律#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingvi=vector<int>;usingi32=int32_t;constintmod=998244353;intpower(intx,inty){intans=1;while(y){if(y&......
  • Atcoder Grand Contest 056 B - Range Argmax
    因为一组\(x\)可能对应多组\(p\)，考虑怎么让决策唯一化。我们从大到小依次钦定每个值的位置，即倒着遍历\(i=n,n-1,\cdots,1\)，找到最左端的位置\(v\)满足，对于现在还活着的所有区间\(j\)满足\(l_j\lev\ler_j\)，都有\(x_j=v\)，令\(p_j=i\)，然后删去所有包含\(i\)的区间。......
  • Atcoder Grand Contest 041 F - Histogram Rooks
    考虑容斥。我们钦定一些格子组成的集合不能被覆盖，设为\(A\)。把与\(A\)中的点同行同列的点抠掉，剩余的点则是可放可不放的，总方案数就是\(2^{\text{剩余点的个数}}\)，乘以\((-1)^{|A|}\)并求和即可。这个做法直接优化显然不行。我们考虑设\(A\)中的点所在的列组成的不可重集......
  • AtCoder ABC 263 D 题解
    AtCoderABC263D题解前言本蒟蒻的第一篇题解，大佬勿喷QwQ传送门们洛谷传送门AtCoder传送门正文设有\(x\)使得\(x\leqk\)时，令\(f(k)\)为对\(A'\)进行运算后\(A'=(A_1,A_2,\ldots,A_k)\)的最小和。同理，对于\(y\)使得\(y\leqk\)时，令\(g(k)\)为对\(A......
  • AtCoder Beginner Contest 339 A-G
    A模拟即可voidsolve(){strings;cin>>s;for(inti=s.size()-1;i>=0;i--)if(s[i]=='.'){cout<<s.substr(i+1)<<endl;return;}}B模拟，可以让下标从0开始，这样......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99