解题思路
注意到KICK和START之间没有重复字母，因此可以维护一个计数器，遇到KICK的时候增加计数器，遇到START的时候累加计数器的值（即当前的START可以与X个KICK组合）。
但是这里需要注意的是KICK首尾是相连的，因此可以出现KICKICKSTART的情况，该情况的输出是2。
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
| #include <cstdio>
#include <iostream>
#include <string>
#include <cinttypes>
using namespace std;
uint64_t cal(string &s) {
uint64_t sum = 0;
int kick_num = 0;
for (int i = 0; i < s.size(); ++i) {
if (s.substr(i, 4) == "KICK") {
++kick_num;
} else if (s.substr(i, 5) == "START") {
sum += kick_num;
}
}
return sum;
}
int main() {
int T;
scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
string s;
cin >> s;
printf("Case #%d: %" PRIu64"\n", i, cal(s));
}
return 0;
}
|
解题思路
由于Mike只能向左上或者右下移动，并且不能走重复的格子，那么很容易想到取得最多硬币的方式必然是从左上角到右下角。
维护一个主对角线数组（从0开始计算），对于方阵来说，对角线的数量为$N \times 2 - 1$，不难推断出每个点$(i, j)$所属的主对角线下标为$N - 1 - i + j$。
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
| #include <cstdio>
#include <iostream>
#include <string>
#include <cinttypes>
#include <vector>
using namespace std;
uint64_t cal(int N) {
uint64_t maxCoins = 0;
int i = 0;
vector<uint64_t> diag(N * 2 - 1, 0);
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
cin >> i;
diag[N - 1 - j + k] += i;
}
}
for (const uint64_t &item : diag) {
maxCoins = maxCoins > item? maxCoins : item;
}
return maxCoins;
}
int main() {
int T, N;
scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
cin >> N;
printf("Case #%d: %" PRIu64"\n", i, cal(N));
}
return 0;
}
|
解题思路
这里有一个结论：最小移动步数的所有可能中，必然有转轮初值中的数字。具体证明过程可以参照ANALYSIS部分。
从我个人的理解角度来说，这个结论可以类比中位数。如果这不是转轮，而是直角坐标系，那么将不同点移动至同一条水平线上的话，水平线的最优位置必然是所有纵坐标的中位数。但是对于转轮来说，首尾联通就导致了无法直接求取这个中位数。
因此可以尝试所有的初值作为那个“中位数”。
对于W较大的情况，需要考虑进一步的优化，来找出一个快速计算步数的方式。对于$1 \leqslant k < l \leqslant i$，如果$X_i - X_k < N - X_i + X_k$（即$k$的两条路径中，$k \rightarrow i$会更近），那么必然有$X_i - X_l < N - X_i + X_l$（因为$k$的最近路径会经过$l$）；反之，如果$N - X_i + X_l < X_i - X_l$（即对于$l$而言，$l \rightarrow 1 \rightarrow N \rightarrow i$会更近），那么必然有$N - X_i + X_k < X_i - X_k$（因为对于$l$的最近路径会经过$k$）。
假定找到了点$p$，其满足：
$$
\begin{cases}
& X_i - X_q < N - X_i + X_q, p \leqslant q \leqslant i \
& N - X_i + X_r < X_i - X_r, 1 \leqslant r < p
\end{cases}
$$
那么对于每一个$q$的移动距离必然为$X_i - X_q$，其和为$(i - p + 1) \times X_i - \sum{ X_q}$。此处的$\sum{ X_q}$可以用一个前缀和数组求区间和$(p,i)$计算。
对于每一个$r$的移动距离为$N - X_i + X_r$，其和为$(p - 1) \times (N - X_i) + \sum{X_r}$。此处的$\sum{ X_r}$可以用区间和$(1, p - 1)$计算。
上述仅是比目标值$i$小数字的情况，大于的情况也是类似的。
最后对于整体而言，必然存在两个分位点$x$和$y$，$1 \leqslant x \leqslant i < y \leqslant W$，然后根据上述结论进行计算。
注意：写二分查找时，需要注意下标计算，不要遗漏可能的解。
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| #include <cstdio>
#include <iostream>
#include <cinttypes>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
Solution() {
cin >> W >> N;
wheels.resize(W + 1);
preSum.resize(W + 1, 0);
for (int i = 1; i <= W; ++i) {
cin >> wheels[i];
}
sort(wheels.begin() + 1, wheels.end());
for (int i = 1; i <= W; ++i) {
preSum[i] = preSum[i - 1] + wheels[i];
}
}
uint64_t solve() {
uint64_t minSteps = UINT64_MAX;
uint64_t left = 0;
uint64_t right = 0;
for (int i = 1; i <= W; ++i) {
int lp = binarySearch(i, true);
int rp = binarySearch(i, false);
left = (i - lp + 1) * wheels[i] - getSum(lp, i) + (lp - 1) * (N - wheels[i]) + getSum(1, lp - 1);
right = getSum(i, rp) - (rp - i + 1) * wheels[i] + (W - rp) * (N + wheels[i]) - getSum(rp + 1, W);
minSteps = min(minSteps, left + right);
}
return minSteps;
}
private:
vector<uint64_t> wheels;
vector<uint64_t> preSum;
int W;
int N;
uint64_t getSum(int i, int j) {
return i <= j ? preSum[j] - preSum[i - 1] : 0;
}
int binarySearch(int point, bool updown) {
if (updown) {
int l = 1;
int r = point;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (wheels[point] - wheels[mid] <= N - wheels[point] + wheels[mid]) {
if (mid == 1 || wheels[point] - wheels[mid - 1] > N - wheels[point] + wheels[mid - 1]) {
return mid;
} else {
r = mid - 1;
}
} else {
l = mid + 1;
}
}
return l;
} else {
int l = point;
int r = W;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (wheels[mid] - wheels[point] > N - wheels[mid] + wheels[point]) {
r = mid - 1;
} else {
if (mid == W || wheels[mid + 1] - wheels[point] > N - wheels[mid + 1] + wheels[point]) {
return mid;
} else {
l = mid + 1;
}
}
}
return l;
}
}
};
int main() {
int T;
scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
Solution A;
printf("Case #%d: %" PRIu64"\n", i, A.solve());
}
return 0;
}
|
解题思路
首先这道题存在一个疑问：比如$[1, 2, 3, 4]$四个数字，能够得到的最终结果有{9, 10, 11, 14, 10, 16}。这其中重复的结果是否要考虑，即是计算$(9 + 10 + 11 + 14 + 10 + 16) / 6$还是计算$(9 + 10 + 11 + 14 + 16) / 5$。
这个问题可以通过观察第二个测试样例[19 3 78 2 31]得知，如果是前者，则结果为352.33333333；如果是后者，则结果为371.2857143。
可以观察到，其最后一轮的得分必然是最后的两张牌的组合得分。因为仅能合并相邻的牌，所以最后一次的组合必然是
$$
[A_1 + A_2 + \cdots + A_i, A_{i + 1} + A_{i + 2} + \cdots + A_n] \text{, 其中} 2 \leqslant i \leqslant n - 1
$$
那么最后的一轮得分的期望也就可以由上述子数组的所有可能情况的算术平均值得到。同理每一轮的得分也可以得到一个类似的数学期望，根据数学期望的性质，最后总得分的期望值必然等于每轮的得分期望之和。
因此可以设$dp[i][j]$代表区间$[i, j]$内的总得分期望，也即最终结果为$dp[0][n - 1]$。
考虑数组$[2, 1, 10]$，易知其$dp[0][1] = 3, dp[1][2] = 11$，而$dp[0][2] = \frac{dp[0][0] + dp[1][2] + dp[0][1] + dp[2][2]}{2} + \frac{13}{1} $。
考虑数组$[1, 2, 3, 4]$，其根据上述的计算过程，可得：
$$
\begin{equation}
\begin{split}
dp[0][3] &= \frac{dp[0][0] + dp[1][3] + dp[0][1] + dp[2][3] + dp[0][2] + dp[3][3]}{3} + \frac{10 + 10 + 10}{3} \\
&= \frac{0 + 15 + 3 + 7 + 10 + 0}{3} + 10 \\
&= 21.66667
\end{split}
\end{equation}
$$
因此得出状态转移方程：
$$
dp[i][j] = \frac{\sum_{i}^{j} dp[i][k] + dp[k][j]}{j - i} + \sum_{i}^{j}A_k
$$
此外，为了避免求和的数字过大，使用平均值更新方程
$$
\bar{x}{n+1} = \frac{\bar{x}{n} \cdot n + x_{n+1}}{n+1} =\bar{x}{n} + \frac{x{n+1} - \bar{x}_{n}}{n+1}
$$
该方法仅通过了前两个测试集，第三个测试集TLE了，还需要继续优化。
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
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
double cal(int N) {
vector<int> nums(N);
vector<long long> pre(N + 1, 0);
vector<vector<double>> dp(N, vector<double>(N, 0.0));
for (int i = 0; i < N; ++i) {
cin >> nums[i];
pre[i + 1] = pre[i] + nums[i];
}
for (int dist = 2; dist <= N; ++dist) {
for (int i = 0, j = i + dist - 1; j < N; ++i, ++j) {
double avg = 0;
for (int k = i, count = 0; k < j; ++k, ++count) {
avg = avg + (dp[i][k] + dp[k + 1][j] - avg) / (count + 1);
}
dp[i][j] = avg + (pre[j + 1] - pre[i]);
}
}
return dp[0][N - 1];
}
int main() {
int T, N;
cin >> T;
cout.precision(7);
cout.setf(ios::fixed);
for (int i = 1; i <= T; ++i) {
cin >> N;
cout << "Case #" << i << ": " << cal(N) << endl;
}
return 0;
}
|
优化
上述解法，本质上是在枚举最后一轮的所有可能，但是发生了超时。经过分析计算过程可以发现，如果不更换解法，那么仅有枚举$k$的部分是可以被优化的。
$$
\begin{equation}
\begin{split}
dp[i][j] &= \frac{\sum_{i}^{j} dp[i][k] + dp[k][j]}{j - i} + \sum_{i}^{j}A_k \\
&= \frac{\sum_{i}^{j}dp[i][k]}{j - i} + \frac{\sum_{i}^{j}dp[k + 1][j]}{j - i} + \sum_{i}^{j}A_k \\
&= \frac{begin[i]}{j - i} + \frac{end[j]}{j - i} + \sum_{i}^{j}A_k
\end{split}
\end{equation}
$$
维护两个数组$begin[i]$和$end[j]$，来提前计算出需要枚举$k$得到的值。这两个数组可以在计算$dp[i][j]$时，一并更新。
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
| #include <iostream>
#include <vector>
using namespace std;
double cal(int N) {
vector<int> nums(N);
vector<long long> pre(N + 1, 0);
vector<vector<double>> dp(N, vector<double>(N, 0.0));
vector<double> begin(N, 0.0), end(N, 0.0);
for (int i = 0; i < N; ++i) {
cin >> nums[i];
pre[i + 1] = pre[i] + nums[i];
}
for (int dist = 2; dist <= N; ++dist) {
for (int i = 0, j = i + dist - 1; j < N; ++i, ++j) {
dp[i][j] = (begin[i] + end[j]) / (dist - 1) + (double)(pre[j + 1] - pre[i]);
begin[i] += dp[i][j];
end[j] += dp[i][j];
}
}
return dp[0][N - 1];
}
int main() {
int T, N;
cin >> T;
cout.precision(7);
cout.setf(ios::fixed);
for (int i = 1; i <= T; ++i) {
cin >> N;
cout << "Case #" << i << ": " << cal(N) << endl;
}
return 0;
}
|
其他解法
解法来源：https://www.acwing.com/file_system/file/content/whole/index/content/1383351/
1
2
3
4
5
6
7
8
9
10
11
12
| double solve(){
double res = 0;
for (int i = 0; i + 1 < n; ++ i){
for (int j = 0; j <= i; ++ j){
res += 1. / (i - j + 1) * A[j];
}
for (int j = i + 1; j < n; ++ j){
res += 1. / (j - i) * A[j];
}
}
return res;
}
|