2021 ECNA 区域赛总结与题解

差不多最后一年了，明年队友估计就都毕业了，看看能不能找到其他人吧，或者 solo 也行？

总结

今年由于疫情依然不能去温莎线下比赛，但相比去年三人三机今天变成了更像线下的三人一机，不过是在各自学校比赛，但令人不能理解是的居然一点监控措施都没有，全凭自己自觉和教练监督。。。。可以理解为摆烂吧😂。我们队算是做到了遵循规则，除了多接了一个显示器用来看代码（自己电脑没法连机房的打印机），以及我还是用的自己的键盘（用 40% 配列太久了改不回来了）。

排名有点出乎意料，考虑到队友忙于实习从不训练、我上了大三之后课程难度增加，只能靠每周 cf 维持一点做题量，这个排名已经很满意了，毕竟如果按 NAC 晋级规则按学校排名是第 6，校排名要是第 5 的话总排名要第 6，完全想 peach😂。

整场比赛还是比较流畅的，基本没有卡太长时间，A 题作为比较简单的题卡了有点久，最后还是靠猜结论过的，F 计算几何某队友到最后也没搞出来，不过没占用太多正常时间。时间再稍微多一点也许能搞搞 I 或者 K，不过到最后也比有点累了，昨晚也只睡了 5 个半小时。

题目

题目整体难度适中？比去年难一点，（读了的题）以思维题为主。除了 J 题摆烂出了最大子矩形原题，题目质量还可以？

A

一开始 wa 是因为忘了考虑相加的转移。考虑加的话要遍历一遍整个 dp 数组，时间复杂度会变成 $O(n^2)$ ，但其实也能过因为时间给了 15s。。。（我 tm 写博客的时候才发现）。但貌似只要遍历前面一些数就行了，因为数大的时候乘肯定比加划算。

 
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> dp(n + 1, 1e9);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = i;
 
        for (int j = 1; j <= min(i / 2 + 1, 1000); j++)
            dp[i] = min(dp[i], dp[j] + dp[i - j]);
 
        string s = to_string(i);
        for (int j = 1; j < (int)size(s); j++) {
            string s1 = s.substr(0, j), s2 = s.substr(j);
            if (s2[0] == '0') continue;
            dp[i] = min(dp[i], dp[stoi(s1)] + dp[stoi(s2)]);
        }
 
        for (int f = 2; f * f <= i; f++) {
            if (i % f == 0) { dp[i] = min(dp[i], dp[f] + dp[i / f]); }
        }
    }
    cout << dp[n] << endl;
}

B

赛时无脑敲了个 lca，但其实稍微再想想就有更简单的做法：dfs 时维护到根节点的距离以及最短的两条到叶子的路径的举例即可。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;
    vector<int> indeg(n), sum(n), color(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        indeg[v]++;
    }
    int c = 0;
    int ans = 1e9;
    auto dfs = [&](auto &slf, int u, int s) -> int {
        sum[u] = s + a[u];
        color[u] = c;
        int mn0 = 1e9, mn1 = 1e9;
        for (auto v : g[u]) {
            auto res = slf(slf, v, s + a[u]);
            if (res < mn1) mn1 = res;
            if (mn1 < mn0) swap(mn0, mn1);
        }
        ans = min(ans, mn0 + mn1 + sum[u]);
        return (mn0 == 1e9 ? 0 : mn0) + a[u];
    };
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) {
            dfs(dfs, i, 0);
            c++;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (g[i].empty() && g[j].empty()) {
                if (color[i] != color[j]) {
                    ans = min(ans, sum[i] + sum[j]);
                }
            }
        }
    }
    cout << ans << endl;
}

G

签到题，枚举所有前缀以及交换顺序即可

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b, c;
    char op, _;
    cin >> a >> op >> b >> _ >> c;
    auto check = [&](string a_, string b_, string c_) {
        __int128 a = stoll(a_), b=stoll(b_), c = stoll(c_);
        if (op=='+') return a+b==c;
        else return a*b==c;
    };
    for (int i=1; i<(int)size(a); i++) {
        for (int j=1; j<(int)size(b); j++) {
            for (int k=1; k<(int)size(c); k++) {
                string a1=a.substr(0, i), a2=a.substr(0+i);
                string b1=b.substr(0, j), b2=b.substr(0+j);
                string c1=c.substr(0, k), c2=c.substr(0+k);
                vector<string> s = {a1, b1, c1};
                sort(begin(s), end(s));
                do {
                    if (check(s[0]+a2, s[1]+b2, s[2]+c2)) {
                        cout << s[0]+a2 << ' ' << op << ' ' <<  s[1]+b2 << " = " << s[2]+c2;
                        exit(0);
                    }
                } while (next_permutation(begin(s), end(s)));
            }
        }
    }
}

J

经典最大子矩阵，单调栈搞搞即可。其实我赛时已经基本忘了怎么做了，只记得是是单调栈，想了半天才想出来正解，这下应该以后忘不了了 233

