AtCoder Beginner Contest 318

A - Full Moon

Problem Statement

Takahashi likes full moons.

Let today be day \(1\). The first day on or after today on which he can see a full moon is day \(M\). After that, he can see a full moon every \(P\) days, that is, on day \(M+P\), day \(M+2P\), and so on.

Find the number of days between day \(1\) and day \(N\), inclusive, on which he can see a full moon.

Constraints

• \(1\leq N\leq 2\times 10^5\)
• \(1\leq M \leq P \leq 2\times 10^5\)
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M P

Output

Print the answer as an integer.

Solution

模拟即可

//
// Created by blackbird on 2023/9/2.
//
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N = 2e6 + 10;
int n, m, p;

void solve() {
    cin >> n >> m >> p;
    if (m > n) {
        cout << "0\n";
        return;
    }
    int ans = 1;
    while (m + p <= n) {
        m += p;
        ans++;
    }
    cout << ans << "\n";
}

signed main() {
    //cin.tie(nullptr)->sync_with_stdio(false); srand(time(0));
    int T = 1; //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

B - Overlapping sheets

Problem Statement

There are \(N\) rectangular sheets spread out on a coordinate plane.

Each side of the rectangular region covered by each sheet is parallel to the \(x\)- or \(y\)-axis.
Specifically, the \(i\)-th sheet covers exactly the region satisfying \(A_i \leq x\leq B_i\) and \(C_i \leq y\leq D_i\).

Let \(S\) be the area of the region covered by one or more sheets. It can be proved that \(S\) is an integer under the constraints.
Print \(S\) as an integer.

Constraints

• \(2\leq N\leq 100\)
• \(0\leq A_i\lt B_i\leq 100\)
• \(0\leq C_i\lt D_i\leq 100\)
• All input values are integers.

Input

The input is given from Standard Input in the following format:

\(N\)
\(A_1\) \(B_1\) \(C_1\) \(D_1\)
\(A_2\) \(B_2\) \(C_2\) \(D_2\)
\(\vdots\)
\(A_N\) \(B_N\) \(C_N\) \(D_N\)

Output

Print the area \(S\) of the region covered by one or more sheets as an integer.

Solution

模拟即可

//
// Created by blackbird on 2023/9/2.
//
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N = 2e6 + 10;
int n, vis[110][110];

void solve() {
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        b--; d--;
        for (int x = a; x <= b; x++) {
            for (int y = c; y <= d; y++) {
                if (!vis[x][y]) ans++;
                vis[x][y] = 1;
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    //cin.tie(nullptr)->sync_with_stdio(false); srand(time(0));
    int T = 1; //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C - Blue Spring

Problem Statement

Takahashi is planning an \(N\)-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for \(1\leq i\leq N\), the regular fare for the \(i\)-th day of the trip is \(F_i\) yen.
On the other hand, a batch of \(D\) one-day passes is sold for \(P\) yen. You can buy as many passes as you want, but only in units of \(D\).
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the \(N\)-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• \(1\leq N\leq 2\times 10^5\)
• \(1\leq D\leq 2\times 10^5\)
• \(1\leq P\leq 10^9\)
• \(1\leq F_i\leq 10^9\)
• All input values are integers.

Input

The input is given from Standard Input in the following format:

\(N\) \(D\) \(P\)
\(F_1\) \(F_2\) \(\ldots\) \(F_N\)

Output

Print the minimum possible total cost for the \(N\)-day trip.

Solution

将 \(n\) 补全至 \(D\) 的整数倍，贪心即可

//
// Created by blackbird on 2023/9/2.
//
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N = 2e6 + 10;
int n, d, p, a[N], s[N];

void solve() {
    cin >> n >> d >> p;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n, greater());
    if (n % d != 0) n += d - n % d;
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    int ans = 0;
    for (int i = d; i <= n; i += d) {
        ans += min(s[i] - s[i - d], p);
    }
    cout << ans << "\n";
}

signed main() {
    //cin.tie(nullptr)->sync_with_stdio(false); srand(time(0));
    int T = 1; //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

D - General Weighted Max Matching

Problem Statement

You are given a weighted undirected complete graph with \(N\) vertices numbered from \(1\) to \(N\). The edge connecting vertices \(i\) and \(j\) \((i< j)\) has a weight of \(D_{i,j}\).

When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.

• The endpoints of the chosen edges are pairwise distinct.

Constraints

• \(2\leq N\leq 16\)
• \(1\leq D_{i,j} \leq 10^9\)
• All input values are integers.

Input

The input is given from Standard Input in the following format:

\(N\)
\(D_{1,2}\) \(D_{1,3}\) \(\ldots\) \(D_{1,N}\)
\(D_{2,3}\) \(\ldots\) \(D_{2,N}\)
\(\vdots\)
\(D_{N-1,N}\)

Output

Print the answer as an integer.

Solution

见 【模板】一般图最大权匹配

#include<bits/stdc++.h>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn = 620; //内存开点数的1.5倍
const int inf = 0x3f3f3f3f;
struct node {
    int x, y, z;
    node() {}
    node(int a, int b, int c) {
        x = a, y = b, z = c;
    }
} g[maxn][maxn];
int n, m, nx, t, lab[maxn], match[maxn], slack[maxn];
int st[maxn], pa[maxn], flower_from[maxn][maxn], S[maxn], vis[maxn];
vector<int> flower[maxn];
deque<int> q;

int dist(node e) {
    return lab[e.x] + lab[e.y] - g[e.x][e.y].z * 2;
}

void update_slack(int x, int y) {
    if (!slack[y] || dist(g[x][y]) < dist(g[slack[y]][y]))
        slack[y] = x;
}

void set_slack(int y) {
    slack[y] = 0;
    for (int x = 1; x <= n; x++)
        if (g[x][y].z > 0 && st[x] != y && S[st[x]] == 0)
            update_slack(x, y);
}

void q_push(int x) {
    if (x <= n) return q.push_back(x);
    for (int i = 0; i < flower[x].size(); i++) q_push(flower[x][i]);
}

void set_st(int x, int b) {
    st[x] = b;
    if (x <= n) return;
    for (int i = 0; i < flower[x].size(); i++) set_st(flower[x][i], b);
}

int get_pr(int b, int xr) {
    int pr = find(flower[b].begin(), flower[b].end(), xr) - flower[b].begin();
    if (pr % 2 == 1) {
        reverse(flower[b].begin() + 1, flower[b].end());
        return flower[b].size() - pr;
    } else return pr;
}
void set_match(int x, int y) {
    match[x] = g[x][y].y;
    if (x <= n) return;
    node e = g[x][y];
    int xr = flower_from[x][e.x], pr = get_pr(x, xr);
    for (int i = 0; i < pr; i++)
        set_match(flower[x][i], flower[x][i ^ 1]);

    set_match(xr, y);
    rotate(flower[x].begin(), flower[x].begin() + pr, flower[x].end());
}

void augment(int x, int y) {
    int xnv = st[match[x]];
    set_match(x, y);
    if (!xnv) return;
    set_match(xnv, st[pa[xnv]]);
    augment(st[pa[xnv]], xnv);
}
int get_lca(int x, int y) {
    for (++t; x || y; swap(x, y)) {
        if (x == 0) continue;
        if (vis[x] == t) return x;
        vis[x] = t;
        x = st[match[x]];
        if (x) x = st[pa[x]];
    }
    return 0;
}
void add_blossom(int x, int lca, int y) {
    int b = n + 1;
    while (b <= nx && st[b]) b++;
    if (b > nx) nx++;
    lab[b] = 0, S[b] = 0;
    match[b] = match[lca];
    flower[b].clear();
    flower[b].push_back(lca);

    for (int xx = x, yy; xx != lca; xx = st[pa[yy]])
        flower[b].push_back(xx), flower[b].push_back(yy = st[match[xx]]), q_push(yy);
    reverse(flower[b].begin() + 1, flower[b].end());
    for (int xx = y, yy; xx != lca; xx = st[pa[yy]])
        flower[b].push_back(xx), flower[b].push_back(yy = st[match[xx]]), q_push(yy);

    set_st(b, b);
    for (int xx = 1; xx <= nx; xx++) g[b][xx].z = g[xx][b].z = 0;
    for (int xx = 1; xx <= n; xx++) flower_from[b][xx] = 0;
    for (int i = 0; i < flower[b].size(); i++) {
        int xs = flower[b][i];
        for (int xx = 1; xx <= nx; xx++)
            if (g[b][xx].z == 0 || dist(g[xs][xx]) < dist(g[b][xx]))
                g[b][xx] = g[xs][xx], g[xx][b] = g[xx][xs];
        for (int xx = 1; xx <= n; xx++)
            if (flower_from[xs][xx]) flower_from[b][xx] = xs;
    }
    set_slack(b);
}

void expand_blossom(int b) {
    for (int i = 0; i < flower[b].size(); i++)
        set_st(flower[b][i], flower[b][i]);
    int xr = flower_from[b][g[b][pa[b]].x], pr = get_pr(b, xr);
    for (int i = 0; i < pr; i += 2) {
        int xs = flower[b][i], xns = flower[b][i + 1];
        pa[xs] = g[xns][xs].x;
        S[xs] = 1, S[xns] = 0;
        slack[xs] = 0, set_slack(xns);
        q_push(xns);
    }
    S[xr] = 1, pa[xr] = pa[b];
    for (int i = pr + 1; i < flower[b].size(); i++) {
        int xs = flower[b][i];
        S[xs] = -1, set_slack(xs);
    }
    st[b] = 0;
}
bool on_found_edge(const node &e) {
    int x = st[e.x], y = st[e.y];
    if (S[y] == -1) {
        pa[y] = e.x, S[y] = 1;
        int nu = st[match[y]];
        slack[y] = slack[nu] = 0;
        S[nu] = 0, q_push(nu);
    } else if (S[y] == 0) {
        int lca = get_lca(x, y);
        if (!lca) return augment(x, y), augment(y, x), true;
        else add_blossom(x, lca, y);
    }
    return false;
}
bool matching(void) {
    memset(S, -1, sizeof(S));
    memset(slack, 0, sizeof(slack));
    q.clear();
    for (int x = 1; x <= nx; x++)
        if (st[x] == x && !match[x]) pa[x] = 0, S[x] = 0, q_push(x);
    if (q.empty()) return false;

    while (1) {
        while (q.size()) {
            int x = q.front();
            q.pop_front();
            if (S[st[x]] == 1) continue;
            for (int y = 1; y <= n; y++)
                if (g[x][y].z > 0 && st[x] != st[y]) {
                    if (dist(g[x][y]) == 0) {
                        if (on_found_edge(g[x][y])) return true;
                    } else update_slack(x, st[y]);
                }
        }
        int d = inf;
        for (int b = n + 1; b <= nx; b++)
            if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2);
        for (int x = 1; x <= nx; x++)
            if (st[x] == x && slack[x]) {
                if (S[x] == -1) d = min(d, dist(g[slack[x]][x]));
                else if (S[x] == 0) d = min(d, dist(g[slack[x]][x]) / 2);
            }
        for (int x = 1; x <= n; x++) {
            if (S[st[x]] == 0) {
                if (lab[x] <= d) return false;
                lab[x] -= d;
            } else if (S[st[x]] == 1) lab[x] += d;
        }
        for (int b = n + 1; b <= nx; b++)
            if (st[b] == b) {
                if (S[st[b]] == 0) lab[b] += d * 2;
                else if (S[st[b]] == 1) lab[b] -= d * 2;
            }
        q.clear();
        for (int x = 1; x <= nx; x++)
            if (st[x] == x && slack[x] && st[slack[x]] != x && dist(g[slack[x]][x]) == 0)
                if (on_found_edge(g[slack[x]][x])) return true;
        for (int b = n + 1; b <= nx; b++)
            if (st[b] == b && S[b] == 1 && lab[b] == 0) expand_blossom(b);
    }
    return false;
}
pair<ll, int> weight_blossom(void) {
    memset(match, 0, sizeof(match));
    nx = n;
    int n_matches = 0;
    ll tot_weight = 0;
    for (int x = 0; x <= n; x++)
        st[x] = x, flower[x].clear();
    int w_max = 0;
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++) {
            flower_from[x][y] = (x == y ? x : 0);
            w_max = max(w_max, g[x][y].z);
        }
    for (int x = 1; x <= n; x++) lab[x] = w_max;

    while (matching()) ++n_matches;
    for (int x = 1; x <= n; x++)
        if (match[x] && match[x] < x)
            tot_weight += (ll) g[x][match[x]].z;
    return make_pair(tot_weight, n_matches);
}
int main() {
    scanf("%d", &n);
    m = n * (n - 1) / 2;
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++)
            g[x][y] = node(x, y, 0);
    for (int x = 1; x <= n; x++) {
        for (int y = x + 1; y <= n; y++) {
            int z;
            cin >> z;
            g[x][y].z = g[y][x].z = z;
        }
    }
    printf("%lld\n", weight_blossom().first);
    return 0;
}

E - Sandwiches

Problem Statement

You are given a sequence of positive integers of length \(N\): \(A=(A_1,A_2,\ldots,A_N)\). Find the number of triples of positive integers \((i,j,k)\) that satisfy all of the following conditions:

• \(1\leq i \lt j \lt k\leq N\),
• \(A_i = A_k\),
• \(A_i \neq A_j\).

Constraints

• \(3\leq N\leq 3\times 10^5\)
• \(1\leq A_i \leq N\)
• All input values are integers.

Solution

记录每一个数前面出现的次数以及下标和，稍加计算即可。

//
// Created by blackbird on 2023/9/2.
//
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N = 2e6 + 10;
int n, a[N], cnt[N], sum[N];

void solve() {
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (cnt[a[i]] != 0) {
            ans += i * cnt[a[i]] - sum[a[i]] - (cnt[a[i]] - 1) * cnt[a[i]] / 2 - cnt[a[i]];
        }
        cnt[a[i]]++;
        sum[a[i]] += i;
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false); srand(time(0));
    int T = 1; //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F - Octopus

Problem Statement

There is an octopus-shaped robot and \(N\) treasures on a number line. The \(i\)-th treasure \((1\leq i\leq N)\) is located at coordinate \(X_i\).
The robot has one head and \(N\) legs, and the \(i\)-th leg \((1\leq i\leq N)\) has a length of \(L_i\).

Find the number of integers \(k\) such that the robot can grab all \(N\) treasures as follows.

• Place the head at coordinate \(k\).
• Repeat the following for \(i=1,2,\ldots,N\) in this order: if there is a treasure that has not been grabbed yet within a distance of \(L_i\) from the head, that is, at a coordinate \(x\) satisfying \(k-L_i\leq x\leq k+L_i\), choose one such treasure and grab it.

Constraints

• \(1 \leq N\leq 200\)
• \(-10^{18} \leq X_1\lt X_2 \lt \cdots \lt X_N\leq 10^{18}\)
• \(1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}\)
• All input values are integers.

