Educational Codeforces Round 160 (Rated for Div. 2)(D单调栈优化dp？C二进制贪心)

A：

直接枚举位置判断大小即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];


void solve()
{
    string s;
    cin>>s;
    string res;
    for(int i=1;i<s.size();i++)
    {
        if(s[i]=='0') continue;
        string a,b;
        for(int j=0;j<i;j++) a.push_back(s[j]);
        for(int j=i;j<s.size();j++) b.push_back(s[j]);
        if(stoi(a)<stoi(b)){
            cout<<a<<" "<<b<<"\n";
            return ;
        }
    }
    cout<<"-1\n";
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

B：比赛直接猜的

就是前面位置能从后面缓过来就换

不能换了说明当前位置只能相同，说明从这个位置开始都要删了

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int cnt[50];

void solve()
{
    string s;cin>>s;
    int res=0;
    n=s.size();
    map<char,int> mp;
    for(auto x:s) mp[x-'0']++;
    for(int i=0;i<s.size();i++){
        int x=s[i]-'0';
        x=x^1;
        if(mp[x]>0){
            mp[x]--;continue;
        }
        cout<<n-i<<"\n";
        return ;
    }
    cout<<0<<"\n";
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

C：

我印象里这个好像是原题吧？我记得做过一个最小次数的..

然后就直接秒出了

之前博客写过，一个数可以被表示成二进制，类似于快速幂

然后直接从低位到高位模拟即可

注意 2的4能合成一个8

所以如果能合并就合成更高维

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int cnt[50];

void solve()
{
    cin>>n;
    auto check=[&](int x)
    {
        vector<int> now(50);
        for(int i=0;i<=30;i++) now[i]=cnt[i];
        for(int i=0;i<=30;i++)
        {
            if(x>>i&1)
            {
                if(now[i]>0) now[i]--;
                else return false;
            }
            now[i+1]+=now[i]/2;
        }
        return true;
    };
    for(int i=1;i<=n;i++)
    {
        int op;int x;cin>>op>>x;
        if(op==1){
            cnt[x]++;
        }
        else {
            if(check(x)){
                cout<<"YES\n";
            }
            else cout<<"NO\n";
        }
    }
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
   // cin>>t;
    while(t--) solve();
}

D：视频连接讲的很清楚

单调栈优化 DP【Codeforces EDU 160 D】_哔哩哔哩_bilibili

比赛一股脑子往每个数做贡献越想越偏了

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];

void solve()
{
    cin>>n;
    vector<int> s(n+10);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<int> f(n+10);
    vector<int> st;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        s[i]=(s[i-1]+f[i-1])%mod;
        while(st.size()&&a[i]<a[st.back()])
        {
            sum-=f[st.back()];
            st.pop_back();
        }
        int j=st.empty()?0:st.back()+1;
        f[i]=(sum+s[i]-s[j]+st.empty())%mod;
        sum=(sum+f[i])%mod;
        st.push_back(i);
    }
    int res=0;
    for(auto x:st) res=(res+f[x])%mod;
    cout<<(res%mod+mod)%mod<<"\n";
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}