不懂 - 洛谷仓库

04.21

最小生成树

考虑 krustal 最小生成树的过程，先把边排序，再做一个依次选边的过程。如果我们有了最后的排序结果，就可以轻易求出最小生成树的边权；如果没有的话，就应该想办法记录

k

条

a_i

与求最小生成树边权和的某些中间量的关系。

先排序，如何限制每条边只能被贡献到一边呢？把反边记录下来，如果考虑到反边时

(u, v)

仍未连通则此时必须选它，选是指计入对 mst 的贡献，因此若两条边都不被选也不影响。要保存的信息就是连通性了，题解告诉我们

Bell(9)

并不大，可以计入 dp 维度，另一个维度存当前 mst 几条边使用了

a_i

。

我在场上一直在想贪心或性质，或反悔贪心。不过似乎连通性不是什么很强的条件，

2^m

种选法中很多不优。似乎考虑到模拟 krustal 的排序后就自然而然了。本质似乎还是发现，确定好某一种选法后，得到答案的过程中，所依赖的信息（连通性）可以压缩，于是一边记录依赖的信息一边记录答案所在维度跑 dp。

操作

先套路性取

\log

转为加法，那么初始有一个

01

数组，我们要做模意义下的

01

背包。

场上在试图优化

(\sum x^{a_i}) \prod (1+x^{b_i})

，很不可做。

先把问题转化为，把

[i+w, j+w]

或到

[i, j]

上面。有一个做法是注意到最多只有

p

次

0

变

1

，用

\log

左右的复杂度找到下一个更新点是可接受的。可以用树状数组维护区间哈希，线段树修改，到完全一样时停止递归。势能是不一样的位置数，但

(0, 1)

是无效的。不过注意到背包在模意义下，任何一个

(0, 1)

必定对应一个

(1, 0)

，就对了。

另一个做法是认为操作很快就会有循环节，所以按

\gcd(p-1, x)

分组，每组内随机打乱，直到不可更新时 break。

前一个做法似乎又是可想的，但是敢去写二分下一个不一致还是需要勇气啊。或许又不那么可想，毕竟过的人也没那么多。

04.22

P8386

有人笨笨的，想先枚举最左的那个匹配

1

后合法的位置

i

，则

[1, i]

不合法

[i+1, n]

合法，就能递推了。

但这是错误的，因为

[1, i]

不合法时，后面接一段合法序列，是有可能合法的。

所以还是来看看怎么判定吧。设

f_i

表示以

i

结尾的部分是否合法，则

f_i = \cup_{a_j=a_i} f_{j-1}

，维护

S=\{a_i \mid f_{i=1}=1\}

即可，计数时，转移系数全部相同即可视为等价类，则只有

|S|

是关心的，转移时维护

|S|

和

f_i

即可。

判定改 dp 最重要的是压缩，即把对答案贡献相同的放进同一个等价类内一起转移，转移时，维护判定用的信息，以及到达终点时区分不同类的信息（这道题不需要）。也可以看成，任意一个合法解顺着唯一的路径到达计数终点（有点自动机的感觉了）。

桂花树

晚点再写。

04.23

树

离场切最近的一次。

操作相当于删点，最后的树形态为留下点的虚树，因此找到最大同时存在于两棵树内的树即可。

做一个 dp，

f_u

表示以

u

为根的最大子树大小。则转移时，枚举

u

的儿子，这些儿子必须在两棵树内都位于

u

的子树中，且它们两两没有祖先后代关系，可以跑最大权独立集。

记录一下最大权独立集的做法：

考虑基础的暴力，

f(msk)

表示要求这个集合内点的最大权独立集，找到最高位

x

，分

x

是否被选向下继续搜索，当

msk<2^{n/2}

时记录答案。

前面

n/2

次拓展只会产生

2^{n/2}

中状态，后面的

2^{n/2}

种情况都会被记忆到。

CPP

std::function<int(LL)> dfs = [&](LL st) {
  if (st < lim && dp[st] != -1) return dp[st];
  if ((st & res) == st) return 0;
  int x = std::__lg(st);
  LL r = st & (all ^ ban[x]);
  int ans = std::max(dfs(st ^ (1ll << x)), dfs(r) + g[x]);
  if (st < lim) dp[st] = ans;
  return ans;
};

