计数和 dp
来我的博客里读。
P14636 [NOIP2025] 清仓甩卖
前提:NOIP2025 考场上得了
经过 3h 奋战,以下思路由 AI 整理。
先将所有商品按原价从大到小排序,考虑一个贪心失败的关键结构:
考虑对
首先,在买
假设这
接着考虑
买完
于是,对于后面的商品,如果满足
因此总体就是:枚举关键的
这里是一份 AI 的实现:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int N=5005;
int c,T;
int n,m;
int a[5005];
int f[5005],invf[5005],pw[5005];
int qpow(int a,int b){
int h=a,ans=1;
while(b){
if(b&1){
ans*=h;
ans%=mod;
}
h*=h;
h%=mod;
b>>=1;
}
return ans;
}
int C(int x,int y){
if(x<0||y<0||y>x) return 0;
int ans=f[x];
ans*=invf[y];
ans%=mod;
ans*=invf[x-y];
ans%=mod;
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
f[0]=invf[0]=1;
for(int i=1;i<N;i++){
f[i]=f[i-1]*i%mod;
invf[i]=qpow(f[i],mod-2);
}
pw[0]=1;
for(int i=1;i<N;i++){
pw[i]=pw[i-1]*2%mod;
}
cin>>c>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1,greater<int>());
int bad=0;
for(int i=1;i<=n;i++){
int pos=i;
while(pos+1<=n&&a[pos+1]==a[i]){
pos++;
}
int k=n+1;
for(int j=pos+1;j<=n&&2*a[j]>a[i];j++){
while(k-1>j&&a[j]+a[k-1]<a[i]){
k--;
}
int front=C(j-2,m-i-1);
int back=pw[n-k+1];
bad+=front*back%mod;
bad%=mod;
}
}
int ans=(pw[n]-bad+mod)%mod;
cout<<ans<<"\n";
}
return 0;
}
CF1920E Counting Binary Strings
转化一下,一个“好”子串是由中心的一个 1 和周围的若干 0 组成,考虑对这个去做计数,设 1 的个数为
考虑把字符串拆为一串 0 和一些单个的 1 交替组成,一共有 1 隔段的 0 串,设第
现在变为求满足以下条件的非负整数
- 对于任意相邻的
b_i ,满足b_i+b_{i+1}<k -
\sum_i (b_i+1) (b_{i+1}+1)=n
考虑设
CF1521D Nastia Plays with a Tree
不难发现删边数等于加边数,将问题转化为删边。
设
:::info[为什么这样定义]
如果只有一维,我们无法得知一个
:::
分三种情况:
方案简单记录一下。
CF1989E Distance to Different
我怎么还是不会做。
考虑
:::info[一个例子]
-
a = 2,2,2,2,2,2 -
b = 1,2,3,3,2,1 -
a = 3,3,3,3,3 -
b = 1,2,3,2,1
:::
这时候发现,
这里是
每个长度为
- 当
n = 1 时,b = 1 。 - 当
n = 2 时,b = 1,1 。
这样可能算重复,不考虑长度为
这时候,考虑对串统计。
CF1336C Kaavi and Magic Spell
设
当
初始化时若
转移时考虑分左边与右边,左边当
答案就是
P6146 [USACO20FEB] Help Yourself G
洛谷题解区非常神奇,都是使用
考虑连通块数量等于
将所有线段端点离散化,统计每个坐标作为左、右端点的线段数量,并预处理左端点后缀和
接着,枚举每对相邻离散化坐标
两侧选择相互独立,将方案数的乘积累加至答案,最后对
时间复杂度为
CF1918D Blocking Elements
考虑直接二分答案,设当前答案为
固定完答案,设
转移为
答案为
CF1666F Fancy Stack
面对可能重复的序列,我们先不去重,最后再除以每种数字出现次数的阶乘。
设
转移将从
考虑
不难发现,在前
现在考虑
所以转移就是
这个转移不依赖
CF1799D2 Hot Start Up (hard version)
超级好的 dp 题,好像是 CSP2024 T3。
不难发现在一次运行之后,一台 CPU 最后一次操作一定为
- 当使用新的一台 CPU 时
- 当
j=a_i 时,dp_{a_{i-1}}=dp_j+hot_{a_i} - 否则
dp_{a_{i-1}}=dp_j+cold_{a_i}
实际上为
- 当使用旧的一台 CPU 时
- 当
a_{i-1}=a_i 时,dp_j=dp_j+hot_{a_i} - 否则
dp_j=dp_j+cold_{a_i}
这是一个线段树的区间修改和单点赋值,直接做就好了。