Visits: 322

Codeforces Round #631 (Div. 1) – Thanks, Denis aramis Shitov!

Dreamoon Likes Coloring

简单构造题。

首先判无解，无解的情况只有两种，要么所有数的和加起来 $<n$，要么第 $i$ 个数大于 $n-i+1$。

然后倒着构造，每次先尽量不重复的覆盖，若第 $i$ 个颜色的左端点 $< i$，则将左端点手动设置为 $i$ 即可。

时间复杂度 $\mathcal O(n)$。

#define Fail return print(-1), 0
const int N = 1e5 + 7;
int n, m, a[N], b[N];
ll s;

int main() {
    rd(n), rd(m), rda(a, m);
    for (int i = 1; i <= m; i++) s += a[i];
    if (s < n) Fail;
    for (int i = 1; i <= m; i++)
        if (a[i] > n - i + 1) Fail;
    for (int i = m, j = n + 1; i; i--) {
        b[i] = j -= a[i];
        if (b[i] < i) b[i] = j = i;
    }
    for (int i = 1; i <= m; i++) print(b[i], " \n"[i==m]);
    return 0;
}

Dreamoon Likes Sequences

简单计数题。

由于要求 $a$ 递增且前缀异或和也要递增，因此在二进制下，后一个数要比前一个数至少多一位。

因此将每一个位数的数的个数乘起来，注意由于可以不选这个位数，因此个数要 $+1$，然后由于最后至少要有一个数，所以最后再 $-1$。

时间复杂度 $\mathcal O(T \log n)$。

int n;

inline void solve() {
    rd(n), rd(P);
    if (P == 1) return print(0);
    modint ans = 1;
    int t = 1;
    while (t <= n) ans *= min(n, (t << 1) - 1) - t + 2, t <<= 1;
    print(ans - 1);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Drazil Likes Heap

贪心，从大到小依次考虑每个数，如果这个数可以删就删，不能跳过。

判断是否能删的方式为，删除这个数受到影响的最深的节点的深度是否 $> g$，如果 $> g$ 则说明可以删除。

但这题有个很大的坑点，给定的代码中要访问到编号为 $2^h \sim 2^{h+1}-1$ 的节点，然后又是多测，所以要清空两倍长度的数组。

然后就有大概一半人都因此 FST 了。。。

时间复杂度 $\mathcal O(n \log n)$。

const int N = 1 << 21 | 1;
int h, g, a[N], d[N], p[N], t;
pq<int> q;

inline int find(int p) {
    if (!a[ls] && !a[rs]) return p;
    if (a[ls] > a[rs]) return find(ls);
    return find(rs);
}

inline void work(int p) {
    if (!a[ls] && !a[rs]) return;
    if (a[ls] > a[rs]) return swap(a[p], a[ls]), ::p[a[p]] = p, work(ls);
    swap(a[p], a[rs]), ::p[a[p]] = p, work(rs);
}

inline int work() {
    while (d[find(p[q.top()])] == g) q.pop();
    int p = ::p[q.top()];
    q.pop();
    a[p] = 0, work(p);
    return p;
}

inline void solve() {
    rd(h), rd(g);
    for (int i = 1; i < (1 << (h + 1)); i++) a[i] = 0;
    rda(a, (1 << h) - 1), t = 0;
    d[1] = 1;
    for (int i = 2; i < (1 << h); i++) d[i] = d[i>>1] + 1;
    while (q.size()) q.pop();
    for (int i = 1; i < (1 << h); i++) q.push(a[i]), p[a[i]] = i;
    vi p;
    for (int i = 1; i <= (1 << h) - (1 << g); i++) p.pb(work());
    ll ans = 0;
    for (int i = 1; i < (1 << g); i++) ans += a[i];
    print(ans);
    for (int x : p) print(x, ' ');
    prints("");
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Dreamoon Likes Strings

题目太神仙了，先咕咕咕着。

Dreamoon Loves AA

题目太神仙了，先咕咕咕着。