Daiwa Securities Co. Ltd. Programming Contest 2023（AtCoder Beginner Contest 331）

A - Tomorrow

解题思路:

模拟。

代码:

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

ll f(ll a, ll b)
{
    if (b < a)
    {
        return b;
    }
    return f(a, b / a) + (b % a);
}

void solve()
{
    int M, D;
    cin >> M >> D;
    int y, m, d;
    cin >> y >> m >> d;
    d++;
    if (d >= D)
    {
        d = 1;
        m++;
        if (m >= M)
        {
            m = 1;
            y++;
        }
    }
    cout << y << ' ' << m << ' ' << d << endl;
}

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

B - Buy One Carton of Milk

解题思路:

n很小，直接枚举所有情况。

代码:

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

ll f(ll a, ll b)
{
    if (b < a)
    {
        return b;
    }
    return f(a, b / a) + (b % a);
}

void solve()
{
    int n;
    cin >> n;
    int s, m, l;
    cin >> s >> m >> l;
    ll ans = 1e9 + 10;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int k = 0; k <= n; k++)
            {
                if (i * 6 + j * 8 + k * 12 >= n)
                {
                    ans = min(ans, (ll)i * s + j * m + k * l);
                }
            }
        }
    }
    cout << ans << endl;
}

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

C - Sum of Numbers Greater Than Me

解题思路:

排序，前缀和，二分。

代码:

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

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b.begin() + 1, b.end());
    vector<ll> s(n + 1);
    for (int i = 1; i <= n; i++)
    {
        s[i] = s[i - 1] + b[i];
    }
    for (int i = 1; i <= n; i++)
    {
        auto idx = upper_bound(b.begin() + 1, b.end(), a[i]) - b.begin();
        cout << s[n] - s[idx - 1] << ' ';
    }
    cout << endl;
}

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

D - Tile Pattern

解题思路:

二维前缀和。

我们将\((a,b,c,d)\)进行拆分，拆成二维前缀和,\((a,b,c,d)=(1,1,c,d)-(1,1,c,b - 1)-(1,1,a - 1,d)+(1,1,a- 1,b- 1)\)。

计算每个以\((1,1)\)为左上角的矩形块，按上式计算即可。

如何计算一个矩形块？

如上图所示，

蓝色区域块为\(g[n][n] * (\frac{a}{n} * \frac{b}{n})\)。
绿色为\(g[n][a \% n] \times \frac{b}{n} + g[b \%n][n] \times \frac{a}{n}\)
黑色区域为\(g[b \%n][a\%n]\)。

代码:

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

void solve()
{
    ll n, q;
    cin >> n >> q;
    vector<vector<ll>> g(n + 10, vector<ll>(n + 10, 0));
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        s = ' ' + s;
        for (int j = 1; j <= n; j++)
        {
            if (s[j] == 'B')
            {
                g[i][j] = 1;
            }
            g[i][j] = g[i][j] + g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
        }
    }
    auto f = [&](ll a, ll b) -> ll
    {
        ll res = (a / n) * (b / n) * (ll)g[n][n];
        res += g[n][b % n] * (ll)(a / n);
        res += g[a % n][n] * (ll)(b / n);
        res += g[a % n][b % n];
        return res;
    };
    while (q--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a++;
        b++;
        c++;
        d++;
        cout << f(c, d) - f(a - 1, d) - f(c, b - 1) + f(a - 1, b - 1) << endl;
    }
}

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

E - Set Meal

解题思路:

如果我们直接遍历两两配对，一定会超时。

我们先对\(a,b\)数组升序排序。

如图：

首先，最大价钱的配对一定是右下角，就是\(a,b\)都取最大值相加。

通过简单画图可以发现，每个格子右下区域块一定都比当前区域要大。也就是说，最优解的右下区域块一定全部都是不可选块。

由此，我们可以遍历每个不可选块，比较他们的上面一块和左边一块，最优解一定在其中。

代码:

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

