标签归档:动态规划

Codeforces Round #572 (Div. 1) C. Array Beauty

题意

我们称一个序列$\{b_i\}_{i=1}^k$的beauty值为$\min_{i \neq j} |b_i – b_j|$。 给定序列$\{a_i\}_{i=1}^n$,问所有长度为k的子序列的beauty值之和。

数据范围:$2 \leq k \leq n \leq 1000, 0 \leq a_i \leq 10^5$

题解

我们可以使用一个常见的技巧:令$P(t)$为所有beauty值大于等于t的长度为k的子序列个数,那么答案就是$ \sum_{t=1}^{\infty} P(t) $。

这样问题就变成了计数题。首先将输入序列排序,令$ p_t(i) = \max\{j : a_j – a_i \geq t\} $,那么转移就可以写成:$ f_t(i, j) = f_t(i, j-1) + f_t(i-1, p_t(j)) $,且$P(t)= f_t(k, n)$。可以在均摊$O(n^2)$时间内求出所有 $p_t(i)$的值,另外计算一个P(t)的值需要$O(nk)$时间。注意到P(t)是单调递减的,因此当出现P(t)=0时就不必继续计算了。这样的t不会超过$\frac{\max a}{k-1}$,因此总的复杂度为$O(n \max a)$。

Nordic Collegiate Programming Contest 2018 [NCPC2018] 题解

A. Altruistic Amphibians

unsolved

B. Baby Bites

solved (0:08, +1)

逐个检查即可。

C. Code Cleanups

solved (0:17)

逐日模拟即可。

D. Delivery Delays

solved (4:55)

首先跑最短路获取APSP。

二分答案,然后dp出送完前i单最早时间,或者不可行

E. Explosion Exploit

solved (3:23)

可以用dp的思想转移。由于随从的顺序无关,可以将他们的血量排序,总状态数会大大减少。

F. Firing the Phaser

unsolved

G. Game Scheduling

unsolved

H. House Lawn

solved (0:34)

如果$\frac{10080rc}{t+r} \geq l$,则说明可行。记录可行的机器中,最便宜的那些机器的名称即可。

I. House Lawn

solved (1:00 +1)

由于相邻两数相差至少为一倍,只需要从大到小排序,然后能减就减。最后结果为0,则选中的那些就是答案。

J. Jumbled String

solved (1:57 +2)

可以根据00和11子序列的数量算出0和1的数量,然后根据01和10子序列的数量调整0和1的位置。注意若干边界情况。

K. King’s Colors

solved (3:07)

用最多k种颜色染色有$(k-1)^{n-1}k$种方案。用恰好$k$种颜色的方案数可以用容斥算出。

 

[2017-2018 ACM-ICPC Latin American Regional Programming Contest] A. Arranging tiles

链接:http://codeforces.com/gym/101889

题意

给定N个凸多边形$1 \leq N \leq 14$,每个凸多边形有一条$y=0$和$y=H$的边。将这些多边形在$0 \leq y \leq H$的区域内排成一排,不允许重叠,求最小的总宽度。允许调换多边形的次序,但不能旋转。

题解

首先可以进行一些预处理:将每个多边形向右平移,直到最左边的端点在y轴上,然后将多边形的左半部分和右半部分分离开来。

原问题可以分为明显的两个部分:首先,两两枚举多边形,求出这两个多边形拼起来的收益(即它们各自宽度之和减去拼起来的宽度),然后,在一个完全图上求出最长哈密尔顿路即可。后一个问题用经典的状压dp即可解决,前一个问题则可以用扫描线解决。

注意到两个多边形的接触点必为其中某一个多边形的顶点。因此,只需要处理出两个多边形的所有顶点的y坐标,然后依次求出每个y坐标处可能得到的收益,并去最小值即可。

总复杂度为$O(N^2K + N^2 2^N)$。

代码

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

constexpr double EPS = 1e-8;

int fcmp(double x, double y = 0.0) {
  if (fabs(x - y) < EPS) return 0;
  return x < y ? -1 : 1;
}

typedef double T;
typedef struct pt {
  T x, y;
  T operator,(pt a) { return x * a.x + y * a.y; }  // inner product
  T operator*(pt a) { return x * a.y - y * a.x; }  // outer product
  pt operator+(pt a) { return {x + a.x, y + a.y}; }
  pt operator-(pt a) { return {x - a.x, y - a.y}; }

  pt operator*(T k) { return {x * k, y * k}; }
  pt operator-() { return {-x, -y}; }
} vec;

