C - Brave Seekers of Unicorns

令 dpℓ,xdp_{\ell, x} 表示以 xx 为结尾、长度为 ℓ\ell 的序列个数，同时，令 fx=∑ℓ=1ndpℓ,xf_x=\sum_{\ell=1}^n dp_{\ell, x}，即对不同长度的 dpxdp_x 进行求和。

对于 dpℓ,xdp_{\ell,x}，我们考虑怎么构造出结尾为 xx 的序列，那肯定是在长度为 ℓ−1\ell-1、结尾为 yy 的序列末尾添加一个元素 xx. 但是题目的限制又要求序列的倒数第三项不能是 y⊕xy\oplus x. 我们把这个思路写成 dpdp 的递推式：

dpℓ,x=∑y<xdpℓ−1,y−∑z:z<z⊕x<xdpℓ−2,z dp_{\ell,x}=\sum_{y\lt x} dp_{\ell-1, y} - \sum_{z:z\lt z\oplus x\lt x} dp_{\ell-2, z}

两边对 ℓ\ell 求和，并把 fx=∑ℓ=1ndpℓ,xf_x=\sum_{\ell=1}^n dp_{\ell,x} 代入上式：

fx=∑y<xfy−∑z:z<z⊕x<xfz f_x=\sum_{y\lt x} f_y - \sum_{z:z\lt z\oplus x\lt x} f_z

所以，我们可以从小到大枚举 xx 同时维护 ∑ifi\sum_i f_i 的前缀和。考虑怎么减去第二部分的和式，由于涉及到异或，我们从二进制拆位的角度考虑。

因为 z<xz\lt x，考虑最高位 p0p_0 使得 xp0=1,zp0=0x_{p_0}=1, z_{p_0}=0，故 z<z⊕xz\lt z\oplus x 一定是成立的。从高位向低位枚举，假设 xx 的最高位是 ww. 我们接下来只需要判断 z⊕x<xz\oplus x\lt x

  • 对于 p>wp\gt w，如果 xp=0x_p=0，那么 zpz_p 也必须 =0=0，不然若 =1=1，则会出现 z⊕x>xz\oplus x\gt x 的情况.

  • 若 p=wp=w，此时 zpz_p 也必须 =0=0.

  • 当 p<wp\lt w 时，考虑每一位 xp=1x_p=1，因为此时已经有 xw=1,zw=0,(z⊕x)w=1x_w=1, z_w=0, (z\oplus x)_w=1，

    • 假设 zp=1,(z⊕x)p=0z_p=1,(z\oplus x)_p=0，此时无论 zi,i<pz_i,i\lt p 取什么，z⊕x<xz\oplus x\lt x 这个不等式一定是成立的，所以可以直接减去一段区间的贡献：z∈[2p,2p+1)z\in[2^p, 2^{p+1})
    • 但若 zp=0,(z⊕x)p=1z_p=0, (z\oplus x)_p=1，此时 ziz_i 并不能任意取 0/10/1，不然异或的结果可能会 ≥x\ge x，需要继续判断后面的 bit.

所以总体时间复杂度 O(nlog⁡n)O(n\log n).

AC Code
 
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
#include <bits/stdc++.h>
constexpr int N = 1e6 + 10;
constexpr int B = 25;
 
