Chengrui's Blog

UVa 10602 - Editor Nottoobad

发表于 2016-03-01 分类于 AOAPC Training Guide ， Chapter 1. Algorithm Design ， General Problem Solving Techniques Disqus：

链接

传送门

大意

给出一些单词，第一个必须手动输入，后面的有两种方式可以语音辅助输入：

重复上个输入的单词
删除最后一个字符

输出最少的手动输入按键次数，和单词输入顺序。

思路

尽量多的利用辅助减少按键的次数，每次都优先输出与上一个输出单词的lcp长度最长的单词，以最大限度地利用辅助。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 110;
bool flag[maxn];
char s[maxn][maxn];
int lcp[maxn][maxn], len[maxn], idx[maxn];

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%s", s[i]);
      len[i] = int(strlen(s[i]));
    }
    for (int i = 0; i < n; ++i) {
      lcp[i][i] = len[i];
      for (int j = i + 1; j < n; ++j) {
        int k = 0;
        while (s[i][k] == s[j][k] && k < len[i] && k < len[j]) {
          ++k;
        }
        lcp[i][j] = lcp[j][i] = k;
      }
    }
    memset(flag, 0, sizeof flag);
    flag[0] = true, idx[0] = 0;
    int ans = len[0], pre = 0, cur = 0, curlcp = -1, cnt = 1;
    while (cnt <= n) {
      for (int i = 0; i < n; ++i) {
        if (flag[i]) {
          continue;
        }
        if (lcp[i][pre] > curlcp) {
          cur = i;
          curlcp = lcp[i][pre];
        }
      }
      ans += len[cur] - lcp[pre][cur];
      pre = cur;
      flag[cur] = true;
      idx[cnt++] = cur;
      curlcp = -1;
    }
    printf("%d\n", ans);
    for (int i = 0; i < n; ++i) {
      puts(s[idx[i]]);
    }
  }
  return 0;
}

UVa 529 - Addition Chains

发表于 2016-03-01 分类于 AOAPC Training Guide ， Chapter 1. Algorithm Design ， General Problem Solving Techniques Disqus：

链接

传送门

大意

定义长度为 $m + 1$ 的 $n$ 加法链为首元素为 $a [0] = 0$ ，末元素 $a [m] = n$ ，严格递增且数列中除首项之外，其余项均满足 $a [k] = a [i] + a [j], (1 \leq i, j \leq k - 1)$ 的数列。给出 $n$ ，满足条件的最小的 $m$ 和加法链。

思路

枚举长度进行验证，注意以下几点：

初始深度为 $l o g_{2} n$ 。
生成的数字比当前最大的小就剪枝。
生成的数字在每次使用最大值相加的构造方法依然不能超过目标值要剪枝。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 110;
int ans[maxn], dep, n;
int k[15];
bool dfs(int d) {
  if (d + 1 == dep) {
    return ans[d] == n;
  }
  int x = dep - d - 2;
  for (int i = 0; i <= d; ++i) {
    for (int j = i; j <= d; ++j) {
      if (ans[i] + ans[j] > ans[d] && ans[i] + ans[j] <= n) {
        ans[d + 1] = ans[i] + ans[j];
        if ((ans[d + 1] << x) >= n && dfs(d + 1)) {
          return true;
        }
      }
    }
  }
  return false;
}

int main() {
  ans[0] = k[0] = 1;
  for (int i = 1; i < 15; ++i) {
    k[i] = k[i - 1] << 1;
  }
  while (~scanf("%d", &n) && n) {
    dep = int(lower_bound(k, k + 15, n) - k) + 1;
    while (!dfs(0)) {
      ++dep;
    }
    printf("1");
    for (int i = 1; i < dep; ++i) {
      printf(" %d", ans[i]);
    }
    puts("");
  }
  return 0;
}

UVa 769 - Magic of David Copperfield

发表于 2016-03-01 分类于 AOAPC Training Guide ， Chapter 1. Algorithm Design ， General Problem Solving Techniques Disqus：

链接

传送门

题意

