AtCoder Beginner Contest 190

发表于2021-02-09更新于2023-09-15字数统计1.3k阅读时长14分

比赛链接

D Staircase Sequences

Description

题目链接

Solution

设首项为 aa，项数为 nn，那么有 n∗(2a+n−1)=2Nn*(2a+n-1)=2N。由于 nn 为正整数，aa 为整数，因此 nn 为 2N2N 的因数，且 2Nn−n+1\frac{2N}{n}-n+1 是偶数。不同的 nn 对应不同的数列，因此答案为满足上述条件的 nn 的个数。

Code

Staircase Sequences
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>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
LL n;

signed main() {
    cin >> n;
    n *= 2;
    LL ans = 0;
    for (int x = 1; x <= sqrt(n); x++) {
        if (n % x == 0) {
            LL tmp = n / x + 1 - x;
            if (tmp % 2 == 0) ans++;
        }
    }
    cout << ans * 2;
    return 0;
}

E Magical Ornament

Description

题目链接

Solution

称必须包括的 KK 种宝石为关键宝石，本题实际上是求对这些宝石进行排列的代价。我们只需要考虑关键宝石两两之间间接相连中间至少要通过几个宝石，之后便容易用状压 dpdp 求解。具体的，我们分别以这 KK 个关键宝石为起点跑 KK 次最短路，同时记录从起点到其余关键宝石的最短距离，并用数组 disdis 记录。设 dp[i][j]dp[i][j] 表示当前宝石集合为 ii，最后一个加入的为第 jj 个关键宝石所需的最少宝石数目，那么有 dp[i][j]=dp[i⊕(1<<j)][k]+dis[k][j]dp[i][j] = dp[i⊕(1<<j)][k] +dis[k][j]，于是答案即为 min⁡1≤i≤Kdp[(1<<K)−1][i]\min \limits_{1 \le i \le K}dp[(1<<K)-1][i]。

上述做法时间复杂度为 O(K(N+M)+K22K))O(K(N+M)+K^22^K))。

Code

Magical Ornament
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 1E5 + 5;
const int MAXS = (1 << 17);
const int MOD = 1E9 + 7;
int n, m, k;
vector<int> G[MAXN];
int dis[17][17], dp[MAXS][17];
int tag[MAXN], vis[MAXN], d[MAXN], c[18];

void bfs(int s) {
    for (int i = 1; i <= n; i++) d[i] = 1e9, vis[i] = 0;
    queue<int> q;
    q.push(s);
    d[s] = 0;
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (vis[now]) continue;
        vis[now] = 1;
        for (auto& to : G[now]) {
            if (d[to] > d[now] + 1) {
                d[to] = d[now] + 1;
                q.push(to);
            }
            if (tag[to])
                dis[tag[s] - 1][tag[to] - 1] = dis[tag[to] - 1][tag[s] - 1] =
                    d[to];
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> c[i];
        tag[c[i]] = i;
    }
    for (int i = 0; i < k; i++)
        for (int j = 0; j < k; j++) dis[i][j] = 1e9;
    for (int i = 1; i <= k; i++) bfs(c[i]);

    for (int i = 0; i < (1 << k); i++)
        for (int j = 0; j < k; j++) dp[i][j] = 1e9;
    for (int i = 0; i < k; i++) dp[1 << i][i] = 1;
    for (int s = 1; s < (1 << k); s++)
        if (__builtin_popcount(s) != 1)
            for (int i = 0; i < k; i++) {
                if ((s >> i) & 1)
                    for (int j = 0; j < k; j++)
                        if ((s >> j) & 1)
                            dp[s][i] =
                                min(dp[s][i], dp[s ^ (1 << i)][j] + dis[i][j]);
            }
    int ans = 1e9;
    for (int i = 0; i < k; i++) ans = min(ans, dp[(1 << k) - 1][i]);
    cout << (ans == 1e9 ? -1 : ans);
    return 0;
}

F Shift and Inversions

Description

题目链接

Solution

初始序列的答案即为数列中逆序对个数，而每把一个数 aia_i 移到数列最后，答案就会加上 2∗∑i≠j[aj>ai]−n+12*\sum \limits_{i \neq j}[a_j>a_i]-n+1。用值域线段树或树状数组可实现对 ∑i≠j[aj>ai]\sum \limits_{i \neq j}[a_j>a_i] 的快速求解。

Code

Shift and Inversions
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 3E5 + 5;
const int MOD = 1E9 + 7;

int n, a[MAXN];

struct BIT {  // Binary Index Trees, 1based
    int lowbit(int x) { return x & (~x + 1); }
    /* O(n) build tree*/
    BIT() {
        for (int i = 1; i <= n; i++) c[i] = 0;
    }
    void build() {
        for (int i = 1; i <= n; i++) {
            int j = i + lowbit(i);  // j is father of i
            if (j <= n) c[j] += c[i];
        }
    }
    /*@param x the position to add val*/
    void add(int x, LL val) {
        while (x <= n) c[x] += val, x += lowbit(x);
    }
    /*range [1, x] sum query*/
    LL query(int x, LL res = 0) {
        while (x) res += c[x], x -= lowbit(x);
        return res;
    }
    array<LL, MAXN> c;
} bit[3];
/*range [l, r] add val*/
inline void add(int l, int r, LL val) {
    if (l > r) return;
    bit[1].add(l, val), bit[1].add(r + 1, -val);
    bit[2].add(l, val * l), bit[2].add(r + 1, -val * (r + 1));
}
/*range [l, r] sum query*/
inline LL query(int l, int r, LL res = 0) {
    if (l > r) return 0;
    res = bit[0].query(r) + bit[1].query(r) * (r + 1) - bit[2].query(r);
    res -= bit[0].query(l - 1) + bit[1].query(l - 1) * l - bit[2].query(l - 1);
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i]++;
        ans += query(a[i] + 1, n);
        add(a[i], a[i], 1);
    }
    cout << ans << "\n";
    for (int i = 1; i <= n - 1; i++) {
        ans += 2 * query(a[i] + 1, n) - n + 1;
        cout << ans << "\n";
    }
    return 0;
}