template <int MOD = 998244353>
class Modulo {
  private:
    static int Pow(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) { res = (1ll * res * a) % MOD; }
            b >>= 1, a = (1ll * a * a) % MOD;
        }
        return res;
    }
    static int Inv(int x) { return Pow(x, MOD - 2); }
 
  public:
    int num;
    /*====================*/
    Modulo(long long temp = 0) { num = temp % MOD; }
    Modulo(const Modulo &temp) { num = temp.num; }
    /*====================*/
    constexpr friend Modulo operator+(const Modulo &a, const Modulo &b) {
        return Modulo((a.num + b.num) >= MOD ? a.num + b.num - MOD : a.num + b.num);
    }
    constexpr friend Modulo operator-(const Modulo &a, const Modulo &b) {
        return Modulo((a.num - b.num + MOD) >= MOD ? a.num - b.num : a.num - b.num + MOD);
    }
    constexpr friend Modulo operator*(const Modulo &a, const Modulo &b) { return Modulo(1ll * a.num * b.num % MOD); }
    constexpr friend Modulo operator/(const Modulo &a, const Modulo &b) {
        return Modulo(1ll * a.num * Inv(b.num) % MOD);
    }
    constexpr friend Modulo operator%(const Modulo &a, const Modulo &b) { return a; }
    /*====================*/
    constexpr friend bool operator<(const Modulo &a, const Modulo &b) { return a.num < b.num; }
    constexpr friend bool operator==(const Modulo &a, const Modulo &b) { return a.num == b.num; }
    constexpr friend bool operator>(const Modulo &a, const Modulo &b) { return a.num > b.num; }
    constexpr friend bool operator<=(const Modulo &a, const Modulo &b) { return a.num <= b.num; }
    constexpr friend bool operator!=(const Modulo &a, const Modulo &b) { return a.num != b.num; }
    constexpr friend bool operator>=(const Modulo &a, const Modulo &b) { return a.num >= b.num; }
    /*====================*/
    constexpr void operator+=(const Modulo &x) {
        num = num + x.num;
        if (num >= MOD) num -= MOD;
    }
    constexpr void operator-=(const Modulo &x) {
        num = num - x.num + MOD;
        if (num >= MOD) num -= MOD;
    }
    constexpr void operator*=(const Modulo &x) { num = 1ll * num * x.num % MOD; }
    constexpr void operator/=(const Modulo &x) { num = 1ll * num * Inv(x.num) % MOD; }
    constexpr void operator%=(const Modulo &x) { num = num % x.num; }
    /*====================*/
    friend std::ostream &operator<<(std::ostream &output, Modulo integer) {
        output << integer.num;
        return output;
    }
    friend std::istream &operator>>(std::istream &input, Modulo &integer) {
        int temp;
        input >> temp;
        integer = (temp % MOD + MOD) % MOD;
        return input;
    }
};
 
using Z = Modulo<998244353>;
 
int n;
Z dp[N], prefix[N], ans;
 
Z sum(int l, int r) {
    if (l > r) return 0;
    else return prefix[r] - prefix[l - 1];
}
 
int main() {
    std::cin >> n;
    dp[0] = prefix[0] = 1;
 
    for (int i = 1; i <= n; i++) {
        Z tmp = 0;
        // highest
        int h = B;
 
        int start = 0, end = 0;
        while (not(i >> h & 1)) h--;
 
        h--;
        int step = 1 << h;
        while (h >= 0) {
            while (h >= 0 && not(i >> h & 1)) h--, step >>= 1;
            if (h < 0) break;
 
            int s = start, e = end;
            s = 1 << h, e = (1 << (h + 1)) - 1;
            tmp += sum(s, std::min(e, i - 1));
            h--;
        }
 
        dp[i] = prefix[i - 1];
        dp[i] -= tmp;
 
        prefix[i] = prefix[i - 1] + dp[i];
    }
 
    ans = 0;
    for (int i = 1; i <= n; i++) ans += dp[i];
    std::cout << ans << "\n";
}

D - Bank Security Unification

令 dpidp_i 表示序列结尾取 fif_i 时的最大 security，那么可以得出一个 O(n2)O(n^2) 的递推式：枚举上一个序列的结尾

dpi=max⁡j<i(dpj+BitAnd(fj,fi)) dp_i=\max_{j\lt i} \Big( dp_j + \texttt{BitAnd}(f_j, f_i) \Big)

