比赛链接:ABC372
Problem A:
Code
#include <bits/stdc++.h>
using namespace std;
int main(){string S;cin>>S;for(int i=0;i<S.size();i++){if(S[i]!='.')cout<<S[i]<<endl;}return 0;
}
Problem B:
Sol
比以往的 B 难一些。先预处理出 3 的幂,然后贪心即可。
Code
#include <bits/stdc++.h>
using namespace std;
vector<int> A;
int power[20];
void init(){power[0]=1;for(int i=1;i<=10;i++)power[i]=power[i-1]*3;
}
int main(){init(); int M;cin>>M;for(int i=10;i>=0;i--){while(M>=power[i]){A.push_back(i);M-=power[i];}}//cout<<A.size()<<endl;for(int val:A)cout<<val<<' ';return 0;
}
Problem C:
Sol
水 C。6 个 if 秒杀。
Code
#include <bits/stdc++.h>
using namespace std;
int main(){string S;int N,Q;cin>>N>>Q>>S;int ans=0;for(int i=0;i<N-2;i++){if(S[i]=='A' && S[i+1]=='B' && S[i+2]=='C')ans++;}while(Q--){int X;char C;cin>>X>>C;X--;if(S[X]==C){cout<<ans<<endl;continue;}if(S[X-2]=='A' && S[X-1]=='B' && S[X]=='C' && C!='C')ans--;if(S[X-1]=='A' && S[X]=='B' && S[X+1]=='C' && C!='B')ans--;if(S[X]=='A' && S[X+1]=='B' && S[X+2]=='C' && C!='A')ans--;if(S[X-2]=='A' && S[X-1]=='B' && S[X]!='C' && C=='C')ans++;if(S[X-1]=='A' && S[X]!='B' && S[X+1]=='C' && C=='B')ans++;if(S[X]!='A' && S[X+1]=='B' && S[X+2]=='C' && C=='A')ans++;S[X]=C;cout<<ans<<endl;}return 0;
}
Problem D:
Sol
单调栈板子题。但是倒着维护,这样可以偷懒不写前缀和。
Code
#include<bits/stdc++.h>
using namespace std;
int H[maxn],ans[maxn];
stack<int> stk;
int main(){int N;cin>>N;for(int i=1;i<=N;i++)cin>>H[i];for(int i=N;i>0;i--){ans[i]=stk.size();while(stk.size() && stk.top()<H[i])stk.pop();stk.push(H[i]); }for(int i=1;i<=N;i++)cout<<ans[i]<<' ';return 0;
}