本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-14 01:17:18
A.永遇乐
出题人谢罪：
本题原本的出题意图是考察分层图和虚点，但是发现两个都不需要……现在看来是 $k_1$ 给小了。
所以能跑过就行，大家能写出做法也很强，下面是参考做法，仅供参考。
题意
求在无向图上从 $1$ 号节点出发，在 $k_1$ 个点中任意一个停留后到达 $k_2$ 个点中任意一个的最短路。
思路
考虑把在点上停留也转化成边，自然想到分层图。
建两层图，每层内连无向边，再把 $k_1$ 个点由第一层向第二层连权值为 $a_i$ 的有向边。答案即为以第二层 $k_2$ 个点为终点的最短路的最小值。
为了快速求出答案，可以将第二层的 $k_2$ 个点向虚点（代码中为 $0$ 号点）连边，这样最终答案即为 $1$ 到 $0$ 的最短路。
代码
#include<iostream>
#include<vector>
#include<queue>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+10;
const int maxs=1e15;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
return s*w;
}
int n,m,ka,kb,d[N*2];
priority_queue <pii > q;
bool f[N*2];\/\/因为建了两层图，所以要开两倍空间
struct edg
{
int v,w;
};
vector <edg> edge[N*2];\/\/同上
void add(int u,int v,int w)
{
edg t;
t.w=w,t.v=v;
edge[u].push_back(t);
}\/\/加边操作
signed main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
add(n+u,n+v,w),add(n+v,n+u,w);\/\/层内建边
}
ka=read(),kb=read();
for(int i=1;i<=ka;i++)
{
int t=read(),ta=read();
add(t,n+t,ta);\/\/层间建边，即为停留的代价
}
for(int i=1;i<=kb;i++)
{
int t=read();
add(n+t,0,0);\/\/连向虚点
}
for(int i=0;i<=2*n;i++) d[i]=maxs,f[i]=0;
d[1]=0;\/\/初始化
q.push({0,1});
while(!q.empty())
{
int u=q.top().second; q.pop();
if(f[u]) continue;
f[u]=1;
for(int i=0;i<edge[u].size();i++)
{
int ne=edge[u][i].v,tw=edge[u][i].w;
if(d[ne]>d[u]+tw)
{
d[ne]=d[u]+tw;
q.push({-d[ne],ne});
}
}
}\/\/Dijkstra
cout<<d[0];
return 0;
}
B.贺新郎
题意
给出 $n$ 个数对 $(a_i,b_i)$，求一种排列使 $\sum_{i=1}^{n-1}\left| a_i-a_{i+1}\right|+\left| b_i-b_{i+1}\right|$ 最大。
思路
看数据范围显然是状压dp，这里可以把题意抽象成在平面直角坐标系中有 $n$ 个点，两点之间距离为曼哈顿距离，本题便转化成了从任意点开始到任意点结束的旅行商问题（可参照P1433），只不过本题要求最大值（当然这里不转化也是状压dp）。
代码
#include<iostream>
#include<cmath>
#define int long long
using namespace std;
const int N=18+10;
const int M=3e5+10;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
return s*w;
}
int n,ans=-1,x[N],y[N];
int s[N][N];\/\/存储跳跃度
int f[N][M];\/\/f[i][j]表示以i结尾，j状态可达到的最大效果值
int dis(int a,int b)
{
return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
signed main()
{
n=read();
for(int i=1;i<=n;i++) x[i]=read();
for(int i=1;i<=n;i++) y[i]=read();
for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
s[i][j]=dis(i,j),s[j][i]=s[i][j];
for(int i=1;i<=n;i++) f[i][1<<(i-1)]=0;\/\/可从任意部分开始，但其实在这份代码里这个初始化没用
for(int k=1;k<(1<<n);k++) for(int i=1;i<=n;i++)\/\/枚举状态和最终点
{
if(k&(1<<(i-1))==0) continue;
for(int j=1;j<=n;j++)\/\/枚举上一个点
{
if(i==j||(k&(1<<(j-1)))==0) continue;
f[i][k]=max(f[i][k],f[j][k-(1<<(i-1))]+s[j][i]);\/\/转移
}
}
for(int i=0;i<n;i++) ans=max(ans,f[i][(1<<n)-1]);\/\/可在任意部分结束，记录答案
cout<<ans;
return 0;
}
C.青玉案
（没想到吧，这题是原题P4042，是出题人在qbxt做到的题）
（虽然原题是紫，但个人觉得大概是蓝）
题意
每个烟花可以公开放，这样会得到若干个烟花并增加热闹值；也可以自己放，只会增加热闹值。求最小热闹值。
思路
若设 $f_i$ 为把第 $i$ 种烟花及其后产生的新烟花全部放完的最小代价，则显然有 $f_i=min(b_i,a_i+\sum_{j=1} ^{s_i}f_{v_j})$，其中 $v$ 是存储公开放这个烟花所产生的新烟花的数组。
显然仅当 $f_{v_j}$ 均小于 $f_i$ 时，$f_i$ 才可能从后边的式子转移。因此类似于最短路算法，把所有烟花放入堆中，按所需代价从小到大处理即可，具体看代码。
（其实好像还有一点拓扑的思想，即只有一种烟花会产生的所有烟花都处理完，才能处理该烟花对应式子的第二项）
代码
此处代码中的 $f_i$ 仅维护了上式的第二项，即 $a_i+\sum_{j=1} ^{s_i}f_{v_j}$。上式第一项由初始加入堆的元素维护，把答案存到了 ${ans}_i$ 中。
#include<iostream>
#include<vector>
#include<queue>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+10;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
return s*w;
}
int n,a[N],b[N],s[N],f[N],ans[N];
bool v[N];
vector <int> edge[N];\/\/存储产生烟花情况
priority_queue <pii > q;
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read(),b[i]=read(),s[i]=read();
for(int j=1;j<=s[i];j++)
{
int t=read();
edge[t].push_back(i);\/\/由产生的烟花连向该烟花
}
q.push({-b[i],i});\/\/初始把每个烟花都以直接放完的代价放入队列
f[i]=a[i];\/\/初值设为公开燃放的代价
}
while(!q.empty())
{
int u=q.top().second,w=-q.top().first; q.pop();
if(v[u]) continue;
v[u]=1,ans[u]=w;\/\/记录答案
for(int i=0;i<edge[u].size();i++)
{
int ne=edge[u][i];
if(v[ne]||f[ne]>b[ne]) continue;
f[ne]+=w;\/\/此处就会将所有f_v_j加到f中
s[ne]--;\/\/记录产生烟花中未处理的数量
if(s[ne]==0) q.push({-f[ne],ne});\/\/若全部处理完则再加入堆
}
}\/\/Dijkstra思想
cout<<ans[1];
return 0;
}
D.破阵子
（类似于P1395，由于把树这个信息坑人地藏了起来，同时点有点权，评了绿）
题意
给定一棵树（因为每两个地区之间有且仅有一条路线，可以确定为一棵树，即保证 $m=n-1$），每将地区上的兵力移到直接连接的地区上时，就会消耗兵力数的代价，求集中所有兵力到同一地区的最小代价。
思路
（既然说了是树那显然是树形dp了吧）
典型换根dp，先钦定 $1$ 为根，设 ${cnt}_i$ 为子树中的兵力数，${sum}_i$ 为子树中所有兵力转移到子树根节点的代价，$j$ 为 $i$ 的子节点，则显然有 ${cnt}_i=a_i+\sum cnt_j$，${sum}_i=\sum (sum_j+cnt_j)$，一遍dfs即可处理完。
然后再计算以每个点为集中点的总代价 ${ans}_i$，其中 ${ans}_1={sum}_1$。若设总兵力数为 $tot$，$v$ 为原树中 $u$ 的子节点，则有：
${ans}_v={ans}_u-{cnt}_v+({tot}-{cnt}_v)={ans}_u+{tot}-2\times {cnt}_v$
这样再dfs一遍同时更新答案最小值即可。
代码
#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N=2e5+10;
const int maxs=1e15;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
return s*w;
}
int n,m,tot=0;
vector <int> edge[N];
int a[N],sum[N],cnt[N],ans[N],minn=maxs;
void dfs(int u,int fat)
{
sum[u]=0,cnt[u]=a[u];
for(int i=0;i<edge[u].size();i++)
{
int ne=edge[u][i];
if(ne==fat) continue;
dfs(ne,u);
cnt[u]+=cnt[ne],sum[u]+=(sum[ne]+cnt[ne]);
}
}\/\/第一遍dfs记录cnt和sum
void dfsb(int u,int fat)
{
minn=min(minn,ans[u]);
for(int i=0;i<edge[u].size();i++)
{
int ne=edge[u][i];
if(ne==fat) continue;
ans[ne]=ans[u]+tot-cnt[ne]*2;
dfsb(ne,u);
}
}\/\/第二遍dfs记录答案
signed main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read(),tot+=a[i];
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
edge[u].push_back(v),edge[v].push_back(u);
}
dfs(1,0);
ans[1]=sum[1];
dfsb(1,0);
cout<<minn;
return 0;
}
E.水调歌头
（分组背包裸题，可参照P1757）
（这题应该是最简单的吧，板子是橙，由于需要自己处理组别，所以我评了黄）
闲聊
这里不讲题意之类的了，只说下部分分，$20\%$ 的数据给的是不会滚动数组的（话说真的有人不会吗），$30\%$ 的数据显然每件事单独为一组，01背包即可，同时这个Subtask中由于还有 $y_i$ 和 $m_i$ 的大小限制，实际有 $n\leq816$ 。
（其实此题 $y_i$ 的限制是辛弃疾的生卒年）
std代码
#include<iostream>
using namespace std;
const int N=4e3+10;
const int K=4e5+10;
const int M=9e2+10;\/\/最多只有(1207-1140+1)*12=816个组
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
return s*w;
}
int n,k,l=1e9,r=-1e9; \/\/这里记录的是下标最大和下标最小的组
int cnt[M],w[M][N],v[M][N],f[K];
int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++)
{
int y=read(),m=read(),tw=read(),tv=read();
int gr=(y-1140)*12+m;\/\/这里转化一下标号，方便存储
cnt[gr]++,l=min(l,gr),r=max(r,gr);\/\/更新组数的范围
w[gr][cnt[gr]]=tw,v[gr][cnt[gr]]=tv;\/\/分组存储
}
for(int i=l;i<=r;i++) for(int j=k;j>=0;j--)\/\/枚举每个组和最终的容量
{
bool tf=true;
for(int tk=1;tk<=cnt[i];tk++) if(j-w[i][tk]>=0)\/\/枚举每件物品
tf=false,f[j]=max(f[j],f[j-w[i][tk]]+v[i][tk]);
if(tf) break;\/\/若所有物品都无法更新，则跳出循环（这里不剪枝会慢很多，但能过）
}
cout<<f[k];
return 0;
}
鲁ICP备2025150228号