看到 BitAnd\tt BitAnd 当时就在猜是不是其实只需要维护 O(log⁡V)O(\log V) 个 dpdp 值就够了，想了一下不太严谨的证明。考虑最高位 pp 使得 fi[p]=1,fj[p]=1f_i[p]=1, f_j[p]=1，那么我们什么时候不应该直接在 fjf_j 后面直接添加 fif_i 呢？答案是，如果 ∃j′,fj′[p]=1\exist j', f_{j'}[p]=1，这样的话，最优解应该是 fj,fj′,fif_j, f_{j'}, f_i，这样可以多赚 2p2^p 的 security.

所以反过来说，我们对每一个 pp 维护 rightmost index ii 使得 fi[p]=1f_i[p]=1，然后 dpdp 的转移只需要从这 O(log⁡V)O(\log V) 个 candidate 里面转移即可。

时间复杂度 O(nlog⁡V)O(n\log V)

AC Code
 
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
#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 1e6 + 10;
constexpr int B = 60;

int n;
ll f[N], dp[N];
int R[B + 1];

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);

    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> f[i];

    for (int i = 1; i <= n; i++) {
        for (int b = B; b >= 0; b--) {
            int id = R[b];
            dp[i] = std::max(dp[id] + (f[id] & f[i]), dp[i]);
        }

        for (int b = B; b >= 0; b--) {
            if (f[i] >> b & 1) R[b] = i;
        }
    }

    std::cout << dp[n] << "\n";
}

G - Biological Software Utilities

计数，唉

首先当有奇数个点的时候必定为 00. 接着讨论 nn 为偶数的时候：

我们把过程分解成两部分，一部分将 nn 个点划分成 n2\frac{n}{2} 条边，另一部分是将这 n2\frac{n}{2} 条边连接成一棵树。

第一部分：选一个最大数，在剩下 n−1n-1 个数里选一个和它配对；再选剩下里最大的数，在剩下 n−3n-3 个数里选一个和它配对；……这样配对可以不重不漏。个数是 (n−1)!!=(n−1)(n−3)…⋅3⋅1(n-1)!!=(n-1)(n-3)\ldots \cdot 3\cdot 1

第二部分：考虑一条边连接到另一条边上的时候，我们一共有 44 种方法，一共连接 n2−1\frac{n}{2}-1 次边，故 4(n2−1)4^{(\frac{n}{2}-1)}；然后有多少种这样的树呢？我们把这 n2\frac{n}{2} 条边看作点，因为我们不关心边与边之间的连接关系，只关注连接，所以套用 Prufer 的结论，一共有 (n2)n2−2(\frac{n}{2})^{\frac{n}{2}-2} 种连接方式。

综上，方案数为

(n−1)!!×(n2)n2−2×4(n2−1) (n-1)!!\times (\frac{n}{2})^{\frac{n}{2}-2} \times 4^{(\frac{n}{2}-1)}
AC Code
 
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
#include <bits/stdc++.h>
using namespace std;

template <int MOD = 998244353>
class Modulo {
  private:
    static int Pow(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) { res = (1ll * res * a) % MOD; }
            b >>= 1, a = (1ll * a * a) % MOD;
        }
        return res;
    }
    static int Inv(int x) { return Pow(x, MOD - 2); }

  public:
    int num;
    /*====================*/
    Modulo(long long temp = 0) { num = temp % MOD; }
    Modulo(const Modulo &temp) { num = temp.num; }
    /*====================*/
    constexpr friend Modulo operator+(const Modulo &a, const Modulo &b) {
        return Modulo((a.num + b.num) >= MOD ? a.num + b.num - MOD : a.num + b.num);
    }
    constexpr friend Modulo operator-(const Modulo &a, const Modulo &b) {
        return Modulo((a.num - b.num + MOD) >= MOD ? a.num - b.num : a.num - b.num + MOD);
    }
    constexpr friend Modulo operator*(const Modulo &a, const Modulo &b) { return Modulo(1ll * a.num * b.num % MOD); }
    constexpr friend Modulo operator/(const Modulo &a, const Modulo &b) {
        return Modulo(1ll * a.num * Inv(b.num) % MOD);
    }
    constexpr friend Modulo operator%(const Modulo &a, const Modulo &b) { return a; }
    /*====================*/
    constexpr friend bool operator<(const Modulo &a, const Modulo &b) { return a.num < b.num; }
    constexpr friend bool operator==(const Modulo &a, const Modulo &b) { return a.num == b.num; }
    constexpr friend bool operator>(const Modulo &a, const Modulo &b) { return a.num > b.num; }
    constexpr friend bool operator<=(const Modulo &a, const Modulo &b) { return a.num <= b.num; }
    constexpr friend bool operator!=(const Modulo &a, const Modulo &b) { return a.num != b.num; }
    constexpr friend bool operator>=(const Modulo &a, const Modulo &b) { return a.num >= b.num; }
    /*====================*/
    constexpr void operator+=(const Modulo &x) {
        num = num + x.num;
        if (num >= MOD) num -= MOD;
    }
    constexpr void operator-=(const Modulo &x) {
        num = num - x.num + MOD;
        if (num >= MOD) num -= MOD;
    }
    constexpr void operator*=(const Modulo &x) { num = 1ll * num * x.num % MOD; }
    constexpr void operator/=(const Modulo &x) { num = 1ll * num * Inv(x.num) % MOD; }
    constexpr void operator%=(const Modulo &x) { num = num % x.num; }
    /*====================*/
    friend std::ostream &operator<<(std::ostream &output, Modulo integer) {
        output << integer.num;
        return output;
    }
    friend std::istream &operator>>(std::istream &input, Modulo &integer) {
        int temp;
        input >> temp;
        integer = (temp % MOD + MOD) % MOD;
        return input;
    }
};