#include <bits/stdc++.h>
using namespace std;
using ll = long long; //}}}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    stack<pair<int, int>> stk;
    ll ans = 0;
    int s = 1e9, e = 0;
 
    auto update = [&](ll cur, int curs, int cure) {
        if (cur > ans || (cur == ans && curs < s)) {
            ans = cur;
            s = curs;
            e = cure;
        }
    };
    for (int i = 0; i < n; i++) {
        int prev = i;
        while (!stk.empty() && stk.top().first >= a[i]) {
            prev = stk.top().second;
            ll cur = ll(i - prev) * stk.top().first;
            update(cur, prev, i - 1);
            stk.pop();
        }
        ll cur = ll(i - prev + 1) * a[i];
        update(cur, prev, i);
        stk.push({a[i], prev});
    }
    while (!stk.empty()) {
        auto [x, i] = stk.top();
        stk.pop();
        ll cur = ll(n - i) * x;
        update(cur, i, n - 1);
    }
    cout << s + 1 << ' ' << e + 1 << ' ' << ans << endl;
}

L

枚举四个角然后排序分层搞一搞，队友写的

import collections
import itertools
import sys
ints = lambda: list(map(int, sys.stdin.readline().split()))
grid = []
gy, gx = ints()
for y in range(gy):
  grid.append(ints())
statues = []
for row in grid:
  for cell in row:
    if ~cell:
      statues.append(cell)
statues.sort()
 
def levels(grid):
  ret1 = collections.defaultdict(set)
  ret2 = collections.defaultdict(set)
  for y in range(gy):
    for x in range(gx):
      cell = grid[y][x]
      if ~cell:
        ret1[y+x].add(cell)
        ret2[y-x].add(cell)
  return ret1, ret2
 
ret1, ret2 = levels(grid)
 
keys1 = sorted(ret1.keys())
keys2 = sorted(ret2.keys())
 
import math
moved = math.inf
 
for keys, ret in (keys1, ret1), (reversed(keys1), ret1), (keys2, ret2), (reversed(keys2), ret2):
  this = len(statues)
  it = iter(statues)
  for key in keys:
    st = set()
    for _ in range(len(ret[key])):
      st.add(next(it))
    this -= len(st & ret[key])
  moved = min(moved, this)
 
print(moved)

M

最短路考虑用 bfs，把所有字符串放入一个 trie 就可以很容易知道哪些方向可以走了，所以状态就是[x][y][trie 中的节点的位置][上一步的方向]。除了状态复杂点其他就是正常 bfs 的套路，注意如果当前在单词结尾的位置，下一步即可以回到 trie 的根，又可以继续顺着 trie 走。

#include <bits/stdc++.h>
using namespace std;
 
struct Trie {
    struct node {
        map<char, int> ch;
        bool term;
    };
    vector<node> t;
    Trie() { new_node(); }
    int new_node() {
        t.emplace_back();
        return t.size() - 1;
    }
    void insert(const string &s) {
        int p = 0;
        for (auto ch : s) {
            if (!t[p].ch.count(ch)) { t[p].ch[ch] = new_node(); }
            p = t[p].ch[ch];
        }
        t[p].term = true;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector s(n, vector<char>(m));
    for (auto &v : s)
        for (auto &c : v)
            cin >> c;
    Trie tr;
    for (int i = 0; i < k; i++) {
        string ss;
        cin >> ss;
        tr.insert(ss);
    }
    vector dis(n, vector(m, vector(size(tr.t), vector(3, -1))));
    queue<array<int, 4>> q;
    for (int i = 0; i < m; i++) {
        if (tr.t[0].ch.count(s[0][i])) {
            int st = tr.t[0].ch[s[0][i]];
            dis[0][i][st][0] = 1;
            q.push({0, i, st, 0});
        }
    }
 
    const vector<pair<int, int>> dir{{1, 0}, {0, -1}, {0, 1}};
    while (!q.empty()) {
        auto [x, y, st, prev] = q.front();
        int olddis = dis[x][y][st][prev];
        q.pop();
        for (int ii = 0; ii < (int)size(dir); ii++) {
            auto [dx, dy] = dir[ii];
            if ((prev == 1 && dy == 1) || (prev == 2 && dy == -1))
                continue;
            unsigned nx = x + dx, ny = y + dy;
            if (nx < n && ny < m) {
                auto go = [&](int st) {
                    if (tr.t[st].ch.count(s[nx][ny])) {
                        int nst = tr.t[st].ch[s[nx][ny]];
                        if (dis[nx][ny][nst][ii] == -1) {
                            dis[nx][ny][nst][ii] = olddis + 1;
                            q.push({(int)nx, (int)ny, nst, ii});
                        }
                    }
                };
                go(st);
                if (tr.t[st].term) {
                    st = 0;
                    go(st);
                }
            }
        }
    }
    int ans = 1e9;
    for (int i = 0; i < m; i++) {
        for (int d = 0; d < 3; d++) {
            for (int st = 0; st < (int)size(tr.t); st++) {
                if (tr.t[st].term && dis[n - 1][i][st][d] != -1) {
                    ans = min(ans, dis[n - 1][i][st][d]);
                }
            }
        }
    }
    if (ans == 1e9) {
        cout << "impossible\n";
    } else
        cout << ans << endl;
}

2021 ECNA 区域赛总结与题解

总结 #

题目 #

A #

代码

B #

代码

G #

代码

J #

代码

L #

代码

M #

代码

总结

题目

A

B

G

J

L

M