A

略。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int n, x, a[105];
signed main() {
    n=read();
    rep(i,1,n) ++a[read()];
    x=read();
    if(a[x]) puts("Yes"); else puts("No");
    return 0;
}

B

略。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
priority_queue<int,vector<int>,greater<int> > q;
string s;
signed main() {
    cin>>s;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='#') q.push(i+1);
    }
    while(q.size()) {
        int x=q.top(); q.pop();
        int y=q.top(); q.pop();
        printf("%d,%d\n",x,y);
    }
    return 0;
}

C

把容器内元素的状况压成一个二进制数，危险状态 ban 掉，DFS判断是否存在一条从 $0$ 到 $2^n -1$ 的路径即可。

每个点最多连出 $n$ 条边，复杂度 $O(n 2^n)$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=5e5+5;
int T, n, U, ans;
int ban[N], v[N];
vector<int> p[N];
string s;
void dfs(int S) {
    v[S]=1;
    if(S==U) {
        ans=1;
        return;
    }
    for(int i=0;i<n;i++) {
        int k=S|(1<<i);
        if(!ban[k]&&!v[k]&&i!=k) dfs(k);
    }
}
void solve() {
    n=read();
    cin>>s;
    U=(1<<n)-1;
    for(int i=0;i<=U;i++) ban[i]=v[i]=0, p[i].clear();
    for(int i=0;i<s.size();i++) {
        if(s[i]=='1') ban[i+1]=1;
    }
    ans=0;
    dfs(0);
    if(ans) puts("Yes"); else puts("No");
}
signed main() {
    T=read();
    while(T--) solve();
    return 0;
}

D

贪心策略：按照 $A_i – B_i$ 递增排序，尽可能选择满足 $n \ge A_i$ 的 $i$。

