YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 1.4k 所需閱讀時間 ≈ 5 分鐘
G(贪心,差分约束,最短路)H(LGV引理,状压DP)

G - 01Sequence

https://atcoder.jp/contests/abc216/tasks/abc216_g

代码

https://atcoder.jp/contests/abc216/submissions/33727628

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
 
int read(){int r;scanf("%d",&r);return r;} // read
 
const int N=200000;
int a[N+10]; // a[空白个数] = 到右侧点, 之间全是1
int r[N+10]; // 读入
int y[N+10]; // 左侧0个数
vector<int> l2i[N+10]; // 左端点到第i个区间
 
int main() {
  int n = read();
  int m = read();
  rep(i,1,m+1){
    int l = read();
    r[i] = read();
    y[i] = (r[i]-l+1) - read(); // 左侧0个数 [[....yi],1,1,1,1,1,1]
    l2i[l].push_back(i);
  }
  int cnt = 0; // 遍历过程中 (<l) 0 的个数
  rep(pos,1,n+1){ // 下标
    for(auto i:l2i[pos]) a[y[i]+cnt] = max(a[y[i]+cnt],r[i]);// [pos.....r[i]]
    printf("%d ", a[cnt] >= pos); // 这一段全是1, 1尽量向右,贪心塞0
    cnt += (a[cnt] < pos); // 计数+1
  }
  return 0;
}

H - Random Robots

数轴上k个机器人, 初始位置分别在xi

每次 每个机器人独立选择 移动(正向+1)或不动 1/2 概率

问经过N次,过程中没有任何两个robot 同时在同位置的概率

mod 998244353

限制

k [2,10]

n 1000

xi [0,1000], 严格单增提供

2s

1024mb

我的思路

一般来说 概率 = 次/总次数 可以互相转化

不相遇 可以 和相遇的容斥互相转化

k 10 的话可能和k的bitmask有关系

如果进行一次

而碰撞比不碰撞似乎好算一些

而且一般是相邻碰撞

pi 和pi+1 在t次时刻碰撞

意味着 t-1 次时距离1, t时 1/4 概率

0~t-1 时刻每次 1/4 +1, 1/4 -1, 1/2 不变

设原来距离 为d

那么 -1 次数 减去 +1 次数 = d-1, 且中间不能有负数情况

变成后缀个数统计问题

似乎可以强行算出t时刻 的概率, 实在组合排列不行, dp[时刻1000][距离2000] 来算也可以

那么无碰撞 = 所有 - 碰撞

所以想办法容斥掉碰撞

题解

用一下LGV引理相关的思路: 相交的路径 总有转化方法,成对的出现互为相反数的贡献,从而有相交的内容贡献和为0

每一个路径组方案贡献1 乘上-1的最终位置的逆序列数量次方, 其实就像当于LGV中所有边权为1 的特殊情况

$\sum_{Q} (-1)^{\sigma(Q)}\cdot(\frac{1}{2})^{NK}\cdot\prod_{i=1}^K {\rm C}(N,Q_i-x_i)$

也就是 方案 * (-1) 的幂次权, 再除以总方案数

Qi 为初始第i个机器人最终的下标

$\sigma(Q)$ 为逆序对个数

那么对于一条具体的有交的路径, 找其编号最小交点, 其中最小的起始位置,做后置路径交换(和LGV一样), 那么将得到一个新的路径组,有同样的交点,最小交点的最小起始位置依然相同, 但逆序对数变化为1, 所以总贡献为0

f[S][j] = 选起点集合在S中, 最终节点最大值 <= j 的 带权 方案数和

ans = f[{1,...,k}][x[k] + n]

考虑状态转移

最终最大节点 < j, f[S][j] += f[S][j-1]

最终最大节点 = j, f[S][j] += lgv中的行列式值 展开最后一列

所以有

$f(S, j) = f(S, j-1) + \sum_{i=1}^{|S|} (-1)^{|S|+i} e(x_{s_i}, j) f(S\setminus{s_i}, j-1).$

$f(S, j) = f(S, j-1) + \sum_{i=1}^{|S|} (-1)^{|S|+i} \binom{n}{j-x_{s_i}} f(S\setminus{s_i}, j-1).$

状态$2^k(n + x_k - x_1)$, 转移倍数$k$

总时间复杂度 $2^kk(n + x_k - x_1)$

注意到j仅依赖于j-1, 所以可以滚动数组降低空间

而S依赖于的都是S子集, 所以保证顺序即可

$for(j) \\ f(S) = f(S) + \sum_{i=1}^{|S|} (-1)^{|S|+i} \binom{n}{j-x_{s_i}} f(S\setminus{s_i}).$

注意到这里的i不是X数组的i而是X选出的x按照顺序组成的S中的i, 且是1-index

也可以表示成$d(S,i) = S$中比$i$大的的个数

$for(j) \\ f(S) = f(S) + \sum_{i=1}^{|S|} (-1)^{d(S,i)} \binom{n}{j-x_{s_i}} f(S\setminus{s_i}).$