Input

The input is given from Standard Input in the following format:

\(N\)
\(X_1\) \(X_2\) \(\ldots\) \(X_N\)
\(L_1\) \(L_2\) \(\ldots\) \(L_N\)

Output

Print the number of integers \(k\) that satisfy the condition in the statement.

Solution

待填

G - Typical Path Problem

Problem Statement

You are given a simple connected undirected graph \(G\) with \(N\) vertices and \(M\) edges.
The vertices and edges of \(G\) are numbered as vertex \(1\), vertex \(2\), \(\ldots\), vertex \(N\), and edge \(1\), edge \(2\), \(\ldots\), edge \(M\), respectively, and edge \(i\) \((1\leq i\leq M)\) connects vertices \(U_i\) and \(V_i\).

You are also given distinct vertices \(A,B,C\) on \(G\). Determine if there is a simple path connecting vertices \(A\) and \(C\) via vertex \(B\).

Constraints

• \(3 \leq N \leq 2\times 10^5\)
• \(N-1\leq M\leq\min\left(\frac{N(N-1)}{2},2\times 10^5\right)\)
• \(1\leq A,B,C\leq N\)
• \(A\), \(B\), and \(C\) are all distinct.
• \(1\leq U_i\lt V_i\leq N\)
• The pairs \((U_i,V_i)\) are all distinct.
• All input values are integers.

