Kick Start 2019 Round C

2019-05-26 20:13 +0800

2019-06-06 23:24 +0800

动态规划当场翻车菜的不要不要的 呜呜呜

Board

最后只得了70分rank=161 失去了一次满分投简历机会(说的好像本来有一样)嘤嘤嘤

A - Wiggle Walk

$R \times C$的地图,每一格走过之后就会变滑(不会再次停在这个位置),问按照指定的方向走之后最后停在的位置的坐标。

内存给了1G,时间给了60s,然后79%的人这题翻了(我日为什么这题翻了只扣12分动规翻了扣了30分啊哭了

只要复杂度卡的好,简单暴力就能过………………

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n = 0, R = 0, C = 0;
bitset<50005> bx[50005];
bitset<50005> by[50005];

pii solve() {
  int x = 0, y = 0;
  string cmd;
  cin >> n >> R >> C >> x >> y >> cmd;
  for (int i = 1; i <= R; ++i) bx[i].reset();
  for (int j = 1; j <= C; ++j) by[j].reset();
  for (int i = 0; i < n; ++i) {
    bx[x].set(y);
    by[y].set(x);
    switch (cmd[i]) {
      case 'N':
        while (by[y][x]) --x;
        break;
      case 'S':
        while (by[y][x]) ++x;
        break;
      case 'E':
        while (bx[x][y]) ++y;
        break;
      default:
        while (bx[x][y]) --y;
        break;
    }
  }
  return make_pair(x, y);
}

int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int _T;
  cin >> _T;
  for (int _t = 1; _t <= _T; ++_t) {
    cout << "Case #" << _t << ": ";
    pii ans = solve();
    cout << ans.first << " " << ans.second;
    cout << endl;
  }
  return 0;
}

B - Circuit Board

问满足每一行最小值最大值之差不超过$K$的最大子区间面积是多少。两个单调队列$O(RC)$预处理一下子区间长度,然后再$O©$遍历所有可能的长度找一下最大值就可以了。

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

int R = 0, C = 0, K = 0;
int len[305][305] = {};

void prepare() {
  memset(len, 0, sizeof(len));
  cin >> R >> C >> K;
  int val[305] = {};
  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < C; ++j) {
      cin >> val[j];
    }

    deque<int> qmin, qmax;
    int l = 0, r = 0;
    while (l < C) {
      while (r < C) {
        while (!qmin.empty() && val[qmin.back()] >= val[r]) qmin.pop_back();
        qmin.push_back(r);
        while (!qmax.empty() && val[qmax.back()] <= val[r]) qmax.pop_back();
        qmax.push_back(r);
        if (val[qmax.front()] - val[qmin.front()] > K) break;
        ++r;
      }
      len[i][l] = r - l;
      if (qmin.front() == l) qmin.pop_front();
      if (qmax.front() == l) qmax.pop_front();
      ++l;
    }
  }
}

int solve() {
  int ans = 0;
  for (int l = 1; l <= C; ++l) {
    for (int j = 0; j <= C - l; ++j) {
      int cnt = 0;
      for (int i = 0; i < R; ++i) {
        if (len[i][j] >= l) cnt++;
        else {
          ans = max(ans, l * cnt);
          cnt = 0;
        }
      }
      ans = max(ans, l * cnt);
    }
  }
  return ans;
}

int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int _T;
  cin >> _T;
  for (int _t = 1; _t <= _T; ++_t) {
    cout << "Case #" << _t << ": ";
    prepare();
    cout << solve() << endl;
  }
  return 0;
}

C - Catch Some

地图上有$N$条狗,分别位于位置$P_i$,每条狗有一种颜色$A_i$,必须穿相同颜色的衣服才可以抚摸单身狗。在位置0(初始点)处可以换衣服,换衣服时间不计,每移动1格需要1单位时间,问抚摸$K$条狗需要的最少时间是多少(最后可以不用回到起点)。

动态规划(然后脑子抽了写错了),$dp[i][j][k]$表示前$i$种颜色的狗里摸了$j$条,$k=1$表示最后一次摸的在前$i$种中,$k=0$表示不在前$i$种中。答案为$dp[1000][K][1]$。

时间复杂度$O(NK)$,这个真的不是很难的DP给我搞WA了。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1000;
const int INF = 0x3f3f3f3f;

int n = 0, k = 0, maxd = 0;
int cnt[1005] = {};
int dp[1005][1005][2] = {};
vector<int> dogs[1005];

void prepare() {
  maxd = 0;
  memset(cnt, 0x00, sizeof(cnt));
  for (int i = 0; i <= MAXN; ++i) dogs[i].clear();
  for (int i = 0; i <= MAXN; ++i) dogs[i].push_back(0);
  for (int i = 0; i <= MAXN; ++i)
    for (int j = 0; j <= MAXN; ++j)
      dp[i][j][0] = dp[i][j][1] = INF;
}

int solve() {
  dp[0][0][0] = 0;
  for (int i = 1; i <= MAXN; ++i) {
    for (int j = 0; j <= cnt[i]; ++j) {
      for (int lst = 0; lst <= k - j; ++lst) {
        dp[i][lst + j][0] = min(dp[i][lst + j][0], dp[i - 1][lst][0] + 2 * dogs[i][j]);
        dp[i][lst + j][1] = min(dp[i][lst + j][1], dp[i - 1][lst][1] + 2 * dogs[i][j]);
        dp[i][lst + j][1] = min(dp[i][lst + j][1], dp[i - 1][lst][0] + 1 * dogs[i][j]);
      }
    }
  }

  return dp[MAXN][k][1];
}

int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int _T;
  cin >> _T;
  for (int _t = 1; _t <= _T; ++_t) {
    cout << "Case #" << _t << ": ";

    prepare();
    cin >> n >> k;
    int color = 0;
    int pos[1005] = {};
    for (int i = 0; i < n; ++i) {
      cin >> pos[i];
      maxd = max(maxd, pos[i]);
    }
    for (int i = 0; i < n; ++i) {
      cin >> color;
      cnt[color]++;
      dogs[color].push_back(pos[i]);
    }
    for (int i = 0; i < MAXN; ++i) {
      sort(dogs[i].begin(), dogs[i].end());
    }
    cout << solve();

    cout << endl;
  }
  return 0;
}