代码

https://atcoder.jp/contests/abc216/submissions/33737388

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int x[2010]; // 初始位置
mint f[2010] = {1}; // f[i] = binom(n,i)
int p[(1<<10)+10]; // p[mask] = (-1)^(mask中1的个数)
mint dp[(1<<10)+10] = {1}; // 第二维滚动 f(S,pos) = f(S, pos-1) + \sum_{i=1}^{|S|} (-1)^{count(S,> i)} \binom{n}{pos-x_{s_i}} f(S\setminus\{s_i\}, pos-1).$

int main() {
  int k=read();
  int n=read();
  rep(i,0,k) x[i]=read();
  rep(i,1,n+1) f[i]=f[i-1]*(n-i+1)/i; // binom(n,i-1) -> binom(n,i)
  rep(mask,0,1<<k) p[mask] = p[mask>>1] * (mask&1?-1:1);
  rep(pos,x[0],x[k-1]+n+1){ // 第二维滚动
    per(mask,0,1<<k) { // 第一维 bitmask 注意顺序
      rep(i,0,k) if(mask&(1<<i)) { // 变成递推贡献, 要增加的bit位
        if(x[i]<=pos && pos<=x[i]+n) { // 保证 binom 不为0
          // f(S) += f(S\i) * binom(n, pos - x[S_i]) * (-1)^count(S,>i)
          dp[mask] += dp[mask^(1<<i)] * f[pos-x[i]] * p[mask>>(i+1)];
        }
      }
    }
  }
  printf("%d\n",(dp[(1<<k)-1] / ((mint)2).pow(k*n)).val()); // 频次/总次数 = 概率
  return 0;
}

总结

G

贪心完全不会

题解说有个cow game

有一些 dj-di <= wij 的限制

寻找最大的 dT-dS, 可以变成最短路问题

http://poj.org/problem?id=3169

H

学了一下LGV引理, 和其思路细节

路径不相交问题首选逆序对容斥，那么可以套用 LGV 引理

相关练习: https://www.luogu.com.cn/problem/P7736

参考

官方题解

LGV引理

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
G(概率论,组合数,期望,贡献统计)H(二分图,霍尔定理,SOSDP,子集反演)

G - Colorful Candies 2

N 个 有色糖果,第i个颜色c[i]

从中选K个有 binom(N,K)种方案

等概率选一种方案

价值=所选的颜色的不同的数量

对于每个 k= 1…N 求期望价值

mod 998244353

限制

N 5e4

c[i] [1,1e9]

4s

1024mb

我的思路

首先只关心不同值,显然c[i]可以离散化到[1..N]

答案 = sum{价值} / binom(N,K)

不同颜色互不影响

所以 选了j种颜色, 一共k个, 如果能算方案出来 f(j), 那么答案 = sum j * f(j)

指定的 c[…] 中选的话

似乎可以卷积

去表示每个颜色 选t个的方案数, 然后卷积意义是前 j 种颜色(可能有的不选) 选k个的方案数

好像无法获得选了几个颜色

题解

反过来, 也就是每个颜色出现一次的概率 的贡献和

P(出现一次) = 1-P(一次都不出现)

binom(n-x,k) / binom(n,k) , 也就是x 是这个颜色的个数

其中 n-x < k 的话, 必定出现p = 1

(binom(n,k) - binom(n-x,k))/binom(n,k) , 也就是x 是这个颜色的个数

可以减少计算

注意到 可以统计个数为x的有多少个, 这样最多 $\sqrt(N)$个统计

因此对于k来讲,是$O(\sqrt{N})$的

总的便是$O(N^{\frac{3}{2}})$

代码

https://atcoder.jp/contests/abc215/submissions/33712411

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
const int MOD = 998244353;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int c[50010];
mint fac[50010] = {1};
mint invv[50010] = {0,1};
mint invfac[50010] = {1};

mint binom(int n,int m){
  if(m > n) return 0;
  return fac[n] * invfac[m] * invfac[n-m];
}

int main(){
  int n = read();
  rep(i,0,n) c[i] = read();

  rep(i,1,n+1) fac[i] = fac[i-1] * i;
  invv[1] = 1;
  rep(i,2,n+1) invv[i] = (MOD - MOD/i) * invv[MOD%i];
  rep(i,1,n+1) invfac[i] = invfac[i-1] * invv[i];

  sort(c,c+n);
  vector<int> sz = {1};
  rep(i,1,n){
    if(c[i] != c[i-1]){
      sz.push_back(1);
    }else{
      sz.back()++;
    }
  }
  sort(sz.begin(),sz.end());
  vector<pair<int,int>> sc; // size count
  int cnt = 0;
  rep(i,0,sz.size()){
    cnt++;
    if(i+1 == (int)sz.size() || sz[i] != sz[i+1]){
      sc.push_back({sz[i],cnt});
      cnt = 0;
    }
  }

  rep(k,1,n+1){
    mint bnk = binom(n,k);
    mint ans = bnk * sz.size() ;
    for(auto [s,t]:sc) {
      if(n-s < k) break; // n-s < k 的话, 必定出现p = 1
      ans -= binom(n-s,k) * t; // * 次数
    }
    ans /= bnk;
    printf("%d\n",ans.val());
  }
  return 0;
}

