Codeforces Round #631 (Div. 2)

Author：我不会玩锐雯
发布时间：April 4, 2020
2060views
No comments
7215字数
Categories： ACM技能点

比赛链接：https://codeforces.com/contest/1330

A. Dreamoon and Ranking Collection

知识点：枚举

只需要枚举一遍，遇到没出现的数字如果还有可用场次则场次数量减一，否则输出答案退出循环。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 2e5 + 117;

int t;
int n, x;
int a[117];
bool vis[117];
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &x);
        memset(vis, false, sizeof(vis));
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            vis[a[i]] = true;
        }
        for(int i = 1; i <= 100; i++) {
            if(!vis[i]) {
                if(x) x--;
                else {
                    printf("%d\n", i - 1);
                    break;
                }
            }
            if(i == 100) {
                printf("%d\n", i + x);
                break;
            }
        }
    }
    return 0;
}

B. Dreamoon Likes Permutations

知识点：排列

思路：设序列中的最大值为x，则合法的情况只有前x项+后n-x项凑成排列和前n-x项+后x项凑成排列两种。那么问题就转化为给定一个序列判断是不是一个排列。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int t;
bool vis[MAXN];
int n, num, cnt;
int a[MAXN], ans[7][2];
bool check(int id, int len) {
    for(int i = 1; i <= len; i++) vis[i] = false;
    for(int i = 0; i < len; i++) vis[a[id + i]] = true;
    for(int i = 1; i <= len; i++)
        if(!vis[i]) return false;
    return true;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        num = 0;
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if(num < a[i]) num = a[i];
        }
        cnt = 0;
        if(check(0, num) && check(num, n - num)) {
            ans[cnt][0] = num;
            ans[cnt++][1] = n - num;
        }
        if(num * 2 != n && check(0, n - num) && check(n - num, num)) {
            ans[cnt][0] = n - num;
            ans[cnt++][1] = num;
        }
        printf("%d\n", cnt);
        for(int i = 0; i < cnt; i++) {
            printf("%d %d\n", ans[i][0], ans[i][1]);
        }
    }
    return 0;
}

C. Dreamoon Likes Coloring

知识点：构造

题意：题目中的$l_i$实际上是给了一个固定长度的块，起点可以是任意合法的点，在赛中花了点时间琢磨。

思路：在不影响前一个的情况下尽可能的往左放，但如果后面的无法填满则要适当的往右移。不合法的情况有两种：当前块必定会影响前面的块；后面的块无法填满后面的区间。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int n, m;
LL sum;
int a[MAXN], ans[MAXN];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    bool pr = true;
    if(sum < n) pr = false;//无法填满
    for(int i = 1; i <= m; i++) {
        if(!pr) break;
        if(i + a[i] - 1 > n) pr = false;//一定会影响到前一个
        else {
            ans[i] = max((LL)i, n - sum + 1);
            sum -= a[i];
        }
    }
    if(pr) {
        for(int i = 1; i <= m; i++) printf("%d ", ans[i]);
    } else puts("-1");
    return 0;
}

D. Dreamoon Likes Sequences

知识点：二进制+dp

划重点：a序列和b序列都严格递增

思路：若$b_i=1***$，则$a_{i+1}$应该满足什么条件？首先$a_i < a_{i+1}$，且满足$a_{i+1}>10000$。反证法：若$a_{i+1}$在区间$[1000,1111]$之间，则$b_{i+1}$在区间$[0000,0111]$之间，不满足b序列严格递增的条件；若$a_{i+1}$在区间$[0000,0111]$之间，则前i项里必定存在某个数大于$a_{i+1}$，也不满足a序列严格递增的条件。

结论：应使$a_i$的位数严格递增。问题转化为统计区间$[1,d]$中不同最高位的个数。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int t;
LL d, m;
LL ans, cnt[37];
void build() {//最高位为i的有多少个数
    LL num = 2, t = 1;
    for(int i = 0; i < 32; i++) {
        if(d < t) cnt[i] = 0;
        else if(d >= num - 1) cnt[i] = t;
        else cnt[i] = d - t + 1;
        num <<= 1;
        t <<= 1;
    }
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &d, &m);
        build();
        ans = 1;
        for(int i = 0; i < 32; i++) {
            ans = ans * (cnt[i] + 1) % m;
        }
        ans = ((ans - 1) % m + m) % m;
        printf("%lld\n", ans);
    }
    return 0;
}

E. Drazil Likes Heap

知识点：堆+贪心

题意：给了一个h阶完全大顶堆，需要删除一部分使得剩下一个g阶完全大顶堆的和最小。

