比赛链接:https://atcoder.jp/contests/abc372
开头:
过去一个多月了,虽然暑假就上了蓝,但感觉自已一直还没达到蓝的水准,网络赛也打了两场,打的一般,开学之后一直比较忙,现在稳定了下来,接下来打算尽量每周3-4篇atcoder的题解吧,这是这周第一篇,虽然有点水(
A. delete .
思路:
签到题
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
std::string s;
std::cin>>s;
for(int i=0;i<s.size();i++){
if(s[i]!='.'){
std::cout<<s[i];
}
}
std::cout<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}
B. 3^A
思路:
以开始读错题了,然后卡了会,其实就是转化成三进制
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
i64 n;
std::cin>>n;
std::vector<i64> a(21);
a[0]=1;
for(int i=1;i<=20;i++){
a[i]=a[i-1]*3;
}
std::vector<int> res(21,0);
int cnt=0;
for(int i=20;i>=0;i--){
if(n>=a[i]){
n-=a[i];
res[i]=1;
cnt++;
if(n>=a[i]){
res[i]=2;
n-=a[i];
cnt++;
}
}
}
std::cout<<cnt<<'\n';
for(int i=0;i<=20;i++){
if(res[i]==1){
std::cout<<i<<' ';
}
else if(res[i]==2){
std::cout<<i<<' '<<i<<' ';
}
}
std::cout<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}
C. Count ABC Again
思路:
只看修改的位置即可,然后计数
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
int n,q;
std::cin>>n>>q;
std::string s;
std::cin>>s;
int res=0;
for(int i=0;i<n;i++){
if(s[i]=='A'&&i+2<n&&s[i+1]=='B'&&s[i+2]=='C'){
res++;
}
}
for(int i=1;i<=q;i++){
int x;char c;
std::cin>>x>>c;
x--;
if(s[x]=='A'){
if(x+2<n&&s[x+1]=='B'&&s[x+2]=='C'){
if(c!='A'){
res--;
}
}
}
else if(s[x]=='B'){
if(x+1<n&&x-1>=0&&s[x+1]=='C'&&s[x-1]=='A'){
if(c!='B'){
res--;
}
}
}
else if(s[x]=='C'){
if(x-2>=0&&s[x-1]=='B'&&s[x-2]=='A'){
if(c!='C'){
res--;
}
}
}
if(c=='A'){
if(x+2<n&&s[x+1]=='B'&&s[x+2]=='C'){
if(s[x]!='A'){
res++;
}
}
}
else if(c=='B'){
if(x+1<n&&x-1>=0&&s[x+1]=='C'&&s[x-1]=='A'){
if(s[x]!='B'){
res++;
}
}
}
else if(c=='C'){
if(x-2>=0&&s[x-1]=='B'&&s[x-2]=='A'){
if(s[x]!='C'){
res++;
}
}
}
s[x]=c;
std::cout<<res<<'\n';
}
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}
D. Buildings
思路:
自己没想出来,但思路是有的,看来题解后明白了
其实就是求每个点之后的单调递增的子序列,每个点的后一个点必定在子序列中,同时为了降低时间复杂度,从后往前遍历,这样一次遍历就求出了所有的结果,当要插入的数比栈顶大时,栈就要弹出
代码:
#include<bits/stdc++.h>
using i64=long long;
void solve(){
int n;
std::cin>>n;
std::vector<int> a(n+1);
for(int i=1;i<=n;i++){
std::cin>>a[i];
}
std::vector<int> res(n+1,0);
std::stack<int> st;
for(int i=n-1;i>=1;i--){
while(st.size()&&a[st.top()]<a[i+1]){
st.pop();
}
st.push(i+1);
res[i]=st.size();
}
for(int i=1;i<=n;i++){
std::cout<<res[i]<<' ';
}
std::cout<<'\n';
}
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}
E. K-th Largest Connected Components(待补)
思路:
洛谷原题:永无乡
看了一下,基本上是并查集+FHQ,还没学到,待我学了再来补
代码: