A - Repdigit
直接判三个数字。
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s;if(s[0]==s[1]&&s[1]==s[2]) cout<<"Yes";else cout<<"No";return 0;
}
B - Digit Sum
每个数最多被拆开 \(5\) 次，暴力枚举 \(1\sim n\)。
#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){int t=i,sum=0;while(t){sum+=(t%10);t/=10;}if(sum==k) ans++;}cout<<ans;return 0;
}
C - AtCoder Riko
题意不是很明确，实际上只会晃动一次。
此时答案有两种情况，所有棒两两组合 & 一些棒两两组合，一些棒单着。
两两组合必定是大配小，因此对其排序。第一种情况我们可以找到排序后序列最后若干个相同的，也就是所有最大的单着，然后对前面进行大配小。第二种情况直接对整个序列大配小。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,k;
int a[N],sum;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);for(k=n;k>=1;k--){if(a[k]!=a[n]) break;}bool flag=1;if(k==0) cout<<a[n]<<' ';else{sum=a[1]+a[k];if(sum!=a[n]||k&1) flag=0; else{for(int i=1;i<=k;i++){if(a[i]+a[k-i+1]!=sum){flag=0;break;} }}if(flag) cout<<sum<<' ';}flag=1;sum=a[1]+a[n];if(n&1) flag=0;else{for(int i=1;i<=n;i++){if(a[i]+a[n-i+1]!=sum){flag=0;break;}}}if(flag) cout<<sum<<' ';return 0;
}
D - Many Repunit Sum
题意难懂。简单来说，给出 \(n\) 个数，数 \(i\) 由 \(A_i\) 个 \(1\) 拼成，求 \(n\) 个数的和。
考虑用一个差分数组，直接对位区间修改。全部完成后，从低到高逐一进位即可。
注意边界，因为某一位最多有 \(2\times 10^5\) 个 \(1\)，若其为所有原数中的最高位，则最多有可能向上进位 \(5\) 次。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,maxa;
int a[N];
int s[2*N];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[1]++,s[a[i]+1]--;maxa=max(maxa,a[i]);} for(int i=1;i<=maxa+10;i++) s[i]=s[i-1]+s[i];for(int i=1;i<=maxa+10;i++) s[i+1]+=(s[i]/10),s[i]%=10;bool flag=0;for(int i=maxa+10;i>=1;i--){if(!flag&&s[i]!=0) flag=1,cout<<s[i];else if(flag) cout<<s[i];}return 0;
}
E - Sparse Range
因为区间右端点不断向右时，左端点是非减的，所以考虑从左往右扫右端点，然后判断左端点最远到哪。
我们只需要找到区间内是否有与右端点差 \(<D\) 的元素就可以了，因为更靠左的点之前已经扫过了。不需要遍历所有区间内元素，而只要找到与右端点大小最接近的两个元素，比他小的元素中最大的，和比他大的元素中最小的。如果存在则将左端点右移 \(1\)。
添加、删除、查询前驱后继，使用 multiset 维护。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int n,d,ans;
int l;
int a[N],st[N],top;
int f[N],g[N];
multiset<int> s({(int)-1e9,(int)2e9});
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>d;for(int i=1;i<=n;i++) cin>>a[i];l=1;for(int i=1;i<=n;i++){s.insert(a[i]);while(l<=i){bool flag=0;auto it=s.lower_bound(a[i]);it++;if(it!=s.end()&&*it-a[i]<d) flag=1;it--;it--;if(it!=s.begin()&&a[i]-*it<d) flag=1; if(!flag) break;s.erase(s.find(a[l]));l++;}ans+=i-l+1;}cout<<ans;return 0;
}