杭电第三场赛后补题

1009. Rise in Price

There are n×n cells on a grid, the top-left cell is at (1,1) while the bottom-right cell is at (n,n). You start at (1,1) and move to (n,n). At any cell (i,j), you can move to (i+1,j) or (i,j+1), provided that you don't move out of the grid. Clearly, you will make exactly 2n−2 steps.

When you are at cell (i,j), including the starting point (1,1) and the destination (n,n), you can take all the ai,j diamonds at this cell, and have a chance to raise the price of each diamond by bi,j dollars. You will sell all the diamonds you have with the final price in the end, and your goal is to choose the optimal path that will maximize your profits. Note that initially the price of each diamond is zero, and you have nothing to sell.

题意：给你两个数组，A:(a_ij 代表下标为i,j的钻石的个数，bij表示经过i，j时间可以使单价提高的价格

这一道题比赛中没有做出来，开始赛后补题：

本道题看到所求的最大值，所以考虑动态规划，对于动态规划，我们需要考虑：

关于状态定义： $f_{ijk}$ 表示经过下标 $(i,j)$ ,钻石数量为 $k$ 的单价
关于状态转移方程：
$f[i][j][k].first = merge(f[i-1][j][k],f[i][j-1][k])+a_{ij}$
$f[i][j][k].second=merge(f[i-1][j][k],f[i][j-1][k])+b_{ij}$

但是由于状态比较多，所以我们需要对过程中一部分不可能推出最优答案的状态删除，以达到减小复杂度的效果，我们知道：

对于 $k_1<k_2\bigcap f_{ijk_1}<f_{ijk_2}$ 时，这个状态 $f_{ijk_1}$ 就不可能推导出最优答案，可以删除。因此我们可以用 $f[i][j]$ 来定义到达下标为 $(i,j)$ 的所有 $<count,price>$ 状态。所以我们可以根据 $count$ 升序排序，定义一个 $pool$ 数组来存储所有状态,每次merge操作插入 $count$ （第一维）最小的状态，当插入第二维Price的时候可以删去前面相同count但是小于待插入元素price的状态，以此达到删除不可能最优状态的效果。具体代码如下：

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef vector<P>V;
const int N=105;
//pool 维护所有的 <数量，单价> 的状态。
int Case,n,m,i,j,k,a[N][N],b[N][N];ll ans;V f[N][N];P pool[1000005];
inline void ext(const P&t){
  //应为merge操作中是小的先进，pool中最后一个元素一定小于待插入元素的第一维，如果其第二维也小于待插入元素，直接剔除就可。
  while(m&&pool[m].second<=t.second)m--;
  if(!m||pool[m].first<t.first)pool[++m]=t;
}
inline void merge(const V&A,const V&B,V&C){
  int ca=A.size(),cb=B.size(),i=0,j=0;
  m=0;
  //这里第一维小的先进，保证pool中的第一维是递增的
  while(i<ca&&j<cb)ext(A[i].first<B[j].first?A[i++]:B[j++]);
  while(i<ca)ext(A[i++]);
  while(j<cb)ext(B[j++]);
  C.resize(m);
  for(i=0;i<m;i++)C[i]=pool[i+1];
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&n);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&a[i][j]);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&b[i][j]);
    //f[i][j]表示到达下标为(i,j)时候取得所有的 <数量，单价> 的全部状态。
    //这里的f[i][j][k].first为数量； second为单价
    f[1][1].resize(1);
    f[1][1][0]=P(a[1][1],b[1][1]);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++){
      if(i==1&&j==1)continue;
      if(i==1)f[i][j]=f[i][j-1];
      else if(j==1)f[i][j]=f[i-1][j];
      //这一步得到f[i][j]的初始状态,也就是f[i][j]的 <数量，单价> 全部状态。
      //在初始化f[i][j]的过程中，需要剔除 f[i][j][k1].first < f[i][j][k2].second && f[i][j][k2].first < f[i][j][k2].second , 也就是单价小，数量也小的可以剔除 
      else merge(f[i-1][j],f[i][j-1],f[i][j]);
      for(k=0;k<f[i][j].size();k++){
        f[i][j][k].first+=a[i][j];
        f[i][j][k].second+=b[i][j];
      }
    }
    ans=0;
    //最后对最后一个位置的所有状态求总价取最大就是答案。
    for(i=0;i<f[n][n].size();i++)ans=max(ans,1LL*f[n][n][i].first*f[n][n][i].second);
    printf("%lld\n",ans);
  }
}