给出 $n \times n$ 的矩阵，最初在最左上的点，可以像上下左右4个方向移动，每次移动 $k$ 步（每次移动的步数 $k$ 不能相同），可以删除任意数量的必然无法走到的卡片。然后继续移动，直至只剩下一张卡片。

思路

每次都走奇数步，根据奇偶性，可知，不会走到与当前格子在同一斜线上的格子，然后删除最左上的一条斜线上的所有纸片。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    int k = (n - 1) << 1;
    for (int i = 0; i < k; ++i) {
      printf("%d", 2 * (n + i) + 1);
      for (int j = 0; j <= i; ++j) {
        if (i - j >= n || j >= n) {
          continue;
        }
        printf(" %d", j * n + i - j + 1);
      }
      puts("");
    }
    if (t) {
      puts("");
    }
  }
  return 0;
}

Codeforces 629D Babaei and Birthday Cake

发表于 2016-03-01 分类于 Codeforces Disqus：

链接

传送门

题意

给出 $n$ 个圆柱形蛋糕的底面半径 $r$ 和高度 $h$ 。要将蛋糕放在桌子上，后面的蛋糕可以放在前面的比它小的蛋糕上，或者放到桌子上。输出放在一起的蛋糕的最大总体积。

思路

计算蛋糕的体积并排序，然后目标转化为求上升子序列和的最大值。得到状态转移方程 $d [i] = m a x (d [j], j < i, V [j] < V [i]) + V [i]$ 。为了求出 $m a x (d [j], j < i, V [j] < V [i])$ ，使用线段树储存 $d [i]$ 的值，保存每个节点的原始序列位置 $p [i]$ ，每次查询，区间 $[0, p [i]]$ 的最大值。然后更新 $p [i]$ 节点的值为 $d [i]$ 。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
const double PI = acos(-1);
const int maxn = 100010;
int n;
LL q[maxn << 2], d[maxn];
struct node {
  LL v;
  int p;
  bool operator < (const node& rhs) const {
    return v < rhs.v || (v == rhs.v && p > rhs.p);
  }
} a[maxn];

void update(int idx, LL x, int id = 1, int b = 0, int e = n) {
  if (idx < b || idx >= e) {
    return;
  }
  if (idx == b && e - b == 1) {
    q[id] = d[b] = x;
    return;
  }
  int mid = (b + e) >> 1, l = id << 1, r = l | 1;
  if (idx < mid) {
    update(idx, x, l, b, mid);
  }else{
    update(idx, x, r, mid, e);
  }
  q[id] = max(q[l], q[r]);
}

LL query(int ql, int qr, int id = 1, int b = 0, int e = n) {
  if (ql >= e || qr <= b) return 0;
  if (ql <= b && e <= qr) return q[id];
  int mid = (b + e) >> 1, l = id << 1, r = l | 1;
  return max( query(ql, qr, l, b, mid), query(ql, qr, r, mid, e) );
}


int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    int r, h;
    scanf("%d%d", &r, &h);
    a[i].v = LL(r) * r * h;
    a[i].p = i;
  }
  sort(a, a + n);
  for (int i = 0; i < n; ++i) {
    int idx = a[i].p;
    d[idx] = query(0, idx) + a[i].v;
    update(idx, d[idx]);
  }
  printf("%.10f\n", query(0, n) * PI);
  return 0;
}

Codeforces 629C Famil Door and Brackets

发表于 2016-02-29 分类于 Codeforces Disqus：

链接

传送门

题意

给出一段长度为 $m$ 括号序列，在它的前后添加"("和")"使得长度变为 $n$ ，输出使最终序列合法的添加方式数目。

思路

定义状态 $d [i] [j]$ 表示长度为 $i$ ，最终还需 $j$ 个")"才能完全匹配的的合法序列前缀数目。可以得到状态转移公式 $d [i] [j] = d [i - 1] [j - 1] + d [i - 1] [j + 1]$ 。预处理后，枚举在原始序列前面添加的长度计算方案数目和。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const LL mod = 1000000007;
const int maxn = 100000;
const int maxm = 2010;
char s[maxn];
LL d[maxm][maxm];