CF1336E1 证明复杂度的方法也是这样。

场上想了半天最大权独立集用网络流怎么做，哈哈。

序列

https://www.luogu.com.cn/problem/AT_arc066_d

对于单点不保存修改，分类讨论强制不选和强制选就可以了。

那么设

f_i

表示只使用

[1, i]

，

g_i

表示只使用

[i, n]

，

h_i

表示强制选

i

，答案可以

O(1)

得到。

f_i

是比较好求的：

f_i = \max\{ f_j+\frac{(j-i)(j-i-1)}{2} C + s_i-s_j\}

，拆开发现是以

-j

为斜率的一次函数，可以拿来做斜率优化。

考虑

h_i

，它是一个

\max_{x \leq i \leq y}\{ f_{x-1} + \frac{(y-x)(y-x+1)}{2} C + s_y - s_{x-1} + g_{y+1} \}

区间问题考虑分治，想办法把

[l, mid]

跟

(mid, r]

分开考虑。拆，考虑

f_i

表示

x=i, y \in (mid, r]

的最大贡献，这也是一个斜率为

-y

自变量为

x

的一次函数，同样可以斜率优化对

i \in [l, mid]

做，做完后拿来更新

[i, mid]

，同样倒着做一次即可更新

(mid, y]

。

考虑跨越

mid

的

(x, y)

，

(x, y)

拿来更新区间中任何一个点时都不会比使用

(x, y)

更劣，因此是正确的。

真没怎么做过这样的题，区间对内部所有点做贡献。不过可以理解的，

f(x, y) \to [x, y]

拆成

f(x, y) \to [x, mid]

和

f(x, y) \to (mid, y]

，前者发现与

y

无关，拆成

f(x, (mid, r]) \to [x, mid]

，后者发现与

x

无关，拆成

f([l, mid], y) \to [mid, y]

，又发现

f(x, (mid, r])

右侧是定值，将

x

看作变量思考。

有空再写，感觉没空。

04.24

图上的游戏

先拆贡献，把边的贡献拆到点上，发现是出度减入度，再乘一个可以自己挑选的系数。那么把点按出度减入度的绝对值排序，双方一定依次选最前面的。也可以发现确定数值的点的贡献一定为

0

，因为所有方案对称。

dp，按

|\text{out}-\text{in}|

排序后跑背包，这是为了处理相等的部分。把确定数值的点挑出来单独跑背包，合并时卷一起就行。

写不动了，理解了一下 hz 的代码。

CPP

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

const int N = 55, mod = 1e9 + 7, iv2 = (mod + 1) / 2;
int n, m, c[N];
void add(auto &x, auto y) {x = (x + y) % mod; }
struct node{
  int ind, oud;
}a[N * N];
int tot;
int power(int x, int y) {
  int ret = 1;
  while (y) {
    if (y & 1) ret = 1ll * ret * x % mod;
    x = 1ll * x * x % mod, y >>= 1;
  }
  return ret;
}
int get_inv(int x) {return power(x, mod - 2); }