typedef pair<pt, pt> seg;

int n;
int height;

struct polygon {
  int width;
  vector<pair<int, int>> lpart, rpart;
  
  void init(vector<pair<int, int>>& pts) {
    int minx = INT_MAX, maxx = INT_MIN;
    for (auto& p : pts) {
      height = max(height, p.second);
      minx = min(minx, p.first);
      maxx = max(maxx, p.first);
    }
    width = maxx - minx;
    for (auto& p : pts) p.first -= minx;
    int i = 1;
    while (pts[i].second < height) rpart.push_back(pts[i++]);
    rpart.push_back(pts[i++]);
    while (i < pts.size()) lpart.push_back(pts[i++]);
    lpart.push_back(pts[0]);
    reverse(range(lpart));
  }
} poly[16];

pt getMidPoint(pair<int, int> pt1, pair<int, int> pt2, double y) {
  pt a { (double) pt1.first, (double) pt1.second }, 
     b { (double) pt2.first, (double) pt2.second };
  vec v = (b - a) * (1.0 / (b.y - a.y));
  return a + v * (y - a.y);
}

double max_overlap(polygon& polyl, polygon& polyr) {
  vector<pair<int, int>> &lpts = polyl.rpart, &rpts = polyr.lpart;
  int ln = lpts.size(), rn = rpts.size(), yn;
  vector<int> ys;
  {
    vector<int> yl(ln), yr(rn);
    rep (i, ln) yl[i] = lpts[i].second;
    rep (i, rn) yr[i] = rpts[i].second;
    set_union(range(yl), range(yr), back_inserter(ys));
    yn = ys.size();
  }
  int lptr = 0, rptr = 0;
  double min_dif = 0.0;
  rep (i, yn) {
    pt lp = getMidPoint(lpts[lptr], lpts[lptr+1], ys[i]),
       rp = getMidPoint(rpts[rptr], rpts[rptr+1], ys[i]);
    min_dif = max(min_dif, lp.x - rp.x);
    while (lptr < ln-1 && lpts[lptr+1].second <= ys[i]) lptr++;
    while (rptr < rn-1 && rpts[rptr+1].second <= ys[i]) rptr++;
  }
  return polyl.width - min_dif;
}

double g[16][16];
double dp[1 << 14][16];

int main() {
  scanf("%d", &n);
  rep (i, n) {
    int k; scanf("%d", &k);
    vector<pair<int, int>> pts;
    rep (j, k) {
      int x, y; scanf("%d%d", &x, &y);
      pts.emplace_back(x, y);
    }
    poly[i].init(pts);
  }
  rep (i, n) {
    rep (j, n) {
      if (i == j) continue;
      g[i][j] = max_overlap(poly[i], poly[j]);
    }
  }
  for (unsigned mask = 1; mask < (1 << n); mask++) {
    if (mask & (mask - 1)) {
      unsigned rem = mask;
      while (rem) {
        unsigned bit = rem & -rem;
        int i = __builtin_ctz(bit);
        dp[mask][i] = -1e15;
        rep (j, n) {
          if (j == i || ((1 << j) & mask) == 0) continue;
          dp[mask][i] = max(dp[mask][i], dp[mask ^ bit][j] + g[j][i]);
        }
        rem -= bit;
      }
    } else {
      int i = __builtin_ctz(mask);
      rep (j, n) dp[mask][j] = (j == i ? 0.0 : -1e15);
    }
  }
  double ans = *max_element(range(dp[(1<<n)-1]));
  double tot = 0.0;
  rep (i, n) tot += poly[i].width;
  printf("%.3f\n", tot - ans);
  return 0;
}

 

2018牛客暑期ACM多校训练营(第一场)题解

A. Monotonic Matrix

给定$1\leq m,n \leq 1000$,求满足下列条件的$m \times n$矩阵个数,使得

  • $a_{i,j} \in \{0, 1, 2\}$
  • 每一行从左到右和每一列从上到下单调不减

题解:考虑每一行大于等于1和大于等于2的位置,其实就是要求两个单调不减的数列$\{a_i\}, \{b_i\}$的个数,满足对于任意$i$,有$a_i \leq b_i$。

B. Symmetric Matrix

给定$1 \leq n \leq 10^5$,求满足每个元素为非负整数,主对角线全0,每一行和为2的$n \times n$的对称矩阵的数量。

题解:把矩阵想象成邻接矩阵,就是要求顶点带标号的所有不允许自环、但允许重边的2-正则图的数量。

