若干杂题题解（From 2025.3 to 2025.6）

xuchuhan · 2025-03-18 20:39:52 · 个人记录

P4187 [USACO18JAN] Stamp Painting G

发现一个序列合法当且仅当存在连续的 k 个数颜色相同。但是正着计数不好处理，正难则反，考虑容斥。

设 dp_i 表示当前填完前 i 个，没有连续的 k 个数的方案。答案即为 m^n-dp_n。考虑如何转移。

• 当 i<k，dp_i=dp_{i-1}\times m。这个显然，因为不可能出现连续的 k 的情况。
• 当 i=k，dp_i=dp_{i-1}\times m-m。即所有数都相同时不合法，共 m 种情况，需要减去。
• 当 i>k，dp_i=dp_{i-1}\times m-dp_{i-k}\times(m-1)。解释一下减去的 dp_{i-k}\times(m-1)，就是减去第 i-k+1,i-k+2,\dots,i 共 i 个数都相同且他们与 i-k 不相同的情况，那么就是 dp_{i-k}\times(m-1)，即除了 i-k 的颜色都能选。这样计算贡献是不重不漏的。

整合一下就行了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,mod=1e9+7;
int n,m,k,ans=1,dp[N];
signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)ans=ans*m%mod;
    dp[0]=1;
    for(int i=1;i<=n;i++){
        if(i<k)dp[i]=dp[i-1]*m%mod;
        else if(i>k)dp[i]=(dp[i-1]*m%mod-dp[i-k]*(m-1)%mod+mod)%mod;
        else dp[i]=(dp[i-1]*m%mod-m+mod)%mod;
    }
    cout<<(ans-dp[n]+mod)%mod;
    return 0;
}

#

P2182 翻硬币

参见我的题解。

P6879 [JOI 2020 Final] 集邮比赛 3 / Collecting Stamps 3

一眼区间 DP。首先断环为链。

尝试设 dp_{i,j} 表示区间 [i,j] 最多能取多少个点。发现无法转移。考虑增加一维，dp_{i,j,T} 表示 当前时间为 T，区间 [i,j] 中最多能取多少个点，发现能够尝试转移，但是 T\leq 10^9，且无法优化这一维，所以只能考虑换一种方式思考。

那么我们可以设 dp_{i,j,k} 表示区间 [i,j] 取了 k 个点的最小时间。最后如果 dp_{i,j,k} 所取到的值是合法的则统计 ans\leftarrow \max(ans,k)。这一步转化也是最巧妙的一步转化。

但是发现这样转移还是有一点困难。考虑再升一个维度：dp_{i,j,k,0/1} 表示区间 [i,j]，取到了 k 个合法点，当前在 [i,j] 的左/右端点的最小时间。转移就很简单了。

首先考虑在当前位置不取点的情况。

• dp_{i,j,k,0}\leftarrow dp_{i+1,j,k,0}+x_{i+1}-x_i
• dp_{i,j,k,0}\leftarrow dp_{i+1,j,k,1}+x_j-x_i
• dp_{i,j,k,1}\leftarrow dp_{i+1,j,k,0}+x_j-x_i
• dp_{i,j,k,0}\leftarrow dp_{i+1,j,k,1}+x_j-x_{j-1}

比较简单，不解释了。然后考虑在当前位置取了点的情况，这时需要满足答案不大于当前位置的爆炸时间。这里只写一种情况，其他情况同理类比。

• 当：dp_{i+1,j,k-1,0}+x_{i+1}-x_i\leq t_i 时，dp_{i,j,k,0}\leftarrow dp_{i+1,j,k-1,0}+x_{i+1}-x_i。

