AcWing第82场周赛题解
本次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://cdkjz.cn/article/dcdgei.html
