Codeforces Round #898 (Div. 4)

首先庆祝自己上了绿名🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄

1873A - Short Sort

1873B - Good Kid

const int N=1e5+10;
int a[N];
void slove(){int n; cin>>n;pair<int,int> p={-1,INT32_MAX};for(int i=0;i<n;i++){cin>>a[i];if(a[i]<p.second){p.first=i; p.second=a[i];}}a[p.first]++;int ans=1;for(int i=0;i<n;i++) ans*=a[i];cout<<ans<<endl;
}

1873C - Target Practice
5个正方形的环，越内圈分数越高。那给出一个坐标我们判断它属于那个环就行。

onst int N=1e5+10;
void slove(){int n=10;int ans=0;for(int i=0;i<n;i++){getchar();int x=min(abs(i-4),abs(i-5));for(int j=0;j<n;j++){int y=min(abs(j-4),abs(j-5));int k=5-max(x,y);char c=getchar();if(c=='X'){ans+=k;}}       }cout<<ans<<endl;
}

1873D - 1D Eraser
给出一个01串和一个数字k，你每次最多可以选择连续的k个元素让它们全部变成0，问最少需要多少次操作
思路：贪心+滑动窗口。

const int N=2e5+10;
int a[N];
void slove(){int n,k; cin>>n>>k;string s; cin>>s;for(int i=0;i<n;i++){if(s[i]=='W') a[i]=0;else a[i]=1;}int ans=0;for(int i=0,j=0,c=0;i<n;i++){if(a[i]){if(c==0) j=i;c++;}if(i-j+1==k || i==n-1){if(c){ans++;c=0;j=i+1;}}}cout<<ans<<endl;
}

1873E - Building an Aquarium
给出一个正整数数组，如果在两边加一个高度为h的边界，那么它就可以容纳一定体积的水。问最多有体积x的水，要装满，h最少为多少。
思路：二分答案。

const int N=2e5+10;
ll a[N];
void slove(){ll n,m; cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}ll ans=1,l=1,r=2e9+10;while(l<=r){ll mid=(l+r)>>1;ll sum=0;for(int i=0;i<n;i++){if(mid-a[i]>0) sum+=mid-a[i];}if(sum<=m){ans=mid;l=mid+1;}else{r=mid-1;}}cout<<ans<<endl;
}

1873F - Money Trees
滑动窗口元素之和问题。

const int N=2e5+10;
ll a[N],h[N];
void slove(){ll n,k; cin>>n>>k;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<n;i++) cin>>h[i];pair<ll,ll> p={0,-1};for(ll i=0,j=0,c=0;i<n;i++){if(i==0){c=a[0];}else{if(h[i-1]%h[i]){j=i; c=a[i];}else{c+=a[i];}}while(c>k){c-=a[j++];}if(i-j+1>p.second-p.first+1){p.first=j; p.second=i;}}printf("%d\n",p.second-p.first+1);
}

1873G - ABBC or BACB
给出一个A和B组成的字符串，你做以下两种操作：

把AB变成BC
把BA变成CB

问最多能进行多少次操作。

注意到第一种操作B会能左边连续的A消掉，第二种操作B能把右边连续的A消掉。

const int N=2e5+10;
void slove(){string s; cin>>s;int n=s.size();int ans=0;vector<int> ac;for(int i=0,c=0;i<n;i++){if(s[i]=='A') c++;else {ac.push_back(c);c=0;}if(i==n-1) ac.push_back(c);}sort(ac.begin(),ac.end());for(int i=ac.size()-1;i>0;i--){ans+=ac[i];}cout<<ans<<endl;
}

1873H - Mad City （补）
这题很有意思，给出一个无向图，A和B所在的点，A想要抓B，B在A行动前马上可以知道然后逃跑。问B能否一直不被抓到。
当时做的时候想的是如果A和B都在环里面，B就可以一直不被抓到；否则就一定会被抓到。但还是漏掉了一些情况。

可以分几种情况：

A和B一开始在同一个地方，Flase
无环，Flase
B在环内，A在环外，True
A在环内，B在环外，这种情况就比较复杂了，要根据A和B各自到环内各个点的最短距离来判断

今天捣鼓了好久终于把这题ak了qaq。

const int N=2e5+10;
struct edge{int u,v;
};
vector<edge> es[N]; 
void slove(){int n,s,t; cin>>n>>s>>t;vector<int> d(n+1);for(int i=1;i<=n;i++) es[i].clear();for(int i=0;i<n;i++){int u,v;  cin>>u>>v;es[u].push_back({u,v}); es[v].push_back({v,u});d[v]++; d[u]++;}if(s==t){printf("NO\n");return;}queue<int> q;for(int i=1;i<=n;i++) if(d[i]==1) q.push(i);while(!q.empty()){int u=q.front(); q.pop();for(auto &e:es[u]){int v=e.v;if(--d[v]==1) q.push(v);}}bool ce=false;for(int i=1;i<=n;i++){if(d[i]>=2){ce=true;break;}}if(!ce) {printf("NO\n");return;}else if((d[s]&d[t])>=2) {printf("YES\n");return;}map<int,int> ds;vector<int> vis(n+1);q.push(s);for(int i=0;;i++){int m=q.size();if(!m) break;for(int j=0;j<m;j++){int u=q.front(); q.pop();vis[u]=1;if(d[u]>=2) {ds[u]=i;}for(auto e:es[u]){if(vis[e.v]) continue;vis[e.v]=1;q.push(e.v);}}}    bool flag=false;fill(vis.begin(),vis.end(),0);q.push(t);for(int i=0;;i++){int m=q.size();if(!m||flag) break;for(int j=0;j<m;j++){int u=q.front(); q.pop();vis[u]=1;if(d[u]>=2&&i<ds[u]&&u!=s) {flag=true;break;}for(auto e:es[u]){if(vis[e.v]) continue;vis[e.v]=1;q.push(e.v);}}}        if(flag) printf("YES\n");else printf("NO\n");
}