最后是初始状态设定。为了方便处理，把起点设为 n+1 号点，x_{n+1}=0,t_{n+1}=\inf。然后对于每个合法的区间 [i,j]，设 dp_{i,j,0,0}=L-x_i,dp_{i,j,0,1}=x_j-L。比较好理解就不提了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=405,inf=1e18;
int n,L,ans,dp[N][N][N>>1][2];
struct node{int x,t;}a[N];
signed main(){
    cin>>n>>L;
    for(int i=1;i<=n;i++)cin>>a[i].x,a[i+n+1].x=a[i].x+L;//断环为链 
    for(int i=1;i<=n;i++)cin>>a[i].t,a[i+n+1].t=a[i].t;//断环为链 
    memset(dp,0x3f,sizeof(dp)),a[n+1]={L,inf};//赋初值&起点处理 
    for(int j=n+1;j<=2*n+1;j++)
        for(int i=n+1;j-i<=n;i--)
            dp[i][j][0][0]=L-a[i].x,dp[i][j][0][1]=a[j].x-L;//赋初值 
    for(int l=1;l<=n+1;l++){
        for(int i=1;i<=n+1;i++){
            int j=i+l-1;
            for(int k=1;k<=l;k++){//区间DP 
                int tmp=0;
                dp[i][j][k][0]=min(dp[i][j][k][0],dp[i+1][j][k][0]+a[i+1].x-a[i].x);
                tmp=dp[i+1][j][k-1][0]+a[i+1].x-a[i].x;
                if(tmp<=a[i].t)dp[i][j][k][0]=min(dp[i][j][k][0],tmp);
                dp[i][j][k][0]=min(dp[i][j][k][0],dp[i+1][j][k][1]+a[j].x-a[i].x);
                tmp=dp[i+1][j][k-1][1]+a[j].x-a[i].x;
                if(tmp<=a[i].t)dp[i][j][k][0]=min(dp[i][j][k][0],tmp);
                dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k][0]+a[j].x-a[i].x);
                tmp=dp[i][j-1][k-1][0]+a[j].x-a[i].x;
                if(tmp<=a[j].t)dp[i][j][k][1]=min(dp[i][j][k][1],tmp);
                dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j-1][k][1]+a[j].x-a[j-1].x);
                tmp=dp[i][j-1][k-1][1]+a[j].x-a[j-1].x;
                if(tmp<=a[j].t)dp[i][j][k][1]=min(dp[i][j][k][1],tmp);
                //转移过程见上文 
                if(dp[i][j][k][0]<1e12||dp[i][j][k][1]<1e12)ans=max(ans,k);//统计答案,注意是||不是&& 
            }
        }
    }
    cout<<ans;
    return 0;
}

#

P2569 [SCOI2010] 股票交易

或许是很经典的单调队列优化 DP？但是没看清题目导致了一些不良后果。

首先可以设 dp_{i,j} 表示第 i 天，手上持有 j 股的最多赚钱数。由于本人没看清题目^{[1]}，导致以为 j 会炸的很惨，想了一会滚动数组优化，后面才发现强制要求 j\leq \text{MaxP}/ll。

然后就考虑转移，发现很困难，因为本人没看清题目^{[2]}，以为一天之内可以同时卖股、买股。但是题目有限制某一天的买入或者卖出均算是一次交易。于是同一天内只能买若干股或卖若干股或不买不卖。

剩下的转移就简单了。分几种情况讨论：

• 不买不卖，继承上一天：dp_{i,j}\leftarrow dp_{i-1,j}。
• 第一次买入股票，没有天数的 W 限制：dp_{i,j}=-j\times AP_i。注意这一种转移存在限制 j\leq AS_i。（否则会是 60pts\kel。）
• 买入部分股票：dp_{i,j}\leftarrow dp_{i-W-1,k}-(j-k)\times AP_i，注意存在天数 W 限制，上一层转移必须是 dp_{i-W-1,\dots}。其次就是不能写成 dp_{i,j}\leftarrow dp_{i-W-1,j-k}+k\times AP_i，这样不方便后续的优化。
• 卖出部分股票：dp_{i,j}\leftarrow dp_{i-W-1,k}+(k-j)\times BP_i，同上。

发现这样第三、四种转移的复杂度是立方级别的，考虑优化。转化一下转移式子：

• 另一种转移同理，即 dp_{i,j}=\max\{dp_{i-W-1,k}+k\times BP_i\}-j\times BP_i。k 的取值范围为 k\in[j+1,j+BS_i]，于是这一种转移需要倒序处理。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+5;
int n,MaxP,W,dp[N][N],AP[N],BP[N],AS[N],BS[N],q[N];
signed main(){
    cin>>n>>MaxP>>W;
    memset(dp,-0x3f,sizeof(dp)),dp[0][0]=0;
    for(int i=1;i<=n;i++){
        cin>>AP[i]>>BP[i]>>AS[i]>>BS[i];
        int head=1,tail=0;
        memset(q,0,sizeof(q));
        for(int j=0;j<=MaxP;j++)dp[i][j]=max(dp[i-1][j],(-j)*AP[i]);
        if(i-W-1<=0)continue;
        for(int j=0;j<=MaxP;j++){
            if(head<=tail&&q[head]<j-AS[i])head++;
            while(head<=tail&&dp[i-W-1][q[tail]]+q[tail]*AP[i]<dp[i-W-1][j]+j*AP[i])tail--;
            q[++tail]=j;
            if(head<=tail)dp[i][j]=max(dp[i][j],dp[i-W-1][q[head]]+q[head]*AP[i]-j*AP[i]);
        }
        head=1,tail=0,memset(q,0,sizeof(q));
        for(int j=MaxP;j>=0;j--){
            if(head<=tail&&q[head]>j+BS[i])head++;
            while(head<=tail&&dp[i-W-1][q[tail]]+q[tail]*BP[i]<dp[i-W-1][j]+j*BP[i])tail--;
            q[++tail]=j;
            if(head<=tail)dp[i][j]=max(dp[i][j],dp[i-W-1][q[head]]+q[head]*BP[i]-j*BP[i]);
        }
    }
    cout<<dp[n][0];
    return 0;
}

