2019 ICPC 南京站 (Gym 103466) 训练记录

正式训练

A. A Hard Problem

显然把所有大于 $\dfrac{n}{2}$ 的数字全部拿出来是符合要求的，再加一个就不行了，于是答案就是 $k = \left\lceil \dfrac{n}{2} \right\rceil + 1$。

任意性证明的话可以从最大的 $k$ 个数开始调整。

C. Digital Path

用 $f_{i, j, k}$ 表示以 $(i, j)$ 结尾且长度为 $k$ 的合法序列方案数。以权值升序更新，并在合适的时候统计答案即可。

K. Triangle

注意到三角形面积公式 $S = \dfrac{1}{2} ab \sin C$，给定点和所求点分一组邻边得到的比例的乘积一定是 $\dfrac{1}{2}$。直接求即可。

用浮点数写的版本在 CF 上被卡了常数，不知道是谁的问题。

 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
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using LD = long double;

const LD eps = 1e-7;

struct Point {
    int x, y;

    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}

    Point operator- (Point u) { return {x - u.x, y - u.y}; }

    LL operator* (Point u) { return (LL)x * u.y - (LL)y * u.x; }
    LL operator^ (Point u) { return (LL)x * u.x + (LL)y * u.y; }
};

int main()
{
    int T;
    scanf("%d", &T);
    while(T--) {
        Point d[3], X;

        for(int i = 0; i < 3; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            d[i] = {x, y};
        }
        scanf("%d%d", &X.x, &X.y);
        
        bool success = false;
        for(int i = 0; i < 3; i++) {
            int j = (i + 1) % 3, k = (i + 2) % 3;
            if(((d[i] - X) * (d[j] - X)) == 0 && ((d[i] - X) ^ (d[j] - X)) <= 0) {
                success = true;
                LD rr = 0;
                if(d[i].x == d[j].x) {
                    rr = (LD)(X.y - d[i].y) / (d[j].y - d[i].y);
                } else {
                    rr = (LD)(X.x - d[i].x) / (d[j].x - d[i].x);
                }

                if(fabsl(rr - 0.5) < eps) {
                    printf("%d %d\n", d[k].x, d[k].y);
                } else if(rr < 0.5) {
                    rr = 0.5 / (1 - rr);
                    LD x = d[j].x + (d[k].x - d[j].x) * rr;
                    LD y = d[j].y + (d[k].y - d[j].y) * rr;
                    printf("%.8Lf %.8Lf\n", x, y);
                } else {
                    rr = 0.5 / rr;
                    LD x = d[i].x + (d[k].x - d[i].x) * rr;
                    LD y = d[i].y + (d[k].y - d[i].y) * rr;
                    printf("%.8Lf %.8Lf\n", x, y);
                }
                break;
            }
        }
        
        if(!success) {
            puts("-1");
        }
    }
    return 0;
}

J. Spy

求期望是假，枚举全部情况求和是真。

如果我们组好了一队，对于给定的对面的一队，两边对打的可能性是 $(n - 1)!$。于是可以对每个我方可能的组队在对面二分查找能打过哪些队伍，跑一遍最大权匹配即可。

时间复杂度 $O(n^3)$。

  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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
using namespace std;

template<typename cost_t>
class HungarianKM {
    int n, nx, ny;
    vector<vector<cost_t>> G;
    vector<bool> visx, visy;
    vector<cost_t> lx, ly;
    vector<int> pre;
    vector<cost_t> slack;