using Z = Modulo<998244353>;

int n;

int main() {
    std::cin >> n;
    if (n % 2 == 1) {
        std::cout << "0\n";
        return 0;
    }

    Z ans = 1, half = n / 2;
    for (int i = 1; i <= n; i += 2) ans *= i;
    for (int i = 1; i <= n / 2 - 2; i++) ans *= half;
    for (int i = 1; i <= n / 2 - 1; i++) ans *= 4;

    std::cout << ans << "\n";
}

I - Binary Supersonic Utahraptors

把题目的式子化简一下发现和两人怎么走的无关，所以直接计算即可。

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    int r = 0;
    for (int i=1; i<=n+m; i++)
    {
        int c;
        cin >> c;
        r += c;
    }

    cout << abs(n - r);
}

J - Burnished Security Updates

读题目可知原图必定是二分图，二分图的 vertex cover 可以直接贪心做。时间复杂度 O(n)O(n).

AC Code
 
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
#include <bits/stdc++.h>
constexpr int N = 3e5 + 10;

int n, m;
int color[N], vis[N], size[N];
std::vector<int> G[N];

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);

    std::cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        std::cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }

    auto dfs = [&](auto F, int u, int fa, int c) -> void {
        vis[u] = true;
        color[u] = c;
        for (auto v : G[u]) {
            if (vis[v]) continue;
            F(F, v, u, 1 - c);
        }
    };
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        dfs(dfs, i, i, 1);
    }

    bool ok = true;
    for (int u = 1; u <= n; u++) {
        vis[u] = 0;
        for (auto v : G[u]) {
            if (color[u] == color[v]) ok = false;
        }
    }
    if (!ok) {
        std::cout << "-1\n";
        return 0;
    }

    auto count = [&](auto F, int u, int &c) -> int {
        int cnt = color[u];
        vis[u] = 1;
        c++;
        for (auto v : G[u]) {
            if (vis[v]) continue;
            cnt += F(F, v, c);
        }
        return cnt;
    };

    int ans = 0;
    for (int u = 1; u <= n; u++) {
        if (vis[u]) continue;
        int tot = 0;
        int cnt = count(count, u, tot);

        if (cnt * 2 > tot) ans += tot - cnt;
        else ans += cnt;
    }

    std::cout << ans << "\n";
}

M - Brilliant Sequence of Umbrellas

我们考虑先构造 { gi=gcd⁡(ai,ai+1) }\set{g_i=\gcd(a_i, a_{i+1})}，然后令 ai=gi−1×gia_i=g_{i-1}\times g_i 即可.

也就是要求 gcd⁡(gi,gi−2)=1\gcd(g_i, g_{i-2})=1，并且 gig_i 越小越好。所以可以 O(n)O(n) 构造 { gi }\set{g_i} 再 O(n)O(n) 构造 aia_i.

