AtCoder Beginner Contest 372
A - delete .
题目：
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
string s;
cin>>s;
for(auto &x: s){
if(x!='.') cout<<x;
}
return 0;
}B - 3^A
题目：
思路：
预处理出3的0~10次方的值，从大到小，找到第一个不大于m的数x，m-=x；
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int m;
cin>>m;
vector<int> b,a;
int t=1;
b.push_back(t);
for(int i=1; i<=10; i++){
t*=3;
b.push_back(t);
}
int cnt=0;
int len=b.size();
// for(int i=0; i<len; i++) cout<<b[i]<<' ';
// cout<<'\n';
int p=len-1;
while(m>0){
while(b[p]>m && p>=0) p--;
m-=b[p];
cnt++;
a.push_back(p);
}
cout<<cnt<<'\n';
// int tt=0;
for(int i=0; i<a.size(); i++){
// tt+=b[a[i]];
cout<<a[i]<<' ';
}
cout<<'\n';
// cout<<tt<<'\n';
return 0;
}C - Count ABC Again
题目：
思路：
先统计出原串中ABC的数量cnt，由于每次只修改一个字符，且该字符只会增加或减少一个ABC，所以可以检查每次操作是否破坏了ABC cnt--，是否增加了ABC cnt++；
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int n,q;
cin>>n>>q;
string s;
cin>>s;
vector<int> x(q);
string c(q,'.');
string s0="ABC";
int res=0;
for(int i=0; i<n; i++){
if(s[i]=='A'){
string ss="";
for(int j=i; j<min(i+3,n); j++){
ss+=s[j];
}
if(ss==s0){
res++;
}
}
}
for(int i=0; i<q; i++){
cin>>x[i]>>c[i];
x[i]--;
int t=x[i];
if(s[t]=='A' && s[min(n-1,t+1)]=='B' && s[min(n-1,t+2)]=='C'){
res--;
// cout<<s[t]<<s[min(n-1,t+1)]<<s[min(n-1,t+2)]<<'\n';
}
else if(s[max(0,t-1)]=='A' &&s[t]=='B' && s[min(t+1,n-1)]=='C'){
res--;
// cout<<s[max(0,t-1)]<<s[t]<<s[min(n-1,t+1)]<<'\n';
}
else if(s[t]=='C' && s[max(0,t-1)]=='B' && s[max(0,t-2)]=='A'){
// cout<<s[max(0,t-2)]<<s[max(0,t-1)]<<s[t]<<'\n';
res--;
}
// cout<<" r1: "<<res<<'\n';
s[t]=c[i];
if(s[t]=='A' && s[min(n-1,t+1)]=='B' && s[min(n-1,t+2)]=='C'){
res++;
// cout<<"<<1"<<n-1<<' '<<t+2<<'\n';
// cout<<res<<'\n';
// cout<<s[t]<<s[min(n-1,t+1)]<<s[min(n-1,t+2)]<<'\n';
}
else if(s[max(0,t-1)]=='A' &&s[t]=='B' && s[min(t+1,n-1)]=='C'){
// cout<<"<<2";
res++;
// cout<<s[max(0,t-1)]<<s[t]<<s[min(n-1,t+1)]<<'\n';
}
else if(s[t]=='C' && s[max(0,t-1)]=='B' && s[max(0,t-2)]=='A'){
// cout<<"<<3";
// cout<<s[max(0,t-2)]<<s[max(0,t-1)]<<s[t]<<'\n';
res++;
}
if(res<=0) res=0;
// cout<<s<<'\n';
// cout<<" r2: ";
cout<<res<<'\n';
}
return 0;
}D - Buildings：
题目：
思路：
正难则反，反着去思考发现，只需维护一个高度的单调栈即可，如果栈顶元素小于当前元素，将栈顶弹出，直到栈顶不小于当前元素，当前元素入栈，每个位置的答案，为在当前位置元素入栈前，栈的大小。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int main()
{
int n;
cin>>n;
vector<int> a(n), res(n);
for(int i=0; i<n; i++) cin>>a[i];
stack<int> sk;
for(int i=n-1; i>=0; i--){
res[i]=sk.size();
while(sk.size() && sk.top()<a[i]){
sk.pop();
}
sk.push(a[i]);
}
for(int i=0; i<n; i++) cout<<res[i]<<' ';
cout<<'\n';
return 0;
}E - K-th Largest Connected Components
题目：
、
思路：
并查集（+启发式合并）+维护每个根节点前十大的节点编号
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=2e5+10;
int p[N], sz[N];
vector<int> d[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
int n,q;
cin>>n>>q;
for(int i=1; i<=n; i++){
p[i]=i,sz[i]=1;
d[i].push_back(i);
}
while(q--){
int op, u, v;
cin>>op>>u>>v;
if(op==1){
int pa=find(u), pb=find(v);
if(pa!=pb){
if(sz[pa]<sz[pb]){
sz[pb]+=sz[pa];
p[pa]=pb;
for(int i=0; i<d[pa].size(); i++){
d[pb].push_back(d[pa][i]);
}
sort(d[pb].begin(),d[pb].end(),greater<int>());
while(d[pb].size()>10){
d[pb].pop_back();
}
}
else{
sz[pa]+=sz[pb];
p[pb]=pa;
for(int i=0; i<d[pb].size(); i++){
d[pa].push_back(d[pb][i]);
}
sort(d[pa].begin(),d[pa].end(),greater<int>());
while(d[pa].size()>10){
d[pa].pop_back();
}
}
}
}
else{
int pa=find(u);
if(d[pa].size()<v) cout<<-1<<'\n';
else{
cout<<d[pa][v-1]<<'\n';
}
}
}
return 0;
}