划重点：大顶堆删除一个节点后是该节点的左右孩子中较大的一个上浮，g阶完全大顶堆应该存储在区间$[1，2^g-1]$中。

思路：要使剩下的和最小，贪心能删大的则删大的，关键在于怎么判断一个点能不能删。

能不能直接删除尽量大的数？不能。如下图所示，如果直接删除7、6、5、4会得到一个2阶大顶堆，而且和最小，但是存储的位置不对。
可以注意到删除根节点后上浮的总是较大的点，也就是说在整颗树中有一条链整体上移了，而这条链可以由dfs找到。如果我们发现链的底端已经在区间$[1，2^g-1]$中了，则该点不能删除，因为删除该点后会使该链再次上移而没有子节点能够补充。如下图所示，如果删除根节点5，则4会上移，左子树为空不符合存储的要求。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 3e6 + 117;
const int MAXM = 2e5 + 117;

int t;
LL sum;
int a[MAXN];
int ans[MAXN], tot;
int h, g, maxnum, tonum;
void init() {
    sum = tot = 0;
    tonum = 1 << g;
    maxnum = 1 << h;
    for(int i = 0; i < maxnum * 2; i++) a[i] = 0;
}
int getid(int i) {
    if(a[i * 2] == 0 && a[i * 2 + 1] == 0) return i;
    if(a[i * 2] >= a[i * 2 + 1]) return getid(i * 2);
    return getid(i * 2 + 1);
}
void update(int i) {
    if(a[i * 2] == 0 && a[i * 2 + 1] == 0) a[i] = 0;
    else if(a[i * 2] >= a[i * 2 + 1]) {
        a[i] = a[i * 2];
        update(i * 2);
    } else {
        a[i] = a[i * 2 + 1];
        update(i * 2 + 1);
    }
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &h, &g);
        init();
        for(int i = 1; i < maxnum; i++) scanf("%d", &a[i]);
        for(int i = 1; i < tonum; i++) {
            while(getid(i) >= tonum) {
                ans[tot++] = i;
                update(i);
            }
        }
        for(int i = 1; i < tonum; i++) sum += a[i];
        printf("%lld\n", sum);
        for(int i = 0; i < tot; i++) printf("%d ", ans[i]);
        putchar(10);
    }
    return 0;
}

总结

或许是很久没打cf了，又或者是打cf的次数太少了，感觉这一场div2的难度低于自己的预期。然而在赛中码代码的效率和读题的能力仍然不够，例如B题赛中写了完全没必要的前缀和、C题花了40多分钟、D题题意没把握到。幸好正确率还可以，cf的hack机制真是可怕，希望继续保持正确率。

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/133/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

Last modification：April 5th, 2020 at 12:04 am

如果觉得我的文章对你有用，请随意赞赏

Codeforces Round #631 (Div. 2)

我不会玩锐雯 • 2020 年 04 月 04 日

比赛链接：https://codeforces.com/contest/1330

A. Dreamoon and Ranking Collection

知识点：枚举

只需要枚举一遍，遇到没出现的数字如果还有可用场次则场次数量减一，否则输出答案退出循环。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e5 + 117;
const int MAXM = 2e5 + 117;

int t;
int n, x;
int a[117];
bool vis[117];
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &x);
        memset(vis, false, sizeof(vis));
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            vis[a[i]] = true;
        }
        for(int i = 1; i <= 100; i++) {
            if(!vis[i]) {
                if(x) x--;
                else {
                    printf("%d\n", i - 1);
                    break;
                }
            }
            if(i == 100) {
                printf("%d\n", i + x);
                break;
            }
        }
    }
    return 0;
}

B. Dreamoon Likes Permutations

知识点：排列

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int t;
bool vis[MAXN];
int n, num, cnt;
int a[MAXN], ans[7][2];
bool check(int id, int len) {
    for(int i = 1; i <= len; i++) vis[i] = false;
    for(int i = 0; i < len; i++) vis[a[id + i]] = true;
    for(int i = 1; i <= len; i++)
        if(!vis[i]) return false;
    return true;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        num = 0;
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if(num < a[i]) num = a[i];
        }
        cnt = 0;
        if(check(0, num) && check(num, n - num)) {
            ans[cnt][0] = num;
            ans[cnt++][1] = n - num;
        }
        if(num * 2 != n && check(0, n - num) && check(n - num, num)) {
            ans[cnt][0] = n - num;
            ans[cnt++][1] = num;
        }
        printf("%d\n", cnt);
        for(int i = 0; i < cnt; i++) {
            printf("%d %d\n", ans[i][0], ans[i][1]);
        }
    }
    return 0;
}

