Yukicoder 2897

题目描述

给定两个点集 \(S,T\)，我们定义 \(d((x_1,y_1),(x_2,y_2))=|x_1-x_2|+|y_1-y_2|\)。

我们定义两个集合 \(S,T\) 的距离 \(D(S,T)=\min \limits_{s\in S,t\in T}\{d(s,t)\}\)。求 \(D(S,T)\)。

思路

我们把每个 \(S\) 中的元素放在一起做一个多源 bfs，然后对每个 \(T\) 中的元素看它的最短路即可。

时空复杂度均为 \(O(V^2)\)。

代码

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

const int MAXN = 200001, MAXV = 1000, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};

int n, m, dist[MAXV][MAXV], ans = int(1e9);
bool vis[MAXV][MAXV];

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  queue<pii> que;
  for(int i = 1, x, y; i <= n; ++i) {
    cin >> x >> y;
    vis[x][y] = 1;
    dist[x][y] = 0;
    que.push({x, y});
  }
  for(; !que.empty(); ) {
    auto [x, y] = que.front();
    que.pop();
    for(int d : {0, 1, 2, 3}) {
      int nx = x + dx[d], ny = y + dy[d];
      if(nx >= 0 && nx < 1000 && ny >= 0 && ny < 1000 && !vis[nx][ny]) {
        vis[nx][ny] = 1;
        dist[nx][ny] = dist[x][y] + 1;
        que.push({nx, ny});
      }
    }
  }
  cin >> m;
  for(int i = 1, x, y; i <= m; ++i) {
    cin >> x >> y;
    ans = min(ans, dist[x][y]);
  }
  cout << ans;
  return 0;
}

Yukicoder 2899

题目描述

给定一个 \(01\) 串 \(S\)，求有多少个长度为 \(N\) 的排列 \(p\) 满足以下条件：

• 对于每个 \(1\le i<j\le N且 S_i=0,S_j=1\)，都要满足 \(p_i<p_j\)。

思路

我们定义 \(dp_{i,j}\) 表示当前考虑到第 \(i\) 个，下一个 \(1\) 的方案数为 \(j\) 的方案数。

如果 \(S_{i+1}=1\)，那么明显 \(dp_{i+1,j-1}\leftarrow j\cdot dp_{i,j}\)。

否则，此时剩余的数有 \(N-i\) 个，其中有 \(N-i-j\) 个数只能用在 \(0\) 上，也就是 \(dp_{i+1,j}\leftarrow (N-i-j)\cdot dp_{i,j}\)。而可以用在 \(1\) 上的 \(j\) 个数，那么如果你当前用了第 \(k\) 大的，那么第 \(k,k+1,\dots,j\) 大的都不能用了（因为他们比当前这个小）。所以我们有转移 \(dp_{i+1,j-k}\leftarrow dp_{i,j}(1\le k\le j)\)。这个可以用差分优化。

时空复杂度均为 \(O(N^2)\)。

代码

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

const int MAXN = 2001, MOD = 998244353;

int n, dp[MAXN][MAXN], sum[MAXN][MAXN];
string s;

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> s;
  s = ' ' + s;
  dp[0][n] = 1;
  for(int i = 0; i <= n; ++i) {
    for(int j = n - i; j >= 0; --j) {
      sum[i][j] = (sum[i][j] + sum[i][j + 1]) % MOD;
      dp[i][j] = (dp[i][j] + sum[i][j]) % MOD;
      if(i == n) {
        continue;
      }
      if(s[i + 1] == '1' && j) {
        dp[i + 1][j - 1] = (dp[i + 1][j - 1] + 1ll * j * dp[i][j] % MOD) % MOD;
      }else if(s[i + 1] == '0') {
        dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * (n - i - j) % MOD) % MOD;
        if(j) {
          sum[i + 1][j - 1] = (sum[i + 1][j - 1] + dp[i][j]) % MOD;
        }
      }
    }
  }
  cout << dp[n][0];
  return 0;
}

Yukicoder 2901

题目描述

你有一个长度为 \(N\) 的序列 \(A\)，有 \(Q\) 次操作：

• 令 \(A_p\leftarrow x\)。
• 判断 \([l,r]\) 是否存在字串使得其按位或为 \(2^K-1\)，如果有，输出最短长度。

思路

使用线段树维护。

线段树中我们记录这些信息：当前区间答案，前/后缀的使前/后缀按位或发生变化的位置和此时的按位或和。具体来说，就是：

• 令 \(sum_i=A_1\operatorname{OR}A_2\operatorname{OR}\dots A_i\)。我们会记录 \(sum_{i-1}\ne sum_i\) 的 \((sum_i,i)\)。

我们在合并信息时，当前 \(区间答案=\min\{左区间答案,右区间答案,中间的答案\}\)。这里中间的答案就是左区间的后缀+右区间的前缀。

因为我们记录的前/后缀