G - Cabbage Master

N种菜,每种 A[i] 个

M个需求, 每个需求B[i] 个, 但是限制c[i][j] = 0/1 表示第i个需求 是否允许得到 第j种菜

如果 能满足所有需求则 成功

现在要尽量少的删除一些菜的个数, 让它无法成功

并且求, 删除同样数量的方案数 mod 998244353

限制

n 20

m 1e4

a[i] 1e5

b[i] 1e5

3s

1024mb

我的思路

一眼感觉网络流, 但是看着这n这么少

又觉得说 会不会是 maskdp

2^20 = 1048576, 大概1e6

网络流思路

就是 S -> Ini 流量 A[i]

Ini -> Outj 流量无限 如果c[i][j] == 1

Outj -> T 流量B[i]

那么目标是让最小割(最大流) <= sum B[i] 即可

题解

二分图

左侧N个颜色, 右侧M个需求

注意到 这里成功对应的是 匹配 = sum 右侧

所以是枚举右侧的的点集,看对应左侧的点集是否大于等于右侧

左侧L, 右侧R

要能完美匹配 $\forall S \subset R $

左侧对应集合并的和 $\ge S$对应需求的和

即 min (左侧对应集合并的和 - S对应需求的和) >= 0

n=20, 考虑枚举左侧的并,来找右侧的max

但似乎通过枚举子集可能有m 2^n 复杂度

但实际上我们要的是

min {f(L0) - g(L0)} >= 0, 其中f 算的集合里左侧的和, g 算的映射到左侧包含于集合的右侧的值的和 (既然B[i] 都是正的,那就是所有的加起来让g达到最大

g中计算 子集和可以sosdp 高维前缀和

那么删除数量X = min( f(L0) - g(L0)) + 1

然后问题变成如何计算方案数

ans = 0 , 不操作1种

对于ans > 0

设 左侧移除的X的值 来自的点集合恰好为S

当存在 S1 满足 S 是 S1 的子集, 且 f(L0) - g(S1) + 1 == X, 这时 S移除X的方案数h(S) 会有贡献

binom(S的个数,X) = sum h(T), T 是S的子集

这就是 子集反演问题

$h(S) = \sum (-1)^{|S|-|T|} binom(T的个数,X)$, T是S的子集

又是求子集的函数和, 那么这里把和原集合有关的移动一下

$(-1)^{|S|} {h(S)} = \sum (-1)^{|T|} \binom{f(T)}{X}$, T是S的子集

同样FWT, SOSDP可以处理

子集反演

$g(S) = \sum f(T)$, T是S的子集合

$f(S) = \sum (-1)^{|S| - |T|} g(T)$ , T是S的子集合

代码

https://atcoder.jp/contests/abc215/submissions/33719233

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#include <atcoder/all>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read

const ll INF = 0x3f3f3f3f; // > 1e9
const int N = 20;
const int MASK = ( 1 << N ) ;
const int M = N * 100000;

mint fac[M+10] = {1}; // 阶乘
mint ifac[M+10] ={1}; // 阶乘的逆向

int f[MASK+10]; // f[1 << i] = A[i], f[mask] = sum A
int g[MASK+10]; // g[左侧mask] = sum B , 通过sosdp 变成子集和
mint h[MASK+10]; // h(S=bitmask) S中移除 X 个的方案数,(每个恰好一个)
int cnt[MASK+10]; // mask 中1的个数
int cont[MASK+10]; // cont[mask] = 多少个父集合 是满足 最小代价为X的 在mask中移除让Hall定理触发不满足

int B[M+10]; // 读入
int adj[M+10]; // adj[右侧] = 左侧的bitmask

mint binom( int n, int m ) { return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m]; }