#

P8867 [NOIP2022] 建造军营

也是把多年未补的坑补上了/dy。注：下文借鉴第一篇题解。

首先缩点，将整张图转化为一棵树。那么树上一个节点代表一个边双，每一个边双里的点和边都可以自由分配。（敌人无论如何都无法炸一条边使得这个边双不连通。）

转化为树之后，问题成为一个显然的树形 DP。设计状态为 dp_{x,0/1} 表示以 x 为根的子树内建/不建军营的方案数。发现这样不好转移，考虑增加限制。我们强制 dp_{x,0/1} 表示以 x 为根的子树内建/不建军营的方案数，若建军营，则强制要求所有军营必须通过已派兵看守的边与 x 连通。

这个限制第一篇题解中没有做详细解释，我自己的理解是：这样做可以不重不漏且方便统计。需要注意的一点是这样做不会漏掉某子树内的军营自成一体，不通过已派兵看守的边与 x 连通的情况，因为这种情况早在对该点进行 DP 的时候就考虑过了。

同时还要有一个限制：强制限制不选 x\to fa_x 的边。这个的原因是由上一个限制而来，因为后面对于 fa_x 进行 DP 的时候，若 x 内部有军营，则会强制限制选 fa_x\to x 的边，这时若在对于 x 进行 DP 时也选了这条边则会导致重复计算。借用一下第一篇题解的图：

那么有了这两个限制，转移就变得简单而不重不漏了。首先赋初值：

然后进行转移：

• 计算 dp_{x,0}：比较简单，dp_{x,0}\leftarrow dp_{x,0}\times \prod_{to\in son(x)}(2\times dp_{to,0})，表示乘上各个儿子子树方案数的乘积。单棵子树的方案数为 dp_{to,0}\times 2，其中 2 表示边 to\to x 选或不选都可以。

• 计算 dp_{x,1}：考虑一棵一棵添加子树。

  • 若到新增前当前子树 x 内未建造过军营，那么当前儿子 to 子树内必须有军营，即 dp_{x,1}\leftarrow dp_{x,1}+dp_{x,0}\times dp_{to,1}。
  • 若到新增前当前子树 x 内已有军营，那么当前儿子子树内可以有军营也可以没有，即 dp_{x,1}\leftarrow dp_{x,1}+dp_{x,1}\times(dp_{v,1}+2\times dp_{v,0})，2 的含义同上文。

  综上，即 dp_{x,1}\leftarrow dp_{x,1}+dp_{x,0}\times dp_{to,1}+dp_{x,1}\times(dp_{v,1}+2\times dp_{v,0})。

最后是统计答案。令 s(x) 表示以 x 为根节点的子树内的边数，则有 s(x)=E_x+\sum_{to\in son(x)}[s(x)+1]，统计答案分两种情况。

那么题目就做完了，笔者有一个小错误一直卡在 15pts，直到 2025.5.3 终于调出来了。再次纪念并放上代码。代码不难但细节很多，码量较大：

