A.Dreamoon and Ranking Collection

题意：

给 $a_n$ 和 $x$ 次操作，要求找到一个最大 $v$ ，使得在 $a_n$ 中最多添加 $x$ 个数能让 $a_n$ 中存在 $1 \sim v$ 中全部的数

题解：

从 $1$ 开始遍历，遇到未曾出现的数则让 $x$ 减 $1$ ，直到 $x$ 为 $0$ 停止，最终找到一个最大的 $v$ 就是答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
map<int, bool> mp;
void solve()
{
    int n, x;
    scanf("%d%d", &n, &x);
    mp.clear();
    for (int i = 0, t; i < n; i++)
    {
        scanf("%d", &t);
        mp[t] = 1;
    }
    int ans = 0;
    for (int i = 1; x; i++)
    {
        if (!mp[i])
        {
            mp[i] = 1;
            x--;
        }
        ans = i;
    }
    for (int i = ans;; i++)
    {
        if (!mp[i])
            break;
        ans = i;
    }
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Dreamoon Likes Permutations

题意：

给定 $a_n$ ,并且 $1 \leq a_i \leq n-1$
要求将 $a_n$ 切割成两部分，长度为 $l_1$ 和 $l_2$ ,其中 $l_1+l_2==n$ ，使得 $a_1 \sim a_{l_1} = [1,l_1]$ 并且 $a_{l_i+1} \sim a_{n} = [1,l_2]$ 。
如果存在则输出所有方案，否则输出 $0$

题解：

显然分出的两段是合法的，当且仅当

段的最大值等于段的长度
段内没有重复元素

于是先扫一遍得到正序倒序第一个重复元素的位置，再正反各扫一遍得到前缀后缀最大值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn], L[maxn], R[maxn];
void solve()
{
    memset(L, 0, sizeof(L));
    memset(R, 0, sizeof(R));
    int n, l, r;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    set<int> s;
    for (int i = 1; i <= n; i++)
    {
        if (s.find(a[i]) == s.end())
            s.insert(a[i]);
        else
        {
            l = i - 1;
            break;
        }
    }
    s.clear();
    for (int i = n; i >= 1; i--)
    {
        if (s.find(a[i]) == s.end())
            s.insert(a[i]);
        else
        {
            r = i + 1;
            break;
        }
    }
    for (int i = 1; i <= n; i++)
        L[i] = max(L[i - 1], a[i]);
    for (int i = n; i >= 1; i--)
        R[i] = max(R[i + 1], a[i]);
    vector<int> ans;
    for (int i = 1; i <= n; i++)
        if (i <= l && i + 1 >= r && L[i] == i && R[i + 1] == n - i)
            ans.push_back(i);
    printf("%d\n", ans.size());
    for (auto i : ans)
        printf("%d %d\n", i, n - i);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Dreamoon Likes Coloring（构造）

题意：

给定 $n$ 个无色的格子和 $l_m$ 长度序列，进行 $m$ 次操作，每次操作将 $[p_i,p_i+l_i-1]$ 的格子都涂成颜色 $i$ ，如果格子原先有颜色就将它覆盖
现要求每种颜色至少出现在一个格子上，且所有格子都要涂上颜色。要求设计一种涂色方案,如果存在方案就任意输出一组 $p_n$ ，否则输出 $-1$

题解：

先考虑方案不存在的情况：

$i+ l_i - 1>n$
$\sum_{i=1}^{m}{l_i} < n$

其余情况均有解，我们先令 $p_i=i$ ，然后 $i$ 从大到小遍历将它放到最右端即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
int l[maxn], p[maxn];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    ll sum = 0;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &l[i]);
        sum += l[i];
    }
    if (sum < n)
    {
        puts("-1");
        return 0;
    }
    for (int i = 1; i <= m; i++)
    {
        p[i] = i;
        if (i + l[i] - 1 > n)
        {
            puts("-1");
            return 0;
        }
    }
    int len = n;
    for (int i = m; i >= 1; i--)
    {
        if (len - l[i] + 1 > i)
        {
            p[i] = len - l[i] + 1;
            len -= l[i];
        }
        else
            break;
    }
    for (int i = 1; i <= m; i++)
        printf("%d ", p[i]);
    puts("");
    return 0;
}

D.Dreamoon Likes Sequences

题意：

给定 $d$ 和 $m$ ，让你构造一个数组 $a_n$ 满足 $1≤a_1<a_2<⋯<a_n≤d$ ，其中 $n \geq 1$
使数组 $b_i=b_{i−1}⊕a_i ,(i \geq 2)$ 且 $b_1=a_1$ 满足 $b_1<b_2<⋯<b_{n−1}<b_n$
求构造 $a_n$ 的方案数，答案模 $m$

