A

最终结果是 $a_n – a_1$，求下最大值最小值就好.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int t,n,maxn,minn;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        maxn=-1; minn=1e9+10;
        for(int i=1,x;i<=n;i++) {
            cin>>x;
            minn=min(x,minn); maxn=max(x,maxn);
        }
        cout<<maxn-minn<<"\n";
    }
    return 0;
}

B

画图大概感受一下，发现每个格子可以提供 $2$ 条对角线。注意一下边界特判.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int t,n,k;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n>>k;
        if(k <= 4*n-4) cout<<(k+1)/2<<"\n";
        if(k == 4*n-3) cout<<2*n-1<<"\n";
        if(k == 4*n-2) cout<<2*n<<"\n";
    }
    return 0;
}

C

设 $f_i$ 为第 $i$ 回合最小下注钱数，因为第 $i$ 回合赢钱后不能比先前输的总钱数多，所以有

$b_i (k-1) > \sum_{j=1}^{i-1}b_j $

即

$b_i \geq \lfloor \frac{\sum_{j=1}^{i-1}b_j} {k-1} \rfloor+1$

注意循环过程中 $b_i$ 的和需要不大于 $a$.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL t,k,x,a;
bool solve() {
    LL y=0,sum=0;
    for(int i=1;i<=x+1;i++) {
        y=1ll+(sum/(k-1ll));
        sum+=1ll*y;
        if(sum > a) return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>k>>x>>a;
        if(solve()) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

D

考虑dp.设 $dp_{i,j}$ 表示以 $x$ 为根节点的子树中，从根节点到叶子结点最多经过 $j$ 个危险节点的方案数.转移方程为

$dp_{x,1} = \prod_{y\in Son(x)}(dp_{y,1}+1)$

$dp_{x,2} = \sum_{y\in Son(x)}(dp_{y,1}+dp_{y,2})$

最后答案为 $1+dp_{i,1}+dp_{i,2} $.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define int long long
const LL P = 998244353;
const int N=3e5+10;
struct Tree{
    int t,nex;
} e[N*2]; int tot,head[N];
void add(int u,int v) {
    e[++tot].t=v; e[tot].nex=head[u]; head[u]=tot;
}
int t,n;
LL dp[N][3],ans;
void init() {
    tot=0;
    for(int i=1;i<=n;i++) dp[i][1]=1,dp[i][2]=0,head[i]=0,e[i].nex=0,e[i+n].nex=0;
    ans=0;
}
void dfs(int x,int fath) {
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].t;
        if(y == fath) continue;
        dfs(y,x);
        dp[x][1]*=(dp[y][1]+1ll)%P;
        dp[x][1]%=P;
        dp[x][2]+=dp[y][1]+dp[y][2];
        dp[x][2]%=P;
    }
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        init();
        for(int i=1,u,v;i<n;i++) {
            cin>>u>>v;
            add(u,v); add(v,u);
        }
        dfs(1,0);
        cout<<(dp[1][1]+dp[1][2]+1ll)%P<<"\n";
    }
    return 0;
}

E

这个 $k$ 的范围看着就很状压，，，

设 $s_i$ 表示边 $i$ 能贡献的链的集合，$f_s$ 表示标记集合 $s$ 中所有边所要花费的最小代价，有状态转移方程

$ f_{s\cup s_i}=min \{ f_{s\cup s_i},f_s+1 \} $

复杂度为 $O(2^{k} n)$.

不太能过，考虑怎么优化。因为链只有 $k$条，每条边的贡献集合 $s_i$ 实际上会有很多重复，可以用 set去重，将复杂度降为 $O(2^{k} k)$.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e5+10;
const int M=2e6+10;
const int Inf=1e9;
int t,n,k;
struct tree{
    int t,nex;
} e[N*2]; int head[N],tot;
void add(int u,int v) {
    e[++tot].t=v; e[tot].nex=head[u]; head[u]=tot;
}
int fa[N],f[N],dep[N],dp[M];
void init() {
    for(int i=0;i<=n;i++) e[i].nex=0,e[i+n].nex=0,head[i]=0,fa[i]=0,f[i]=0,dep[i]=0,dp[i]=Inf;
    tot=0;
}
void dfs(int x,int fath) {
    dep[x] = dep[fath] + 1;
    fa[x]=fath;
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].t;
        if(y == fath) continue;
        dfs(y,x);
    }
    return;
}
set<int> s;
void solve() {
    s.clear();
    dfs(1,0);
    cin>>k;
    for(int i=0;i< 1<<k;i++) dp[i]=Inf;
    for(int i=1,x,y;i<=k;i++) {
        cin>>x>>y;
        if(dep[x] < dep[y]) swap(x,y);
        while(dep[x] > dep[y]) { f[x]|=(1<<(i-1)); x=fa[x];}
        while(x != y) {f[x]|=(1<<(i-1)); f[y]|=(1<<(i-1)); x=fa[x]; y=fa[y];}
    }
    for(int i=2;i<=n;i++) s.insert(f[i]);
    dp[0]=0;
    for(int i=0;i<(1<<k);i++) {
        for(auto c : s) {
            dp[i|c] = min(dp[i|c],dp[i]+1);
        }       
    }
    cout<<dp[(1<<k)-1]<<"\n";
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        init();
        for(int i=1,u,v;i<n;i++) {
            cin>>u>>v;
            add(u,v); add(v,u);
        }
        solve();
    }
    for(int i=1;i<=n;i++) i++;
    return 0;
}

F

没啥意思的题，老trick的堆叠.

先求出BST的中序遍历，根据BST的性质，它的中序遍历应该是单调不减的。所以我们可以利用这个性质向中序遍历里的每个连续-1段填数。原问题被转化为向一个长度为 $len$ 的空序列里填入 $[l,r]$ 中的数，使序列单调不下降.这个问题的答案为 $ \binom {r-l+len} {len} $. 证明暂略.

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define int long long
const int N=1e6+10;
const int Mod=998244353;
int T,n,C;
struct Tree{
    int l,r,val;
} t[N];
int a[N],cnt;
void dfs(int x) {
    if(t[x].l != -1) dfs(t[x].l);
    a[++cnt]=t[x].val;
    if(t[x].r != -1) dfs(t[x].r);
    return;
}
int inv(int bs,int num=Mod-2){
    int res=1; 
    for(;num;num/=2){
        if(num & 1) res=(res*bs)%Mod;
        bs=(bs*bs)%Mod;
    } 
    return res;
}
int calc(int x,int y){
    int up=1,dn=1;
    for(int i=0;i<y;++i){
        up=up*(x-i)%Mod;
        dn=dn*(i+1)%Mod;
    } 
    return up*inv(dn)%Mod;
}
void solve() {
    cnt=0;
    dfs(1);
    a[0]=1; a[n+1]=C;
    LL ans=1;
    for(int i=1,l,r;i<=n;i++) {
        if(a[i] == -1) {
            l=i; r=i;
            for(;i<=n;i++) if(a[i] == -1) r=i; else break;
            ans*=calc(a[r+1]-a[l-1]+r-l+1,r-l+1);
            ans%=Mod;
        }
    }
    cout<<ans<<"\n";
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--) {
        cin>>n>>C;
        for(int i=1,ll,rr,vv;i<=n;i++) {
            cin>>ll>>rr>>vv;
            t[i].l=ll; t[i].r=rr; t[i].val=vv;
        }
        solve();
    }
    for(int i=1;i<=100;i++) i++;
    return 0;
}