    void bfs(int i) {
        queue<int> q;
        q.push(i);
        visx[i] = true;

        function<bool(int)> check = [&] (int v) {
            visy[v] = true;
            if(matchy[v] != -1) {
                q.push(matchy[v]);
                visx[matchy[v]] = true;
                return false;
            }
            while(v != -1) {
                matchy[v] = pre[v];
                swap(v, matchx[pre[v]]);
            }
            return true;
        };

        while(true) {
            while(!q.empty()) {
                int u = q.front();
                q.pop();
                for(int v = 0; v < n; v++) {
                    if(!visy[v]) {
                        cost_t delta = lx[u] + ly[v] - G[u][v];
                        if(slack[v] >= delta) {
                            pre[v] = u;
                            if(delta) {
                                slack[v] = delta;
                            } else if(check(v)) {
                                return;
                            }
                        }
                    }
                }
            }
            
            cost_t a = numeric_limits<cost_t>::max();
            for(int j = 0; j < n; j++) {
                if(!visy[j]) {
                    a = min(a, slack[j]);
                }
            }
            for(int j = 0; j < n; j++) {
                if(visx[j]) lx[j] -= a;
                if(visy[j]) {
                    ly[j] += a;
                } else {
                    slack[j] -= a;
                }
            }
            for(int j = 0; j < n; j++) {
                if(!visy[j] && slack[j] == 0 && check(j)) {
                    return;
                }
            }
        }
    }

public:
    vector<int> matchx, matchy;

    HungarianKM(int _n, int _m) : n(max(_n, _m)), nx(_n), ny(_m) {
        G.assign(n, vector<cost_t>(n, 0));
        matchx.assign(n, -1);
        matchy.assign(n, -1);
        lx.resize(n);
        ly.assign(n, 0);
        pre.resize(n);
    }
    
    void add_edge(int u, int v, cost_t w) {
        G[u][v] = max(w, G[u][v]);
    }

    cost_t solve() {
        for(int i = 0; i < n; i++) {
            lx[i] = *max_element(G[i].begin(), G[i].end());
        }

        for(int i = 0; i < n; i++) {
            slack.assign(n, numeric_limits<cost_t>::max());
            visx.assign(n, false);
            visy.assign(n, false);
            bfs(i);
        }

        cost_t res = 0;
        for(int i = 0; i < n; i++) {
            if(G[i][matchx[i]] > 0) {
                res += G[i][matchx[i]];
            } else {
                matchx[i] = -1;
            }
        }
        return res;
    }
};

using LL = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;

    vector<pair<LL, int>> teams(n);
    for(int i = 0; i < n; i++) {
        cin >> teams[i].first;
    }
    for(int i = 0; i < n; i++) {
        cin >> teams[i].second;
    }
    sort(teams.begin(), teams.end());
    partial_sum(teams.begin(), teams.end(), teams.begin(), [] (auto x, auto y) {
        return make_pair(y.first, x.second + y.second);
    });

    HungarianKM<int> solver(n, n);

    vector<LL> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> b[i];
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            auto it = lower_bound(teams.begin(), teams.end(), make_pair(a[i] + b[j], -1));
            if(it == teams.begin()) {
                continue;
            }
            solver.add_edge(i, j, prev(it)->second);
        }
    }

    cout << solver.solve() << "\n";
    return 0;
}

F. Paper Grading

OI 味好冲的一道题…缝，就嗯缝。

考虑把所有字符串扔到 Trie 上，然后查询操作实际上是查询在给定子树内有多少个数字权值在 $[l, r]$ 范围内。注意到子树的 DFS 序是连续的，由此可以直接将问题转化为二位数点。

至于交换操作，实际上等价于删去两个点再重新加两个点。于是问题就变成了离线下所有操作之后 CDQ 分治的模板题。

话说打 OI 的时候我很不擅长写这种又臭又长的题，一不小心写出 bug 就一调一整天。至少四年没写了，没想到这次一个小时写出来直接一遍过了。

  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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <bits/stdc++.h>
using namespace std;

const int MX = 200005;

struct oper_t {
    int type; // 0 for modify, 1 for query
    tuple<int, int, int> info; // (x, y, delta) for modify, (x, y, ctrb) for query

    oper_t(int t, tuple<int, int, int> i) : type(t), info(i) {}
};

struct Trie {
    shared_ptr<Trie> son[26];
    vector<int> labels;
    int dfn, end;
};

void Trie_insert(shared_ptr<Trie> o, const char *s, int label) {
    while(*s != '\0') {
        if(o->son[*s - 'a'] == nullptr) {
            o->son[*s - 'a'] = make_shared<Trie>();
        }
        o = o->son[*s - 'a'];
        s++;
    }
    o->labels.push_back(label);
}