C. Dreamoon Likes Coloring

知识点：构造

题意：题目中的$l_i$实际上是给了一个固定长度的块，起点可以是任意合法的点，在赛中花了点时间琢磨。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int n, m;
LL sum;
int a[MAXN], ans[MAXN];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    bool pr = true;
    if(sum < n) pr = false;//无法填满
    for(int i = 1; i <= m; i++) {
        if(!pr) break;
        if(i + a[i] - 1 > n) pr = false;//一定会影响到前一个
        else {
            ans[i] = max((LL)i, n - sum + 1);
            sum -= a[i];
        }
    }
    if(pr) {
        for(int i = 1; i <= m; i++) printf("%d ", ans[i]);
    } else puts("-1");
    return 0;
}

D. Dreamoon Likes Sequences

知识点：二进制+dp

划重点：a序列和b序列都严格递增

结论：应使$a_i$的位数严格递增。问题转化为统计区间$[1,d]$中不同最高位的个数。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e5 + 117;
const int MAXM = 2e5 + 117;

int t;
LL d, m;
LL ans, cnt[37];
void build() {//最高位为i的有多少个数
    LL num = 2, t = 1;
    for(int i = 0; i < 32; i++) {
        if(d < t) cnt[i] = 0;
        else if(d >= num - 1) cnt[i] = t;
        else cnt[i] = d - t + 1;
        num <<= 1;
        t <<= 1;
    }
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &d, &m);
        build();
        ans = 1;
        for(int i = 0; i < 32; i++) {
            ans = ans * (cnt[i] + 1) % m;
        }
        ans = ((ans - 1) % m + m) % m;
        printf("%lld\n", ans);
    }
    return 0;
}

E. Drazil Likes Heap

知识点：堆+贪心

题意：给了一个h阶完全大顶堆，需要删除一部分使得剩下一个g阶完全大顶堆的和最小。

划重点：大顶堆删除一个节点后是该节点的左右孩子中较大的一个上浮，g阶完全大顶堆应该存储在区间$[1，2^g-1]$中。

思路：要使剩下的和最小，贪心能删大的则删大的，关键在于怎么判断一个点能不能删。

能不能直接删除尽量大的数？不能。如下图所示，如果直接删除7、6、5、4会得到一个2阶大顶堆，而且和最小，但是存储的位置不对。
可以注意到删除根节点后上浮的总是较大的点，也就是说在整颗树中有一条链整体上移了，而这条链可以由dfs找到。如果我们发现链的底端已经在区间$[1，2^g-1]$中了，则该点不能删除，因为删除该点后会使该链再次上移而没有子节点能够补充。如下图所示，如果删除根节点5，则4会上移，左子树为空不符合存储的要求。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 3e6 + 117;
const int MAXM = 2e5 + 117;

int t;
LL sum;
int a[MAXN];
int ans[MAXN], tot;
int h, g, maxnum, tonum;
void init() {
    sum = tot = 0;
    tonum = 1 << g;
    maxnum = 1 << h;
    for(int i = 0; i < maxnum * 2; i++) a[i] = 0;
}
int getid(int i) {
    if(a[i * 2] == 0 && a[i * 2 + 1] == 0) return i;
    if(a[i * 2] >= a[i * 2 + 1]) return getid(i * 2);
    return getid(i * 2 + 1);
}
void update(int i) {
    if(a[i * 2] == 0 && a[i * 2 + 1] == 0) a[i] = 0;
    else if(a[i * 2] >= a[i * 2 + 1]) {
        a[i] = a[i * 2];
        update(i * 2);
    } else {
        a[i] = a[i * 2 + 1];
        update(i * 2 + 1);
    }
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &h, &g);
        init();
        for(int i = 1; i < maxnum; i++) scanf("%d", &a[i]);
        for(int i = 1; i < tonum; i++) {
            while(getid(i) >= tonum) {
                ans[tot++] = i;
                update(i);
            }
        }
        for(int i = 1; i < tonum; i++) sum += a[i];
        printf("%lld\n", sum);
        for(int i = 0; i < tot; i++) printf("%d ", ans[i]);
        putchar(10);
    }
    return 0;
}

总结

版权属于：小影
本文链接：http://kindkidll.com/index.php/archives/133/
所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

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

总结

Leave a Comment Cancel reply

【每日一题】4月7日树

链式前向星

handsome主题修改记录

红黑树入门

【每日一题】4月2日月月查华华的手机

Educational Codeforces Round 143 (Rated for Div. 2)

牛客小白月赛30

【每日一题】4月6日数码

SOS DP

【每日一题】4月1日 Rinne Loves Edges

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

总结