Atcoder Beginner Contest 379 (A-F)
A - Cyclic
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
char a,b,c;
cin>>a>>b>>c;
cout<<b<<c<<a<<" "<<c<<a<<b<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
B - Strawberries
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int n,k;
cin>>n>>k;
string s;
cin>>s;
int ans=0;
for(int i=0,j=0;i<n;){
while(j<n&&s[j]==s[i]) j++;
if(s[i]=='O') ans+=(j-i)/k;
i=j;
}
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
C - Sowing Stones
对比其余 \(C\) 题，算是有点难度的。首先如果棋子之和不等于 \(n\) ，或者最小的 \(x_i\) 不为 \(1\) ，那么无解。
因为每个棋子只能往后移动，因此我们直接贪心往后放即可。相邻的 \(x_i\) 之间的都需要移动，发现贡献是一个等差数列。
直接求即可。如果数量不够，说明无解。多的棋子直接给下一个 \(x_i\) ，注意这部分也要算贡献。最后判断一下棋子有没有剩余即可。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int n,m;
cin>>n>>m;
vector<pair<int,int>> a(m+1);
for(int i=0;i<m;i++) cin>>a[i].first;
i64 sum=0;
for(int i=0;i<m;i++) {
int x;
cin>>x;
sum+=x;
a[i].second=x;
}
a[m].first=n+1;
sort(a.begin(),a.end());
if(sum!=n||a[0].first!=1) return cout<<"-1\n",void();
i64 ans=0;
for(int i=0;i<m;i++){
a[i].second--;
int d=a[i+1].first-a[i].first-1;
if(a[i].second<d) return cout<<"-1\n",void();
ans+=1LL*d*(d+1)/2;
if(a[i].second>d){
a[i+1].second+=(a[i].second-d);
ans+=1LL*(a[i].second-d)*(a[i+1].first-a[i].first);
}
}
if(a[m].second) ans=-1;
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
D - Home Garden 思维
因为只有全局加操作，因此我们可以使用类似懒标记的思想，将所有的加操作加到标记上，那么插入一个新花盆的时候，我们可以赋初值为 \(-sum\) 。然后维护好单调性，有多少个大于 \(h\) 我们直接二分即可。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int q;
cin>>q;
int hh=q,tt=q;
vector<i64> a(q);
i64 sum=0;
while(q--){
int op;
cin>>op;
if(op==1){
a[--hh]=-sum;
}else if(op==2){
int t;
cin>>t;
sum+=t;
}else{
int h;
cin>>h;
int p=lower_bound(a.begin()+hh,a.begin()+tt,h-sum)-(a.begin()+hh);
cout<<tt-hh-p<<"\n";
tt=hh+p;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
E - Sum of All Substrings
经典的拆分算贡献的题目，我们发现每一位数字的贡献为 \(i\times a_i \times(10^0+10^1+...+10^{n-i})\)。
等差数列求和即可。但是本题数据范围很大，要用高精度，复杂难写。我们可以用数组存取每一位的系数，
那么每次操作，就相当于区间加上一个系数，用差分解决即可。最后模拟处理一下进位即可。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int n;
cin>>n;
string s;
cin>>s;
s="?"+s;
vector<i64> a(500010);
for(int i=1;i<=n;i++){
int x=n-i+1,y=i*(s[i]-'0');
a[1]+=y;a[x+1]-=y;
}
for(int i=1;i<=n;i++) a[i]+=a[i-1];
i64 k=0;
for(int i=1;i<=n;i++){
a[i]+=k;
k=a[i]/10;
a[i]%=10;
}
int cnt=n;
while(k){
a[++cnt]=k%10;
k/=10;
}
for(int i=cnt;i;i--) cout<<a[i];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}
F - Buildings 2
首先我们可以知道：\(l\) 能够看到的建筑物 \(r\) 一定能够看到， \(r\) 能够看到的建筑物 \(l\) 不一定能够看到。
因此想要找 \(l,r\) 都能够看到的建筑物，只需要去找 \(l\) 能够看到的建筑物中位置在 \(r\) 右边的即可。
考虑离线，将询问按照左端点进行分类。每个位置能够看到的建筑物，我们可以倒着维护一个单调队列。
然后在这个单调队列上进行二分即可。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){
int n,q;
cin>>n>>q;
vector<int> h(n+1);
vector<array<int,2>> Q[n+1];
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
Q[l].push_back({r,i});
}
vector<int> st(n+1),ans(q+1);
int cnt=0;
for(int i=n;i;i--){
for(auto [j,id]:Q[i]){
int l=1,r=cnt;
while(l<r){
int mid=l+r+1>>1;
if(st[mid]>j) l=mid;
else r=mid-1;
}
if(st[l]<=j) ans[id]=0;
else ans[id]=l;
}
while(cnt&&h[st[cnt]]<h[i]) cnt--;
st[++cnt]=i;
}
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
//cin>>t;
while(t--){
Showball();
}
return 0;
}