Translation Notice
This article was machine-translated using DeepSeek-R1.

• Original Version: Authored in Chinese by myself
• Accuracy Advisory: Potential discrepancies may exist between translations
• Precedence: The Chinese text shall prevail in case of ambiguity
• Feedback: Technical suggestions regarding translation quality are welcomed

Foreword

• This is my first time writing solutions for 7 problems (A~G) in an ABC contest. If there are any shortcomings or areas needing improvement, please feel free to provide feedback. Your support is greatly appreciated!

A - ASCII code

Problem Statement

Given a positive integer $N$, output the character whose ASCII code is $N$.
$97\le N\le 122$

Input Format

$N$

Output Format

Print the character corresponding to ASCII code $N$.

Analysis

Note a corresponds to 97, b to 98, …, z to 122. Beginner conversion examples:

• C

  1 2	int n = 97; putchar(n); /* Output: a */

  putchar automatically converts to character. printf("%c", n) works similarly.
• C++

  1 2	int n = 97; cout << char(n) << endl; // Output: a

  Direct cout << n outputs 97, requires char conversion.
• Python

  1 2	n = 97 print(chr(n)) # Output: a

  Requires chr conversion.
• Java

  1 2 3

  int n = 97; char c = (char) n; System.out.print(c);

  Casting required.
• JavaScript

  1 2 3

  var n = 97; var c = String.fromCharCode(n); console.log(c); // Output: a

  Uses String.fromCharCode.

Need more examples?

Code

Straightforward Python (AC in 25s):

1

print(chr(int(input())))

B - Takahashi’s Failure

Problem Statement

Takahashi’s house has $N$ foods. The $i$-th food has deliciousness $A_i$.
He dislikes $K$ foods: $B_1,B_2,\dots,B_K$.
Takahashi will randomly select a food with maximum deliciousness and eat it.
Is it possible for him to eat a disliked food?

$1\le K\le N\le 100$
$1\le A_i\le 100$
$1\le B_i\le N$

Input Format

$N~K$
$A_1~\dots~A_N$
$B_1~\dots~B_K$

Output Format

Print Yes if possible, No otherwise.

Analysis

Check if any disliked food has maximum deliciousness. See code.

Code

Note convert to 0-indexed for $B_i$:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <cstdio>
using namespace std;

int a[105];

int main()
{
    int n, k, mx = 0;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++)
    {
        scanf("%d", a + i);
        if(a[i] > mx) mx = a[i];
    }
    while(k--)
    {
        scanf("%d", &n);
        if(a[--n] == mx)
        {
            puts("Yes");
            return 0;
        }
    }
    puts("No");
    return 0;
}

C - Slot Strategy

Problem Statement

Refer to AtCoder.

$2\le N\le 100$

Input Format

$N$
$S_1$
$\vdots$
$S_N$

Output Format

Print the answer.

Analysis

Let $\text{cnt}[i][j]$ be the count of $S_k[j] = i$. Compute cost for each target digit. See code.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <cstdio>
using namespace std;

int cnt[10][10]; // cnt[i][j] = number of (s[j]=i)

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        char s[15];
        scanf("%s", s);
        for(int j=0; j<10; j++)
            cnt[s[j] ^ 48][j] ++;
    }
    int ans = 1000;
    for(int i=0; i<10; i++)
    {
        int cur = 0;
        for(int j=0; j<10; j++)
        {
            int c = j + (cnt[i][j] - 1) * 10;
            if(c > cur) cur = c;
        }
        if(cur < ans) ans = cur;
    }
    printf("%d\n", ans);
    return 0;
}

D - Distinct Trio

Problem Statement

Given integer sequence $A=(A_1,\dots,A_N)$, count triples $(i,j,k)$ where:

• $1\le i < j < k\le N$
• $A_i \ne A_j \ne A_k$

$3\le N\le 2\times 10^5$
$1\le A_i\le 2\times 10^5$

Input Format

$N$
$A_1~\dots~A_N$

Output Format

Print the count.

Analysis

Approach:

1. Total triples $C_n^3$ minus invalid ones.
2. For each $x$ in $A$:
   • Subtract $C_{\text{cnt}_x}^2 \times (N-\text{cnt}_x)$ for pairs (x,x,y)
   • Subtract $C_{\text{cnt}_x}^3$ for triples (x,x,x)

Time: $O(N + \max A)$

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <cstdio>
#define maxn 200005
using namespace std;

using LL = long long;
int cnt[maxn];

inline LL C2(int n) { return n * (n - 1LL) >> 1LL; }
inline LL C3(int n) { return C2(n) * (n - 2LL) / 3LL; }

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        int a;
        scanf("%d", &a);
        cnt[a] ++;
    }
    LL ans = C3(n);
    for(int i=1; i<maxn; i++)
        if(cnt[i] > 1)
        {
            ans -= C2(cnt[i]) * (n - cnt[i]);
            if(cnt[i] > 2) ans -= C3(cnt[i]);
        }
    printf("%lld\n", ans);
    return 0;
}

E - Road Reduction

Problem Statement

Given undirected graph with $N$ nodes and $M$ edges. Find a spanning tree minimizing the sum of distances from node 1 to all others.

$2\le N\le 2\times 10^5$
$N-1\le M\le 2\times 10^5$
$1\le C_i\le 10^9$

Input Format

$N~M$
$A_1~B_1~C_1$
$\vdots$
$A_M~B_M~C_M$

Output Format

