AcWing第82场周赛题解

• A题
• • 题目链接
  • 题解
  • 复杂度分析
• B题
• • 题目链接
  • 题解
  • 复杂度分析
• C题
• • 题目链接
  • 题解
  • 复杂度分析

本次AcWing周赛主要还是要考察细节，难度不大。

成都创新互联长期为上千客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为田家庵企业提供专业的网站制作、成都网站制作，田家庵网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。A题 题目链接

第k个数

题解

#include#include#include 
using namespace std;
int main() {int n, k;
    cin >>n >>k;
    vectora(n);
    for (int i = 0; i< n; i++) {cin >>a[i];
    }
    sort(a.begin(), a.end());
    cout<< a[n - k]<< endl;
    return 0;
}

复杂度分析

快排，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)。

B题 题目链接

多米诺骨牌

题解

将各种情况考虑清楚即可。

#includeusing namespace std;
int main() {int n;
    cin >>n;
    int flag = 0;
    int ans = 0;
    int sum = 0;
    for (int i = 0; i< n; i++) {char c;
        cin >>c;
        if (c == '.') sum++;
        else {if (flag == 0 && c == 'L') {sum = 0;
                flag = -1;
            } else if (flag == 0 && c == 'R') {ans += sum;
                sum = 0;
                flag = 1;
            } else if (flag == -1 && c == 'R') {ans += sum;
                sum = 0;
                flag = 1;
            } else if (flag == 1 && c == 'L') {ans += sum % 2;
                sum = 0;
                flag = -1;
            }
        }
    }
    if (flag == 1) sum = 0;
    cout<< ans + sum<< endl;
    return 0;
}

复杂度分析

读入同时进行处理即可，时间复杂度为 O ( n ) O(n) O(n)。

C题 题目链接

构造序列

题解

根据题意，0必须单独，1最多可以存在两个，共有n个0和m个1，因而可以推出只有满足
n - 1 ≤ \leq ≤ m ≤ \leq ≤ 2 × \times × (n + 1)
才能构造出满足规则的序列。

#includeusing namespace std;
int main() {int n, m;
    cin >>n >>m;
    if (m< n - 1 || m >2 * (n + 1)) cout<< -1<< endl;
    else {string s = "";
        if (n >m) s += "0";
        while (m >n && n) {s += "110";
            m -= 2;
            n -= 1;
        }
        while (m && n) {s += "10";
            m--;
            n--;
        }
        for (int i = 0; i< m; i++) {s += "1";
        }
        cout<< s<< endl;
    }
    return 0;
}

复杂度分析

明显可以 O ( n ) O(n) O(n)的时间复杂度完成构造。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文题目：AcWing第82场周赛题解-创新互联
标题路径：http://myzitong.com/article/dcdgei.html