如何 AK ABC252

cancan123456 · 2022-05-23 22:08:46 · 个人记录

我离 4 Kyu 仍然遥遥无期。

默哀：

1. 我 T2 选错语言 RE 了一次。
2. lhx T1 因为复制的时候不小心多按了个字母上去 CE 了一次。

\text{A - ASCII code}

大水题。

\text{B - Takahashi's Failure}

对 A 排序，那么 Takahshi 吃的一定是 A_i 最大的食物。

然后看 B_i 中的最大值和 A_i 最大值是否相同就行了。

\text{C - Slot Strategy}

枚举所有数字，然后看每个 reel 需要转几次才能转到，对其排序，然后如果有 x 个相同的次数都是 y，那么显然需要等 10(x-1)+y 才行，然后去个最大值就是该情况的解。

\text{D - Distinct Trio}

考虑维护两个集合，支持插入某个数 x 次，还有维护从两个集合中选出两个不同的数的方案数 ans。

考虑一次插入 y 个 x 对 ans 的影响，即会形成多少个新的数对，显然是另一个集合的元素个数减 x 的出现次数与 x 的乘积。

然后稍微搞搞就行了。

\text{E - Road Reduction}

显然我们需要让 d_i 最小，那么显然是最短路，又因为最短路可以构成一棵树，所以跑 Dijkstra 就行了。

要输出方案就记录前驱就行。

\text{F - Bread}

显然，该题目等同于合并果子倒过来。

\text{G - Pre-Order}

给定一个先序遍历，求有几棵树的先序遍历为该序列。

先序遍历：对于一棵树，先遍历其根节点，然后先序遍历左子树，然后右子树。

考虑区间 DP。

\text{Problems' Codes}

// A - ASCII Code
#include <cstdio>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    print("%c", n):
    return 0;
}

// B - Takahashi's Failure
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
int a[N], b[N];
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= k; i++) {
        scanf("%d", b + i);
        b[i] = a[b[i]];
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + k + 1);
    if (a[n] == b[k]) {
        printf("Yes");
    } else {
        printf("No");
    }
    return 0;
}

// C - Slot Strategy
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
int S[N][10];
int min(int a, int b) {
    return a < b ? a : b;
}
int max(int a, int b) {
    return a > b ? a : b;
}
int notime[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            scanf("%1d", S[i] + j);
        }
    }
    int ans = 0x7fffffff;
    for (int nowans, a = 0; a < 10; a++) {
        for (int i = 1; i <= n; i++) {
            for (int t = 0; t < 10; t++) {
                if (S[i][t] == a) {
                    notime[i] = t;
                    break;
                }
            }
        }
        nowans = 0;
        sort(notime + 1, notime + n + 1);
        for (int l = 1, r; l <= n; l = r + 1) {
            r = l;
            for (; r < n && notime[l] == notime[r + 1]; r++);
            nowans = max(nowans, (r - l) * 10 + notime[l]);
        }
        ans = min(ans, nowans);
    }
    printf("%d", ans);
    return 0;
}

// D - Distinct Trio
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200005;
typedef long long ll;
int a[N];
ll cnt1[N], cnt2[N];
ll sum1, sum2;
ll nowans;
void add1(int x, ll k) {
    cnt1[x] += k;
    sum1 += k;
    nowans += k * (sum2 - cnt2[x]);
}
void add2(int x, ll k) {
    cnt2[x] += k;
    sum2 += k;
    nowans += k * (sum1 - cnt1[x]);
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    add1(a[1], 1);
    for (int i = 3; i <= n; i++) {
        add2(a[i], 1);
    }
    ll ans = 0;
    for (int i = 2; i < n; i++) {
        ll cnt1ai = cnt1[a[i]], cnt2ai = cnt2[a[i]];
        add1(a[i], -cnt1ai);
        add2(a[i], -cnt2ai);
        ans += nowans;
        add1(a[i], cnt1ai);
        add2(a[i], cnt2ai);
        add1(a[i], 1);
        add2(a[i + 1], -1);
    }
    printf("%lld", ans);
    return 0;
}

// E - Road Reduction
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 200005;
typedef long long ll;
struct Edge {
    int v, w, next;
} edge[2 * N];
int head[N];
int cnt;
void add_edge(int u, int v, int w) {
    cnt++;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
struct Point {
    int u;
    ll dis;
};
bool operator < (const Point & a, const Point & b) {
    return a.dis > b.dis;
}
priority_queue < Point > q;
bool vis[N];
ll dis[N];
int pre[N];
void dijkstra() {
    memset(dis, 0x7f, sizeof dis);
    dis[1] = 0;
    q.push((Point) {1, 0});
    while (!q.empty()) {
        Point f = q.top();
        q.pop();
        int u = f.u;
        ll disu = f.dis;
        if (dis[u] != disu) {
            continue;
        }
        for (int v, w, i = head[u]; i != 0; i = edge[i].next) {
            v = edge[i].v;
            w = edge[i].w;
            if (dis[v] > disu + w) {
                dis[v] = disu + w;
                pre[v] = (i + 1) / 2;
                q.push((Point) {v, dis[v]});
            }
        }
    }
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int u, v, w, i = 1; i <= m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dijkstra();
    for (int i = 2; i <= n; i++) {
        printf("%d ", pre[i]);
    }
    return 0;
}

// F - Bread
#include <cstdio>
#include <queue>
using namespace std;
const int N = 200005;
typedef long long ll;
ll a[N];
priority_queue < ll , vector < ll > , greater < ll > > q;
int main() {
    int n;
    ll l;
    scanf("%d %lld", &n, &l);
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", a + i);
        sum += a[i];
        q.push(a[i]);
    }
    if (l > sum) {
        q.push(l - sum);
        n++;
    }
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        ll x = q.top();
        q.pop();
        ll y = q.top();
        q.pop();
        ans += x + y;
        q.push(x + y);
    }
    printf("%lld", ans);
    return 0;
}