CF 552C
给你两个数 m,w,你有w^1 …. w^infinite 个砝码，能否让天平平衡
就是问给你一个m，能不能把其表示为一个w进制数
因为有-1，所以右边只能为0,1,w-1
void solve(){
int m,w;
cin>>w>>m;
while(m){
if(m%w==0){
}else if(m%w==1){
}else if(m%w==(w-1)){
++m;
}
else{
cout<<"NO\n";
return;
}
m/=w;
}
cout<<"YES\n";
return;
}
CF 547B
双单调栈，我们可以求出每个数作为最小值可以扩张到哪里，然后更新ans，注意ans[i]是ans[i+1]的子集合，也就是能取到ans[i+1]一定能取到ans[i]
void solve(){
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;++i){
cin>>a[i];
}
vector<int>l(n+1),r(n+1);
vector<int>st;
for(int i=1;i<=n;++i){
while(st.size()&&a[st.back()]>=a[i])st.pop_back();
if(!st.size()){
l[i]=1;
}else{
l[i]=st.back()+1;
}
st.push_back(i);
}
st.clear();
for(int i=n;i>=1;--i){
while(st.size()&&a[st.back()]>=a[i])st.pop_back();
if(!st.size()){
r[i]=n;
}else{
r[i]=st.back()-1;
}
st.push_back(i);
}
vector<int>ans(n+1);
for(int i=1;i<=n;++i){
ans[r[i]-l[i]+1]=max(ans[r[i]-l[i]+1],a[i]);
}
for(int i=n-1;i>=1;--i){
ans[i]=max(ans[i+1],ans[i]);
}
for(int i=1;i<=n;++i){
cout<<ans[i]<<" \n"[i==n];
}
return;
}