11

· · 个人记录

A 评估

\sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} |a_i - a_j| ^ 2 = (n - 1) \times \sum_{i = 1}^{n} a_i ^ 2 + \sum_{i = 1}^{n - 1} \sum_{j = i + 1}^{n} a_ia_j

前缀和优化 \sum_{j = i + 1}^{n} a_j = s_n - s_i

B 拆分数字

先算出三进制下 n 的数位和(也就是最少要几个 3^i)

k >= ans

然后利用 3^i = 3 \times 3^{i - 1} 判断

k \% 2 = ans \% 2

C 露营

三个联通块点
曼哈顿距离!

#include <bits/stdc++.h>
using namespace std;
int a, b, c, d, e, f, ans = INT_MAX;
int main(){
    cin >> a >> b >> c >> d >> e >> f;
    for (int i = 0; i <= 1000; i ++)
        for (int j = 0; j <= 1000; j ++) ans = min(ans, abs(i - a) + abs(j - b) + abs(i - c) + abs(j - d) + abs(i - e) + abs(j - f) + 1);
    cout << ans;
}

D 寻宝

dp!
pair <string, int> dp[1005][1005]
字典序 + 距离 

if (mp[1][1] != 'a' && k) mp[1][1] = 'a', k --;
tmp.push_back(mp[1][1]);
dp[1][1] = {tmp, k};
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++) {
        if (i == 1 && j == 1) continue;
        if (i == 1) {
            if (mp[i][j] != 'a' && dp[i][j - 1].second) dp[i][j] = {dp[i][j - 1].first + 'a', dp[i][j - 1].second - 1};
            else dp[i][j] = {dp[i][j - 1].first + mp[i][j], dp[i][j - 1].second};
        } else if (j == 1) {
            if (mp[i][j] != 'a' && dp[i - 1][j].second) dp[i][j] = {dp[i - 1][j].first + 'a', dp[i - 1][j].second - 1};
            else dp[i][j] = {dp[i - 1][j].first + mp[i][j], dp[i - 1][j].second};
        } else {
            if (dp[i - 1][j] > dp[i][j - 1]) {
                if (mp[i][j] != 'a' && dp[i - 1][j].second) dp[i][j] = {dp[i - 1][j].first + 'a', dp[i - 1][j].second - 1};
                else dp[i][j] = {dp[i - 1][j].first + mp[i][j], dp[i - 1][j].second};
            } else {
                if (mp[i][j] != 'a' && dp[i][j - 1].second) dp[i][j] = {dp[i][j - 1].first + 'a', dp[i][j - 1].second - 1};
                else dp[i][j] = {dp[i][j - 1].first + mp[i][j], dp[i][j - 1].second};           
            }
        }
    }
cout << dp[n][n].first;
\textcolor{orange}{MLE} \textcolor{40de5a}{80pts}

滚动数组！