第 19 场强者挑战赛

1 敲打骷髅兵

不难发现，设 $f_i$ 表示击败血量为 $i$ 所需要的敲打次数。

则 $f_1=1$ , $f_i=2f_{i-1}+1$ 。

打表找规律即可。

void solve(){ int n, t = 1;cin >> n;while(t <= n) t <<= 1;cout << t - 1 << '\n';
}

2 净化王胖子

设房间 $i$ 与房间 $i + 1$ 之间的通道编号为 $i$ ，则一共 $1\sim n-1$ 个通道。

每次从 $x\rightarrow y$ ，就是经过了 $[x, y)$ 这些通道。

用线段树维护每个通道通过次数之后，贪心处理即可。

#include<bits/stdc++.h>
using namespace std;
#define int long longint const N = 2e5 + 10;#define lc u << 1
#define rc u << 1 | 1// 维护端点, 线段和, 加法懒标记
struct treeNode{int l, r, sum, add;
}tr[N * 4];// 向上更新
void pushup(int u){tr[u].sum = tr[lc].sum + tr[rc].sum;
}// 向下更新
void pushdown(int u){if(tr[u].add){tr[lc].sum += tr[u].add * (tr[lc].r - tr[lc].l + 1);tr[rc].sum += tr[u].add * (tr[rc].r - tr[rc].l + 1);tr[lc].add += tr[u].add;tr[rc].add += tr[u].add;tr[u].add = 0;}
}void buildTree(int u, int l, int r){tr[u] = {l, r, 0, 0};if(l == r) return ; // 是叶子结点则返回int mid = l + r >> 1; // 不是叶子结点就分裂buildTree(lc, l, mid);buildTree(rc, mid + 1, r);pushup(u);
}// 区间加 (区间减也是区间加)
void segmentAdd(int u, int l, int r, int x){if(l <= tr[u].l && r >= tr[u].r){ // 覆盖则修改tr[u].sum += (tr[u].r - tr[u].l + 1) * x;tr[u].add += x;return ;}int mid = tr[u].l + tr[u].r >> 1; // 不覆盖就分裂pushdown(u);if(l <= mid) segmentAdd(lc, l, r, x);if(r > mid) segmentAdd(rc, l, r, x);pushup(u);
} // 区间求和
int askSegmentSum(int u, int l, int r){if(l <= tr[u].l && r  >= tr[u].r){ // 覆盖则返回return tr[u].sum;}int mid = tr[u].l + tr[u].r >> 1;pushdown(u);int sum = 0;if(l <= mid) sum += askSegmentSum(lc, l, r);if(r > mid) sum += askSegmentSum(rc, l, r);return sum;
}int n, k;
int p[N];void solve(){cin >> n >> k;buildTree(1, 1, n - 1);for(int i = 1; i <= n; i ++){int x;cin >> x;p[x] = i;}for(int i = 1; i < n; i ++){int l = p[i], r = p[i + 1];if(l > r) swap(l, r);segmentAdd(1, l, r - 1, 1);}vector<int> vc;for(int i = 1; i < n; i ++){vc.push_back(askSegmentSum(1, i, i));}sort(vc.begin(), vc.end(), [&] (auto &a, auto &b){return a > b;});// for(auto &x : vc) cout << x << ' ';if(accumulate(vc.begin(), vc.end(), 0LL) < k){cout << "-1";}else{for(int i = 0; i < vc.size(); i ++){k -= vc[i];if(k <= 0){cout << i + 1;return; }}}
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); solve();return 0;
}

3 云顶天宫

设 $f_{i,0}$ 表示考虑 $1\sim i$ 这些圆盘，从未出现过 $m$ 的方案数。

$f_{i,1}$ 表示出现过 $m$ 但是不以 $m$ 结尾， $f_{i,2}$ 表示出现过 $m$ 且以 $m$ 结尾。

以上三个状态保证 $m$ 不相邻。

实际上，存在 $m$ 并且 $m$ 不相邻一定可以构造答案，否则不能。

所以答案是 $f_{n,1}+f_{n,2}$ 。

constexpr int P = 998244353;
using Z = MInt<P>;int const N = 1100;int n, m;Z f[N][3];void solve(){cin >> n >> m;f[1][0] = m - 1;f[1][1] = 0;f[1][2] = 1;for(int i = 2; i <= n; i ++){f[i][0] = f[i - 1][0] * (m - 1);f[i][1] = (m - 1) * (f[i - 1][1] + f[i - 1][2]);f[i][2] = f[i - 1][0] + f[i - 1][1];}cout << (f[n][1] + f[n][2]) << '\n'; 
}

4 古墓机关

一开始想复杂了，实际上就是一道球盒模型。

相当于 $n$ 个有编号的球，放进 $m$ 个盒子，允许为空。

答案就是 $\choose m-1$ 。

数据不严格，费马小定理处理阶乘逆元即可。

int fact[N], infact[N];void init(){fact[0] = 1;infact[0] = 1;for(int i = 1; i < N; i ++){fact[i] = fact[i - 1] * i % mod;infact[i] = ksm(fact[i], mod - 2, mod);}
}int C(int n, int m){return fact[n] * infact[m] % mod * infact[n - m] % mod;
}void solve(){int n, m; // n 个球放进 m 个盒子, 盒子可以为空cin >> n >> m;cout << C(n + m - 1, m - 1) << '\n';
}