Codeforces Round #631 (Div. 2)

48494 ワード
問題を解く
個人ブログ:http://www.kindkidll.com/index.php/archives/133/
試合リンク:https://codeforces.com/contest/1330
A. Dreamoon and Ranking Collection
ナレッジポイントナレッジポイント:列挙
一度列挙するだけで、現れていない数字がまだ利用可能な回数があれば、回数を1つ減らします.そうしないと、出力答えはループを終了します.
#include 
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
", i - 1);
                    break;
                }
            }
            if(i == 100) {
                printf("%d
", i + x);
                break;
            }
        }
    }
    return 0;
}

B. Dreamoon Likes Permutations
ナレッジポイントナレッジポイント:配置はいち
構想:シーケンス中の最大値をxとすると、合法的な場合は前x項+後n-x項のコンパクト配列と前n-x項+後x項のコンパクト配列の2種類しかない.すると問題は,あるシーケンスが配列であるか否かを判断することに転化する.
#include 
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
", cnt);
        for(int i = 0; i < cnt; i++) {
            printf("%d %d
", ans[i][0], ans[i][1]);
        }
    }
    return 0;
}

C. Dreamoon Likes Coloring
ナレッジポイントナレッジポイント:構築こうぞう
标题:标题中のl i l_i liは実際には固定長のブロックを与えており、起点は任意の合法的な点であり、試合で時間をかけて考えている.
考え方:前に影響を及ぼさずにできるだけ左に置くが、後ろの埋めきれない場合は適切に右に移動する.不法な場合は2つあります.現在のブロックは必ず前のブロックに影響します.後ろのブロックは後ろの区間を埋めることができません.
#include 
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∗∗∗b_i=1***bi=1∗∗∗、a i+1 a_ai+1はどんな条件を満たすべきですか?まずa i10000 a_满足的{i+1}>10000 ai+1>10000.反証法:a i+1 a_{i+1}ai+1区間[1001111][1001111][1001111]間,b i+1 b_{i+1}bi+1在区间[0000111][0000111][0000111][0000111]之间,不满足b系统的严密增加条件.a i+1 a_{i+1}ai+1区間[0000111][0000111][0000111][0000111]の間には、前のi項において、a i+1 aより大きい数が必ず存在する{i+1}ai+1も、aシキスが厳しく増加する条件を満たさない.結論:a i a_i ai的比特数严格增加了.问题是统计区间[1,d][1,d][1,d][1,d]中的不同的最高位的个数变换。include 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", ans); } return 0; } E.Drazil Likes Heap知识点:工作+想张题意:给予h次完全大顶工作,如果剩下的g次完全大顶工作的和最小,需要部分删除.积分:大屋根斯塔克删除了1个诺片后,在那个诺片左右的孩子中浮出很大,g层完全大屋根斯塔克应该区间[1,2 g-1][1,2^g-1][1,2 g-1][1,2 g-1][1,2 g-1][1,2 g-1][1,2 g-1]被划分.考虑方:剩下和最小,可以大幅削减贪欲的东西,判断肝脏是怎么能削减一点?
  • 可以直接删除大的数量吗?できません.正如下图所示,直接删除7、6、5、4的话,可以得到2次大的工作,最小,但是被格纳的地方不同.Codeforces Round #631 (Div. 2)_第1张图片
  • は、ルートノードを削除した後に浮上する常に大きな点、すなわち、ツリー全体にわたってチェーンが全体的に移動し、このチェーンはdfsによって見つけることができることに気づくことができる.チェーンの下端が区間[1,2 g−1][1,2^g−1][1,2 g−1][1,2 g−1]にあることを発見した場合、この点は削除できない.この点を削除すると、サブノードが補充できないため、チェーンが再び上に移動する.下図に示すように、ルートノード5を削除すると、4が上に移動し、左サブツリーが空でストレージの要件に合致しません.Codeforces Round #631 (Div. 2)_第2张图片 
    • #include 
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
    "    , sum);
        for(int i = 0; i < tot; i++) printf("%d ", ans[i]);
        putchar(10);
    }
    return 0;
}

    まとめ
    久しぶりにcfを打ったのか、cfを打つ回数が少なすぎたのか、div 2の難易度が自分の予想を下回ったような気がします.しかし、試合中のコードの効率と問題を読む能力はまだ足りない.例えば、B問題試合で全く必要のない接頭辞とC問題を書いたのに40分以上かかり、D問題の意味が把握できなかった.幸い正解率はまあまあですが、cfのhackメカニズムは本当に怖いので、正解率を維持し続けたいです.
    ipの固定とホスト名の設定
    2行のコード、1時間理解しました!2つの配列は隣接テーブルを記録します!(劉汝佳白書)