void solve()
{
    int n, m, l;
    cin >> n >> m >> l;
    vector<int> a(n + 1), b(m + 1);
    vector<pii> da(n + 1), db(m + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        da[i] = {a[i], i};
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        db[i] = {b[i], i};
    }
    sort(da.begin() + 1, da.end());
    sort(db.begin() + 1, db.end());
    set<pii> s;
    for (int i = 1; i <= l; i++)
    {
        int x, y;
        cin >> x >> y;
        s.insert({x, y});
    }
    ll ans = 0;
    if (s.find({da[n].se, db[m].se}) == s.end())
    {
        cout << da[n].fi + db[m].fi << endl;
        return;
    }
    for (auto t : s)
    {
        auto pa = lower_bound(da.begin() + 1, da.end(), (pii){a[t.fi], t.fi}) - da.begin();
        auto pb = lower_bound(db.begin() + 1, db.end(), (pii){b[t.se], t.se}) - db.begin();
        // cout << pa << ' ' << pb << endl;
        if (pa > 1 && s.find({da[pa - 1].se, t.se}) == s.end())
        {
            ans = max(ans, da[pa - 1].fi + b[t.se]);
        }
        if (pb > 1 && s.find({t.fi, db[pb - 1].se}) == s.end())
        {
            ans = max(ans, a[t.fi] + db[pb - 1].fi);
        }
    }
    cout << ans << endl;
}

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

    return 0;
}

F - Palindrome Query

解题思路:

线段树维护字符串前后哈希值。

结点元素有：区间左右端点，区间前缀哈希值\(pre\)，区间后缀哈希值\(suf\)。

\(pushup\):

\[l.len = l.r - l.l + 1\\ r.len = r.r - r.l + 1\\tr[u].pre = l.pre \times hash[r.len] + r.pre,\\ tr[u].suf = r.suf \times hash[l.len] + l.suf. \]

修改操作：就是单点修改。

查询操作：返回间前缀哈希值\(pre\)，区间后缀哈希值\(suf\)，合并过程中需要求取子区间长度，为了过程计算也要返回。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;
ull h[N];
int n, q;
string s;

struct node
{
    ll l, r;
    ull pre, suf;
} tr[4 * N];

void pushup(int u)
{
    int mid = (tr[u].r - tr[u].l) >> 1;
    int len1 = tr[u << 1].r - tr[u << 1].l + 1;
    int len2 = tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1;
    tr[u].pre = tr[u << 1].pre * h[len2] + tr[u << 1 | 1].pre;
    tr[u].suf = tr[u << 1 | 1].suf * h[len1] + tr[u << 1].suf;
}

void build(int u, int l, int r)
{
    tr[u].l = l;
    tr[u].r = r;
    if (l == r)
    {
        tr[u] = {l, r, s[l], s[l]};
        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 idx, char c)
{
    if (tr[u].l == tr[u].r)
    {
        tr[u].pre = tr[u].suf = c;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (idx <= mid)
    {
        modify(u << 1, idx, c);
    }
    else
    {
        modify(u << 1 | 1, idx, c);
    }
    pushup(u);
}

array<ull, 3> query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        int len = tr[u].r - tr[u].l + 1;
        return {tr[u].pre, tr[u].suf, len};
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid)
    {
        return query(u << 1, l, r);
    }
    if (l > mid)
    {
        return query(u << 1 | 1, l, r);
    }
    auto lv = query(u << 1, l, r);
    auto rv = query(u << 1 | 1, l, r);
    array<ull, 3> res;
    res[0] = lv[0] * h[rv[2]] + rv[0];
    res[1] = rv[1] * h[lv[2]] + lv[1];
    res[2] = lv[2] + rv[2];
    return res;
}

void solve()
{
    cin >> n >> q >> s;
    s = ' ' + s;
    h[0] = 1;
    for (int i = 1; i < N; i++)
    {
        h[i] = h[i - 1] * base;
    }
    build(1, 1, n);
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int idx = 0;
            char str[2];
            cin >> idx >> str;
            modify(1, idx, *str);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            array<ull, 3> t = query(1, l, r);
            // cout << t[0] << ' ' << t[1] << endl;
            if (t[0] == t[1])
            {
                puts("Yes");
            }
            else
            {
                puts("No");
            }
        }
    }
}

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

    return 0;
}

contest programming securities beginner

contest programming beginner atcoder

contest programming beginner registry

contest programming beginner keyence

contest programming beginner systems

beginner atcoder contest 296

beginner atcoder contest 295

beginner atcoder contest abcde

beginner atcoder contest 335

beginner atcoder contest 334