别点开，里面没有 club
2026-08-15 09:11:06
发布于：浙江
P2123
注意到重排，注意到 恰好依赖前面一项的 与前缀的 ，所以考虑邻项交换。
显然，我们需要最小化每一个 。
推式子，；
不考虑第一项，展开：。
假设交换 ，则前面那一坨值不变，变的只是 。因此若满足 ，则原方案一定不劣；否则交换 不劣。
那是不是按照这个排序就行了呢？注意到，这个不满足“不可比性的传递性”。
比如说 ，这样就不符合传递性了。
那咋办？继续找性质吧。
我们又注意到， 更小的放到前面一定不劣。现在，我们把 作为次要条件加进去，看看对不对。
::::info[证明满足非自反性、非对称性、传递性]
显然。
::::
然后不满足它交换一定不劣、满足它交换一定不优，所以可以大胆排了！
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <pii> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i].first >> a[i].second;
}
std::sort(a.begin() + 1, a.begin() + n + 1, [](pii x, pii y) -> bool{
if(std::min(x.first, y.second) != std::min(x.second, y.first)) return (std::min(x.first, y.second) < std::min(x.second, y.first));
return (x.first < y.first);
});
std::vector <ll> c(n + 5), pre(n + 5);
for(int i = 1; i <= n; i++){
pre[i] = pre[i - 1] + a[i].first;
if(i == 1) c[i] = a[1].first + a[1].second;
else c[i] = std::max(c[i - 1], pre[i]) + a[i].second;
}
std::cout << c[n] << '\n';
}
}
时间复杂度：。
P2949
按截止时间排序。开个堆，维护当前价值最小值。如果大小超过了当前时间，弹出最小值。
诶这为啥是对的来着（
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <pii> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i].first >> a[i].second;
}
std::sort(a.begin() + 1, a.begin() + n + 1, [](pii x, pii y) -> bool{
return (x.first < y.first);
});
ll cur = 0, ans = 0;
std::priority_queue <int, std::vector <int>, std::greater <int>> q;
for(int i = 1; i <= n; i++){
cur += a[i].second, q.push(a[i].second);
if(q.size() > a[i].first){
cur -= q.top();
q.pop();
}
ans = std::max(ans, cur);
}
std::cout << ans << '\n';
}
}
时间复杂度：。
以下是数据结构题。
HDU-5603
考虑类似区间数颜色的方法。
按左端点扫描。如果某个点坐标小于左端点了，那就删除它，加入它那组后一个点。如果扫到了线段的左端点，那么将右端点前缀所有点 。
需要支持动态单点添加、单点删除、前缀 、单点查询的数据结构，平衡树或权值树状数组即可做到。这里使用树状数组实现。
namespace cjdst{
const int N = 1000000;
int tr[N + 5];
std::vector <int> add[N + 5];
void modify(int idx, int val){
for(int i = idx; i <= N; i += (i & (-i))) tr[i] += val;
}
int query(int idx){
int ans = 0;
for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
return ans;
}
bool solve(){
int n, m;
if(!(std::cin >> n >> m)) return 0;
std::vector <pii> a(n + 5);
std::vector <std::vector <int>> b(m + 5);
std::vector <int> id(m + 5), ans(m + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i].first >> a[i].second;
add[a[i].first].push_back(a[i].second);
}
std::sort(a.begin() + 1, a.begin() + n + 1);
std::priority_queue <pii, std::vector <pii>, std::greater <pii>> q;
for(int i = 1; i <= m; i++){
int len;
std::cin >> len;
b[i].resize(len + 5);
for(int j = 1; j <= len; j++){
std::cin >> b[i][j];
}
q.push({b[i][1], i});
id[i] = 1;
}
for(int i = 1; i <= N; i++){
while(!q.empty() && q.top().first < i){
auto it = q.top();
q.pop();
ans[it.second] += query(N - it.first + 1);
if(b[it.second][id[it.second] + 1]){
id[it.second]++;
ans[it.second] -= query(N - b[it.second][id[it.second]] + 1);
q.push({b[it.second][id[it.second]], it.second});
}
}
for(int j:add[i]){
modify(N - j + 1, 1);
}
}
for(int i = 1; i <= m; i++){
std::cout << ans[i] << '\n';
}
for(int i = 1; i <= N; i++){
add[i].clear();
tr[i] = 0;
}
return 1;
}
}
时间复杂度：。
CF2045E
首先考虑 做法，也就是枚举每一个区间，计算它们的贡献。显然答案为 的区间 的贡献是 。
现在考虑如何快速求出这些区间。
有一个很好的方法是，注意到产生贡献的要求是 ，这个可以拆成 与 ，分别枚举两行，看看每个区间是哪个数产生的贡献。
这里以第一行为例。
假设产生贡献的数为 。则区间需要满足：
- 。
- 。
- 。这个小于号是为了不重复统计区间。
- 。
对于上面两个情况，能取到的 应该满足形如 ；对于下面的情况，能取到的 应该满足形如 或 。算出 后取并集即可。
注意到这个其实就是要我们快速求出 开始的前、后最大值，可以单调栈递推求出。
。
CF526F
做这题之前先尝试做一下这个“橙题”。
本来想找个以前的题解的，好像不知道为啥被删了，算了。
二维平面每个点都不在同一行同一列，考虑离散化转化为一维排列。
现在就看存在多少个子区间 满足 。
首先，我们按 扫描线，单调栈+线段树处理出 为结尾后缀的极差 。
但是我们感觉直接统计 的数量，这个无疑也是困难的。考虑预先将每个 加上 ，变成统计 的数量。但是无疑还是困难的……吗？
注意到，，也就是说，如果存在 ，那它一定是最小值！
现在问题就转化成了求全局最小值和最小值出现的次数了，线段树秒了。
。
P4147
笛卡尔树大学习。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <std::vector <char>> a(n + 5, std::vector <char>(m + 5));
std::vector <int> dep(m + 5), lson(m + 5), rson(m + 5);
int ans = 0;
auto dfs = [&](auto &&self, int cur) -> int{
int siz = 1;
if(lson[cur]) siz += self(self, lson[cur]);
if(rson[cur]) siz += self(self, rson[cur]);
ans = std::max(ans, siz * dep[cur]);
return siz;
};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
std::cin >> a[i][j];
if(a[i][j] == 'F') dep[j]++;
else dep[j] = 0;
}
std::vector <int> stack;
int root = -1;
for(int j = 1; j <= m; j++){
int lst = -1;
while(!stack.empty() && dep[stack.back()] >= dep[j]) lst = stack.back(), stack.pop_back();
if(lst != -1) lson[j] = lst;
if(stack.empty()) root = j;
else rson[stack.back()] = j;
stack.push_back(j);
}
dfs(dfs, root);
for(int j = 1; j <= m; j++){
lson[j] = rson[j] = 0;
}
}
std::cout << ans * 3 << '\n';
}
}
时间复杂度：。
P3960
注意到题目说的是全体同学都要判断，实际上真正移动的只有第 行第 列往左移一位，第 列第 个往上移一位，最后把 加到最后。
看上去很难，但是注意到移动前后位置都是连续的，所以我们可以看作单点增删、查询排名。
所以我们可以维护每一行前 个点，再单独维护最后一列，通过排名进行操作。
如果只是这样的话就能开 个 Treap 做了，但是注意到 ，如果真的开的话就有 个点，显然开不下。
所以满足这题的最好的数据结构是动态开点线段树。
注意值域要多开至少 ；long long 要开全。
namespace cjdst{
const int N = 300000, M = 15000000;
ll tr[M + 5], tr2[M + 5];
int lson[M + 5], rson[M + 5];
int root[N + 5], rootlst;
ll n, m, q;
int ctnode;
int new_node(ll l, ll r){
ctnode++;
if(l == r) tr[ctnode] = l;
tr2[ctnode] = (r - l + 1);
return ctnode;
}
ll modify(int u, ll l, ll r, int val, ll val2){
if(l == r){
ll ans = tr[u];
tr[u] = val2;
tr2[u] = (tr[u] != 0);
return ans;
}
ll mid = (l + r) >> 1;
if(!lson[u]) lson[u] = new_node(l, mid);
if(!rson[u]) rson[u] = new_node(mid + 1, r);
ll ans;
if(val <= tr2[lson[u]]) ans = modify(lson[u], l, mid, val, val2);
else ans = modify(rson[u], mid + 1, r, val - tr2[lson[u]], val2);
tr2[u] = tr2[lson[u]] + tr2[rson[u]];
return ans;
}
void build_lst(int u, ll l, ll r){// 建最后一列的树
if(l == r){
tr[u] = l * m;
return;
}
int mid = (l + r) >> 1;
lson[u] = new_node(l, mid);
rson[u] = new_node(mid + 1, r);
build_lst(lson[u], l, mid);
build_lst(rson[u], mid + 1, r);
}
void solve(){
std::cin >> n >> m >> q;
for(int i = 1; i <= n; i++){
root[i] = new_node(1 + m * (i - 1), 1 + m * (i - 1) + m + q * 2);
}
rootlst = new_node(1, n + q * 2);
build_lst(rootlst, 1, n + q * 2);
for(int _ = 1; _ <= q; _++){
ll x, y;
std::cin >> x >> y;
ll ans;
if(y == m){
ans = modify(rootlst, 1, n + q * 2, x, 0);
modify(rootlst, 1, n + q * 2, n, ans);
}else{
ans = modify(root[x], 1 + m * (x - 1), 1 + m * (x - 1) + m + q * 2, y, 0);
ll cur = modify(rootlst, 1, n + q * 2, x, 0);
modify(root[x], 1 + m * (x - 1), 1 + m * (x - 1) + m + q * 2, m - 1, cur);
modify(rootlst, 1, n + q * 2, n, ans);
}
std::cout << ans << '\n';
}
}
}
int main(){
// freopen("test.out", "w", stdout);
cjdst::init();
int T = 1;
// std::cin >> T;
for(int _ = 1; _ <= T; _++){
cjdst::solve();
}
}
时间复杂度：，假设 同阶。
以下是 DP 题。
P1858
这有青？这有青？这有青？
就是记录下前 个物品容量为 的前 优解。转移可以归并排序。做完了。
。
P2851
做法是显然的。对着 FJ 的钱跑多重背包，对着找的钱跑完全背包即可。假设枚举钱的上界为 ，则可做到 。难的是上界应该怎么估算。其实对着时间空间限制极限卡即可
感性推测一下， 应该不会离 太远。事实上，。下面给出证明。
首先证明子问题：对于一个找零序列 满足 ，则 ，或者存在找零序列 满足 ，也就是一定有不劣的带 的方案。
由抽屉原理可知， 一定存在子序列为 的倍数。具体证明是对 做个前缀和，至少有一对前缀和满足同余，差分回来这个子区间就一定是 的倍数。这时，我们将这个替换成若干个 一定不劣。
因此，一定存在一种情况，使得找零中 的数量不超过 个。
现在，我们看 的数量。如果付钱时存在 ，那可以两两消掉；否则一定存在一个付的数量超过 ，根据上文也可以变成若干个 消掉。
因此， 的数量也不超过 ，也就是 。
时间复杂度：。
P13957
神秘贪心题。
按价格排序。则有一个结论：免费拿的价格一定大于等于买的价格。如果知道这个结论，证明挺简单的，交换一下即可。
于是枚举价格跑背包即可。
。
CF1442D
这道题的难点是注意到到序列有单调不减的性质。所以选一个数组一定会尽量拿完。
所以，这个就等价于选若干个整数组，再选一个数组的前缀。
我们枚举那个选前缀的数组，对其它数组跑一遍背包即可。这个显然是缺一分治板子。
。
P13323
回顾一下普通的 LCS。DP 的两维是选到第一个数组的位置和第二个数组的位置，然后看这两个位置是否相同来转移。
这个 DP 其实也类似，就是要处理不能完全匹配的情况。我们可以枚举 前面的区间，看看有多少个颜色相同的数，由它转移。
这样是 的，疑似能过，那我就不写优化了。
P7972
这个感觉非常困难，等理解了以后再写。
CF115E
定义 为前 个点中，最后选的一段为 。
显然有转移：；。
然后把第 维删掉，就变成了区间加 ，前缀查询问题，直接上线段树。
。
P9691
定义 为……等等，这是道绿。
定义 为前 个点中，恰好以 结尾的。然后令 ，答案为 。
则有：。显然这个可以扫描线单调队列维护。
或 。
CF1129D
定义 为以 结尾，右端点为 的答案。
则有 ，非常抽象。如何维护？
令 为 上一个颜色相同的下标。考虑开个 ，扫描 ，然后将 ，然后就转化成了求 ，更加抽象了。
现在我们发现需要维护一个数据结构，支持加入 ， 前缀 ，求全局 （ 为常数）的和。那咋办？
遇事不决，考虑分块。然后你就会发现有个 的做法。不想写了。
P14347
这题神了。无法比较这题和一般 CF Div2 B 的难度。
首先注意到先覆盖再取反是不劣的。然后考虑 DP。
我们会发现 DP 作用在一个点上，最多只有 种状态。然后暴力枚举状态转移即可。
，其中 。
P6239
注意到连边数是偶数，启发我们往异或角度思考。
定义 为前 条边，连了 个点，最后 个点连边数量为 。然后枚举上一个的 ，长度取 。然后注意到可以有重边，所以转移时得乘个组合数。这样可以实现 。
考虑多加一维 辅助转移，表示已经处理了第 个点和后 个点的连边。这样，我们每次转移 只需要枚举 个点，看看是否连边即可。由于每次连边 那一维会 ，所以直接“推”的方式转移没有后效性，还不用特殊处理重边，复杂度还更低。时间复杂度 。
非常神秘啊，感觉不是人类能想到的。
期望 DP 式子 存档
对于一张图（可能有环），定义到达点 的概率为 ，第 次到达点 的概率为 。这个 相当于 。
假设 有 的概率到达 。则 有 贡献的 ，所以总的 有 贡献的 。
P3750
第一部分就是求出哪些需要按，哪些不需要按。这个很显然，从后往前扫，按所有 1 的即可。这是个调和级数，。
第二部分就是求次数了。你注意到这玩意操作后有概率是错的，得多操作一次；有概率是对的，少操作一次。发现有环，感觉很难转移啊。
其实我们可以设 为 个需要按的操作一次后变为 个需要按的。则有 ，移个项得 ，即 。
然后注意到 ，所以从 开始递推即可。
namespace cjdst{
const ll N = 100000, mod = 100003;
std::vector <int> v[N + 5];
int a[N + 5], b[N + 5];
ll dp[N + 5];
ll inv[N + 5], frac = 1;
int n, m;
void solve(){
std::cin >> n >> m;
inv[1] = 1;
for(int i = 1; i <= n; i++){
frac = frac * i % mod;
if(i > 1) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
for(int j = i; j <= n; j += i) v[j].push_back(i);
}
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
int cur = 0;
for(int i = n; i; i--){
if(a[i]){
b[i] = 1;
cur++;
for(int j:v[i]) a[j] ^= 1;
}
}
if(cur <= m){
std::cout << cur * frac % mod << '\n';
return;
}
dp[n] = 1;
ll ans = 0;
for(int i = n - 1; i; i--){
dp[i] = (dp[i + 1] + 1) * (n - i) % mod * inv[i] + 1;
dp[i] %= mod;
}
for(int i = 1; i <= n; i++){
if(i <= cur && i > m) ans = (ans + dp[i]) % mod;
}
std::cout << (ans + m) * frac % mod << '\n';
}
}
时间复杂度：，瓶颈在第一部分。
P3232
看到 就说明复杂度一定不能带 。
考虑求出经过每条边的期望次数，从小到大排序。
定义经过 的期望次数为 ，则有 。
当然 的值得额外加 。
对于连接 的边，经过它期望概率为 。
然后呢？这个感觉不太好 DP 的样子啊。
考虑将 当成未知数，高斯消元求线性方程组。由于这是由实际 DP 推出来的，所以显然唯一解。
namespace cjdst{
const int N = 500, M = 125000;
const double eps = 1e-12;
std::vector <pii> v[N + 5];
double a[N + 5][N + 5], ans[M + 5];
int n, m;
void solve(){
std::cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
std::cin >> x >> y;
v[x].push_back({y, i});
v[y].push_back({x, i});
}
for(int i = 1; i < n; i++){
for(auto j:v[i]){
a[j.first][i] = double(1) / v[i].size();
}
}
for(int i = 1; i <= n; i++){
a[i][i] -= 1;
}
a[1][n + 1] = -1;
a[n + 1][n] = a[n + 1][n + 1] = 1;// 其实这个用不上
for(int i = 1; i <= n; i++){
for(int j = i; j <= n + 1; j++){
if(fabs(a[j][i]) > eps){
std::swap(a[i], a[j]);
break;
}
}
for(int j = n + 1; j >= i; j--){
a[i][j] /= a[i][i];
}
for(int j = 1; j <= n + 1; j++){
if(j == i) continue;
for(int k = n + 1; k >= i; k--){
a[j][k] -= a[j][i] * a[i][k];
}
}
}
for(int i = 1; i <= n; i++){
for(auto j:v[i]){
if(i == n) ans[j.second] = a[j.first][n + 1] / v[j.first].size();
else ans[j.second] = a[i][n + 1] / v[i].size() + a[j.first][n + 1] / v[j.first].size();
}
}
std::sort(ans + 1, ans + m + 1);
double ans2 = 0;
for(int i = 1; i <= m; i++){
ans2 += ans[i] * (m - i + 1);
}
std::cout << std::setprecision(3) << std::fixed << ans2 << '\n';
}
}
时间复杂度：。
错排问题
UPD：原表述有误。
定义 为钦定存在 个下标满足 ，剩下可选可不选（注意，同一种 的取值可能贡献不止 个方案）。显然它的数量为 ，容斥系数为 。所以答案为 。
P1758
Ad-hoc 神题。
转化成选两次相同的方案数，怎么想到的？
然后令第一次选到了 ，第二次选到了 ，就有了一个很显然的 DP。
毒瘤题还卡空间，记得滚动数组。
namespace cjdst{
const ll N = 500, mod = 1024523;
ll dp[2][N + 5][N + 5];
std::string a, b;
void solve(){
int n, m;
std::cin >> n >> m >> a >> b;
a = " " + a + " ";
b = " " + b + " ";
dp[1][0][0] = 1;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
for(int k = 0; k <= i + j; k++){
if(i && k && a[i] == a[k]) dp[1][j][k] += dp[0][j][k - 1];
if(i && i + j - k && a[i] == b[i + j - k]) dp[1][j][k] += dp[0][j][k];
if(j && k && b[j] == a[k]) dp[1][j][k] += dp[1][j - 1][k - 1];
if(j && i + j - k && b[j] == b[i + j - k]) dp[1][j][k] += dp[1][j - 1][k];
dp[1][j][k] %= mod;
}
}
for(int j = 0; j <= m; j++){
for(int k = 0; k <= i + j; k++){
dp[0][j][k] = dp[1][j][k];
dp[1][j][k] = 0;
}
}
}
std::cout << dp[0][m][n] << '\n';
}
}
时间复杂度：。
CF1204E
为啥大家对我的风评都不太好，我线上是啥很爱说脏话的人吗？我不是始终贯彻良言一句三冬暖的思想吗？我为人彬彬有礼，对那些动不动就骂人的人特别反感！
为啥大家对我的风评都不太好，我线上是啥很爱说脏话的人吗？我不是始终贯彻良言一句三冬暖的思想吗？我为人彬彬有礼，对那些动不动就骂人的人特别反感！
为啥大家对我的风评都不太好，我线上是啥很爱说脏话的人吗？我不是始终贯彻良言一句三冬暖的思想吗？我为人彬彬有礼，对那些动不动就骂人的人特别反感！
考虑转化。注意到可以转化为一个二维网格， 往 轴一格， 往 轴一格。然后每个 求的是说过程中到达并不越过 这条线的方案数。
虽然说求刚好到达要容斥，但是你注意到答案 ，所以其实可以看成到达（可以越过）的方案数之和，不用容斥。
假设第一次到达的点为 ，然后我们按 对称一下，发现刚好会到达 ，而这个与到达 的点一一对应。所以就是求这个的方案数。注意，如果 本来就在另一边的话就不用对称了。
额我的代码好像 是反的，将就着看吧。
namespace cjdst{
const ll N = 5000, mod = 998244853;
ll frac[N + 5], invfrac[N + 5];
ll ksm(ll x, ll y){
ll ans = 1;
while(y){
if(y & 1) ans = x * ans % mod;
x = x * x % mod, y >>= 1;
}
return ans;
}
int n, m;
ll C(ll n, ll m){
if(n <= 0 || m < 0 || m > n) return 0;
return (frac[n] * invfrac[m] % mod * invfrac[n - m] % mod);
}
ll catlan(ll n, ll m, ll k){
if(n + k < m) return C(n + m, m);
return C(n + m, m - k);
}
void solve(){
frac[0] = 1;
for(int i = 1; i <= N; i++){
frac[i] = frac[i - 1] * i % mod;
}
invfrac[N] = ksm(frac[N], mod - 2);
for(int i = N - 1; i >= 0; i--){
invfrac[i] = invfrac[i + 1] * (i + 1) % mod;
}
std::cin >> n >> m;
std::swap(n, m);
ll ans = 0;
for(int i = 1; i <= m; i++){
ans += catlan(n, m, i);
ans %= mod;
}
std::cout << ans << '\n';
}
}
时间复杂度：。
有帮助，赞一个