RELATEED CONSULTING
相关咨询
选择下列产品马上在线沟通
服务时间:8:30-17:00
你可能遇到了下面的问题
关闭右侧工具栏

新闻中心

这里有您想知道的互联网营销解决方案
AcWing第82场周赛题解-创新互联
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场周赛题解-创新互联
分享URL:http://lswzjz.com/article/dcdgei.html