int main() {
  rep(i,1,M+1) fac[i] = fac[i - 1]*i;
  ifac[M] = fac[M].inv();
  per(i,0,M) ifac[i] = ifac[i + 1]*(i + 1);
  int n = read();
  int m = read();
  rep(i,0,n)f[1 << i]=read();//f[1 << i]=A[i]
  rep(j,0,m)B[j]=read();
  rep(i,0,n)rep(j,0,m) if(read())adj[j]|=1 << i; // 转换成mask
  rep(j,0,m)g[adj[j]] += B[j]; // g[对应左侧mask] += B[j]
  rep(mask,1,1 << n) cnt[mask] = cnt[mask >> 1] + ( mask & 1 ); // 计算1个数
  rep(mask,1,1 << n) f[mask] = f[mask&(-mask)] + f[mask&(mask-1)]; // 去掉最后一个1 和最后一个1的mask之和
  rep(pwr,0,n) rep(mask,1,1 << n) if(mask & (1 << pwr)) g[mask] += g[mask ^ (1 << pwr)]; // sosdp 高维前缀和
  rep(mask,0,1 << n) if(!g[mask]) g[mask] = -INF; // 右侧没有集合对应左侧集合是mask的子集合
  int X = INF; // 答案第一部分 删除个数
  rep(mask,1,1 << n) X = min(X,f[mask]-g[mask]+1 ); // Hall定理, min(左子集值和 - 右侧来源子集和)
  if(max(X,0) == 0) { // 本来就不合法
    printf( "0 1\n" );
    return 0;
  }
  // h'(S) = (-1)^|S| h(S) = sum (-1)^|T| binom(f[t], X) SOSDP
  rep(mask,1,1 << n) h[mask] = binom(f[mask], X) * (cnt[mask] & 1 ? -1 : 1);
  rep(pwr,0,n) rep(mask,0,1 << n) if(mask & (1 << pwr)) h[mask] += h[mask ^ (1 << pwr)];
  rep(mask,0,1 << n) h[mask] = h[mask] * ((cnt[mask] & 1)?-1:1);

  // SOSDP 父集合反演(本质上还是 子集反演, 你只是把每个mask 看成mask的取反即可, 最外层是pwr顺序, mask每次之间没有链式依赖,都是两两依赖, 所以mask不需要换顺序
  rep(mask,1,1 << n) if( f[mask] - g[mask] + 1 == X ) cont[mask] = 1;
  rep(pwr,0,n) rep(mask,0,1 << n) if(mask & (1 << pwr)) cont[mask ^ (1 << pwr)] += cont[mask]; // 统计父集合可行的次数

  mint ans = 0;
  rep(mask,0,1 << n) if(cont[mask]) ans += h[mask];
  printf("%d %d\n",X, ans.val());
  return 0;
}

总结

G

其实还算基础知识点, 如何批量算模拟元,批量阶乘和阶乘模逆元,如何基于它们快速bionom

然后就是概率统计变形状和相同次数统计变成$\sqrt{N}$

评分 2267 也差不多

H

二分图,霍尔(Hall)定理

二分图一定程度上, 就不在意初始设计的方向了, 因为是匹配, 内部是没有关系的

霍尔定理对于这种大于1流量的也适用(因为从本质上看 左/右侧最多k个, 无非是k个点, 有无穷大边, 无非是这些拆开后的左右侧按照原来的关系两两有边, 而这个思路是不是特殊题型还能反过来思考)

这种”任意”的条件，可以考虑是在哪个部分将它破坏的

还涉及到 子集反演(以及用子集反演完成父集合反演)

参考

官方题解

hall’s theorem

發表於 更新於 分類於 ， Disqus： 文章字數： 2.9k 所需閱讀時間 ≈ 10 分鐘
G(排列,图,容斥,DP,环)H(scc,网络流,费用流)

G - Three Permutations

https://atcoder.jp/contests/abc214/tasks/abc214_g

给[1..N]的排列p和q

求多少个排列r 满足 r[i] != p[i] , r[i] != q[i], i = [0..N]

mod 1e9+7

限制

n 3000

题解

我的思路

如果只是给一个排列p

要找另一个排列r让每个位置对应不等(r[i] != p[i])

一个想法是, 把它直接按照p[i]的1到n重新排序

问题变成了 找r[i] != i的排列方案数

考虑长度n的和n-1之间变化

如果i放的n,而n放的i ,那么 去掉i和n, 方案数 为f(n-2)

n 有 n-1中交替放的方案, (n-1) f(n-2)

如果i放的n,而n放的不是i, 那么,交换i和n放的, 前n-1也合法, f(n-1)

f(n-1) 每个方案每个位置和n换, 贡献(n-1)f(n-1)

f(n) = (n-1)(f(n-1) + f(n-2))

f(1) = 0

f(2) = 1

f(3) = 2(1+0) = 2

那么对于两个序列

首先一样的思路按照p 来排序

那么变成 r[i] != q[i], r[i] != i

但因为q[i]的限制并不能 像上面那样转移

题解

如果对于每个位置,计算ri=pi或ri=qi的排列方案数,可以考虑容斥

假设 i1,i2,…ik, 对应的下标满足, ri=pi 或 ri=qi, 那么要计算所有r[i1],r[i2]..r[ik]的值方案