#include<bits/stdc++.h>
#define int long long
#define ID(i) i*2-2
using namespace std;
const int N=5e5+5,M=1e6+5,mod=1e9+7;
int n,m,tot,col,ans,dfn[N],low[N],is[M<<1],vis[N],dccV[N],dccE[N],in[N],siz[N],dp[N][2];
struct node{int to,id;};
struct edge{int x,y;}e[M];
vector<node>v[N];
vector<int>g[N];
int fpow(int a,int b,int p){int ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p,b/=2;}return ans;}
void Tarjan(int x,int preid){
    dfn[x]=low[x]=++tot;
    for(int i=0;i<v[x].size();i++){
        int to=v[x][i].to,id=v[x][i].id;
        if((id^1)==preid)continue;
        if(!dfn[to]){
            Tarjan(to,id);
            if(dfn[x]<low[to])is[id]=is[id^1]=1;
            low[x]=min(low[x],low[to]);
        }
        else low[x]=min(low[x],dfn[to]);
    }
    return;
}
void DFS(int x,int now){
    if(vis[x])return;
    vis[x]=1,dccV[now]++,in[x]=now;
    for(int i=0;i<v[x].size();i++){
        int to=v[x][i].to,id=v[x][i].id;
        if(is[id])continue;
        DFS(to,now);
    }
    return;
}
void dfs(int x,int fa){
    siz[x]=dccE[x];
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==fa)continue;
        dfs(to,x);
        siz[x]+=siz[to]+1;
    }
    return;
}
void DP(int x,int fa){
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==fa)continue;
        DP(to,x);
        dp[x][1]=(dp[to][1]*dp[x][0]%mod+(dp[to][0]*2%mod+dp[to][1])%mod*dp[x][1]%mod)%mod,dp[x][1]%=mod;
        dp[x][0]=dp[x][0]*dp[to][0]*2%mod,dp[x][0]%=mod;
    }
    if(x==1)ans+=dp[x][1],ans%=mod;
    else ans+=dp[x][1]*fpow(2,siz[1]-siz[x]-1,mod)%mod,ans%=mod;
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x==y)continue;
        e[i]={x,y};
        v[x].push_back({y,ID(i)});
        v[y].push_back({x,ID(i)+1});
    }
    for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i,-1);
    for(int i=1;i<=n;i++)if(!vis[i])DFS(i,++col);
    for(int i=1;i<=m;i++){
        if(e[i].x==e[i].y)continue;
        if(in[e[i].x]!=in[e[i].y])
            g[in[e[i].x]].push_back(in[e[i].y]),g[in[e[i].y]].push_back(in[e[i].x]);
        else dccE[in[e[i].x]]++;
    }
    for(int i=1;i<=col;i++)
        dp[i][0]=fpow(2,dccE[i],mod),dp[i][1]=(fpow(2,dccE[i]+dccV[i],mod)-dp[i][0]+mod)%mod;
    dfs(1,0),DP(1,0);
    cout<<ans;
    return 0;
}

P4805 [CCC 2016] 合并饭团

以后做题前还是要认真思考，不然会习惯性以为某个简单题很困难/ll。

首先是一眼区间 DP。但是似乎没办法通过常规的状态“dp_{i,j} 表示区间 [i,j] 中的最大价值”进行转移。观察性质：最后最大的饭团大小一定是初始时某一段区间的饭团大小之和。那么可以设状态 dp_{i,j} 表示区间 [i,j] 能否合并成一个饭团。最后统计答案即：若 dp_{i,j}=1，则 ans\leftarrow \max(ans,\sum_{x=i}^j a_x)。取 \sum 的部分用前缀和处理，以下记为 s_i。

然后考虑转移，这是简单的。不妨只考虑第二种合并三个饭团的情况。考虑在区间 [i,j] 中枚举断点 x,y，将区间分成三段 [i,x],[x+1,y],[y+1,j]，如果这三段都可以被合成成一个饭团且区间 [i,x] 的饭团大小之和等于区间 [y+1,j] 的饭团大小之和，那么区间 [i,j] 可以被合并成一个饭团。即：if(dp[i][x]&&dp[x+1][y]&&dp[y+1][j]&&s[x]-s[i-1]==s[j-s[y]])。

这样做是 \mathcal{O(n^4)} 的，但是开 \text{O(2)} 可过，先放一下代码再讲优化。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=405;
int n,ans,s[N],dp[N][N];
signed main(){
    cin>>n;
    for(int i=1,x;i<=n;i++)cin>>x,s[i]=s[i-1]+x;
    for(int i=1;i<=n;i++)dp[i][i]=1;
    for(int l=2;l<=n;l++){
        for(int i=1;i+l-1<=n;i++){
            int j=i+l-1;
            for(int k=i;k<j;k++)if(dp[i][k]&&dp[k+1][j]&&s[k]-s[i-1]==s[j]-s[k])dp[i][j]=1;
            for(int k=i;k<j;k++)for(int p=k+1;p<j;p++)if(dp[i][k]&&dp[p+1][j]&&dp[k+1][p]&&s[k]-s[i-1]==s[j]-s[p])dp[i][j]=1;
        }
    }
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(dp[i][j])ans=max(ans,s[j]-s[i-1]);
    return cout<<ans,0;
}

