CF1644-A-E

A.Doors and Keys

题目大意

给定一段字符串，其中R,G,B代表门，r,g,b分别代表解开R,G,B的钥匙，问是否能够通过所有的门。

思路

记录一下门和钥匙的下标即可。

Code

void solve() {
  std::string mp;
  std::cin >> mp;
  std::map a;
  for (int i = 0; i < mp.size(); i++) {
    a[mp[i]] = i;
  }
  if (a['r'] < a['R'] && a['g'] < a['G'] && a['b'] < a['B']) {
    std::cout << "YES\n";
  } else {
    std::cout << "NO\n";
  }
}
 

B.Anti-Fibonacci Permutation

题目大意

输出n个满足\(p_{i-1}+p_{i-2} \neq p_i\)性质的序列。

思路

首先一个合法的序列是逆序列，需要有n个序列，那我们只需要变动首位即可。

Code

void solve() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cout << i << " ";
        for (int j = n; j >= 1; j--) {
            if (i != j) {
                std::cout << j << " ";
            }
        }
    }
    std::cout << "\n";
}

C. Increase Subarray Sums

题意

给定一个长度为n的数组，和一个值X。

定义\(f(k)\)为对序列中任意k个增加X后所有连续子序列的最大值。（k从0到n）

思路

预处理出所有和当前长度相等或者更大长度的连续子序列中的最大值。

每次加值后都与前一部分的连续子序列最大值比较一下。

void solve() {
  int n, x;
  std::cin >> n >> x;
  std::vector a(n + 5), s(n + 5), ans(n + 5, -1e9);
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    s[i] = s[i-1] + a[i];
  }
  int mx_ans = -1e9;
  for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
      int r = l + len - 1;
      ans[len] = std::max(ans[len], s[r] - s[l-1]);
      mx_ans = std::max(ans[len], mx_ans);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      ans[i] = std::max(ans[i], ans[j]);
    }
  }
  ans[0] = std::max(mx_ans, *std::max_element(a.begin(),a.end()));
  for (int i = 0, last; i <= n; i++) {
    if (!i) {
      std::cout << ans[i] << " ";
      last = ans[i];
    } else {
      ans[i] += i * x;
      if (last > ans[i]) {
        std::cout << last << " ";
      } else {
        last = ans[i];
        std::cout << last << " ";
      }
    }
  }
    std::cout << "\n";
}

D. Cross Coloring

题意

有一个n行y列的网格，k种染料（非白色），你有q次操作，每次选定一个格子\((x,y)\)，并将其所在的行列的全部格子染成同色，问一共有多少种不同的染色结果。

思路

计算每次染色的贡献情况，假定目前是第\(i\)次染色，如果当前行或者列没有被染色，那么会产生\(k\)种染色结果，如果当前行和列均已经被染色了，那么此时再染上去也只是重复前某次染色操作，不会对答案造成影响。

需要注意的是：如果当前网格均已被染色，那么往后任何染色操作都不会答案造成影响，因为它都可以变成前面某次染色操作中的一种。

Code

void solve() {
  int n, m, k, q;
  std::cin >> n >> m >> k >> q;
  std::vector row(n + 5, false), col(m + 5, false);
  std::vector op(q + 5);
  ll ans = 1;
  for (int i = 1; i <= q; i++) {
    int x, y;
    std::cin >> x >> y;
    op[i] = {x, y};
  }
  int xx = 0, yy = 0;
  for (int i = q; i >= 1; i--) {
    if (!row[op[i].first] || !col[op[i].second]) {
      ans = ans * k % mod;
      xx += !row[op[i].first], yy += !col[op[i].second];
      row[op[i].first] = col[op[i].second] = true;
    }
    if (xx == n || yy == m) {
      break;
    }
  }
  std::cout << ans % mod << "\n";
}

E.Expand the Path

题意

机器人从\((1,1)\)出发，有若干条行走指令，R往右走一格，D往下走一格，现可以使得任意单个指令可以重复若干次，形成新的指令集，问在不走出地图的前提下，机器人一共可以探索到多少个位置。

思路

首先确定一共最后的坐标，计算得出右走和下走的剩余步数。

同时观察当前指令和下一个指令是什么，在走到某个点的时候，考虑是对地图进行扩展探索还是执行下一条指令。

比如说当前的指令和下一个指令都是D，那么我们可以看看前面的指令里是否又出现过R，倘若有，那么可以进行横向扩展，否则就继续按照原指令执行。

最后记得加上到达终点后再进行扩展的小矩形的贡献。

Code

using i64 = long long;

void solve() {
  i64 n;
  std::string op;
  std::cin >> n >> op;
  i64 x = 1, y = 1, sd = 0, sr = 0;
  for (int i = 0; i < (int)op.size(); i++) {
    if (op[i] == 'D') {
      x++, sd = 1;
    }
    else {
      y++, sr = 1;
    }
  }
  sd = (sd ? n - x + 1 : 1), sr = (sr ? n - y + 1 : 1);
  i64 res = 1;
  for (int i = 0, ld = 0, lr = 0; i < (int)op.size() - 1; i++) {
    if (op[i] == 'D') {
      ld = 1;
    }
    if (op[i] == 'R') {
      lr = 1;
    }
    if (op[i + 1] == 'D') {
      if (lr == 1) {
        res += sr;
      } else {
        res++;
      }
    }
    if (op[i + 1] == 'R') {
      if (ld == 1) {
        res += sd;
      } else {
        res++;
      }
    }
  }
  // int类型此处容易爆炸，需要换成longlong类型来进行最后的计算
  res += sd * sr;
  std::cout << res << '\n';
}