对于每个 i in i[1..k],在图中,我们增加一个(pi,qi)的边, 只需计算每条边分配给其一个端点的总数，以便没有两条不同的边共享一个分配给它的顶点。(意思就是边即是i, 而给边分配的点,即是r[i]的值, 不能共享点,意味着值不重复

(注意到 如果(pi,qi)链接的话, 只可能是 链 或 环,不可能出现分叉

对于每个联通分量考虑(除去孤立点和自环)

因为环之间两两不相关, 所以每一组i的选择答案 = 不同环的方案的乘积

我们对于一个K个点的环内, 选了k条边, 的方案数

当所有边被选(所有的i都有相等关系), 那么有2种方案

不是全部都选, 考虑把环剖成链讨论首尾是否选择

dp[i][j][s0=0/1/2][si=0/1/2] 表示前i条边,选择了j条, 且第一条是s0 状态,第i条是si状态的方案数

0: 未选择

1: 该边分配了左点

2: 该边分配了右点

状态转移

不选 dp[i][j][s0][0] = sum dp[i-1][j][s0][0..2]

向左 dp[i][j][s0][1] = sum dp[i-1][j-1][s0][0..1]

向右 dp[i][j][s0][2] = sum dp[i-1][j-1][s0][0..2]

这样最后长n的环选了k条链的总方案数 就是sum dp[n][k][s0][s1], 且 (s0 != 1 || s1 != 2)

记为circle[n][k]

如果gi 表示 指定了i个不合法的选择, 剩余的n-i个任意选(可以合法也可以不合法,但始终满足是排列)

那么 $ans = \sum_{i=0}^n (-1)^i(n-i)! g_i$

而gi也可以通过上面环的结果, 去做dp

f[i][k] = 前i个环指定了k个边 的方案数

f[i][k] = sum{f[i-1][k-t] * circle[sz[i]][t]} 前i个环指定了k个边 的方案数

于是把所有环剖成链连续放在数组上

g[i][j][s0][s1] = 前i边,指定分配了j条, i所在环的起始是s0,结束是s1的方案数, 这里也是把s0也与i做相关意义了

转移类似, 分别是跨环转移 和 环内转移

感觉这题还可以改控制最大环长, 但增大总长度, 变成矩阵乘法

代码

https://atcoder.jp/contests/abc214/submissions/33643608

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

using mint = atcoder::modint1000000007;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)

int read(){int r;scanf("%d",&r);return r;} // read

const int N = 3000;

int p[N+10];
int q[N+10];
int e[N+10]; // 单向边
int vis2[N+10]; // 每个环的结束位置 = 1, 例如环为 2 3 5, 那么 [2]=1,[2+3=5]=1,[5+5=10]=1, 自环结束位置=2
// 0 不分配, 1 分配左点, 2分配右点
mint g[N+10][N+10][3][3]; // [i][j][s0][si] 每个环剖成链以后,长度i的链 分配了j条, 当前环 首个点state 0, 最后一个点statei
mint fac[N+10]; // n!

int main() {
  int n=read();
  fac[0]=1;
  rep(i,1,n+1) fac[i]=fac[i-1]*i;
  rep(i,0,n) p[i] = read();
  rep(i,0,n) e[p[i]] = q[i] = read(); // 建立边 p,q => e
  { // e => vis2
    vector<bool> vis(n+1,false); // 点是否被访问
    int m = 0;
    rep(i,1,n+1) if(!vis[i]){
      if(e[i]==i) { // 自环
        vis2[++m]=2;
        continue;
      }
      for(int j=i;!vis[j];j=e[j]) {
        vis[j]=1;
        m++;
      }
      vis2[m]=1;
    }
  }
  g[0][0][0][0] = 1; // 初始状态
  vis2[0] = 1;       // 初始状态
  rep(i,0,n+1) rep(j,0,i+1){ // 剖成链, 前i个边, 指定j个不合法, 第i个点所在环首个点s0,第i个点s1状态
    if(vis2[i]) { // 环结束位置
      g[i][j][1][2] = 0; // 环首为向左环尾向右
      if(vis2[i]==2) g[i][j][1][1]=0; // 自环, 不选是一种, 选左和选右相同, 去掉一个
      rep(k,0,3) rep(l,0,3) { // i+1 是新的环
        auto v = g[i][j][k][l];
        g[i+1][j  ][0][0] += v; // 新环 本身与i 无关, 应该是1,这里相当于全部乘上前面的倍数
        g[i+1][j+1][1][1] += v;
        g[i+1][j+1][2][2] += v;
      }
    } else { // 环内
      rep(k,0,3) rep(l,0,3){
        auto v = g[i][j][k][l];
        g[i+1][j  ][k][0] += v;
        g[i+1][j+1][k][1] += ((l == 2) ? 0 : v); // 不能下一个向左 这一个向右
        g[i+1][j+1][k][2] += v;
      }
    }
  }

  mint res = 0;
  rep(i,0,n+1) {
    mint cnt = 0; // 方案数
    rep(j,0,3) rep(k,0,3) cnt += g[n][i][j][k];
    res += fac[n-i]*cnt*(i%2?-1:1); // 容斥
  }
  printf("%d",res.val());
  return 0;
}

H - Collecting

https://atcoder.jp/contests/abc214/tasks/abc214_h

有向图 N点, M边

xi个东西在点i上

k个人一个一个遍历graph

1开始, 遍历有限长度, 找最大可被收集的东西个数

限制

n2e5, m 2e5

k 10

xi [1..1e9]

4s

1024mb

题解

我的思路

显然 可以scc缩点, 然后问题变成 一个有向无环图

找k(<=10)条路径, 被经过的点的和最大

这没啥想法了

例如

a->b->c

a->b->d

a->e->d

a->e->f

一次选择的贪心 是否对全局也是最好的?

题解

果然也是先scc变成DAG

然后这里是最小费用流问题

  1. DAG每个点拆成out,in, 增加源S和汇T
  2. DAG中每个u, 增加 in[u] -> out[u], 流量1, 费用-valu, 以及无限(K)流量费用0
  3. DAG中(u,v)变成 out[u] -> in[v] , 流量无限(K), 费用0
  4. S -> in[1] 容量k, 费用0 ( 这里可以简化成去掉S, 1 作为S, 通过 in[1] -> out[1] 总容量k 来保证最大流 = K
  5. out[u] -> T 容量无限(k), 费用0

求min cost max flow , 答案乘上 -1

我看atcoder的库是可以限制最大流的求 mincost

然后这样做的话 代价有些是负的

办法是

  1. DAG中每个u, in[u] -> out[u], 流量1费用0, 流量无限(费用val[u])
  2. DAG中(u,v), out[u] -> in[v], 无限流量, 费用sum X[u+1..v-1]
  3. out[u] -> T, 无限流量, 代价sum X[u+1..N]

ans = s->t 流=K 的最小代价 - K * sum X

原理

本质上希望每个流的代价增加 sum X

那么整体形式就是 从 in[u0] -> out[u0] -> in[v1] -> out[v1] -> T

希望 每次到out[u] 的时候, 费用和的增量是 前缀和X[0..u], 这样每个 out[u] -> T, 只需要是X[0..n] - X[0..u] 即可

那么自然 out[u]-> in[v] -> out[v]

这一整段增加为 X[0..v] - X[0..u] // 保证拓扑序 来让它非负? atcoder的scc返回保证了逆向拓扑序!!

那么, 这里设计 in[v] -> out[v] 增加X[v]

所以 out[u] -> in[v] 增加 X[0..v] - X[0..u] - X[v]

它这个没有拓扑似乎也保证不了 cost非负?

保证的是没有负环!?

注意因为没有S所以 链增加的是 X[0..n] - X[0..start]

费用流 mcmf

费用流, 每个边有流量限制和每单位费用

最大流最小费 = 最短路

最大流最大费 = 最长路

满足正向单位费用的相反数 = 逆向单位费用

最小费用以流量的单价作为边权值跑最短路，注意因为不会有负环（否则费用是负无限大）所以用SPFA就可以了

如果增广路中出现了负环，那么在上一次选择中一定有一条更短的路径。(如果开始就有负环呢？ 那么它说明你图建错了

最小费用流, 就是在做最大流的时候, 把dfs改成 spfa, 而距离= 路径上单位cost代价之和

代码

https://atcoder.jp/contests/abc214/submissions/33655383

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#include <atcoder/scc>
#include <atcoder/mincostflow>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int main() {
  int N = read();
  int M = read();
  int K = read();
  vector<int> A(M), B(M);
  atcoder::scc_graph graph(N); // 0-index 点
  rep(i,0,M){
    A[i] = read() - 1; // 0-index
    B[i] = read() - 1;
    graph.add_edge(A[i], B[i]);
  }
  const vector<vector<int>> scc = graph.scc(); // 连通块 atcoder的scc返回还保证了逆拓扑序
  const int V = scc.size(); // DAG节点个数
  vector<int> belongs(N); // [节点] = 所在块
  rep(i,0,V) for(int u : scc[i]) belongs[u] = i;
  vector<ll> X(V); // 新图每个点上的值
  rep(i,0,N) X[belongs[i]] += read();
  vector<ll> accum(V + 1, 0); // 前缀和
  rep(i,0,V) accum[i + 1] = accum[i] + X[i];

  atcoder::mcf_graph<int, ll> network(2 * V + 1); // in[1]变成 S, T = 2*V
  int S = 2*belongs[0];
  int T = 2*V;
  rep(i,0,V) {
    network.add_edge(2 * i, 2 * i + 1, 1, 0); // in[i] -> out[i], 容量1, 费用 -X[i] + X[i]
    network.add_edge(2 * i, 2 * i + 1, K, X[i]); // in[i] -> out[i], 容量K(无穷), 费用 0 + X[i]
    network.add_edge(2 * i + 1, 2 * V, K, accum[V] - accum[i + 1]); // out[i] -> T 费用 0 + All - X[0..i]
  }
  rep(i,0,M) {
    int u = belongs[A[i]];
    int v = belongs[B[i]];
    if (u != v) network.add_edge(2 * u + 1, 2 * v, K, accum[v] - accum[u + 1]); // out[u] -> in[v] , 容量k, 费用 0 + X[0..v] - X[0..u]
  }
  auto [maxflow, mincost] = network.flow(S,T,K/* 限流 */);
  printf("%lld\n",(accum[V] - accum[belongs[0]]) * K - mincost);
}

总结

G

容斥还是不熟 感觉这个式子需要记忆 $ans = \sum_{i=0}^n (-1)^i c_i$

然后这个排列会构成多个环感觉很常用虽然知道, 但是这里通过边表示i, 分配点表示取值还是没有想到, 感觉也是一种转化思路

然后环拆成链+两头也是很经典的方法了

实现上把 环变成链 再在数组上连续性, 去做dp的方法, 比多重再算g更神奇

另外这里递推贡献更新时没有保证正确性, 有的在处理时才修复正确性 比如[1][2] 和自环

H

网络流完全不会, 学了一手费用流, 看起来就是正常最大流 变了spfa和 路径cost和

atcoder 内置的scc 和mincostflow

1
2
#include <atcoder/scc>
#include <atcoder/mincostflow>

然后这个神奇的让 所有费用变正的 前缀和变化法 , 感觉其它地方似乎也能用

参考

官方题解

oi wiki 费用流

發表於 更新於 分類於 ， Disqus： 文章字數： 1.8k 所需閱讀時間 ≈ 6 分鐘
G(DP, 字符串),H/Ex(图,DP,拓扑排序,dij,拆点)

G - Replace

字符串S,T包含小写英文

可以执行k种 操作, 任意次 任意顺序

第i种 操作: 1代价, 把一个字符Ci 换成 字符串Ai

问S变成T 的最小代价 或不可能

限制

|S|<=|T| <= 50

k <= 50

|Ai| <= 50

2s

1024mb

题解

我的思路

既然是字符(离散)换成字符串

那么岂不是 dp[i][j] 表示 S前i 个换成 T前j个

dp[i][j] = dp[i-1][j-k], s[i] -> T[j-k+1..j] 可行

那么问题是如何判断可行

换句话说, 如果我们能算出 T[j-k+1..j] 能否逆向变成s[i] 也是办法

但是感觉这个会分叉很多

题解

dp[i][j][c] = 最小代价T[i..j] => 字符 c

f[i][j][k][l] = 最小代价T[i..j] => 字符串 A[k][1..l] (这个很关键, 是把字符中前缀设置成状态)

1
2
3
for i = N -> 1:
  for j = i -> N:
    计算 f[i][j][k][l], f[i][j][c], f[i][j][k][1]

计算f[i][j][k][l] 时 (T[i..j] => A[k][1..l])

注意到替换时顺序不会变相当于

时 (T[i.m][m+1.j] => A[k][1..l-1] A[k][l])

$f[i][j][k][l] = min(f[i][m][k][l-1] + dp[m+1][j][A[k][l]])$

计算dp[i][j][c] / f[i][j][k][1]

  1. 本身就是c字符, i==j, Ti = c, 0
  2. 一步到位 T[i..j] = A[k], C[k] = c
  3. 先转换到某个A[k] 再转一步, min(f[i][j][k][|A[k]|]+1),C[k] = c

f[i][j][k][1] 从dp[i][j][A[k][1]] 中读即可

这大概是O(n^4)的状态

O(n^5) 的转移复杂度

这其中还有一个问题是, 对于A和C都是单个字符的, 你会出现T[i...j] -> c0 -> c1 -> c2

你需要求最短路dij/spfa松弛 即可

代码

https://atcoder.jp/contests/abc261/submissions/33608140

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;} // read

const int INF = 0x3f3f3f3f; // 无穷大
const int maxc = 'z' - 'a'; // 最大字符对应数字

vector<int> t;
int f[60][60][60][60]; // [l..r] => a[k][0...i] (prefix(a[k][i]))
int dp[60][60][30]; // [l..r] => char c

int c[60] = {maxc + 1}; // 不存在的字符
vector<int> a[60]; // c[i] -> a[i];
vector<pair<int,int> > c2c; // 单字符映射

char tmp[60];
int lcStr2VecInt(vector<int> & res){ // lower case string to vector<int>
  scanf("%s", tmp);
  int sz = strlen(tmp);
  res.resize(sz);
  rep(i,0,sz) res[i] = tmp[i] - 'a'; // s 放在 c[0],a[0]
  return sz;
}

void setMin(int &v0,int v1){v0 = min(v0,v1);}

int main(){
  int ns = lcStr2VecInt(a[0]); // s 放在 c[0],a[0]
  int nt = lcStr2VecInt(t); // t
  int K = read() + 1; // 包含s
  rep(i,1,K){
    scanf("%s", tmp);
    c[i] = tmp[0] - 'a';
    if(lcStr2VecInt(a[i]) == 1) c2c.push_back({c[i], a[i][0]});
  }
  rep(l,0,nt) {
    rep(r,l,nt) { // 全部设置为无穷大
      rep(k,0,K) rep(i,0,50) f[l][r][k][i] = INF;
      rep(c,0,maxc+1) dp[l][r][c] = INF;
    }
    dp[l][l][t[l]] = 0; // 本身就是字符
  }
  // --- init ---
  per(l,0,nt) rep(r,l,nt){ // T[l..r], 各种顺序都行 保证依赖关系先被运算
    rep(k,0,K){
      int sz = a[k].size();
      rep(i,1,sz){ // T[l..j][j+1..r] = > a[k][0..i-1],a[k][i]
        int &v = f[l][r][k][i];
        rep(j,l,r) setMin(v, f[l][j][k][i-1] + dp[j+1][r][a[k][i]]);
        if(i == sz - 1) setMin(dp[l][r][c[k]], v + 1); // T[i..j] => a[k] => c[k]
      }
    }
    // dp[l][r][c]=min(dp[l][r][k][|a[k]|]) + 1 = min(len > 1(上面算了), len = 1) + 1, len = |a[k]|
    rep(c,0,maxc+1) for(auto [c0, c1]: c2c) setMin(dp[l][r][c0], dp[l][r][c1] + 1); // 26 次 松弛
    rep(k,0,K) setMin(f[l][r][k][0], dp[l][r][a[k][0]]); // 更新 f 中首字母
  }
  int & ans = f[0][nt-1][0][ns-1];
  printf("%d\n", ans == INF? -1: ans);
  return 0;
}


H/Ex - Game on Graph

N点, M边

有向边 [ui,vi,weight i], 无重边 无自环

初始,点v上有个棋子

T和A交替游戏

  • 如果棋子所在点 没有向外路径 则结束游戏
  • 如果有路径,任选一个走路径

T 让weight和尽量小, A让和尽量大

T(结束游戏优先级 > 和尽量小)

A(让游戏无限循环优先级 > 和尽量大)

限制

N 2e5

M 2e5

Wi [0,1e9]

2s

1024mb

题解

我的思路

并不是有环就一定无限, 例如 a->b->c->d->a

a连了个有限的, c也连了个更短的有限的

那么虽然你可以走到b,让对手走到c,这样在走到有限的 会比a直接去到有限的更短

考虑从叶子反过来, 判断是否有限,感觉bfs或者spfa/dij的感觉

题解

图上环状dp

dp[x][0] 从x出发 尽量小

dp[x][1] 从x出发 尽量大

dp[x][0] = min (f[y][1] + weight[x][y]), 相当于 反向图的最短路

dp[x][1] = max (f[y][0] + weight[x][y]), 需要所有f[y][0] 被计算后才有意义

然后就反图+拓扑+dij 就没了???

我感觉这个条件必要, 但总觉得没有证明到充分

代码

https://atcoder.jp/contests/abc261/submissions/33603896

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
ll dp[2][200010];
ll mx[200010]; // 只记录1的, 因为0的直接记录在pq和dp中, 而1的在子节点未完全计算时pq和dp都不会记录
int deg[200010]; // 正向图出度, 反向图入度
vector<pair<int,int> > g[200010]; // 反向图 v = {u, weight}
 
template <typename T> using minPQ = priority_queue<T,vector<T>, greater<T>>; // 小根堆
 
int main(){
  int n = read();
  int m = read();
  int v = read();// 起点
  rep(i,0,2) fill(dp[i],dp[i]+n+1,-1); // 未访问
  rep(i,0,m) {
    int u = read();
    int v = read();
    int w = read();
    g[v].push_back({u, w});
    deg[u] ++;
  }
  minPQ<array<ll,3>> q; // 小根堆, dij 每次找最小的未达点变为可达 {距离, 0/1, 点}
  rep(i,1,n+1) if(deg[i] == 0) rep(j,0,2) q.push({0, j, i}); // dp[0/1][i] 反向入度为0 的节点
  while(q.size()) {
    auto [d, i, u] = q.top(); q.pop();
    if(dp[i][u] != -1) continue; // 计算过
    dp[i][u] = d; // 更新值
    if(!i) { // dp[0][u] -> dp[1][v]
      for(auto [v, w] : g[u]) { // 更新反向边 并更新 deg[v] --
        mx[v] = max(mx[v], d + w); // 更新值但是 不一定进入pq dp[x][1] = max (f[y][0] + weight[x][y])
        if(--deg[v] == 0) q.push({mx[v], 1, v}); // dp[1][v] 只能所有计算都计算后才有意义
      }
    } else for(auto [v, w] : g[u]) q.push({d + w, 0, v}); // dp[1][u] -> dp[0][v] dij
  }
  if(dp[0][v] == -1) printf("INFINITY\n");
  else printf("%lld\n", dp[0][v]);
  return 0;
}

总结

G

大小只有50的情况, 对字符串中的前缀设计状态, 从而有dp的状态

第二就是 小的情况 多次松弛简单也效率满足, 不需要上dij

H/Ex

我感觉这个条件必要, 但总觉得没有证明到充分???

可能关键在于,虽然点上有 0/1两个状态,但实际上这两个状态不相关, 所以其实每个点可以拆点

这样就变成了路径的逆向dp了, 有环一定不行, 所以关键在这个拆点 -> 变成dij

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(SA,后缀数组,单调栈)G(bitmask, 集合论, 图, DP, 子集遍历),H/Ex(DP, 卷积, fft, NTT, 分治NTT)

F - Common Prefixes

题目

https://atcoder.jp/contests/abc213/tasks/abc213_f

给长n字符串S

求其每个位置开始的后缀字符串, 和所有其它后缀字符串的 公共前缀和

范围

n 1e6

3s

1024mb

閱讀全文 »
0%