专栏文章
【抽象】2025 sm的NOIP模拟赛 第二篇
题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @min5njgv
- 此快照首次捕获于
- 2025/12/01 20:58 3 个月前
- 此快照最后确认于
- 2025/12/01 20:58 3 个月前
R42 T1
P14460 【MX-S10-T1】『FeOI-4』寻雾启示题意
给定 ，现在有一个人从 点出发， 点每隔 秒会刷新一个羊毛，当处于 点时，可以拿走目前 点刷新出的所有羊毛。当从一个铺了羊毛的位置到一个没有铺羊毛的位置，需要花费一个羊毛和 时间，否则需要消耗 时间。若没有羊毛铺路，则不能去往下一格没有羊毛的位置。
现在求对于 时，这个人把 的位置都铺了羊毛的最少时间。
。
思路
首先铺羊毛的形式一定时等一会羊毛，把手上的羊毛铺完后回去拿羊毛或者等一会羊毛，于是我们设 表示铺完前 个位置的最小时间，考虑枚举一个位置 走回起点拿羊毛再铺到 ，那么我们有转移式
这是一个 的 dp，考虑优化。
先拆分项，把跟 有关的弄到一起，跟 有关的弄到一起，那么有
\max(f_j+j\times t_2,i\times k)+j\times t_2 + (i-j)\times t_1 &= \max(f_j+j\times t_2+j\times(t_2-t_1),i\times k+j\times(t_2-t_1))+i\times t_1
\end{aligned}$$
然后由于 $f_i+j\times t_2$ 递增，于是我们可以考虑用指针去移动 $i\times k$ 能够覆盖的位置，不能覆盖到的用线段树处理即可，复杂度 $\Omicron(m\log m)$。
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
#define L (p<<1)
#define R (p<<1|1)
using namespace std;
template<typename T> inline void read(T &x){
T w=1;
x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const ll N=1e5+10,inf=1e17;
ll m,k,t1,t2;
ll f[N];
vector<ll>v[N];
ll sum[N<<2];
void pushup(ll p){
sum[p]=min(sum[L],sum[R]);
}
void build(ll l,ll r,ll p){
sum[p]=inf;
if(l==r) return ;
ll mid=l+r>>1;
build(l,mid,L),build(mid+1,r,R);
return ;
}
void modify(ll l,ll r,ll x,ll z,ll p){
if(l==r){
sum[p]=z;
return ;
}
ll mid=l+r>>1;
if(mid>=x) modify(l,mid,x,z,L);
else modify(mid+1,r,x,z,R);
pushup(p);
return ;
}
ll query(ll l,ll r,ll x,ll y,ll p){
if(x>y) return inf;
if(x<=l&&r<=y) return sum[p];
ll mid=l+r>>1,res=inf;
if(mid>=x) res=min(res,query(l,mid,x,y,L));
if(mid<y) res=min(res,query(mid+1,r,x,y,R));
return res;
}
void solve(){
read(m),read(k),read(t1),read(t2);
build(0,m,1);
f[0]=0;
modify(0,m,0,0,1);
v[1].push_back(0);
ll pos=0;
for(int i=1;i<=m;i++){
for(auto p : v[i]) pos=max(pos,p);
f[i]=min(query(0,m,pos+1,i-1,1)+1ll*i*t1,1ll*i*k+min(0ll,pos*(t2-t1))+1ll*i*t1);
ll s=(f[i]+1ll*i*t2-1)/k+1;
if((f[i]+1ll*i*t2)%k==0&&t2<t1) s++;
if(s<=m) v[s].push_back(i);
if(s<=i) pos=max(pos,1ll*i);
modify(0,m,i,f[i]+1ll*i*t2+1ll*i*(t2-t1),1);
// cout<<s<<" ";
}
// cout<<"\n";
for(int i=1;i<=m;i++){
write(f[i]);
if(i!=m) putchar(' ');
}
putchar('\n');
for(int i=0;i<=m;i++) v[i].clear();
}
int main(){
// freopen("a2.in","r",stdin);
// freopen("a.out","w",stdout);
int T;
read(T);
while(T--) solve();
return 0;
}
/*
10
1 998244353 32449587 103432545
10 1000000000 10 9
10 1000000000 8 2
10 3 1000000000 1000000000
10 8 1000000000 1000000000
100 72 97 91
100 30 97 86
1000 344350423 343943497 36846398
1000 182539971 663315063 130231850
100000 431722183 935312919 310876391
*/
```
# R42 T2
[P14461 【MX-S10-T2】『FeOI-4』青年晚报](https://www.luogu.com.cn/problem/P14461)
## 题意
给定两个 $m$ 次多项式 $F_0(x),G_0(x)$，并有递推式
F_i(x)=G_{i-1}(x)+G'{i-1}(x)\
G_i(x)=F{i-1}(x)-F'_{i-1}(x)\
给定 $n$，求 $F_n(x)$ 和 $G_n(x)$ 的各项系数。
$1\le m\le 5\times 10^3,1\le n\le 10^9$。
### 思路1
以 $F$ 为例，我们设 $f_{i,j}$ 表示 $F_i(x)$ 的 $j$ 次项系数，$g_{i,j}$ 同理，根据递推式，那么我们有
$$\begin{aligned}
f_{i,j} &= g_{i-1,j}+g_{i-1,j+1}\times(j+1)\\
&= f_{i-2,j}-f_{i-2,j+1}\times(j+1)+(f_{i-2,j+1}+f_{i-2,j+2}\times(j+2))\times (j+1)\\
&= f_{i-2,j}-f_{i-2,j+2}\times(j+1)\times (j+2)
\end{aligned}$$
在多项式意义下，即
F_i(x)=F_{i-2}(x)-F_{i-2}''(x)
G_i(x)=G_{i-2}(x)-G_{i-2}''(x)
因此我们只要会算 $F$ 就会算 $G$，考虑怎么算。
为了方便，我们强制 $n$ 为偶数，如果是奇数只要做一次递推即可。
我们尝试计算 $F_4(x)$。
$$\begin{aligned}
F_4(x) &= F_2(x)-F_2(x)''\\
&= (F_0(x)-F_0(x)'')-(F_0(x)-F_0(x)'')''\\
&= F_0(x)-2F_0(x)''+F_0(x)''''
\end{aligned}$$
似乎有点规律。我们再尝试计算 $F_6$。
$$\begin{aligned}
F_6(x) &= F_4(x)-F_4(x)''\\
&= (F_0(x)-2F_0(x)''+F_0(x)'''')-(F_0(x)-2F_0(x)''+F_0(x)'''')''\\
&= F_0(x)-3F_0(x)''+3F_0(x)''''-F_0(x)''''''
\end{aligned}$$
观察可得公式
F_{2n}(x)=\sum_{i=0}^{n}(-1)^i\times C_{n}^{i}\times F_0(x)^{(2i)}
然后注意到 $m$ 次多项式在导最多 $m+1$ 次后就会变成 $0$，于是我们有
F_{2n}(x)=\sum_{i=0}^{\min(n,\lfloor\frac{m+1}{2}\rfloor)}(-1)^i\times C_{n}^{i}\times F_0(x)^{(2i)}
然后直接做就行了，复杂度 $\Omicron(m^2)$。
### 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
T w=1;
x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const ll N=5e3+10,mod=1e9+7;
ll m,n;
struct Dx{
ll x[N];
Dx friend operator ~ (Dx a){
for(int i=0;i<m;i++) a.x[i]=1ll*a.x[i+1]*(i+1)%mod;
a.x[m]=0;
return a;
}
Dx friend operator - (Dx a,Dx b){
for(int i=0;i<=m;i++) a.x[i]=(a.x[i]-b.x[i]+mod)%mod;
return a;
}
Dx friend operator + (Dx a,Dx b){
for(int i=0;i<=m;i++) a.x[i]=(a.x[i]+b.x[i]+mod)%mod;
return a;
}
Dx friend operator * (Dx a,ll b){
for(int i=0;i<=m;i++) a.x[i]=(a.x[i]*b%mod+mod)%mod;
return a;
}
}F,G,ansF,ansG;
ll inv[N];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m);
for(int i=0;i<=m;i++) read(F.x[i]);
for(int i=0;i<=m;i++) read(G.x[i]);
inv[0]=inv[1]=1;
for(int i=2;i<=m;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
ll sum=1,tag=1;
if(n&1){
Dx nF=G+(~G),nG=F-(~F);
n--;
F=nF,G=nG;
}
for(int i=0;i<=min(n/2,(m+1)/2);i++){
ansF=ansF+((F*sum)*tag);
ansG=ansG+((G*sum)*tag);
tag=-tag;
F=(~F),F=(~F),G=(~G),G=(~G);
sum=sum*(n/2-i)%mod*inv[i+1]%mod;
}
for(int i=0;i<=m;i++){
write(ansF.x[i]);
if(i!=m) putchar(' ');
}
putchar('\n');
for(int i=0;i<=m;i++){
write(ansG.x[i]);
if(i!=m) putchar(' ');
}
putchar('\n');
return 0;
}
/*
*/
```
### 思路2（口胡）
注意到对于系数的转移的式子是杨辉三角的形式的，直接做即可。
# R42 T3
[P14462 【MX-S10-T3】『FeOI-4』寻宝游戏](https://www.luogu.com.cn/problem/P14462)
神秘corner case，使大运创思我。
## 题意
有 $n+10^6$ 个桶，前 $n$ 个桶中第 $i$ 个桶有 $a_i$ 袋泡面，现在给定 $q$ 此询问，每次询问给定一个区间 $[l,r]$，求在只保留区间 $[l,r]$ 内的桶和泡面以及 $[n+1,n+10^6]$ 的空桶的情况下是否能够将所有泡面移动到一个桶中。如果可以，输出最少的移动次数，否则输出 $-1$。
一次合法的移动如下：
- 选择互不相同的 $i,j,k$，并且满足桶 $i,j$ 中至少有一袋泡面，在 $i,j$ 中各取一袋泡面，都放入桶 $k$ 中。
$1\le n,q\le 3\times 10^5$。
## 思路
先考虑 $r-l+1\ge 3$ 的情况。
贪心地想，我们最后将所有泡面放在最大值桶中总是最优的，但是由于奇偶性问题，我们还需要比较放在严格次大值的桶的情况。
我们把这个确定的最后放置泡面的桶称为万能桶（最大值或严格次大值）。考虑如果我们确定最后放在万能桶，其他桶的泡面应该怎么移动。
我们设剩下的桶为 $a_1,a_2…a_k$，并且有 $a_1\ge a_2\dots\ge a_k$，考虑分类讨论。
- $a_1\le \sum_{i=2}^{k} a_i$。这个时候我们考虑每次移动让 $a_1\sim a_k$ 中的最大值和次大值匹配，并且移动到万能桶中。那么对于 $2\mid (\sum_{i=1}^{k} a_i)$ 的情况，显然最小移动次数为 $\frac{\sum_{i=1}^{k}a_i}{2}$。否则我们考虑从万能桶中拿一个出来和任意一个剩余桶匹配，那么和变为偶数，同时 $\sum_{i=1}^{k} a_i$ 增加 $1$，因此此时的移动次数为 $\frac{(\sum_{i=1}^{k} a_i)+1}{2}+1$。整合一下两种情况，那么答案就是 $\lfloor\frac{(\sum_{i=1}^{k}a_i)+1}{2}\rfloor + (\sum_{i=1}^{k} a_i)\bmod 2$。
- $a_1\gt \sum_{i=2}^{k}a_i$。这个时候我们考虑让 $a_1$ 去匹配后面的，并且将这些泡面放到 $a_{n+1}$ 中。那么显然此时 $(\sum_{i=1}^{k}a_i)+a_{n+1}$ 总和不变，并且每次我们使 $a_i$ 减 $1$，$(\sum_{i=1}^{k}a_i)+a_{n+1}$ 加 $1$。设 $S=\sum_{i=2}^{k} a_i$。若本身 $\sum_{i=1}^{k} a_i$ 就是偶数，那么通过 $\frac{a_1-T}{2}$ 步使得 $a_1=(\sum_{i=2}^{k}a_i)+a_{n+1}$ 后，再用 $\frac{a_1+T}{2}$ 步按照情况 $1$ 移动，显然是最终需要 $a_1$ 步。如果 $\sum_{i=1}^{k} a_i$ 是奇数，那么可以在一开始就从万能桶中拿一个出来和 $a_1$ 匹配放到 $a_{n+1}$ 中，这样一次性让 $a_1$ 减 $1$，$a_{n+1}$ 加 $2$，最终的步数也是 $a_1$。特别地，若最初时就有 $a_1=(\sum_{i=2}^{k}a_i)+1$，那么移动步数为 $a_1+1$。
整理一下，我们的移动步数就是 $\max(a_1,\lfloor\frac{(\sum_{i=1}^{k}a_i)+1}{2}\rfloor+(\sum_{i=1}^{k}a_i)\bmod 2)$。
更特别地，若 $\sum_{i=l}^{r}([a_i=1])=r-l+1$，只需要 $\lfloor\frac{r-l+1}{2}\rfloor$ 次即可。具体地，区间长度为奇数时把泡面匹配到区间内一个桶中，偶数时把所有泡面都匹配到一个空桶中。
接下来考虑 $r-l+1\le 2$ 的情况。
若 $r-l+1=1$，此时不用移动，答案为 $0$。
若 $r-l+1=2$，我们设桶 $l$ 值为 $x$，桶 $r$ 值为 $y$，并且默认 $x\le y$：
- $x=1,y=1$，此时直接匹配放到一个空桶中即可，答案为 $1$。
- $x=1,y=2$，此时如何移动东无法完成，答案为 $-1$。
- $y\ge x>1$，此时我们考虑使用一次移动分别从 $x,y$ 中取一个放到空桶中，变为 $x-1,y-1,2$，这个时候就可以按照 $r-l+1\ge 3$ 的情况做了。
- $x=1,y\gt 2$，此时我们考虑两个桶分别取一个放到一个空桶中，变为 $y-1,2$，由于 $y\gt 2$，减 $1$，后仍有 $y\gt 1$，因此可以按 $y\ge x\gt 1$ 的情况做。
## 代码
```cpp
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
T w=1;
x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const ll N=3e5+10,inf=1e16;
struct tree{
ll ma,se,sum,cnt;
bool id1;
}tr[N<<2];
ll n,q,a[N];
#define L (p<<1)
#define R (p<<1|1)
void pushup(ll p){
if(tr[L].ma>tr[R].ma){
tr[p].ma=tr[L].ma;
tr[p].cnt=tr[L].cnt;
if(tr[R].ma!=tr[p].ma) tr[p].se=max(tr[L].se,tr[R].ma);
else tr[p].se=max(tr[L].se,tr[R].se);
}
else if(tr[L].ma<tr[R].ma){
tr[p].ma=tr[R].ma;
tr[p].cnt=tr[R].cnt;
if(tr[L].ma!=tr[p].ma) tr[p].se=max(tr[R].se,tr[L].ma);
else tr[p].se=max(tr[R].se,tr[L].se);
}
else{
tr[p].ma=tr[L].ma;
tr[p].cnt=tr[L].cnt+tr[R].cnt;
tr[p].se=max(tr[L].se,tr[R].se);
}
tr[p].id1=(tr[L].id1&tr[R].id1);
tr[p].sum=tr[L].sum+tr[R].sum;
}
void build(ll l,ll r,ll p){
tr[p]={-inf,-inf,0,0,0};
if(l==r) return ;
ll mid=l+r>>1;
build(l,mid,L),build(mid+1,r,R);
return ;
}
void add(ll l,ll r,ll x,ll p){
if(l==r) return (void)(tr[p]={a[x],-inf,a[x],1,(a[x]==1)});
ll mid=l+r>>1;
if(mid>=x) add(l,mid,x,L);
else add(mid+1,r,x,R);
pushup(p);
return ;
}
struct g{
ll ma,se,cnt;
};
void chan(g &a,g b){
if(a.ma<b.ma) swap(a,b);
if(a.ma>b.ma) a.se=max(a.se,b.ma);
else if(a.ma==b.ma){
a.cnt+=b.cnt;
a.se=max(a.se,b.se);
}
}
g query(ll l,ll r,ll x,ll y,ll p){
if(x<=l&&r<=y) return {tr[p].ma,tr[p].se,tr[p].cnt};
ll mid=l+r>>1;
g res={-inf,-inf,0};
if(mid>=x) chan(res,query(l,mid,x,y,L));
if(mid<y) chan(res,query(mid+1,r,x,y,R));
return res;
}
bool all_1(ll l,ll r,ll x,ll y,ll p){
if(x<=l&&r<=y) return tr[p].id1;
ll mid=l+r>>1;
bool res=1;
if(mid>=x) res&=all_1(l,mid,x,y,L);
if(mid<y) res&=all_1(mid+1,r,x,y,R);
return res;
}
ll ges(ll l,ll r,ll x,ll y,ll p){
if(x<=l&&r<=y) return tr[p].sum;
ll mid=l+r>>1;
ll res=0;
if(mid>=x) res+=ges(l,mid,x,y,L);
if(mid<y) res+=ges(mid+1,r,x,y,R);
return res;
}
ll calc(ll s1,ll s2,ll s3){
ll sum=s1+s2+s3;
ll ma=max(s1,(max(s2,s3)));
ll se=max(s1*(s1!=ma),max(s2*(s2!=ma),s3*(s3!=ma)));
if(s1==s2&&s2==s3) se=ma;
ll cnt=(s1==ma)+(s2==ma)+(s3==ma);
ll t1=max(cnt>1 ? ma : se,(sum-ma+1>>1)+(sum-ma&1));
ll t2=max(ma,(sum-se+1>>1)+(sum-se&1));
return min(t1,t2);
}
void solve(){
read(n),read(q);
build(1,n,1);
for(int i=1;i<=n;i++) read(a[i]),add(1,n,i,1);
while(q--){
ll l,r;
read(l),read(r);
if(r-l+1>=3){
if(all_1(1,n,l,r,1)) write((r-l+1)>>1);
else{
g t=query(1,n,l,r,1);
ll sum=ges(1,n,l,r,1);
if(t.se==-inf) t.se=t.ma;
ll t1=max(t.cnt>1 ? t.ma : t.se,(sum-t.ma+1>>1)+(sum-t.ma&1));
ll t2=max(t.ma,(sum-t.se+1>>1)+(sum-t.se&1));
write(min(t1,t2));
// cout<<"\n"<<t.ma<<" "<<t.se<<" "<<t.cnt<<"\n---\n";
}
}
else if(r-l+1==1) write(0);
else{
if(a[l]>a[r]) swap(l,r);
if(a[l]==1&&a[r]==1) write(1);
else if(a[l]==1&&a[r]==2) write(-1);
else if(a[l]==1&&a[r]>2) write(calc(a[r]-2,1,2)+2);
else if(a[l]>1) write(calc(a[l]-1,a[r]-1,2)+1);
}
putchar('\n');
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T;
read(T);
while(T--) solve();
return 0;
}
/*
1
4
1
1 2 5 5
1 4
*/
```
# R43 T1
[CF1503E 2-Coloring](https://www.luogu.com.cn/problem/CF1503E)
很高的质量，但是T1给紫。
## 题意
现在往一个 $n$ 行 $m$ 列的网格中放棋子，要求：
- 每行放了棋子的格子必须为一个区间，且不允许不放。
- 每列的空格必须为一个区间，且不允许放满。
求放置方案数。
$1\le n,m\le 2021$。
## 思路
首先手模或观察可得，最终的网格大致时上面下面各一个山峰，并且只有可能有两种形式：
- 第一种，如下图，这种情况是下面的峰顶和上面的峰顶位于同一条线上，并且两者不会在峰顶相连。
为了方便，我们即 $t_{i,j}$ 表示长度为 $i$ 且严格不降的最大值 $\le j$ 的序列数。
在这种情况下，我们考虑枚举上峰顶和下峰顶靠近中间的位置 $l,r$，以及这条重合线的高度，那么这种情况的方案数我们有
2\sum_{i=1}^{n-1}\sum_{l=1}^{m}\sum_{r=l+1}^{m} t_{l-1,i}\times t_{m-l,i-1}\times t_{r-1,i-1}\times t_{m-r,i}
在这里我们默认让下峰顶在上峰顶右边，由于是对称的，所以最后方案数会乘 $2$。
- 第二种，如下图，这种情况不像第一种有明确的“线”，而是上峰顶和下峰顶侧面有交。
类似于第一种，我们考虑枚举中间的线的位置以及上峰顶高度和下峰顶高度，那么这种情况的方案数为
2\sum_{i=1}^{m-1}\sum_{h1=2}^{n-1}\sum_{h2=n-h1+1}^{n-1} (t_{i,h1}-t_{i,h1-1})\times t_{m-i,n-h2-1}\times(t_{m-i,h2}-t_{m-i,h2-1})\times t_{i,n-h1-1}
这两个式子显然是可以前缀和优化到 $\Omicron(n^2)$ 的，预处理一部分求和即可。
Ps：笔者的代码在 $n\gt m$ 时会出错，至今不知道为什么。
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
T w=1;
x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const ll N=3e3+10,mod=998244353;
ll n,m;
ll t[N][N],f[N][N],g[N][N];
int main(){
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
read(n),read(m);
if(n>m) swap(n,m);
for(int i=0;i<=m;i++) t[0][i]=1;
for(int i=1;i<=m;i++){
for(int j=0;j<=n;j++) t[i][j]=t[i-1][j];
for(int j=1;j<=n;j++) t[i][j]=(t[i][j]+t[i][j-1])%mod;
}
ll ans=0;
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
f[i][j]=(f[i][j-1]+t[j-1][i]*t[m-j][i-1]%mod)%mod;
}
}
for(int i=1;i<n;i++){
for(int r=2;r<=m;r++){
// ans=(ans+t[l-1][i]*t[m-l][i-1]%mod*t[r-1][n-i-1]%mod*t[m-r][n-i]%mod)%mod;
ans=(ans+f[i][r-1]%mod*t[r-1][n-i-1]%mod*t[m-r][n-i]%mod)%mod;
}
}
for(int mid=1;mid<m;mid++){
for(int h2=1;h2<n;h2++){
g[mid][h2]=(g[mid][h2-1]+(t[m-mid][h2]-t[m-mid][h2-1]+mod)%mod*t[m-mid][n-h2-1]%mod)%mod;
}
}
for(int mid=1;mid<m;mid++){
for(int h1=2;h1<n;h1++){
// ans=(ans+(t[mid][h1]-t[mid][h1-1]+mod)%mod*t[mid][n-h1-1]%mod*(t[m-mid][h2]-t[m-mid][h2-1]+mod)%mod*t[m-mid][n-h2-1]%mod)%mod;
ans=(ans+(t[mid][h1]-t[mid][h1-1]+mod)%mod*t[mid][n-h1-1]%mod*(g[mid][n-1]-g[mid][n-h1]+mod)%mod)%mod;
}
}
ans=(ans*2ll)%mod;
write((ans+mod)%mod);
return 0;
}
/*
行只能选择一个区间放
列只能放一段前缀和后缀
17 13
575053520
737338284
*/
```
# R43 T3
这题质量一般。
## 题意
有一个 $n$ 行 $m$ 列的矩阵，并给出 $c$ 次矩阵加的操作。给定一个常数 $k$，每一行中数值 $\ge k$ 的格子为黑格，否则为白格。
现在给定 $q$ 次询问，每次给定 $x,y$，表示要选中 $x$ 行，每行选取 $y$ 个格子，设有一行选的 $y$ 个格子中有 $a$ 个白格，$b$ 个黑格，那么这一行的价值为 $a\times b$。求每次询问的所有选取方案的最大价值。
$1\le n,m,c\le3\times 10^5,1\le k\le 10,1\le q\le 10^6$。
## 思路
缝合题。
注意到 $k$ 非常小，我们考虑线段树上每个区间维护区间内的严格前 $k$ 小值以及这些值每个值的个数，合并时归并合并即可。
然后矩形加的操作可以离线下来，转换为经典的扫描线。
那么对于一行的黑格和白格个数，我们在扫描线的过程就能够求出来。分别设为 $b_i$ 和 $w_i$，并设 $sum_i=\min(b_i,w_i)$。
考虑查询。贪心地想，一行的价值是 $\min(\lfloor\frac{y}{2}\rfloor,sum_i)\times(y-\min(\lfloor\frac{y}{2}\rfloor,sum_i))$，显然 $sum_i$ 越大越好，于是我们可以初始时考虑将所有 $sum_i$ 降序排序，查询时二分找到最后一个 $\ge \lfloor\frac{y}{2}\rfloor$ 的位置，分类讨论一下和 $x$ 的大小后求值即可。
注意二分边界。
复杂度 $\Omicron(n\log n+q\log n)$。
## 代码
```cpp
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T &x){
T w=1;
x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const int N=3e5+10,K=12,inf=2e9+10;
int n,m,c,q,k;
#define min(a,b) (a<b?a:b)
#define pii pair<int,int>
#define fi first
#define se second
struct SGT{
struct node{
int tag;
pii c[K];
void operator += (int s){
for(int i=0;i<k&&c[i].fi<inf;++i) c[i].fi+=s;
}
}tr[N<<2];
#define L (p<<1)
#define R (p<<1|1)
void pushup(int p){
int i=0,j=0,pos=0;
while(pos<k&&(i<k||j<k)&&(tr[L].c[i].fi<=c||tr[R].c[j].fi<=c)){
if(tr[L].c[i].fi<tr[R].c[j].fi){
tr[p].c[pos]=tr[L].c[i];
++pos,++i;
}
else if(tr[L].c[i].fi>tr[R].c[j].fi){
tr[p].c[pos]=tr[R].c[j];
++pos,++j;
}
else{
tr[p].c[pos]={tr[L].c[i].fi,tr[L].c[i].se+tr[R].c[j].se};
++pos,++i,++j;
}
}
while(pos<k) tr[p].c[pos]={inf,0},pos++;
}
void pushdown(int p){
tr[L]+=tr[p].tag,tr[R]+=tr[p].tag;
tr[L].tag+=tr[p].tag,tr[R].tag+=tr[p].tag;
tr[p].tag=0;
}
void build(int l,int r,int p){
tr[p].tag=0,tr[p].c[0]={0,r-l+1};
for(int i=1;i<=k;++i) tr[p].c[i]={inf,0};
if(l==r) return ;
int mid=l+r>>1;
build(l,mid,L),build(mid+1,r,R);
return ;
}
void add(int l,int r,int x,int y,int z,int p){
if(x<=l&&r<=y){
tr[p].tag+=z;
return (tr[p]+=z);
}
if(tr[p].tag) pushdown(p);
int mid=l+r>>1;
if(mid>=x) add(l,mid,x,y,z,L);
if(mid<y) add(mid+1,r,x,y,z,R);
pushup(p);
return ;
}
}T;
int x,y,xx,yy,xt,yt,lb,rb;
struct line{
int l,r,id;
};
vector<line>v[N];
int sum[N];
typedef long long ll;
ll pre[N],pre1[N];
bool cmp(int a,int b){
return a>b;
}
signed main(){
freopen("army.in","r",stdin);
freopen("army.out","w",stdout);
read(n),read(m),read(c),read(k),read(q);
for(int i=1;i<=c;++i){
read(x),read(y),read(xx),read(yy);
v[x].push_back({y,yy,1});
if(xx+1<=n) v[xx+1].push_back({y,yy,-1});
}
T.build(1,m,1);
for(int i=1;i<=n;++i){
for(line p : v[i]) T.add(1,m,p.l,p.r,p.id,1);
int t=0,j=0;
while(j<k&&T.tr[1].c[j].fi<k){
t+=T.tr[1].c[j].se;
++j;
}
sum[i]=min(t,m-t);
// for(int j=0;j<k;j++){
// cout<<T.tr[1].c[j].fi<<" "<<T.tr[1].c[j].se<<"\n";
// }
// cout<<"\n";
}
// for(int i=1;i<=n;++i) cout<<sum[i]<<" ";
// cout<<"\n";
sort(sum+1,sum+n+1,cmp);
for(int i=1;i<=n;++i) pre[i]=pre[i-1]+(1ll*sum[i]*sum[i]),pre1[i]=pre1[i-1]+1ll*sum[i];
// cout<<'\n';
while(q--){
read(xt),read(yt);
int yg=yt/2;
if(sum[xt]>=yg) write(1ll*xt*(yg*(yt-yg)));
else{
lb=-1,rb=n+1;
int kt=0;
while(lb<=rb){
int md=lb+rb>>1;
if(sum[md]>=yg) lb=md+1,kt=md;
else rb=md-1;
}
write(1ll*kt*(1ll*yg*(1ll*yt-1ll*yg))+1ll*(pre1[xt]-pre1[kt])*yt-(pre[xt]-pre[kt]));
}
putchar('\n');
}
return 0;
}
/*
10 10 5 2 1
1 1 6 8
6 5 6 5
4 4 5 8
4 1 5 2
4 1 6 6
6 6
ans:
24
expected:
25
*/
```
# R44 T3
妙妙~~暴力~~题。
## 题意
给定一个长度为 $n$ 的字符串 $T$，以及 $x,k$。字符串只由 ```?,N,O,I,P``` 组成，```?``` 表示这个位置还没有确定，可以放另外的四个字母之一。
给定一个 $4$ 行 $4$ 的表格 $a$，$a_{i,j}$ 表示相邻两个字符 $s_x,s_{x+1}$ 满足 $s_i$ 为 ```"NOIP"``` 里的第 $i$ 个字母，$s_{i+1}$ 为第 $j$ 个字母时的权值。一个字符串 $S$ 的权值定义为所有相邻字符的权值之和。
求所有的在 $T$ 基础上的合法的权值 $\ge x$ 的字符串按字典序降序排序后的第 $k$ 个字符串。如果不存在，输出 $-1$。
$1\le n,k\le10^3$。
## 思路
首先我们明显有一个暴力：直接按规则暴力搜索每一个位置并安排字母，如果其权值 $\ge x$ 就加入备选方案，最后把所有方案进行一个字典序降序排序，第 $k$ 个方案就是答案。
这样的复杂度~~hdu机子都跑不动~~包炸的，我们考虑剪一点枝。
首先，贪心地想，既然最后要求的是字典序降序排序后的第 $k$ 大，我们不妨改一下搜索顺序，每次的搜索按四个字母的字典序降序来枚举放置，那么我们枚举的方案就是字典序降序的。我们记录一个合法方案数 $cnt$，那么只要有一个方案权值 $\ge k$，我们就令 $cnt\gets cnt+1$。如果 $cnt=k$，那么此时搜索到的方案就是答案，可以直接结束搜索。
但是这个东西依旧过不了，而它的瓶颈在于我们会搜索一些很显然没有可能合法的方案，于是我们考虑把这些搜索也剪掉。
我们记 $f_{i,j}$ 表示后缀 $[i,n]$ 中在第 $i$ 个位置放置第 $j$ 个字母能够获得的最大权值，显然我们有
f_{i,j}=\max_{g=1}^{4}{f_{i+1,g}+a_{j,g}}
于是，我们在搜索时记录一个到了当前位置 $pos$ 时已经拥有的权值 $val$，那么能够在位置 $pos$ 放置第 $j$ 个字母并且继续搜索 $pos+1$ 的必要条件就是 $val+f_{pos,j}\ge x$。如果不满足，我们就不进行这一次的搜索。
再加上一开始的贪心之后，我们就可以做到 $\Omicron(nk)$ 的复杂度，可以通过。
## 复杂度、正确性证明
首先方案合法性显然，其次由于本身搜索方案就是按字典序降序来搜索的，因此方案的第 $k$ 大性也满足。
对于复杂度，首先根据贪心以及取方案的正确性，那么我们刚好会取到前 $k$ 个合法方案，并且取一次的复杂度是 $\Omicron(n)$ 的，因此取方案的复杂度是 $\Omicron(nk)$ 的。
那么还有可能影响复杂度的因素就只剩搜索中途的一种情况：有可能搜索到半路就无法继续往下搜索，然后只能回退，也就是搜索到了一些无用方案。
考虑反证法。假设目前的这个位置为无用方案，这意味着这个位置放任意字母都不满足 $val+f_{pos,j}\ge k$。既然这条搜索方案的已经被堵死了，那么显然我们会在更早的位置就直接终止了对这条方案道路的搜索，也就是所有不合法方案都会第一时间被终止，并不会产生搜索到半路没有造成贡献就回退的情况，因此复杂度是正确的。
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
T w=1;
x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const ll N=1e3+10,inf=1e15;
char s[N];
ll a[6][6];
ll n,x,K;
ll base[260];
struct matrix{
ll c[4][4];
void init(){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++) c[i][j]=-inf;
}
}
ll query(ll row){
ll res=-inf;
for(int i=0;i<4;i++) res=max(res,c[row][i]);
return res;
}
}t[N],f[N];
matrix operator * (const matrix &a,const matrix &b){
matrix c;
c.init();
for(int i=0;i<4;i++){
for(int k=0;k<4;k++){
for(int j=0;j<4;j++){
c.c[i][j]=max(c.c[i][j],a.c[i][k]+b.c[k][j]);
}
}
}
return c;
}
ll cnt;
ll lu[N],z[N];
ll ord[4]={3,1,0,2};
char ji[4]={'N','O','I','P'};
bool fl=0;
void dfs(ll pos,ll sum,ll lst){
if(fl) return ;
if(pos>n){
if(sum>=x){
cnt++;
if(cnt==K){
for(int i=1;i<=n;i++) z[i]=lu[i];
fl=1;
}
}
return ;
}
if(s[pos]=='?'){
for(int i=0;i<4;i++){
ll val=sum+f[pos].query(ord[i])+(lst==-1 ? 0 : a[lst][ord[i]]);
if(!fl&&val>=x){
lu[pos]=ord[i];
dfs(pos+1,sum+(lst==-1 ? 0 : a[lst][ord[i]]),ord[i]);
}
}
}
else{
ll val=sum+f[pos].query(base[s[pos]])+(lst==-1 ? 0 : a[lst][base[s[pos]]]);
if(!fl&&val>=x){
lu[pos]=base[s[pos]];
dfs(pos+1,sum+(lst==-1 ? 0 : a[lst][base[s[pos]]]),base[s[pos]]);
}
}
}
void print(matrix a){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++) write(a.c[i][j]),putchar(' ');
putchar('\n');
}
}
int main(){
freopen("perm.in","r",stdin);
freopen("perm.out","w",stdout);
read(n),read(x),read(K);
scanf("%s",s+1);
base['N']=0,base['O']=1,base['I']=2,base['P']=3;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++) read(a[i][j]);
}
for(int i=1;i<n;i++){
t[i].init();
if(s[i]=='?'){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
t[i].c[j][k]=a[j][k];
}
}
}
else{
for(int j=0;j<4;j++) t[i].c[base[s[i]]][j]=a[base[s[i]]][j];
}
}
t[n].init();
if(s[n]=='?'){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++) t[n].c[i][j]=0;
}
}
else{
for(int i=0;i<4;i++) t[n].c[base[s[n]]][i]=0;
}
f[n]=t[n];
for(int i=n-1;i>=1;i--) f[i]=t[i]*f[i+1];
// for(int i=1;i<=n;i++){
// print(f[i]);
// putchar('\n');
// }
dfs(1,0,-1);
if(!fl) write(-1);
else for(int i=1;i<=n;i++) putchar(ji[z[i]]);
return 0;
}
/*
考虑维护矩阵乘 + 贪心 + 暴力搜索
如果说我退回了一个位置，说明这个位置放当前字母的情况已经枚举完了
*/
```
# R45 T4
[CF917D Stranger Trees](https://www.luogu.com.cn/problem/CF917D)
## 题意
给定一棵 $n$ 个点的无根树，求当 $x=0,1,\dots,n-1$ 时，恰好有 $x$ 条边和原树重合的 $n$ 个点的生成树有多少。
$1\le n\le 8000$。
## 思路
遇到这种有”恰好“的题目，考虑转换为“至少”。
若有一个 $n$ 个点，$k$ 个连通块的图，则连通的方案数为
n^{k-1}\prod_{i=1}^{k}s_i
其中 $s_i$ 为第 $i$ 个连通块大小。
那么首先我们记 $f_S$ 表示边集恰好为 $S$ 的方案数，$g_S$ 表示笔记至少包含 $S$ 的方案数，那么我们有
g_S=\sum_{S\in T} f_T
反向考虑 $g$ 对 $f$ 的贡献，类似于容斥，于是我们就有了一个 $\Omicron(2^nn)$ 的暴力：
设 $f_i$ 为恰好重合 $i$ 条边的方案数，$g_i$ 为至少 $i$ 条边的方案数。
暴力枚举重合的是哪些边，算出所有的 $g_i$，然后我们就有
f_i=\sum_{j=i}^{n-1} (-1)^{j-i}\times C_{j}^{j-1}\times g_i
但是这样显然过不了，于是我们考虑是否能够快速求出 $g$。
显然我们有一个简单的 $\Omicron(n^3)$ dp：设 $f_{i,j,k}$ 表示以 $i$ 为根子树数内已经有 $j$ 个连通块并且 $i$ 所处连通块大小为 $k$，转移的时候每枚举一个儿子 $v$ 就进行更新转移即可。转移时枚举当前点与儿子的 $j,k$。复杂度根据树上背包的计算是 $\Omicron(n^3)$。
然后优化计算与状态：设 $f_{i,j,0/1}$ 表示以 $i$ 为根的子树内已经有 $j$ 个连通块且 $i$ 所处的联通块中是否已经有**一个**点被选择出来。转移时考虑当前点到儿子的边是否选择，我们有
f_{u.x,0}\times f_{v,y,1}\to f'{u,x+y,0}\
f{u,x,1}\times f_{v,y,1}\to f'{u,x+y,1}\
f{u,x,0}\times f_{v,y,0}\to f'{u,x+y-1,0}\
f{u,x,0}\times f_{v,y,1}\to f'{u,x+y-1,1}\
f{u,x,1}\times f_{v,y,0}\to f'_{u,x+y-1,1}
依旧树上背包分析，复杂度 $\Omicron(n^2)$。
然后在计算时，$g_i$ 实际上就等于 $f_{1,n-i,1}\times n^{n-j-2}$，这根据 prufer 序列可得（实际上就是 $n-j-2$ 个点的完全图的生成树个数）。
计算也是 $\Omicron(n^2)$ 的。
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
T w=1;
x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const int N=8e3+5,mod=1e9+7;
bool b1;
int n,m;
int head[N],id;
struct edge{
int v,next;
}e[N<<1];
void add(int u,int v){
e[++id]=(edge){v,head[u]},head[u]=id;
}
vector<int>f[N],g[N];//没选，选
int ff[N],gg[N];
int siz[N];
int fac[N],inv[N];
void init(){
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%mod;
}
int C(int x,int y){
if(x<y||x<0||y<0) return 0;
return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void dfs(int u,int fa){
siz[u]=1;
f[u].resize(4),g[u].resize(4);
f[u][1]=1,g[u][1]=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(v==fa) continue;
dfs(v,u);
for(int j=1;j<=siz[u];j++){
for(int k=1;k<=siz[v];k++){
ff[j+k]=(ff[j+k]+1ll*f[u][j]*g[v][k]%mod)%mod;
gg[j+k]=(gg[j+k]+1ll*g[u][j]*g[v][k]%mod)%mod;
ff[j+k-1]=(ff[j+k-1]+1ll*f[u][j]*f[v][k]%mod)%mod;
gg[j+k-1]=((gg[j+k-1]+1ll*f[u][j]*g[v][k]%mod)%mod+1ll*g[u][j]*f[v][k]%mod)%mod;
}
}
siz[u]+=siz[v];
f[u].resize(siz[u]+3),g[u].resize(siz[u]+3);
for(int j=1;j<=siz[u];j++) f[u][j]=ff[j],g[u][j]=gg[j],ff[j]=gg[j]=0;
}
}
int pw[N];
bool b2;
int main(){
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
read(n);
init();
for(int i=1;i<n;i++){
int x,y;
read(x),read(y);
add(x,y),add(y,x);
}
dfs(1,0);
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=1ll*pw[i-1]*n%mod;
// for(int i=0;i<n;i++){
// cout<<1ll*g[1][i+1]%mod<<" ";
// }
// cout<<"\n";
for(int i=0;i<n;i++){
int ans=0;
for(int j=i;j<n;j++){
if(n-j<2) ans=(ans+1ll*(j-i&1 ? -1 : 1)*C(j,j-i)%mod)%mod;
else ans=(ans+1ll*(j-i&1 ? -1 : 1)*C(j,j-i)%mod*g[1][n-j]%mod*pw[n-j-2]%mod)%mod;
}
write((ans+mod)%mod);
putchar(' ');
}
// putchar('\n');
// cerr<<fabs(&b1-&b2)/1048576.0<<"MB";
return 0;
}
```
# CSP T4
[P14364 [CSP-S 2025] 员工招聘 / employ](https://www.luogu.com.cn/problem/P14364)
特别地，补一下题。
## 题意
不多写了。
## 思路
膜拜jiangly。
我们考虑反过来 dp 被拒绝若干个人的的方案数。
注意到我们并不关注放到当前天的人是谁，我们只关注有多少个人的 $c$ 与已经**被拒绝**的人数的关系。
我们假设已经知道了到当前天有多少人被拒绝。设到当前已经有 $x$ 个人被拒绝了。
转移时考虑 $s$：
- $s_i=0$，此时无论如何无法过审，随便放人。
- $s_i=1$，考虑分类讨论：
- 过审：选择的人满足 $c>x$。
- 不过审：选择的人满足 $c\le x$。
注意到 $c>x$ 是一个非常不好算的转移，我们考虑将其容斥为“所有方案数 $-$（$c\le x$ 的方案数）“，这样第二种转移的两种分讨就能共用一次转移方案了。
于是我们设 $f_{i,j,k}$ 表示 前 $i$ 个位置已经有 $j$ 个人被拒绝并且已经有 $k$ 个人被钦定了位置且有 $\le x$ 的方案数。
最终的答案就是
\sum_{i=0}^{n-m}\sum_{j=0}^{n} f_{n,i,j}\times (n-j)!
乘上阶乘是剩下的人可以随便放。
复杂度 $\Omicron(n^3)$。
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
T w=1;
x=0;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const ll N=5e2+10,mod=998244353;
ll f[2][N][N];
ll n,a[N],m;
char c[N];
void ad(ll &x,ll y){
x=(x+y)%mod;
}
ll fac[N];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m);
scanf("%s",c+1);
for(int i=1;i<=n;i++){
ll x;
read(x);
a[x]++;
}
for(int i=1;i<=n;i++) a[i]+=a[i-1];
ll opt=0;
f[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
for(int k=0;k<=i;k++) f[opt^1][j][k]=0;
}
if(c[i+1]=='0'){
for(int j=0;j<=i;j++){
for(int k=0;k<=i;k++) ad(f[opt^1][j+1][k],f[opt][j][k]);
}
}
else{
for(int j=0;j<=i;j++){
for(int k=0;k<=i;k++){
ad(f[opt^1][j][k],f[opt][j][k]);
ll sum=a[j]-k;
ad(f[opt^1][j][k+1],-f[opt][j][k]*sum%mod);
ad(f[opt^1][j+1][k+1],f[opt][j][k]*sum%mod);
}
}
}
opt^=1;
}
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
ll ans=0;
for(int i=0;i<=n-m;i++){
for(int j=0;j<=n;j++) ad(ans,f[opt][i][j]*fac[n-j]%mod);
}
write((ans+mod)%mod);
return 0;
}
```相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...