避雷：H 我不会。

随便写写吧：https://codeforces.com/contest/1810.

终于更完了，james1 你也是够懒的。

A. Beautiful Sequence

如果有一个数满足 ai≥ia_i\geq i 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

void solve(void) {
    int n, flag = 0; cin >> n;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        if (x <= i) flag = 1;
    }
    cout << (flag ? "YES\n" : "NO\n");
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1; cin >> T; 
    while (T--) solve();
    return 0;
}

B. Candies

不难发现决策是唯一的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

void solve(void) {
    int n; cin >> n; vector<int> ans;
    while (n % 2 && n > 1) {
        if ((n >> 1) & 1) ans.push_back(2), n >>= 1;
        else ans.push_back(1), n = (n >> 1) + 1;
    }
    if (n != 1) return cout << "-1\n", void();
    reverse(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (int i : ans) cout << i << " "; cout << "\n";
}

int main(void) {
    ios::sync_with_stdio(0); 
    int T = 1; cin >> T; 
    while (T--) solve();
    return 0;
}

C. Make It Permutation

枚举结束的数字即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 1e5 + 5;

int n, c, d;
int a[N];

void solve(void) {
    cin >> n >> c >> d;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    int m = unique(a + 1, a + n + 1) - (a + 1);
    i64 ans = 1ll * m * c + d;
    for (int i = 1; i <= m; ++i) ans = min(ans, 1ll * (a[i] - i) * d + 1ll * (m - i) * c);
    cout << ans + 1ll * c * (n - m) << "\n";
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1; cin >> T; 
    while (T--) solve();
    return 0;
}

D. Climbing the Tree

蜗牛爬水井是小学时非常常见的脑筋急转弯题，要注意蜗牛可能会直接爬出水井。

对于本题来说，我们需要用更为一般的代数手段，也就是不等式组描述这个问题。给条件相当于要解出一组取值范围看能否与之前的合并，问能否爬出相当于要对于当前的高度取值范围 [L,R][L,R]，分别看高度为 L,RL,R 时所需的爬出天数（显然这个函数是单调递增的）。

先来看第一个问题。什么时候高度最大？第 nn 天需要爬 aa 时，即 (n−1)×(a−b)+a(n-1)\times (a-b) + a。最小呢？第 n−1n-1 天白天爬完之后还剩 11 的高度没有爬完，以至于需要第 nn 天接着爬。

再来看第二个问题。不妨设高度为 hh，那么要满足 an−b(n−1)≥han - b(n-1) \geq h，将 nn 解出向上取整即可。

有点小细节但不多，比如天数为 11 需要特判之类的。样例非常友好，写挂了全能调出来。

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 <bits/stdc++.h>
using namespace std;
typedef long long i64;

i64 calc(i64 h, int a, int b) {
    if (a >= h) return 1; 
    // (a - b)n >= h - b
    return (h - b + a - b - 1) / (a - b);
}

void solve(void) {
    int q; cin >> q;
    i64 L = 1, R = 2e18;
    while (q--) {
        int op, a, b; i64 n; cin >> op >> a >> b;
        if (op == 1) {
            cin >> n;
            i64 r = (n - 1) * (a - b) + a;
            i64 l = (n == 1 ? 1 : (n - 2) * (a - b) + a + 1);
            if (l > R || r < L) cout << "0 ";
            else {
                cout << "1 ";
                L = max(L, l); R = min(R, r);
            }
        } else {
            // cerr << L << " " << R << " E$TD\n";
            i64 n1 = calc(L, a, b), n2 = calc(R, a, b);
            if (n1 != n2) cout << "-1 ";
            else cout << n1 << " ";
        }
    }
    cout << "\n";
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1; cin >> T; 
    while (T--) solve();
    return 0;
}

E. Monsters

如果直接做的话，考虑一个被一个大点分割成两部分的图，这样左半部分和右半部分都是跑满的。

但实际上，如果一个出生点可以从另一个出生点走过来，那么这个出生点就没必要重新计算了。我直觉感觉这玩意儿是 O(nlog⁡n)O(n\log n) 的，但是这不对。

设 D(x)D(x) 表示 xx 为出生点可以走到的点集。假设 u∈D(x),D(y)u\in D(x),D(y)，而且 ∣D(x)∣<∣D(y)∣|D(x)|< |D(y)|，那么 yy 能够走到 xx 但是 xx 不能走到 yy。以中间那个阻止 xx 继续前进的点分割，yy 必然有不小于 xx 的规模，因此 2∣D(x)∣≤∣D(y)∣2|D(x)|\le |D(y)|。因此任意一个点最多只会被计算 log⁡n\log n 个有效出生点计算到。证得 O(nlog⁡2n)O(n\log^2 n)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 2e5 + 5;

int n, m, a[N], vis[N];
vector<int> G[N];

bool work(int x) {
    #define pii pair<int, int>
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.emplace(0, x);
    int cnt = 0;
    while (!q.empty()) {
        int u = q.top().second; q.pop(); 
        if (vis[u] == x) continue; vis[u] = x;
        ++cnt;
        if (a[u] >= cnt) return 0;
        for (int v : G[u]) if (vis[v] != x) q.emplace(a[v], v);
    }
    return cnt == n;
}

void solve(void) {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) vector<int>().swap(G[i]), cin >> a[i];
    while (m--) {
        int u, v; cin >> u >> v;
        G[u].emplace_back(v); G[v].emplace_back(u);
    }
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i)
        if (a[i] == 0 && vis[i] == 0) 
            if (work(i)) return cout << "YES\n", void();
    cout << "NO\n";
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1; cin >> T; 
    while (T--) solve();
    return 0;
}