C. Fluorescent 2

在模2域下,给定$m \times n$的01矩阵$M$,$1 \leq n \leq 50$,$1 \leq m \leq 1000$,求对于每一个$n$维向量$v$,$Mv$中0的个数的三次方的和。

D. Two Graphs

给定图$G_1 = (V, E_1), G_2 = (V, E_2)$,求有多少$E_1$的子集$E’$,使得$(V, E’)$与$G_2$同构。点数不超过8。

题解:枚举所有的排列,如果构成子图,就把选出来的边用bitmap表示出来,最后去重即可。

E. Removal

给定$1 \leq n \leq 10^5$个数的序列,每个数为不超过$k$的正整数。问删掉$m$个数后,有多少种不同的子序列。$k, m$不超过10。

题解:用dp[i][j][k]表示前i个数删去j个数后,最后一个数为k的方案数。可以在$O(1)$时间内转移。

F. Sum of Maximum

给定数列$a_1, a_2, \cdots, a_n$,求

\[\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_1} \cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \cdots, x_n\}\]

题解:把$\max\{x_1, x_2, \cdots, x_n\}$写为$\sum_{m=1}^a [\exists i, x_i \geq m]$,进而改写为$\sum_{m=1}^a 1-[\forall i, x_i < m]$。将$a_i$排序后,从大到小分段计算,每一段都是$x_i$的一个前缀积乘以$i^k$的求和,后者可用Lagrange插值法快速计算。

G. Steiner Tree

H. Longest Path

I. Substring

给一个字符集为{a,b,c}的字符串,求在同构意义下的子串的等价类的数目。两个串同构当且仅当长度相等,并且存在字符集到字符集的双射f,使得一个串经过f变换后变成另一个串。

题解:将原串经过6种双射f后变成的6个串丢到SAM里,求出所有本质不同的子串。含有大于等于2种子串有6中不同的同构串,而只含有1种字符的串只有3中不同的同构串,分类讨论一下即可。

J. Different Integers

给一个序列,每次询问给出一个区间,求序列扣除这个区间后,有多少个不同数。

题解:在某次询问中,某数不出现当且仅当这个数第一次出现到最后一次出现包含于询问区间中即可。只要离线排序一下,按右端点的顺序处理即可。

2017-2018 问题求解(四)上机考试题解

Day1

A 差异度

题意:给$n (1 \leq n \leq 10^5)$个20位的01串,求两两之间hamming距离的最小值。

解法:此题解法甚多。下面列举3个常见的解法:

  1. 注意到当$n$很大时,最终答案不会太大(考虑一个01串hamming距离为$d$的邻域大小随$d$是指数增长的,然后用鸽巢原理即可)。所以,从小到大枚举答案$d$,并在每个串的$d$-邻域内搜索即可。
  2. 建图。将所有20位的01串视为顶点,相差1位的两个串连边。问题就变成了:给定一个顶点子集,求这个子集中两两距离的最小值。这用多线程bfs就可以解决。时间复杂度为$2^{20}*20$。
  3. 用FWT处理出所有可能的异或值,取popcount最小的那个即可。(FWT课内没学,用了感觉有点犯规,但写起来方便是真的

B 工作安排

题意:某人有$T (0 \leq T \leq 100)$时间,$N (0 \leq N \leq 100)$组工作。每组工作有3种类型:至多选一个做,至少选一个做,无限制。每组工作中最多有100个工作,每个工作有完成的时间和所能得到的收益值。求所能获得的最大收益。

题解:较为复杂的背包问题。用常规的dp就可以解决。对于每组工作的附加限制,在更新dp值的时候需要特殊处理。

Day2

A 矩阵分割游戏

题面:NOI1999 棋盘分割

题意:给一个8*8的矩阵,每次可以横着或竖着掰成两半并舍弃一块,最后得到$n$块子矩阵。求子矩阵数字和的标准差的最小值。

题解:由gay率论相关知识,要使标准差取得最小值,只要让平方和最小即可(因为和是固定的)。然后dp或者记忆化爆搜即可。

B 旅行箱

题意:有$n \leq 42$个数,取出它的一个子集,使得子集和在不超过$W$的前提下,使得子集和最大。(简单背包问题)

题解:用meet-in-the-middle思想。将集合分成两部分,预处理出每部分的所有子集和。然后将这些子集和排序,对于一部分的某个子集和$S$,在另一部分中找出不超过$W-S$的最大子集和,然后取最大值即可。复杂度$O(n2^{n/2})$。