Print indices of $N-1$ edges in the tree.

Analysis

Optimal tree preserves shortest paths from node 1. Use Dijkstra’s algorithm and track edges.

Code

• Priority queue (182ms):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

  #include <cstdio> #include <queue> #define maxn 200005 #define INF 9223372036854775807LL using namespace std; using LL = long long; using pli = pair<LL, int>; struct Edge { int v, id; LL d; inline Edge(int u, int l, int i): v(u), d(l), id(i) {} }; vector<Edge> G[maxn]; LL dis[maxn]; int ans[maxn]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i=1; i<=m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); G[--a].emplace_back(--b, c, i); G[b].emplace_back(a, c, i); } priority_queue<pli, vector<pli>, greater<pli>> q; for(int i=1; i<n; i++) dis[i] = INF; q.emplace(0LL, 0); while(!q.empty()) { auto [d, v] = q.top(); q.pop(); if(dis[v] == d) for(const Edge& e: G[v]) { LL nd = d + e.d; if(nd < dis[e.v]) q.emplace(dis[e.v] = nd, e.v), ans[e.v] = e.id; } } for(int i=1; i<n; i++) printf("%d ", ans[i]); return 0; }

• Set (202ms):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

  #include <cstdio> #include <vector> #include <set> #define maxn 200005 #define INF 9223372036854775807LL using namespace std; using LL = long long; using pli = pair<LL, int>; struct Edge { int v, id; LL d; inline Edge(int u, int l, int i): v(u), d(l), id(i) {} }; vector<Edge> G[maxn]; LL dis[maxn]; int ans[maxn]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i=1; i<=m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); G[--a].emplace_back(--b, c, i); G[b].emplace_back(a, c, i); } set<pli> s; // <distance, vertex> for(int i=1; i<n; i++) dis[i] = INF; s.emplace(0LL, 0); while(!s.empty()) { auto [d, v] = *s.begin(); s.erase(s.begin()); for(const Edge& e: G[v]) { LL nd = d + e.d; if(nd < dis[e.v]) { if(dis[e.v] < INF) s.erase(pli(dis[e.v], e.v)); s.emplace(dis[e.v] = nd, e.v); ans[e.v] = e.id; } } } for(int i=1; i<n; i++) printf("%d ", ans[i]); return 0; }

F - Bread

Problem Statement

Given initial loaf of length $L$, split into parts including all elements of array $A$. Each split of $k$ costs $k$. Find minimum total cost.

$2\le N\le 2\times 10^5$
$1\le A_i\le 10^9$
$A_1+\dots+A_N\le L\le 10^{15}$

Input Format

$N~L$
$A_1~\dots~A_N$

Output Format

Print the minimal cost.

Analysis

Merge all elements (plus remaining $L-\sum A$ if needed) using a min-heap. Always merge smallest two elements.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <cstdio>
#include <queue>
using namespace std;

using LL = long long;

int main()
{
    int n;
    LL l;
    scanf("%d%lld", &n, &l);
    priority_queue<LL, vector<LL>, greater<LL>> q;
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%d", &x);
        q.push(x);
        l -= x;
    }
    if(l > 0) q.push(l);
    LL ans = 0LL;
    while(q.size() > 1)
    {
        LL x = q.top(); q.pop();
        x += q.top(); q.pop();
        ans += x;
        q.push(x);
    }
    printf("%lld\n", ans);
    return 0;
}

G - Pre-Order

Problem Statement

Count valid rooted trees with given pre-order traversal $P_1,\dots,P_N$, where children are visited in ascending order. Modulo 998244353.

$2\le N\le 500$
$P_1=1$
$P$ is permutation.

Input Format

$N$
$P_1~\dots~P_N$

Output Format

Print the count modulo 998244353.

Analysis

Let $dp(l,r)$ be the count for subarray $A_l,\dots,A_{r-1}$. Transition:

• $dp(l,r) = dp(l+1,r) + \sum_{k} dp(l+1,k) \times dp(k,r)$ if $A_l < A_k$

Code

• Version 1 (59ms):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

  #include <cstdio> #define MOD 998244353 #define maxn 505 using namespace std; using LL = long long; int p[maxn], dp[maxn][maxn]; int main() { int n; scanf("%d", &n); for(int i=0; i<n; i++) scanf("%d", p + i); for(int l=n; l>0; l--) { dp[l][l] = 1; for(int r=l+1; r<=n; r++) { dp[l][r] = dp[l + 1][r]; for(int k=l+1; k<r; k++) if(p[l] < p[k] && (dp[l][r] += LL(dp[l + 1][k]) * dp[k][r] % MOD) >= MOD) dp[l][r] -= MOD; } } printf("%d\n", dp[1][n]); return 0; }

• Version 2 (66ms):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  #include <cstdio> #define MOD 998244353 #define maxn 505 using namespace std; using LL = long long; int p[maxn], dp[maxn][maxn]; int main() { int n; scanf("%d", &n); for(int i=0; i<n; i++) scanf("%d", p + i); for(int i=1; i<=n; i++) dp[i][i] = 1; for(int d=1; d<=n; d++) for(int l=1, r=d+1; r<=n; l++, r++) { dp[l][r] = dp[l + 1][r]; for(int k=l+1; k<r; k++) if(p[l] < p[k] && (dp[l][r] += LL(dp[l + 1][k]) * dp[k][r] % MOD) >= MOD) dp[l][r] -= MOD; } printf("%d\n", dp[1][n]); return 0; }