题解：

考虑到异或的性质，所以对二进制下每个最高位相同的数只能取一个，比如取了 $2(10)$ 就不能取 $3(11)$ ,取了 $4(100)$ 就不能取 $5(101),6(110),7(111)$ ...
因此对于 $a_i$ 的每个数字而言，其二进制中最高位的那个 $1$ 的位置一定是唯一的，且是递增的
而对于二进制下每个最高位相同的数有 $(2^{i+1}-1)-(2^{i}-1)$ 种，再考虑到没有限定 $n$ ，所以这个二进制的最高位可以不取，因此对于每个二进制的方案有 $(2^{i+1}-1)-(2^{i}-1)+1$ 种
最终结果就是各个二进制相乘，但是要注意因为在每位都算上了当前位不取的情况，所以最终结果包含了各位都不取的情况，不满足 $n \geq 1$ ,所以最终结果要 $-1$
同时在算每一位的时候要特判一下 $n$ 和 $2^{i+1}-1$ 的大小，取较小者即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    ll ans = 1;
    for (int i = 0; i < 30; i++)
    {
        if ((1 << i) > n)
            break;
        ans = (ans * (min(n, (1 << (i + 1)) - 1) - (1 << i) + 2)) % m;
    }
    printf("%lld\n", (ans - 1 + m) % m);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Drazil Likes Heap（贪心）

题意：

首先给了 $n$ 阶完全大顶堆的概念：一共有 $2^n-1$ 个节点，且对每个节点 $i$ 都满足 $a_i<a_{\lfloor \frac{i}{2} \rfloor}$
给定 $h$ 和 $g$ 以及由 $2^h-1$ 个数组成的 $a_n$ ，要求从这 $h$ 阶完全大顶堆中删除 $2^h-2^g$ 个节点使它成为一个 $g$ 阶完全大顶堆，并且满足结点编号从 $1 \sim 2^g-1$ 且 $\sum_{i=1}^{2^g-1}{a_i}$ 最小
输出最终的 $\sum_{i=1}^{2^g-1}{a_i}$ 和依次删除的节点编号
并给定了一段伪代码告诉你如果删去一个节点
图片说明

题解：

从伪代码可以得出删除一个结点的方案就是用节点 $i$ 较大的子节点填充到节点 $i$ 的位置，继续向下递归
知道了删除的策略就可以从根节点 $1$ 开始向下遍历，对于每个节点 $i$ 来说，如果 $i$ 节点子树的高度大于 $g$ 说明必须要从中删去一些节点才满足要求，那么根据 $n$ 阶完全大顶堆的性质，要使结果最小肯定删除 $i$ 节点是最优的，因为在这棵子树中 $a_i$ 最大。根据这个策略删除 $2^h-2^g$ 个节点就是答案了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = (1 << 21) + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn];
int get_id(int x)
{
    if (!a[x << 1] && !a[x << 1 | 1])
        return x;
    if (a[x << 1] > a[x << 1 | 1])
        return get_id(x << 1);
    else
        return get_id(x << 1 | 1);
}
void dfs(int x)
{
    if (!a[x << 1] && !a[x << 1 | 1])
        a[x] = 0;
    else if (a[x << 1] > a[x << 1 | 1])
    {
        a[x] = a[x << 1];
        dfs(x << 1);
    }
    else
    {
        a[x] = a[x << 1 | 1];
        dfs(x << 1 | 1);
    }
}
void solve()
{
    int h, g;
    scanf("%d%d", &h, &g);
    for (int i = 1; i < 1 << (h + 1); i++)
        a[i] = 0;
    for (int i = 1; i < 1 << h; i++)
        scanf("%d", &a[i]);
    vector<int> ans;
    int limit = (1 << g) - 1;
    for (int i = 1; i < 1 << g; i++)
        while (get_id(i) > limit)
        {
            ans.push_back(i);
            dfs(i);
        }
    ll sum = 0;
    for (int i = 1; i < 1 << g; i++)
        sum += a[i];
    printf("%lld\n", sum);
    for (auto i : ans)
        printf("%d ", i);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

Codeforces Round #631 (Div. 2)

A.Dreamoon and Ranking Collection

题意：

题解：

B.Dreamoon Likes Permutations

题意：

题解：

C.Dreamoon Likes Coloring（构造）

题意：

题解：

D.Dreamoon Likes Sequences

题意：

题解：

E.Drazil Likes Heap（贪心）

题意：

题解：