题解 - 2022 ICPC 亚洲区域赛 (沈阳) 热身赛

发表于 更新于 分类于 ， ， 本文字数： 156 阅读时长 ≈ 1 分钟

经典热身赛用原题

题目概览

A - The introduction of NEU

解题思路

From 东北大学章程网 , Archived

代码参考

Show code

A.phpview raw
1
Apr

B - Random Permutation

解题思路

2020 年 ICPC 澳门站的 L, 答案是

\[ \frac{(n!)^2}{n^n} \]

代码参考

Show code

B.pyview raw
1
2
3
4
import math

n = int(input())
print((math.factorial(n) ** 2) / (n ** n))

C - The Great Wall

解题思路

2020 年 ICPC 银川站的 B

代码参考

Show code

C.cppview raw
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 <bits/stdc++.h>
using namespace std;
const int N = 10000 + 7;
int a[N], dp[2][N][10];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= 3; ++j) dp[0][i][j] = dp[1][i][j] = -(1000000000 + 7);
  int Now = 0, Last = 1;
  dp[Now][0][3] = 0;
  for (int i = 1; i <= n; ++i) {
    swap(Now, Last);
    for (int j = 1; j <= i; ++j) {
      dp[Now][j][0] = max(dp[Last][j - 1][3], dp[Last][j][0]);
      dp[Now][j][1] =
        max({dp[Last][j][1], dp[Last][j][0] - a[i], dp[Last][j - 1][3] - a[i]});
      dp[Now][j][2] =
        max({dp[Last][j][2], dp[Last][j][0] + a[i], dp[Last][j - 1][3] + a[i]});
      dp[Now][j][3] = max({dp[Last][j][3],
                           dp[Last][j - 1][3],
                           dp[Last][j][1] + a[i],
                           dp[Last][j][2] - a[i]});
    }
  }
  for (int i = 1; i <= n; ++i) cout << dp[Now][i][3] << '\n';
}

D - A Bite of Teyvat

解题思路

参见 题解 - 2021 ICPC 亚洲区域赛 (沈阳) 的 A