优化：我们发现瓶颈在于枚举两个端点的时间会爆炸。有没有办法只枚举一个断点呢？有的兄弟有的我们只枚举一个端点，另一个断点可以通过 s_x-s_{i-1}=s_j-s_y 的大小限制算出来，使用双指针算法，前后两个指针往中间挪，这样时间复杂度就是 \mathcal{O(n)} 的，总的时间复杂度就是 \mathcal{O(n^3)} 的。可以通过。代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=405;
int n,ans,s[N],dp[N][N];
signed main(){
    cin>>n;
    for(int i=1,x;i<=n;i++)cin>>x,s[i]=s[i-1]+x;
    for(int i=1;i<=n;i++)dp[i][i]=1;
    for(int l=2;l<=n;l++){
        for(int i=1;i+l-1<=n;i++){
            int j=i+l-1,l=i,r=j;
            for(int k=i;k<j;k++)if(dp[i][k]&&dp[k+1][j]&&s[k]-s[i-1]==s[j]-s[k])dp[i][j]=1;
            while(l<=r){
                int x=s[l]-s[i-1];
                while(s[j]-s[r-1]<x)r--;
                if(s[j]-s[r-1]==x&&dp[i][l]&&dp[l+1][r-1]&&dp[r][j]){dp[i][j]=1;break;}
                l++;
            }
        }
    }
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(dp[i][j])ans=max(ans,s[j]-s[i-1]);
    return cout<<ans,0;
}

P2466 [SDOI2008] Sue 的小球

直接口胡过程算了。主要是记录一下一个典型的 trick。

首先是一个典题：一眼区间 DP，设 dp_{l,r,0/1} 表示拿完了区间 [l,r]，且当前在 l/r 的最大答案。但是发现这样不好直接转移，因为直接转移的时候会带上 time，而我们是无法同时记录最优的 time 和最优的 dp 值的。考虑费用前置的 trick（可能是这个名字，不重要），即将后面产生的贡献在前面处理掉一部分。比如说从 [l+1,r] 转移到 [l,r] 的这一段时间内，区间 [1,l],[r+1,n] 集体下落了若干，那么将这下落的若干直接算进费用里面。这个是好求的。最后对于单独一个点的贡献（上面举的例子就是点 l），直接加上这个点的初始权值即可，因为下落时减去的贡献已经被算过了。

怎么口胡还胡了这么多/oh，本来想两行搞定的哈哈。剩余细节就不说了，反正很简单而且是自己写的。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
int n,x0,p,s[N],dp[N][N][2];
struct node{int x,y,v;}a[N];
bool cmp(node x,node y){return x.x<y.x;}
signed main(){
    cin>>n>>x0;
    for(int i=1;i<=n;i++)cin>>a[i].x;
    for(int i=1;i<=n;i++)cin>>a[i].y;
    for(int i=1;i<=n;i++)cin>>a[i].v;
    a[n+1]={x0,0,0},sort(a+1,a+n+2,cmp);
    for(int i=1;i<=n+1;i++)if(a[i].x==x0&&a[i].y==0&&a[i].v==0){p=i;break;}
    for(int i=1;i<=n+1;i++)s[i]=s[i-1]+a[i].v;
    memset(dp,-0x3f3f3f3f3f,sizeof(dp)),dp[p][p][0]=dp[p][p][1]=0;
    for(int l=2;l<=n+1;l++){
        for(int i=1;i+l-1<=n+1;i++){
            int j=i+l-1;
            dp[i][j][0]=max(dp[i][j][0],dp[i+1][j][0]-(a[i+1].x-a[i].x)*(s[i]+s[n+1]-s[j])+a[i].y);
            dp[i][j][0]=max(dp[i][j][0],dp[i+1][j][1]-(a[j].x-a[i].x)*(s[i]+s[n+1]-s[j])+a[i].y);
            dp[i][j][1]=max(dp[i][j][1],dp[i][j-1][0]-(a[j].x-a[i].x)*(s[i-1]+s[n+1]-s[j-1])+a[j].y);
            dp[i][j][1]=max(dp[i][j][1],dp[i][j-1][1]-(a[j].x-a[j-1].x)*(s[i-1]+s[n+1]-s[j-1])+a[j].y);
        }
    }
    double res=(double)max(dp[1][n+1][0],dp[1][n+1][1]);
    printf("%.3lf",res/1000.0);
    return 0;
}