pair<int, int> Trie_query(shared_ptr<Trie> o, const char *s, int k) {
    for(int i = 0; i < k; i++) {
        o = o->son[s[i] - 'a'];
        if(o == nullptr) {
            return {-1, -1};
        }
    }
    return {o->dfn, o->end};
}

int dfn_str[MX];

void dfs(shared_ptr<Trie> u) {
    static int cnt = 0;
    u->dfn = ++cnt;

    for(int id : u->labels) {
        dfn_str[id] = cnt;
    }

    for(shared_ptr<Trie> cur : u->son) {
        if(cur != nullptr) {
            dfs(cur);
        }
    }
    u->end = cnt;
}

void solve(oper_t *begin, oper_t *end, vector<int> &ans) {
    size_t n = (end - begin);
    if(n == 1) {
        return;
    }
    oper_t *mid = begin + n / 2;

    vector<oper_t *> modify;
    for(oper_t *i = begin; i != mid; i++) {
        if(i->type == 0) {
            modify.push_back(i);
        }
    }
    sort(modify.begin(), modify.end(), [&] (oper_t * u, oper_t * v) {
        return get<0>(u->info) < get<0>(v->info);
    });

    vector<oper_t *> query;
    for(oper_t *i = mid; i < end; i++) {
        if(i->type == 1) {
            query.push_back(i);
        }
    }
    sort(query.begin(), query.end(), [&] (oper_t * u, oper_t * v) {
        return get<0>(u->info) < get<0>(v->info);
    });

    static int bit[MX + 10];
    auto bit_insert = [&] (int u, int val) {
        while(u <= MX) {
            bit[u] += val;
            u += u & -u;
        }
    };
    auto bit_query = [&] (int u) {
        int res = 0;
        while(u) {
            res += bit[u];
            u -= u & -u;
        }
        return res;
    };

    size_t it = 0;
    for(oper_t *cur_query : query) {
        auto [cur_x, cur_y, ctrb] = cur_query->info;

        while(it != modify.size()) {
            auto [xx, yy, delta] = modify[it]->info;
            if(xx > cur_x) {
                break;
            }
            bit_insert(yy, delta);
            it++;
        }

        if(ctrb > 0) {
            ans[ctrb] += bit_query(cur_y);
        } else {
            ans[-ctrb] -= bit_query(cur_y);
        }
    }

    for(size_t i = 0; i < it; i++) {
        auto [xx, yy, delta] = modify[i]->info;
        bit_insert(yy, -delta);
    }

    solve(begin, mid, ans);
    solve(mid, end, ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    shared_ptr<Trie> o = make_shared<Trie>();
    for(int i = 1; i <= n; i++) {
        string str;
        cin >> str;
        Trie_insert(o, str.c_str(), i);
    }
    dfs(o);

    vector<oper_t> ops;
    for(int i = 1; i <= n; i++) {
        ops.emplace_back(0, make_tuple(dfn_str[i], i, 1));
    }

    int qid = 0;
    for(int i = 1; i <= m; i++) {
        int op;
        cin >> op;
        if(op == 1) {
            int x, y;
            cin >> x >> y;
            ops.emplace_back(0, make_tuple(dfn_str[x], x, -1));
            ops.emplace_back(0, make_tuple(dfn_str[y], y, -1));
            swap(dfn_str[x], dfn_str[y]);
            ops.emplace_back(0, make_tuple(dfn_str[x], x, 1));
            ops.emplace_back(0, make_tuple(dfn_str[y], y, 1));
        } else {
            string str;
            int k, l, r;
            cin >> str >> k >> l >> r;
            ++qid;
            
            pair<int, int> dfn_rg = Trie_query(o, str.c_str(), k);
            if(dfn_rg.first != -1) {
                ops.emplace_back(1, make_tuple(dfn_rg.second, r, qid));
                ops.emplace_back(1, make_tuple(dfn_rg.first - 1, r, -qid));
                ops.emplace_back(1, make_tuple(dfn_rg.second, l - 1, -qid));
                ops.emplace_back(1, make_tuple(dfn_rg.first - 1, l - 1, qid));
            }
        }
    }

    vector<int> ans(qid + 1);
    solve(ops.data(), ops.data() + ops.size(), ans);

    for(int i = 1; i <= qid; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

赛中两个队友还过了 H 题，由于我全程没有参与将其略过。

过了 F 之后还剩一个半小时，此时两位队友已经口胡了很久 B。我大概打了个表发现 I 题状态数只有 $20$ 万出头，于是直接上手写。写了 40min 左右写完了，但好像没选对写法所以直到最后都没过这题。赛后看别人的代码发现把状态反过来设计直接就过。

这么说来 20 年银川站好像就是这样，理论上完全等价的两个做法我们队正着写就死活不对，别的队反着写直接就过了（

赛后补题

I. Space Station

首先我们发现 $0$ 的位置完全不受任何约束，同时我们只需要计算总和在 $50$ 以内时候的转移状态。

设 $X$ 是一个表示每个数分别用了几次的序列，记 $f_{X}$ 表示从 $X$ 到总和超过 $50$ 时候的总方案数，枚举下一个加进来的数是多少直接转移即可。

这样设计状态可以直接 DFS 记忆化搜索。如果 $f_X$ 表示从啥都没有到 $X$ 的方案数理论上也能做，但这样就只能 BFS，实际写出来代码好像就过不了，不是很懂为什么。

 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
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int mod = 1000000007;
const int MX = 100005;

int fac[MX], inv[MX];

int Pow(int a, int b) {
    int ans = 1;
    for(; b; b >>= 1) {
        if(b & 1) ans = (LL)ans * a % mod;
        a = (LL)a * a % mod;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, init, mxVal = 0;
    cin >> n >> init;

    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = (LL)fac[i - 1] * i % mod;
    inv[n] = Pow(fac[n], mod - 2);
    for(int i = n; i; i--) inv[i - 1] = (LL)inv[i] * i % mod;

    vector<int> cnt(50);
    for(int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        mxVal = max(mxVal, val);
        if(val < 50) {
            cnt[val]++;
        }
    }

    vector<int> used(50);
    map<vector<int>, int> dp;

    function<int(int)> dfs = [&] (int sum) -> int {
        if(sum >= mxVal) {
            return fac[n - cnt[0] - accumulate(used.begin(), used.end(), 0)];
        }
        if(dp.count(used)) {
            return dp[used];
        }
        int ans = 0;
        for(int i = 1; i <= sum; i++) {
            used[i]++;
            ans = (ans + (LL)(cnt[i] - used[i] + 1) * dfs(sum + i)) % mod;
            used[i]--;
        }
        return dp[used] = ans;
    };

    cout << (LL)fac[n] * inv[n - cnt[0]] % mod * dfs(init) % mod << "\n";
    return 0;
}

B. Chessboard

不知道从哪来的记忆碎片使得我总觉得我做过类似的题（除了没有凸性限制），且当时采用的做法好像是把整个方格怎么切一刀然后数。

然后就进到沟里去了。

考虑归纳法。刚开始我们的染色区域是一个 $1 \times 1$ 的矩形。不难证明：若目前的染色区域是 $r \times c$ 的矩形，那么下一步我们只能将其扩展为 $(r + 1) \times c$ 或者 $r \times (c + 1)$，不能只走半行就拐走。

两个方向上分别要进行 $n - 1$ 和 $m - 1$ 次扩展，因此总的方案数是 $\dbinom{n + m - 2}{n - 1}$。至此我们固定了扩展顺序，还需要考虑对称性问题。

注意到第一次扩展的方向有两种选择（左/右或上/下），于是需要额外乘 $2$。

同时当 $n,m \geq 2$ 的时候必然会有至少一次拐弯，而首次拐弯的方向也有两种选择，故在 $n, m \geq 2$ 的情况下还要再乘 $2$。

剩下 DEG 感觉多少都有点可做，有空了仔细看看。