1010. Road Discount

There are n cities in Byteland, labeled by 1 to n. The Transport Construction Authority of Byteland is planning to construct n−1 bidirectional roads among these cities such that every pair of different cities are connected by these roads directly or indirectly.

The engineering company has offered m possible candidate roads to construct. The i-th candidate road will cost ci dollars, and if it is finally constructed, there will be a road connecting the ui-th city and the vi-th city directly. Fortunately, each road has its discounted price, the i-th of which is di.

The Transport Construction Authority of Byteland can buy at most k roads at their discounted prices. Please write a program to help the Transport Construction Authority find the cheapest solution for k=0,1,2,…,n−1.

题意：就是在最小连通图问题，但是不同的是每条路有原价和折扣价，我们要找出正好包含k条折扣价的路的最小连通图；

我们可以定义 $f(k)$ 表示包含恰好 $k$ 为最小生成树中使用黑边的最小边权和，所以 $f(k)$ 是一个凸函数，求出 $f(k)$ 的方法为：

选择参数c，将每条黑色的边权加上 $c$
求出修改边权后的图的最小生成树，令 $sum(c)$ 为对应的边权和， $l(c)$ 为最小生成树使用黑边数量的最小值， $r(c)$ 为最小生成树使用黑边数量的最大值
二分找到答案 $c$ ，若满足 $l(c) \leqslant k\leqslant r(c)$ ,则 $f(k)=sum(c)-k\times c$

所以我们得到题解

#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int>P;
const int N=1005,M=200005,V=1000;
int Case,n,m,i,f[N];P fl[V*2+5];
struct E{int x,y,w;}a[M],b[M];
inline bool cmp(const E&a,const E&b){return a.w<b.w;}
//getfather函数
int F(int x){
  return f[x] == x ? x : f[x] = F(f[x]);
}
//union函数
inline bool merge(int x,int y){
  if(F(x) == F(y)) return 0;
  f[f[x]]=f[y];
  return 1;
}

inline void reduce(E*e){
  //根据边权值来排序
  sort(e+1,e+m+1,cmp);
  for(int i=1;i<=n;i++)f[i]=i;
  for(int i=1,cnt=0;i<=m;i++)
    if(merge(e[i].x,e[i].y))
      e[++cnt]=e[i];
}
//查询函数
inline P call(int k){
  for(int i=1;i<=n;i++)f[i]=i;
  int A=1,B=1,sum=0,cnt=0;
  while(A<n&&B<n){
    if(a[A].w<=b[B].w+k){
      if(merge(a[A].x,a[A].y))sum+=a[A].w;
      A++;
    }else{
      if(merge(b[B].x,b[B].y))sum+=b[B].w+k,cnt++;
      B++; 
    }
  }
  while(A<n){
    if(merge(a[A].x,a[A].y))sum+=a[A].w;
    A++;
  }
  while(B<n){
    if(merge(b[B].x,b[B].y))sum+=b[B].w+k,cnt++;
    B++;
  }
  return P(sum,cnt);
}
inline int ask(int k){
  for(int i=-V;i<=V;i++) 
    if(fl[i+V].second<=k) 
      return fl[i+V].first-k*i;
  return -1;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
      scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].w,&b[i].w);
      b[i].x=a[i].x,b[i].y=a[i].y;
    }
    reduce(a);
    reduce(b);
    for(i=-V;i<=V;i++)fl[i+V]=call(i);
    for(i=0;i<n;i++)printf("%d\n",ask(i));
  }
}

杭电多校联赛（三）补题

杭电多校联赛（三）补题

杭电第三场赛后补题

1009. Rise in Price

1010. Road Discount

推荐阅读更多精彩内容