G. The Maximum Prefix

直接做怎么做？设 fif_i 表示前 ii 个数，当前前缀和为 jj，最大前缀和为 kk，然后刷表转移对于每个状态是 O(1)O(1) 的，炸了。

需要合并无效状态。考虑对于一段后缀，如果它本身的最大前缀和是 00，那么它不会对前面的贡献产生影响。也就是说，对于任意一段后缀，其能对整个序列的最大前缀和产生贡献的都是其最大前缀和。

设 fi,jf_{i,j} 代表考虑前 ii 个数，且满足 [i+1,n][i+1,n] 的最大前缀和为 jj 的期望答案。可以以 pip_i 的系数转移到 fi+1,j−1f_{i+1,j-1}，1−pi1-p_i 的系数转移到 fi+1,j+1f_{i+1,j+1}。

答案便是 fi,0f_{i,0}。

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 <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int P = 1000000007;
const int N = 5e3 + 5;

inline int poww(int a, int b) {
    int r = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) r = 1ll * r * a % P;
    return r;
}
inline int inv(int x) { return poww(x, P - 2); }
inline void add(int &x, i64 k) { x = (x + k) % P; }

int n;
int p[N];
int f[N][N];

void solve(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y; cin >> x >> y;
        p[i] = 1ll * x * inv(y) % P;
    }
    for (int i = 0; i <= n + 2; ++i) for (int j = 0; j <= n + 2; ++j) f[i][j] = 0;
    for (int i = 0; i <= n; ++i) cin >> f[0][i];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= n; ++j) if (f[i][j]) {
            // i + 1 位置填 1
            if (j) add(f[i + 1][j - 1], 1ll * p[i + 1] * f[i][j]); 

            // i + 1 位置填 -1
            add(f[i + 1][j + 1], 1ll * (1 + P - p[i + 1]) * f[i][j]);
            if (j == 0) add(f[i + 1][0], 1ll * (1 + P - p[i + 1]) * f[i][j]);
        }
    for (int i = 1; i <= n; ++i) cout << f[i][0] << " \n"[i == n];
}

int main(void) {
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1; cin >> T; 
    while (T--) solve();
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

来过，就留下您的脚印吧！

Nothing built can last forever.
本站由 iznomia 使用 Stellar 1.30.4 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。