证明：由于无论选择哪个 $i$ 收益都是 $1$，所以选择补回来多的一定不劣。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
ll read() {
   ll a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=2e5+5;
int m;
ll n;
struct node {
    ll x, y;
} a[N];
bool operator<(const node& a,const node& b) {
    return (a.x-a.y)>(b.x-b.y);
}
ll cil(ll x,ll y) { return (x+y-1)/y; }
priority_queue<node> q;
signed main() {
    n=read(), m=read();
    rep(i,1,m) {
        a[i].x=read(), a[i].y=read();
        q.push(a[i]);
    }
    ll ans=0;
    while(q.size()&&n>0) {
        node t=q.top(); q.pop();
        if(n<t.x) continue;
        ll dlt=n-t.x;
        ll cnt=dlt/(t.x-t.y);
        ans+=cnt;
        n-=cnt*(t.x-t.y);
        if(n>=t.x) {
            n-=t.x-t.y;
            ans++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

E

设 $f(i,j)$ 为从 $(i,j)$ 到达 $(n,m)$ 至少需要多少钱。

$$
f(i,j) = \min \left\{ f(i+1,j),f(i,j+1) \right\} + p_{i+j-1} – a_{i,j}
$$

如果计算出的 $f(i,j)<0$，说明不需要额外花钱，直接置为 $0$ 即可。

为什么不能设 $f(i,j)$ 为从 $(1,1)$ 到达 $(i,j)$ 至少需要多少钱呢？

因为我们无法解决，到达 $(i,j)$ 后钱还有剩的情况，即存在后效性。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
int n, m, p[500000];
signed main() {
    n=read(), m=read();
    vector a(n+5,vector<int>(m+5));
    rep(i,1,n) rep(j,1,m) a[i][j]=read();
    rep(i,1,n+m-1) p[i]=read();
    vector f(n+5,vector<ll>(m+5,1e18));
    f[n][m]=0;
    per(i,n,1) per(j,m,1) {
        if(i+1<=n) f[i][j]=min(f[i][j],f[i+1][j]);
        if(j+1<=m) f[i][j]=min(f[i][j],f[i][j+1]);
        f[i][j]+=p[i+j-1]-a[i][j];
        f[i][j]=max(f[i][j],0ll);
    }
    printf("%lld\n",f[1][1]);
    return 0;
}

F

线段树板子题。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
   int a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=5e5+5;
int n, q;
string s;
struct node {
    int w, lt, rt, lw, rw, len;
    node() { w=lt=rt=lw=rw=len=0; }
    node(int a,int b,int c,int d,int e,int g) {
        w=a, lt=b, rt=c, lw=d, rw=e, len=g;
    }
};
node operator+(const node& a,const node& b) {
    node c=node(0,0,0,0,0,0);
    c.w=max(a.w,b.w);
    if(a.rw==b.lw) c.w=max(c.w,a.rt+b.lt);
    c.lw=a.lw, c.rw=b.rw;
    c.lt=a.lt, c.rt=b.rt;
    if(a.lw==a.rw&&a.len==a.lt&&a.rw==b.lw) c.lt=max(c.lt,a.lt+b.lt);
    if(b.lw==b.rw&&b.len==b.rt&&a.rw==b.lw) c.rt=max(c.rt,b.rt+a.rt);
    c.len=a.len+b.len;
    return c;
}
namespace seg {
    node t[N<<2];
    void pushup(int x) {
        t[x]=t[x<<1]+t[x<<1|1];
    }
    void build(int x=1,int l=1,int r=n) {
        if(l==r) {
            t[x]=node(1,1,1,s[l-1]-'a',s[l-1]-'a',1);
            return;
        }
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        pushup(x);
    }
    void upd(int p,int k,int x=1,int l=1,int r=n) {
        if(l==r) {
            t[x]=node(1,1,1,k,k,1);
            return;
        }
        int mid=(l+r)>>1;
        if(p<=mid) upd(p,k,x<<1,l,mid);
        else upd(p,k,x<<1|1,mid+1,r);
        pushup(x);
    }
    node query(int L,int R,int x=1,int l=1,int r=n) {
        // printf("%d %d\n",l,r);
        if(L<=l&&r<=R) return t[x];
        int mid=(l+r)>>1;
        node res1, res2;
        if(L<=mid) res1=query(L,R,x<<1,l,mid);
        if(R>mid) res2=query(L,R,x<<1|1,mid+1,r);
        if(res1.w&&!res2.w) return res1;
        if(!res1.w&&res2.w) return res2;
        if(res1.w&&res2.w) return res1+res2;
        return res1;
    }
};
signed main() {
    n=read(), q=read();
    cin>>s;
    seg::build();
    while(q--) {
        int op=read();
        if(op==1) {
            string c;
            int x=read();
            cin>>c;
            seg::upd(x,c[0]-'a');
        } else {
            int l=read(), r=read();
            node ans=seg::query(l,r);
            printf("%d\n",ans.w);
        }
    }
    return 0;
}

G

D 的加强版。

$A_i,B_i$ 数量很多，但值域很小，于是按照值域缩一下数量，保留每个$A_i$ 最大的 $B_j$ 即可。

不难发现，对于一个操作 $(A_i,B_i)$，其代价为 $A_i-B_i$，收益为 $B_i$，前提是 $n’ \ge A_i$。

设 $f_n$ 为当前有 $n$ 瓶可乐时能够额外产生的最大收益，这就是一个有限制的完全背包。

但是这样不能处理较大规模的数据。

我们断言：在 $n$ 较大时，不存在上述前提的限制，所以操作的顺序是无所谓的。

所以说我们可以把某一种操作放在前面连续进行多次。

操作数量很少，枚举即可，那么答案就是

$$
\max_{j=lim_0}^{lim_1} \Big \{ f_j + \lfloor \frac{n-j} {A_i-B_i} \rfloor \times B_i \Big \}
$$

复杂度取决于 $lim_0$ 和 $lim_1$ 的选取。

对于下界 $lim_0$，我们至少要留出来一个其他 $A_i$，所以令 $lim_0 = \max_{i=1}^m {A_i}$ 即可。

对于上界 $lim_1$，可以取 $lim_1(lim_1+1)$。

证明是不会的。没啥人做这题，日文翻译后也看不明白。

使用した $i’$ 以外のアイテムに対する $D_i$​ の総和が $K(K+1)$ 以上だと仮定する。

まず、操作の過程において $x$ が最初に K 以上になったタイミングについて考える。最初の $x$ を $K$ より大きくするメリットはないので、このときの $x$ は $K$ 以上 $2K$ 未満と仮定してよく、これ以降の操作について ​$x \ge B_i$ という条件を気にする必要はない。

仮定より、これ以降に使用した i′ 以外のアイテムに対する $D_i$ の総和は $K(K+1)−(2K−1)=K(K−1)+1$ 以上であり、特に使用した個数は $K$ 以上である。これらのアイテムのうち最初の $j$ 個に対するDi​ の総和を $S_j​ (0≤j≤K)$ とおく。鳩の巣原理より、$S_l​ \equiv S_r​ (\bmod D_{i’}​)$ なる $0≤l<r≤K$ が存在する。$l+1,l+2,…,r$ 個目のアイテムを使用する代わりに、アイテム $i$ を $\frac{S_r-S_l}{D_{i’}​​}$ 個使用することにして損しない。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned long long
#define PII pair<int,int>
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
#define ef emplace_front
#define SET(a,b) memset(a,b,sizeof(a))
#define CPY(a,b) memcpy(a,b,sizeof(b))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
ll read() {
   ll a=0, f=1; char c=getchar();
   while(!isdigit(c)) {
       if(c=='-') f=-1;
       c=getchar();
   }
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
   return a*f;
}
const int N=305;
ll n, f[N*N];
int m, mx[N], lim, mxa;
vector<PII > v;
signed main() {
    n=read(), m=read();
    rep(i,1,m) {
        int a=read(), b=read();
        lim=max(lim,a*(a+1));
        mx[a]=max(mx[a],b);
        mxa=max(mxa,a);
    }
    rep(i,1,300) if(mx[i]) {
        v.eb(MP(i-mx[i],mx[i]));
    }
    for(auto [x,y]:v) rep(i,x,lim) {
        if(i-x>=y) f[i]=max(f[i],f[i-x]+y);
    }
    ll ans=0;
    if(n<=lim) {
        rep(i,1,n) ans=max(ans,f[i]);
        printf("%lld\n",n+ans);
        exit(0);
    }
    for(auto [x,y]:v) {
        rep(j,mxa,lim) ans=max(ans,f[j]+(n-j)/x*y);
    }
    printf("%lld\n",n+ans);
    return 0;
}