int main() {
  d[0][0] = 1;
  for (int i = 1; i < maxm; ++i) {
    d[i][0] = d[i - 1][1];
    for (int j = 1; j <= i; ++j) {
      d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % mod;
    }
  }
  int n, m;
  scanf("%d%d%s", &n, &m, s);
  int minb = 0, b = 0, len = n - m;
  for (int i = 0; i < m; ++i) {
    if (s[i] == '(') {
      ++b;
    } else {
      --b;
    }
    minb = min(minb, b);
  }
  LL ans = 0LL;
  for (int i = 0; i <= len; ++i) {
    for (int j = 0; j <= i; ++j) {
      if (j >= -minb && b + j <= len && b + j >= 0) {
          ans = (ans + d[i][j] * d[len - i][b + j]) % mod;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

UVa 589 - Pushing Boxes

发表于 2016-02-28 分类于 AOAPC Training Guide ， Chapter 1. Algorithm Design ， General Problem Solving Techniques Disqus：

链接

传送门

题意

给出 $r \times c (1 \leq r, c \leq 20)$ 的矩阵，代表推箱子的地图，输出把箱子推到指定地点的方案，要求推的次数最少，推的次数相同时，人走动的次数尽量少。

思路

可以将推的次数和走动次数转化为一个权值，将人的位置和箱子的位置作为状态，进行bfs，记录每个状态到达的最小权值。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn = 25;
const char dirs[2][5] = {"news", "NEWS"};
const int dir[4][2] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
int r, c;
int vis[maxn][maxn][maxn][maxn];
char path[maxn][maxn][maxn][maxn];
char a[maxn][maxn], ans[maxn * maxn * maxn * maxn];
struct Pos {
  int x, y;
};
struct Status {
  Pos s, b;
  int w;
  Status() {}
  Status(Pos& s, Pos& b, int w): s(s), b(b), w(w) {}
  bool operator < (const Status& rhs) const {
    return w > rhs.w;
  }
};
priority_queue<Status> q;

int main() {
  int t = 0;
  while (~scanf("%d%d", &r, &c) && (r || c)) {
    Status k;
    for (int i = 1; i <= r; ++i) {
      scanf("%s", a[i] + 1);
      for (int j = 1; j <= c; ++j) {
        if (a[i][j] == 'S') {
          k.s.x = i, k.s.y = j;
        } else if (a[i][j] == 'B') {
          k.b.x = i, k.b.y = j;
        }
      }
    }
    memset(path, 0, sizeof path);
    memset(vis, 0x3f, sizeof vis);
    vis[k.s.x][k.s.y][k.b.x][k.b.y] = k.w = 0;
    q = priority_queue<Status>();
    q.push(k);
    bool flag = true;
    printf("Maze #%d\n", ++t);
    while (!q.empty()) {
      k = q.top();
      q.pop();
      if (a[k.b.x][k.b.y] == 'T') {
        flag = false;
        int len = 0;
        while (vis[k.s.x][k.s.y][k.b.x][k.b.y] != 0) {
          char& c = path[k.s.x][k.s.y][k.b.x][k.b.y];
          ans[len++] = path[k.s.x][k.s.y][k.b.x][k.b.y];
          for (int i = 0; i < 4; ++i) {
            if (tolower(c) == dirs[0][i]) {
              k.s.x -= dir[i][0], k.s.y -= dir[i][1];
              if (isupper(c)) {
                k.b.x -= dir[i][0], k.b.y -= dir[i][1];
              }
              break;
            }
          }
        }
        while (len--) {
          putchar(ans[len]);
        }
        break;
      }
      for (int i = 0; i < 4; ++i) {
        Pos ns = k.s;
        ns.x += dir[i][0], ns.y += dir[i][1];
        if (ns.x == k.b.x && ns.y == k.b.y) {
          Pos nb = k.b;
          nb.x += dir[i][0], nb.y += dir[i][1];
          if (nb.x >= 1 && nb.y >= 1 && nb.x <= r && nb.y <= c && a[ns.x][ns.y] != '#' && k.w + 100000 < vis[ns.x][ns.y][nb.x][nb.y]) {
            q.push(Status(ns, nb, k.w + 100000));
            vis[ns.x][ns.y][nb.x][nb.y] = k.w + 100000;
            path[ns.x][ns.y][nb.x][nb.y] = dirs[1][i];
          }
        } else if (ns.x >= 1 && ns.y >= 1 && ns.x <= r && ns.y <= c && a[ns.x][ns.y] != '#' && k.w + 1 < vis[ns.x][ns.y][k.b.x][k.b.y]) {
          q.push(Status(ns, k.b, k.w + 1));
          vis[ns.x][ns.y][k.b.x][k.b.y] = k.w + 1;
          path[ns.x][ns.y][k.b.x][k.b.y] = dirs[0][i];
        }
      }
    }
    puts(flag ? "Impossible.\n" : "\n");
  }
  return 0;
}

UVa 1456 - Cellular Network

发表于 2016-02-27 分类于 AOAPC Training Guide ， Chapter 1. Algorithm Design ， Dynamic Programming Disqus：

链接

传送门

大意

手机蜂窝数据可以得到手机在 $n$ 个地方的概率， $p_{i}$ 。现在要查询手机的位置，可以分成 $w$ 组，分别查询，输出查询次数的期望值的最小值。

思路

要使查询次数最小，应该优先查找存在概率高的地点，先对位置排序。然后设状态 $d [i] [j]$ 为前 $i$ 个地点，分成 $j$ 组查询的最小期望。对于每个状态，可以通过枚举最后一组的大小进行转移。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 110;
double a[maxn], sum, f[maxn][maxn];

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, w, sum = 0;
    scanf("%d%d", &n, &w);
    for (int i = 1; i <= n; ++i) {
      scanf("%lf", &a[i]);
      sum += a[i];
    }
    sort(a + 1, a + n + 1, greater<int>());
    for (int i = 1; i <= n; ++i) {
      a[i + 1] += a[i];
      a[i] /= sum;
    }
    for (int i = 1; i <= n; ++i) {
      f[i][0] = inf;
      for (int j = 1; j <= w; ++j) {
        f[i][j] = inf;
        for (int k = j; k <= i; ++k) {
          f[i][j] = min(f[i][j], f[k - 1][j - 1] + i * (a[i] - a[k - 1]));
        }
      }
    }
    printf("%.4f\n", f[n][w]);
  }
  return 0;
}

UVa 11404 - Palindromic Subsequence

发表于 2016-02-21 分类于 AOAPC Training Guide ， Chapter 1. Algorithm Design ， Dynamic Programming Disqus：

链接

传送门

题意

给出一个字符串，输出它的最长回文子串。

思路

将原字符串反转后求LCS，保留字典序最小的LCS。由求出的LCS字典序最小，因而无法保证回文，比如： $c b c a b c b$ 、 $b c b a c b c$ 求出的LCS为 $b c a b c$ ，而最长回文子串 $b c a c b$ 由于字典序比 $b c a b c$ 大被替换掉了。因此要取LCS前半部分构造出回文子串。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

const int maxn = 1010;
char s1[maxn], s2[maxn];
struct node {
  int len;
  string s;
  bool operator < (const node& rhs) const {
    return len > rhs.len || (len == rhs.len && s < rhs.s);
  }
} d[maxn][maxn];

int main() {
  while (~scanf("%s", s1 + 1)) {
    int len = int(strlen(s1 + 1));
    for (int i = 1; i <= len; ++i) {
      s2[i] = s1[len - i + 1];
    }
    s2[len + 1] = 0;
    for (int i = 0; i <= len; i++) {
      d[0][i].len = 0, d[0][i].s = "";
    }
    for (int i = 1; i <= len; ++i) {
      for (int j = 1; j <= len; ++j) {
        if (s1[i] == s2[j]) {
          d[i][j].len = d[i - 1][j - 1].len + 1;
          d[i][j].s = d[i - 1][j - 1].s + s1[i];
        } else {
          d[i][j] = min(d[i][j - 1], d[i - 1][j]);
        }
      }
    }
    node& k = d[len][len];
    len = k.len >> 1;
    for (int i = 0; i < len; ++i) {
      putchar(k.s[i]);
    }
    if (k.len & 1) {
      putchar(k.s[len]);
    }
    for (int i = len - 1; i >= 0; --i) {
      putchar(k.s[i]);
    }
    puts("");
  }
  return 0;
}

UVa 10534 - Wavio Sequence

发表于 2016-02-21 分类于 AOAPC Training Guide ， Chapter 1. Algorithm Design ， Dynamic Programming Disqus：

链接

传送门

题意

给出数列 $a_{i}$ 输出最长的长度为 $2 n + 1$ 的前 $n$ 项严格递增，后 $n$ 项严格递减的子序列的长度。

思路

求两边LIS，枚举每个点的上升前缀 $d 1_{i}$ 和下降后缀 $d 2_{i}$ ，答案为 $m a x (m i n (d 1_{i}, d 2_{i}) * 2 - 1)$ 。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 10010;
int a[maxn], g[maxn], d1[maxn], d2[maxn];

int main() {
  int n;
  while (~scanf("%d", &n)) {
    for (int i = 0; i < n; ++i) {
      scanf("%d", &a[i]);
    }
    fill(g, g + n + 1, inf);
    for (int i = 0; i < n; ++i) {
      int k = int(lower_bound(g + 1, g + n + 1, a[i]) - g);
      d1[i] = k;
      g[k] = a[i];
    }
    fill(g, g + n + 1, inf);
    for (int i = n - 1; i >= 0; --i) {
      int k = int(lower_bound(g + 1, g + n + 1, a[i]) - g);
      d2[i] = k;
      g[k] = a[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
      ans = max(ans, (min(d1[i], d2[i]) << 1) - 1);
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 1325 - Hypertransmission

发表于 2016-02-21 分类于 AOAPC Training Guide ， Chapter 1. Algorithm Design ， Designing Efficient Algorithms Disqus：

链接

传送门

题意

给出 $n$ 个星球的位置和广播的类型，定义接受与自身不同类型的个数大于相同类型个数的星球为间谍星球（星球自身的广播也算在内），输出使间谍星球个数的最大值，和最大值下的接受半径。

思路

枚举所有星球间的边，从小到大排序，依次将边加入。注意加边时要将同长度的边一起加入。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps = 1e-8;
const int maxn = 1010;
struct point {
  double x, y, z;
  int type, same, diff;
} p[maxn];
struct node {
  int u, v;
  double l;
  bool operator < (const node& rhs) const {
    return l < rhs.l;
  }
} d[maxn * maxn];

double dis(point& a, point& b) {
  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z));
}

int main() {
  int n;
  while (~scanf("%d", &n)) {
    for (int i = 0; i < n; ++i) {
      p[i].diff = 0, p[i].same = 1;
      scanf("%lf%lf%lf%d", &p[i].x, &p[i].y, &p[i].z, &p[i].type);
    }
    int num = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        d[num].u = i, d[num].v = j;
        d[num].l = dis(p[i], p[j]);
        ++num;
      }
    }
    sort(d, d + num);
    int ans = 0, res = 0;
    double r = 0;
    for (int i = 0; i < num; ++i) {
      point& a = p[d[i].u];
      point& b = p[d[i].v];
      if (a.type == b.type) {
        if (a.same + 1 == a.diff) {
          --res;
        }
        if (b.same + 1 == b.diff) {
          --res;
        }
        ++a.same, ++b.same;
      } else {
        if (a.same == a.diff) {
          ++res;
        }
        if (b.same == b.diff) {
          ++res;
        }
        ++a.diff, ++b.diff;
      }
      if (i != num - 1 && fabs(d[i].l - d[i + 1].l) < eps) {
        continue;
      }
      if (res > ans) {
        ans = res;
        r = d[i].l;
      }
    }
    printf("%d\n%.4lf\n", ans, r);
  }
  return 0;
}