int fac[N], inv[N], C[N][N];
int p[N][N], f[2][N][N][N], g[2][N][N][N];
void init() {
  fac[0] = inv[0] = 1;
  for (int i=1; i<=m; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
  inv[m] = get_inv(fac[m]);
  for (int i=m-1; i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
  for (int i=0; i<=n; ++i) {
    C[i][0] = 1;
    for (int j=1; j<=i; ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
  p[0][0] = 1;
  for (int i=1; i<=n; ++i)
    for (int j=0; j<=m; ++j)
      for (int k=0; j+k<=m; ++k)
        add(p[i][j + k], 1ll * p[i - 1][j] * inv[k]);
  for (int i=0; i<=m; ++i)
    for (int j=0; j<=m; ++j) a[++tot] = (node) {i, j};
  sort(a + 1, a + tot + 1, [](node x, node y) {
    return abs(x.ind - x.oud) > abs(y.ind - y.oud);
  });
  g[0][0][0][0] = 1;
  for (int i=1; i<=tot; ++i) {
    int l = (i & 1), r = (l ^ 1);
    int mul = 1ll * inv[a[i].ind] * inv[a[i].oud] % mod;
    for (int k=0; k<=n; ++k)
      for (int in=0; in<=m; ++in)
        for (int out=0; out<=m; ++out) {
          if (!g[r][k][in][out]) continue;
          for (int x=0,pw=1; k+x<=n&&in+x*a[i].ind<=m&&out+x*a[i].oud<=m; ++x,pw=1ll*pw*mul%mod) {
            add(g[l][k + x][in + x * a[i].ind][out + x * a[i].oud], 1ll * pw * g[r][k][in][out] % mod * C[k + x][x]);
            add(f[l][k + x][in + x * a[i].ind][out + x * a[i].oud], 1ll * pw * f[r][k][in][out] % mod * C[k + x][x]);
            if (x & 1) {
              int tmp = std::abs(a[i].ind - a[i].oud);
              if ((k + x) % 2 == 0) tmp = mod - tmp;
              add(f[l][k + x][in + x * a[i].ind][out + x * a[i].oud], 1ll * pw * g[r][k][in][out] % mod * C[k + x][x] % mod * tmp);
            }
          }
          g[r][k][in][out] = f[r][k][in][out] = 0;
        }
  }
}

int main() {
  cin >> n >> m;
  for (int i=1; i<=n; ++i) cin >> c[i];
  init();
  for (int i=1,cnt=0; i<=n; ++i) {
    cnt += c[i] == 2;
    for (int j=1; j<=m; ++j) {
      //printf("calc %d %d\n", i, j);
      int ans = 0;
      for (int in=0; in<=j; ++in)
        for (int out=0; out<=j; ++out) {
          add(ans, 1ll * f[tot & 1][cnt][in][out] * p[i - cnt][j - in] % mod * p[i - cnt][j - out]);
          //printf("add in %d out %d f %d p %d * %d\n", in, out, f[tot & 1][cnt][in][out], p[i - cnt][j - in], p[i - cnt][j - out]);
        }
      ans = 1ll * ans * fac[j] % mod * fac[j] % mod;
      cout << 1ll * ans * iv2 % mod << " ";
    }
    cout << "\n";
  }
  return 0;
}

04.25

P11915

首先答案有单调性，可以二分也可以从高到低扫，一边扫一边排除不合法的

(u, v)

，直到答案集合被清空。

那么假设希望

dis \leq d

，对于所有

dis > d

的点对

(i, j)

，我们希望加上

(u, v)

后

dis(i, j) \leq d

。我们断言，

i \to u \to v \to j

和

i \to v \to u \to j

中至多一个合法，也就是，枚举

(u, v)

和

(i, j)

，用

(i, j)

排除不合法的

(u, v)

，就能删掉所有不合法点对。

要省掉一维，对

v

记录

mx_v=\max\{dis(v, j) \mid \exist i, dis(i, j) > d \}

，直接比较

dis(u) + mx_v

，若合法则直接跳过当前

d

，否则弹掉

(u, v)

，复杂度是均摊的立方。

感觉得紫。

CF1774F2

考虑到操作

3

相当于把当前序列克隆一遍并对克隆体减去全部操作

2

的值，再把当前累计要减的 tag 翻倍。由翻倍得知这种操作最多出现

\log

次，相当于只用考虑前

\log

次操作。

设

f_i

表示进行第

i

个三操作会造成多少伤害，注意到有

2 f_i \leq f_{i+1}

，从大到小排序，若第

i

个操作不选，则后面操作可以任选，故扫一遍即可，复杂度

O(n \log x)

。

04.30

怎么感觉大家都什么都会。

这是第一题

从后往前倒推 sg 函数值，同行有障碍物是好做的，如果没有的话，注意到只能一直往一个方向走，且 sg 值不会超过

3

，递推一下，如果走进来那个格子的下方是

x

，则继续往下走的 sg 值是

y

。这玩意其实有终点，就是走一步就要到当前格子的情况。

CPP

v3 f(n, v2(m, v1(3, -1)));
std::function<int(int, int, int)> dfs = [&](int u, int v, int op) {
  if (u >= n || a[u][v]) return 100;
  if (f[u][v][op] != -1) return f[u][v][op];
  int p = (v - 1 + m) % m;
  int s1 = op != 1 ? dfs(u, p, 0) : 100;
  p = (v + 1) % m;
  int s2 = op != 0 ? dfs(u, p, 1) : 100;
  int s3 = dfs(u + 1, v, 2);
  return f[u][v][op] = mex(s1, s2, s3);
};

就是考虑到，当 op 确定后，相当于是一个确定的数跟另一个要去 dfs 的值求 mex，把这视为函数复合，则做做前后缀和就可以了。

确实不可以回头走，所以，当手动确定方向之后，就最多只能走一圈了。不能回头反而让问题变简单了啊，你怎么搞反了。

经验好像是要把式子展开看看，或者看看你是不是想复杂了。就像事实上是二元而不是三元。

CPP

#include <bits/stdc++.h>

int mex(int a, int b = 3, int c = 3) {
  if (a != 0 && b != 0 && c != 0) return 0;
  else if (a != 1 && b != 1 && c != 1) return 1;
  else if (a != 2 && b != 2 && c != 2) return 2;
  else return 3;
}

struct tp {
  int a[4];
  tp() { for (int i = 0; i < 4; i++) a[i] = i; }
  tp operator + (const tp &t) const {
    tp res;
    for (int i = 0; i < 4; i++) res.a[i] = t.a[a[i]];
    return res;
  }
};

int main() {
  #ifndef LOCAL
  freopen("first.in", "r", stdin);
  freopen("first.out", "w", stdout);
  #endif
  int n, m; scanf("%d %d", &n, &m); 
  std::vector<std::vector<int>> c(n, std::vector<int>(m + 1));
  std::vector<std::pair<int, int>> p;
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= m; j++) {
      char t; scanf(" %c", &t);
      if (t == '#') c[i][j] = 1;
      else if (t == 'B') c[i][j] = 2;
    }
  }
  std::vector<std::vector<int>> f(n + 1, std::vector<int>(m + 1));
  f[n].assign(m + 1, 100);
  int ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    std::vector<tp> a(m + 2), pl(m + 2), pr(m + 2), sl(m + 2), sr(m + 2);
    for (int j = 1; j <= m; j++)
      for (int k = 0; k < 4; k++)
        if (c[i][j] == 1) a[j].a[k] = 3;
        else a[j].a[k] = mex(f[i + 1][j], k);
        for (int j = 1; j <= m; j++) 
          pl[j] = a[j] + pl[j - 1], pr[j] = pr[j - 1] + a[j];
        for (int j = m; j >= 1; j--) 
          sl[j] = sl[j + 1] + a[j], sr[j] = a[j] + sr[j + 1];
        for (int j = 1; j <= m; j++) {
          if (c[i][j] == 1) f[i][j] = 3;
          else 
            f[i][j] = mex(f[i + 1][j], (pl[j - 1] + sl[j + 1]).a[3], (sr[j + 1] + pr[j - 1]).a[3]);
          if (c[i][j] == 2) ans ^= f[i][j];
        }
  }
  puts(ans ? "Alice" : "Bob");
}

loj2732

等价于求只保留

\geq x

的数组成多少个连续段，等价于有多少对相邻的数

(a, b)

一个在

x

上一个在

x

下。

拆贡献。若

x \leq a

贡献

-1

，否则贡献

1

，对

b

也一样。于是只有当

a \leq x \leq b

的时候会有

2

的贡献，容易用树状数组维护。

05.01

T1

我从下往上贪心做的。有一些奇怪的神秘维护划分树也过了呀。为什么别人那么能把自己不确定正确性的东西写出来呢。

T2

先把题意等价到，在

n \times m

的矩阵中四连通游走，从

(x', y')

出发，一共移动

t'

次，且第

t'-t

次不能位于

(x, y)

。拆成从

(x', y')

出发移动

t'

次，从

(x', y')

移动

t'-t

次到

(x, y)

，从

(x, y)

移动

t

次，均不能触碰边界。

容易发现两维独立，求出来卷起来就好了。

那么怎么求从

x

出发游走

t

步不触碰上下边界的方案数呢，考虑经典的反射容斥（P3266），答案是一个

O(t/n)

项组合数加减。

枚举

n

，再考虑在

t

移动时快速求出答案。那么注意到组合数的上下指标移动都是

O(1)

级别的，每次递推复杂度为

O(t^2/n)

。

当

n \geq \sqrt{t}

时这样做，否则使用

O(nt)

的朴素暴力，复杂度为

O(t \sqrt t)

。

不懂

文章操作