（AtCoder Beginner Contest 321）(退背包，二叉树)

A.直接暴力即可

​
#include<bits/stdc++.h>
using namespace std;
const int N =2e5+10;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
int n,m;
 
void solve(){
    string s;
    cin>>s;
    for(int i=1;i<s.size();i++){
        int x=s[i-1]-'0';
        int y=s[i]-'0';
        if(x<=y){
            cout<<"No\n";
            return ;
        }
    }
    cout<<"Yes\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;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
int n,m;
int a[N];
void solve(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        cin>>a[i];
    }
    int res=INT_MAX;
    for(int j=0;j<=100;j++){
        vector<int> b;
        for(int i=1;i<n;i++) b.push_back(a[i]);
        b.push_back(j);
        sort(b.begin(),b.end());
        int now=0;
        for(int i=1;i<b.size()-1;i++) now+=b[i];
        if(now>=m){
            res=min(res,j);
        }
    }
    if(res==INT_MAX){
        cout<<-1;
        return ;
    }
    cout<<res;
}
 
signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
   // cin>>t;
    while(t--) solve();
}

C.我二分+数位dp了

直接二分当前数的范围内有多少个 “321”的数的个数

import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce,cache
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
import bisect
 
BUFSIZE = 4096
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
 
def I():
    return input()
 
 
def II():
    return int(input())
 
 
def MI():
    return map(int, input().split())
 
 
def LI():
    return list(input().split())
 
 
def LII():
    return list(map(int, input().split()))
 
 
def GMI():
    return map(lambda x: int(x) - 1, input().split())
 
 
def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
 
 
def solve():
    k = II()
 
 
    @cache
    def dfs(i: int, limit: bool, num: bool, pre: int,s:str) -> int:
        if i == len(s):
            return int(num)
        res = 0
        if not num: res = dfs(i + 1, False, False, 10,s)
        up = int(s[i]) if limit else 9
        di = 0
        if not num: di = 1
        for d in range(di, up + 1):
            if pre > d:
                res += dfs(i + 1, limit and d == up, True, d,s)
        return res
 
    l, r = 1, 10 ** 18
 
    while l < r:
        mid = (l + r) >> 1
        if dfs(0, True, False, 10,str(mid)) >= k:
            r = mid
        else:
            l = mid + 1
    print(l)
 
 
if __name__ == '__main__':
    for _ in range(1):
        solve()

D.

每个ai都要乘每个bi

排序后双指针维护当前ai+bi<=k的最有边界即可

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+10;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
int n,m,k;
int a[N],b[N];
void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];    
    }
    for(int j=1;j<=m;j++) cin>>b[j];
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    int res=0;
    int now=0;
    for(int j=1;j<=m;j++) now+=b[j];
    int idx=m;
   
    for(int i=1;i<=n;i++)
    {
        while(idx>=1&&a[i]+b[idx]>=k)
        {
            now-=b[idx];
            idx--;
        }
    //    cout<<idx<<"\n";
        res+=idx*a[i]+now+(m-idx)*k;
    }
    cout<<res;
}
 
signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
   // cin>>t;
    while(t--) solve();
}

E.

直接get函数就是找以当前x为根节点的子树下面距离为k的有多少个数，最大值是n

那么最左边界是x<

然后往父节点跳即可，边跳边计算父节点的另一个儿子节点

#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;
 
 
 
void solve()
{
 
    int n,x,k;
    
    int res=0;
    auto get=[&](int x,int k,int n){
        if(k>=64) return 0ll;
        if(k<0) return 0ll;
        __int128 num=1ll<<k,l=x;
        l=l<<k;
        __int128 r=l+num-1;
        if(l>n) return 0ll;
        LL res=min(r,(__int128)n)-l+1;
        return res;
    };
    
    cin>>n>>x>>k;
    if(k)
    {
        res+=get(x,k,n);
    }
    while(x>1&&k>0){
        k--;
        res+=get((x^1),k-1,n);
        x/=2;
    }
    if(k==0&&x){
        res++;
    }
    cout<<res<<"\n";
}
 
signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
    
    cin>>t;
    while(t--) solve();
}

F：退背包问题

添加就是正常的01背包

然后删除就是

维护g数组

状态是，不选当前球，体积为i的方案数

那么g[i]=f[i]-g[i-x]

考虑容斥原理

不选当前球体积为i=选+不选当前球体积为i-选当前球体积为i的方案数

=f[i]-g[i-x]

g[i-x]可以理解为选了这个球后，剩下的 i−x�−�就是由不选该球的方案数组成

#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;
int n,m;
int a[N];
int dep[N];
 
 
void solve()
{
    int q,k;
    cin>>q>>k;
    vector<int> f(k+1,0);
    f[0]=1;
    while(q--){
        string op;
        int x;cin>>op>>x;
        if(op[0]=='+'){
            for(int i=k;i>=x;i--){
                f[i]+=f[i-x];
                f[i]%=mod;
            }
        }
        else
        {
            //不选该球和为j的方案书
            //选和不选
            vector<int> g(k+1,0);
            for(int i=0;i<=k;i++){
                if(i<x){
                    g[i]=f[i];
                }
                else{
                    g[i]=f[i]-g[i-x];
                    if(g[i]<0) g[i]+=mod;
                }
            }
            f.swap(g);
        }
        cout<<f[k]<<"\n";
    }
}
 
signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
    
   // cin>>t;
    while(t--) solve();
}