AC Code
 
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
#include <bits/stdc++.h>
#include <random>
using ll = long long;
constexpr ll maxv = 1e12;
constexpr int maxn = 1e6;

ll n, cnt;
std::vector<ll> g, ans;

void run() {
    std::cin >> n;

    g.clear(), ans.clear();
    g.push_back(1), g.push_back(2);
    ll p = 3, f = 0;
    while (g.size() < maxn) {
        while (std::gcd(p, g[f]) != 1) p++;
        g.push_back(p), f++, p++;
    }

    ans.push_back(1);
    for (int i = 1; i < g.size(); i++)
        if (g[i] * g[i - 1] <= n) ans.push_back(g[i] * g[i - 1]);
        else break;

    std::cout << ans.size() << "\n";
    for (auto i : ans) std::cout << i << " ";
    std::cout << "\n";
}

int main() {
    int t = 1;
    while (t--) run();
}

N - Best Solution Unknown

考虑一个数 aia_i 能不能吃完所有其他数，考察数组里的最大值 am=Ma_m=M，不妨设 i<mi\lt m. 要是 aia_i 可以吃掉整个数组，那么如果不吃掉 ama_m 那么就吃不完整个数组，反过来说，只要能吃掉 ama_m 就一定可以吃完整个数组。

也就是说我们只需要判断 aia_i 是否可以吃掉 ama_m. 由于 aj,j<ma_j,j\lt m 都有 aj<ama_j\lt a_m，所以 aia_i 的最优决策一定是把 a1…am−1a_1\dots a_{m-1} 全部吃完再来尝试吃掉 ama_m. 如果能全部吃掉，那么应该有

ai+m−2≥am a_i+m-2\ge a_m

现在问题被归约到一个子问题上，在 [1,m−1][1,m-1] 这个区间里，aia_i 可以吃完这个子区间内的所有数吗？同理，我们依然考虑子区间内的最大值 am′=M′a_{m'}=M'，不妨设 i<m′i\lt m' 则

ai+m′−2≥am′ a_i+m'-2\ge a_{m'}

于是可以进一步归约……所以我们可以考虑分治做法：每次考虑区间的最大值 am=Ma_m=M，在其左右两侧的某个 aia_i 想要吃掉整个数组，就必须先完全吃掉左侧/右侧，再跨过 ama_m 这关。于是这就对左右两侧的 aia_i 的下界有了一定限制。

每次向下递归时，必定抛弃一个元素 ama_m，因此至多 O(n)O(n) 层递归，每层递归都需要 O(log⁡n)O(\log n) 的时间查询最大值所在的下标和值。时间复杂度 O(nlog⁡n)O(n\log n).

AC Code
 
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
#include <bits/stdc++.h>
constexpr int N = 1e6 + 10;

int n, a[N];
std::array<int, N * 4> T;
std::vector<int> ans;

void pushup(int p) {
    int ls = p << 1, rs = p << 1 | 1;
    T[p] = a[T[ls]] > a[T[rs]] ? T[ls] : T[rs];
}
void build(int p = 1, int l = 1, int r = n) {
    if (l == r) {
        T[p] = l;
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    pushup(p);
}
std::pair<int, int> query(int ql, int qr, int p = 1, int l = 1, int r = n) {
    if (ql > r || qr < l) return {-1, -1};
    if (ql <= l && r <= qr) return {a[T[p]], T[p]};
    int mid = l + ((r - l) >> 1);
    return std::max(query(ql, qr, p << 1, l, mid), query(ql, qr, p << 1 | 1, mid + 1, r));
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    build();

    auto dfs = [&](auto F, int l, int r, int C) -> void {
        if (l > r) return;

        auto [V, index] = query(l, r);
        if (V >= C) ans.push_back(index);
        F(F, l, index - 1, std::max(C, V - index + l + 1));
        F(F, index + 1, r, std::max(C, V + index - r + 1));
    };
    dfs(dfs, 1, n, 0);

    std::cout << ans.size() << "\n";
    std::sort(ans.begin(), ans.end());
    for (auto x : ans) std::cout << x << " ";
    std::cout << "\n";
}
ICPC/NTU Training
License

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