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://pwwzsj.com/article/dcdgei.html