Solution

建立圆方树，则 \(b\) 在 \(a\) 和 \(c\) 的树上路径，或者树上路径的方点与 \(b\) 相连时，满足条件。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10;

int n, tot, m;
int a, b, c;
vector<int> g[N], G[N];
int dfn[N], low[N], idx;
stack<int> s;

void yfs(int u, int fa) {
    dfn[u] = low[u] = ++idx; s.push(u);
    for (auto v : g[u]) {
        if (v == fa) continue;
        if (!dfn[v]) {
            yfs(v, u);
            low[u] = min(low[u], low[v]);
            if (dfn[u] <= low[v]) {
                tot++;
                int x;
                do {
                    x = s.top(); s.pop();
                    G[x].push_back(tot); G[tot].push_back(x);
                } while (x != v);
                G[u].push_back(tot); G[tot].push_back(u);
            }
        } else low[u] = min(low[u], dfn[v]);
    }
}

int dep[N];
int f[N][22], fa[N];
void dfs(int u, int pre) {
    f[u][0] = fa[u] = pre;
    dep[u] = dep[pre] + 1;
    for (int i = 1; i <= 21; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for (auto v : G[u]) {
        if (v == pre) continue;
        dfs(v, u);
    }
}

vector<int> getpath(int x, int y) {
    vector<int> path, tmp;
    while (dep[x] > dep[y]) path.push_back(x), x = fa[x];
    while (dep[y] > dep[x]) tmp.push_back(y), y = fa[y];
    while (x != y) {
        path.push_back(x),x = fa[x];
        tmp.push_back(y),y = fa[y];
    }
    path.push_back(x);
    while (!tmp.empty()) path.push_back(tmp.back()), tmp.pop_back();
    return path;
}

//int lca(int x, int y) {
//    if (dep[x] < dep[y]) swap(x, y);
//    int k = dep[x] - dep[y];
//    for (int i = 0; i <= 21; i++) {
//        if (k >> i & 1) x = f[x][i];
//    }
//    if (x == y) return x;
//    for (int i = 21; i >= 0; i--) {
//        if (f[x][i] != f[y][i]) {
//            x = f[x][i];
//            y = f[y][i];
//        }
//    }
//    return f[x][0];
//}

void solve() {
    cin >> n >> m >> a >> b >> c;
    tot = n;idx = 0;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    yfs(1, 0);
    dfs(1, 0);

    vector<int> path = getpath(a, c);

    int ok = 0;
    for (auto u : path) {
        if (u == b) ok = 1;
        if (u > n) {
            for (auto v : G[u]) {
                if (v == b) ok = 1;
            }
        }
    }
    if (ok) cout << "Yes\n";
    else cout << "No\n";
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1; //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}