Codeforces Round #758 (Div.1 + Div. 2) A-B题解

发布于 2021-12-11  459 次阅读


内容纲要

A. Find Array

题目大意:

给出一个n, 构造出一个长度为n的数列,使得:

a_{1} < a_{2} < ... < a_{n}

对于每一个a_{i}都不能被a_{i-1}整除

题解:

没啥好说,直接从2开始输出n个数就好了。

代码:

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int k;
        scanf("%d", &k);
        for(int i = 2; i < k + 2; i++){
            printf("%d " , i);
        }
        printf("\n");
    }
}

B. Build the Permutation

题目大意:
给出n,a,b,要求构造一个长度为n,内容为1-n(不重复)的队列,有a个极大值,b个极小值(第一个和最后一个不算),如果不存在就输出-1。

题解:

稍微画一下就会发现abs(a-b)不能大于1且a+b不能大于n - 2,否则就是无法构造的出来的。

然后因为要从1-n中选,易得极小值一定是1到b中的数,极大值一定是n - a到n中的数,所以先轮流交替取,构造出包含1到b,n-a到n的数列,然后再根据最后一个构造的数是极大值还是极小值继续在中间的数中构造单独递增或者递减序列就可以了。

代码:

#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, a, b;
        cin >> n >> a >> b;
        int da = a, db = b;
        if (a + b > n - 2) {
            printf("-1\n");
            continue;
        }
        if (abs(a - b) > 1) {
            printf("-1\n");
            continue;
        }
        int flag;
        if(a > b){
            flag = 2;
        } else {
            flag = 1;
        }
        for (int i = 0; i < n; i++) {
            if((a == -1 && b == 0) || (a == 0 && b == -1)){
                break;
            }
            if (a >= 0 && flag != 1) {
                printf("%d ", (da - a) + 1);
                a--;
                flag = 1;
                continue;
            }
            if(b >= 0 && flag != 2){
                printf("%d ", n - (db - b));
                b--;
                flag = 2;
                continue;
            }
        }
        if(flag == 2){
            for(int i = n - db - 1; i >= da + 1; i--){
                printf("%d ", i);
            }
        } else {
            for(int i = da + 2; i <= n - db; i++){
                printf("%d ", i);
            }
        }
        printf("\n");
    }
}

总结

C没想出来,感觉挺复杂的,可能涉及到什么我还没学过的结构,等会了再补题。

前面两题还行吧,至少做出来了


不爱嘉然小姐十年了。十年里,爱过的每个人都像她。