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

A - Last Two Digits

Problem Statement

Given a positive integer $N$, output its last two digits.
$100\le N\le 999$

Input Format

$N$

Output Format

Print the last two digits of $N$. Note that the output may have leading 0s.

Sample

Analysis

Since $N$ is guaranteed to be a three-digit number, we can directly treat the input as a string and output its last two characters.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <cstdio>
using namespace std;

int main()
{
    getchar();
    putchar(getchar());
    putchar(getchar());
    return 0;
}

B - Practical Computing

Problem Statement

Output $N$ integer sequences $A_0,\dots,A_{N-1}$ defined as:

• Length of $A_i$ is $i+1$.
• The $(j+1)$-th element of $A_i$, denoted $a_{i,j}$ ($0\le j\le i < N$), is:
  • $1$ if $j=0$ or $j=i$;
  • $a_{i-1,j-1}+a_{i-1,j}$ otherwise.

$1\le N\le 30$

Input Format

$N$

Output Format

Print $N$ lines. The $i$-th line contains $i$ numbers from $A_{i-1}$, separated by spaces.

Sample

Sample Input 1

1

3

Sample Output 1

1
2
3

1
1 1
1 2 1

Sample Input 2

1

10

Sample Output 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Analysis

The problem essentially describes the Yang Hui Triangle (Pascal’s Triangle). We can compute the elements sequentially as per the rules. Time complexity $\mathcal O(n^2)$, space complexity $\mathcal O(n)$ or $\mathcal O(n^2)$. See Code 1 and 2.

Alternatively, since $a_{i,j} = \binom{i}{j}$, we can compute it with $\mathcal O(1)$ space (code to be added).

Code

• Code 1 (Standard approach without optimization, cin/cout, $7\text{ms}~3604\text{KB}$)
  Time: $\mathcal O(n^2)$
  Space: $\mathcal O(n^2)$
  Difficulty: Low

  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 <iostream> using namespace std; int arr[35][35]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { arr[i][0] = 1; arr[i][i] = 1; } for (int i = 2; i < n; i++) { for (int j = 1; j < i; j++) { arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { cout << arr[i][j] << " "; } cout << endl; } return 0; }

• Code 2 (Standard approach + rolling array, scanf/printf, $6\text{ms}~1656\text{KB}$)
  Time: $\mathcal O(n^2)$
  Space: $\mathcal O(n)$
  Difficulty: Medium-Low

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

  #include <cstdio> using namespace std; int a[35]; int main() { int n; scanf("%d", &n); a[0] = 1, puts("1"); for(int i=1; i<n; i++) { putchar('1'); for(int j=i-1; j>0; j--) a[j] += a[j - 1]; for(int j=1; j<i; j++) printf(" %d", a[j]); a[i] = 1, puts(" 1"); } return 0; }

C - K Swap

Problem Statement

Given a sequence $A=(a_1,a_2,\dots,a_N)$ of length $N$ and an integer $K$, you can perform the following operation any number of times:

• Choose an integer $1\le i\le N-K$, swap $a_i$ and $a_{i+K}$.

Determine if $A$ can be sorted in non-decreasing order through these operations.

$2\le N\le 2\times 10^5$
$1\le K\le N-1$
$1\le a_i\le 10^9$

Input Format

$N~K$
$a_1~\dots~a_N$

Output Format

Print Yes if possible, otherwise No.

Sample

Sample Input 1

1
2

5 2
3 4 1 3 4

Sample Output 1

1

Yes

Explanation: After two swaps, $A$ becomes sorted.

Sample Input 2

1
2

5 3
3 4 1 3 4

Sample Output 2

1

No

Sample Input 3

1
2

7 5
1 2 3 4 5 5 10

Sample Output 3

1

Yes

Analysis

Elements at positions $i, i+K, i+2K, \dots$ (for $0 \le i < K$) can be freely rearranged. For each such group, sort them and check if the entire array becomes sorted.

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
32
33
34
35

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

int a[maxn], b[maxn];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++)
    {
        scanf("%d", a + i);
        b[i] = a[i];
    }
    sort(b, b + n);
    for(int i=0; i<k; i++)
    {
        multiset<int> s1, s2;
        for(int j=i; j<n; j+=k)
        {
            s1.insert(a[j]);
            s2.insert(b[j]);
        }
        if(s1 != s2)
        {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

Note: Python’s array slicing makes this problem concise. Example Python code:

1
2
3
4
5

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    a[i::k] = sorted(a[i::k])
print('Yes' if a == sorted(a) else 'No')

D - Together Square

Problem Statement

Given $N$, count the number of positive integer pairs $(i,j)$ satisfying:

• $1\le i,j\le N$
• $i\times j$ is a perfect square.

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

Input Format

$N$

Output Format

Print the answer.

Sample

Analysis

For $i \times j$ to be a square, the product’s prime factors must have even exponents. Enumerate coprime pairs $(x,y)$ where $x,y \le \sqrt{N}$, and count valid $(i,j)$ pairs derived from them. Time complexity $\mathcal O(N \log \sqrt N)$.

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

#include <cstdio>
using namespace std;

inline int gcd(int a, int b)
{
    while(b ^= a ^= b ^= a %= b);
    return a;
}

int main()
{
    int n = 0; char c;
    while((c = getchar()) != '\n')
        n = (n << 3) + (n << 1) + (c ^ 48);
    int t = __builtin_sqrt(n);
    long long ans = 0LL, x;
    for(int i=1; i<=t; i++)
        for(int j=i; j<=t; j++)
            if(gcd(i, j) == 1)
            {
                ans += (x = n / (i > j? i * i: j * j));
                if(i != j) ans += x;
            }
    printf("%lld\n", ans);
    return 0;
}

E - Small d and k

Problem Statement

Given an undirected graph with $N$ vertices and $M$ edges, where each vertex has degree ≤3. Answer $Q$ queries:

• Find the sum of indices of vertices within distance $k_i$ from $x_i$.

$1\le N,Q\le 1.5\times 10^5$
$0\le M\le \min\{\frac{N(N-1)}2,\frac32N\}$
$0\le k_i\le 3$

Input Format

$N~M$
$a_1~b_1$
$\vdots$
$a_M~b_M$
$Q$
$x_1~k_1$
$\vdots$
$x_Q~k_Q$

Output Format

Print $Q$ lines with answers.

Sample

Sample Input

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

6 5
2 3
3 4
3 5
5 6
2 6
7
1 1
2 2
2 0
2 3
4 1
6 0
4 3

Sample Output

1
2
3
4
5
6
7

1
20
2
20
7
6
20

Analysis

Leverage the constraints:

• Maximum reachable nodes per query: 3⁴ = 81 (practical limit ≈28)
• Use BFS up to depth 3 for each query. Reset visited markers efficiently.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <cstdio>
#include <queue>
#define maxn 150005
using namespace std;

vector<int> G[maxn];
int dis[maxn];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int Q; scanf("%d", &Q);
    for(int i=1; i<=n; i++) dis[i] = -1;
    while(Q--)
    {
        int x, k;
        scanf("%d%d", &x, &k);
        vector<int> ans;
        queue<int> q;
        q.push(x);
        dis[x] = 0;
        while(!q.empty())
        {
            int v = q.front(); q.pop();
            int d = dis[v];
            if(d <= k) ans.push_back(v);
            if(++d > k) continue;
            for(int u: G[v])
                if(dis[u] == -1)
                {
                    dis[u] = d;
                    q.push(u);
                }
        }
        int res = 0;
        for(int v: ans)
            res += v, dis[v] = -1;
        printf("%d\n", res);
    }
    return 0;
}