Atcoder abc216

發表於 2022-08-01 更新於 2024-10-23 分類於 Atcoder ， ABC 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

#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], 严格单增提供

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

#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;
}

总结

贪心完全不会

题解说有个cow game

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

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

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

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

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

参考

官方题解

LGV引理