坦夫稼轩（互测赛）题解

· · 题解

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;
}