Codeforces Round 875

發表於 2023-05-29 更新於 2024-04-11 分類於 Codeforces ， Div1 Disqus：文章字數： 2.6k 所需閱讀時間 ≈ 9 分鐘

B(数学,暴力)C(xor hash,Catalan number)D(数学,树,DP,重轻链)

https://codeforces.com/contest/1830

B - The BOSS Can Count Pairs

长度n数组 a,b

计算多少对 i < j 满足 ai * aj = bi + bj

t 1e4

sum n 2e5

ai,bi [1,n]

512mb

我的思路

加的范围保证了 <= 2n

所以对于同样的a 直接整合

然后 2n (1+1/2+1/3+…), 所以真的枚举的乘法对是满足范围的

然后对于具体的 v0=ai,v1=aj

那么对应 bi/bj 是两个集合, 或者map[b]=count

每次选小的去大的里面搜, 这复杂度不知道多少, 过了pretest,被hack tle了

https://codeforces.com/contest/1830/submission/207625447

题解

一样的，范围 <= 2n

所以 min(ai,aj) <= sqrt(2n)

也是fr[ai][bi] = 出现次数

对于 ai=aj 没啥难的, 我也实现了

对于 ai != aj, 考虑 ai >= aj, aj <= sqrt(2n)

$\displaystyle \sum_{i=1}^n \sum_{a_j=1}^{\min(a_i-1,\frac{2\cdot n}{a_i})} fr[a_j] [ a_i \cdot a_j-b_i ]$

注意到 $\min(a_i-1,\frac{2n}{a_i}) \le \sqrt{2n}$

所以时间复杂度为 $O(n\sqrt{n})$

C - The BOSS Can Count Pairs

长度n括号合法序列

k个限制

每个限制是 [li..ri]也是合法括号序列

问方案数 mod 998244353

n 3e5

我的思路

首先经典括号序列就是 +1/-1, 合法就是前缀和处处非负，区间为0

对于两个不相关的区间则互相不影响

如果两个区间相交，因为两个的中间都大于等于两端，所以直接切割成3段

1
2

xxxx
  yyyy

如果两个区间包裹，则相当于抛开中间的那部分,剩余长度

1 2	xxxxxxxx yyyy

然后就是所有切出来的长度的方案的prod

方案数 = 卡特兰[len/2]

问题到了如何切割，

我尝试了半天不知道有什么快速的O(n)?的方法

想出来的方法要么是不知道复杂度的，要么是没正确性证明的

想了 in/out扫描线, 想了 set/map 维护出入, 想了并查集，没想出具体怎么实现

题解

首先也是卡特兰数

然后也是 +1/-1转换

然后如果 s[下标顺序集合] 一定是合法括号序列，则称它为一个group

情况一: 就是上面我说的包裹的情况 $l_1\le l_2\le r_2\le r_1$

$[l_2,r_2]$

$[l_1,l_2-1] \cup [r_2+1,r_1]$

情况二: 就是上面我说的相交的情况 $l_1 \lt l_2 \le r_1 \lt r_2$

$[l_1,l_2-1]$

$[l_2,r_2]$

$[r_2+1,r_1]$

而上面的这种操作，可以得到 “被同样组区间覆盖的”属于同一个group

然后就是 xor hash了

代码

https://codeforces.com/contest/1830/submission/207689079

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 998244353

namespace CMM{
  const int _mod = 998244353;
  class modint{
    private:
      long long _v;
    public:
      modint() :_v(0) {  }
      modint(long long _a) {
        _v = (_a < 0)? _mod - ((-_a) % _mod) : (_a % _mod);
      }

      int val()const { return _v; }
      modint operator+()const { return *this; }
      modint operator-()const { return { _mod - _v }; }
      modint operator+(const modint& rhs) const { return modint(*this) += rhs; }
      modint operator-(const modint& rhs) const { return modint(*this) -= rhs; }
      modint operator*(const modint& rhs) const { return modint(*this) *= rhs; }
      modint operator/(const modint& rhs) const { return modint(*this) /= rhs; }

      bool operator==(const modint& rhs)const { return _v == rhs._v; }
      bool operator!=(const modint& rhs)const { return _v != rhs._v; }
      bool operator> (const modint& rhs)const { return _v >  rhs._v; }
      bool operator>=(const modint& rhs)const { return _v >= rhs._v; }
      bool operator<=(const modint& rhs)const { return _v <= rhs._v; }
      bool operator< (const modint& rhs)const { return _v <  rhs._v; }

      modint& operator+=(const modint& rhs) {
        (_v += rhs._v) %= _mod;
        return *this;
      }
      modint& operator-=(const modint& rhs) {
        (_v += _mod - rhs._v) %= _mod;
        return *this;
      }
      modint& operator*=(const modint& rhs) {
        _v = _v * rhs.val() % _mod;
        return *this;
      }
      modint& operator/=(const modint& rhs) { // 费马小定理
        _v = _v * rhs.inv().val() % _mod ;
        return *this;
      }
      modint pow(long long pwr) const {
        long long res(1);
        long long _b(_v);
        while (pwr) {
          if (pwr & 1) (res *= _b) %= _mod;
          (_b *= _b) %= _mod;
          pwr /= 2;
        }
        return res;
      }
      modint inv() const {
        assert(_v != 0);
        return pow(_mod - 2);
      }
  };
};

// ---------

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

using mint=CMM::modint;
const int N=300000;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> rnd(0,LLONG_MAX);

mint fac[2*N+10]={1};
mint ifac[2*N+10];
mint cat2[2*N+10]; // cat2[len] = catalan[len/2], cat2[2k+1]=0
void w(){
  int n = read(); // 3e5
  int k = read();
  vector<ll> h(n+1,0);
  auto add=[&](int l,int r){
    ll Hash = rnd(gen);
    h[l-1] ^= Hash;
    h[r] ^= Hash;
  };
  add(1,n); /// the initial string must be an RBS
  rep(i,0,k){
    ll l=read();
    ll r=read();
    add(l,r); // 0-index
  }
  rep(i,1,n) h[i]^=h[i-1]; // prefix => value
  h.pop_back(); // 去掉结束
  sort(begin(h),end(h));
  mint ans=1;
  int prei=0;
  rep(i,0,n) if(i+1==n || h[i+1] != h[prei]){
    ans=ans*cat2[i+1-prei];
    prei = i+1;
  }
  printf("%d\n",ans.val());
}

int main(){
  rep(i,1,2*N+1) fac[i]=fac[i-1]*i;
  ifac[2*N]=fac[2*N].inv();
  per(i,0,2*N) ifac[i]=ifac[i+1]*(i+1);
  rep(i,0,N+1) cat2[i*2] = fac[2*i]*ifac[i]*ifac[i+1];
  int t = read();
  while(t--) w();
  return 0;
}

D - Mex Tree

给定n点树，需要上色 0/1

path的value= mex(路径上颜色)

value(树) = sum value(所有path(u<=v))

求最大的 value(树)

n 2e5

256mb

我的思路

上色只能上0/1

所以mex(0)=1,mex(0,1)=2,mex(1)=0

所以如果让树上黑白间隔，那么所有长度(点数)>=2的路径value都是2

而选定根是黑或白则其它颜色都定了

则ans = 2(长度>=2路径数) + (=0的点数)

问题是，这就是最大值吗?

显然有反例

1	n个点-a-b-n点

如果a-b都染色1, 左右其它都是0, 则对于1个点有2n贡献, 对于长度为2,只有a-b 贡献是0,其它贡献都是2, 对于长度>=2贡献都是2

而a-b 不同染色，一个点的贡献是n+1,对于长度为2所有贡献都是2,对于长度>=2所有贡献都是2

所以n足够大时，显然上面的 (2n)+(0) >= (n+1)+(2)

树上dp

dp[u]= 从u向下的路径 {纯1的条数,纯0的条数，10都有的条数, 已经有的贡献最大值}

而注意到纯1和纯0与u的取值有关，u有取值后，另一个则为0

dp[u][u是0/1] = 从u向下的路径 {纯u的条数, 10都有的条数, 已经有的贡献最大值}

又注意到 10都有的情况,因为后面不论怎么连都是贡献2了，可以直接计算剩余贡献了

dp[u][u是0/1] = 从u向下的路径 {纯u的条数, 已经有的贡献最大值}

然而这看上去是 O(n^2) 的

题解

也是先想的黑白间隔/二分，因为这样的总价值为 2(n(n+1)/2) - O(n)

假设有大小为k的同色连通分量，注意到会让价值下降 $O(k^2)$

而注意到直接的黑白间隔下降不超过$O(n)$,因此同色连通最大不超过$O(\sqrt{n})$

也是dp,和我的dp不能说相似，只能说一模一样dp[i][j][color]= 子树i,同色联通大小为j,颜色为color

时间复杂度O(n\sqrt{n})

然后这里还卡了一下空间复杂度，希望是线性空间复杂度

void dfs(u){
  初始化state[u], 大小为 1
  for(v:e[u]){
    dfs(v);
    merge(state[v] to state[u])
  }
}

代码

https://codeforces.com/contest/1830/submission/207692852

#include <bits/stdc++.h>
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);)
// 只接受v=0/1
#define mex(v) (v^1)

ll read(){ll r;scanf("%lld",&r);return r;}
auto chmin=[](auto&a,const auto&b){a=min(a,b);};

const int lim = 893;// sqrt(2e5)
const ll INF = 0x3f3f3f3f'3f3f3f3f;

void w(){
  ll n=read();
  vector<vector<int>> e(n + 1);
  vector<int> sz(n + 1);
  rep(i,1,n){
    int u=read();
    int v=read();
    e[u].push_back(v);
    e[v].push_back(u);
  }

  auto dfs0 = [&](auto self, int u, int fa) -> void { // 重儿子放在最前面
    rep(i,0,size(e[u])) if (e[u][i] == fa) { // remove parent
      swap(e[u][i],e[u].back());
      e[u].pop_back();
      break;
    }
    sz[u] = 1;
    rep(i,0,size(e[u])) {
      int &v=e[u][i];
      self(self,v,u);
      sz[u] += sz[v];
      if(sz[v] > sz[e[u][0]]) swap(v,e[u][0]);
    }
  };
  dfs0(dfs0,1, 0);
  auto _=[&](int siz){return min(siz,lim);}; // bound

  auto dfs = [&](auto self, int u) -> array<vector<ll>,2> {
    array<vector<ll>,2> dp; // 逆贡献尽量小 dp[color][同色连通块大小] = 逆贡献
    rep(c,0,2) dp[c].resize(1 + 1, INF); // care MLE
    rep(c,0,2) dp[c][1] = 2-mex(c);
    sz[u] = 1; // 重用
    for (auto v: e[u]) {
      auto dpv = self(self, v);
      array<vector<ll>, 2> ndp;
      rep(c,0,2) ndp[c].resize(_(sz[u])+_(sz[v])+1,INF);
      rep(i,1,_(sz[u])+1) rep(j,1,_(sz[v])+1) rep(c,0,2) {
        chmin(ndp[c][i  ] , dp[c][i] + dpv[c^1][j]);                 // u-v 不同色
        chmin(ndp[c][i+j] , dp[c][i] + dpv[c][j] + i*j*(2-mex(c)) ); // u-v 同色
      }
      sz[u] += sz[v];
      rep(c,0,2) {
        dp[c].resize(_(sz[u])+1, INF);
        rep(i,1,_(sz[u])+1) dp[c][i] = ndp[c][i];
      }
    }
    return dp;
  };
  auto dp = dfs(dfs, 1);
  ll ans = INF;
  rep(i,1,_(sz[1])+1) rep(c,0,2) ans = min({ans, dp[c][i]});
  printf("%lld\n", n * (n + 1) - ans);
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

F - The Third Grace

n个区间,m个点(初始都未激活),有价值pi

f(区间) = 改区间中下标最大的已经激活的点pi

问对于所有激活方案，求 max sum f(所有区间)

n 1e6

m 1e6

pi [0,1e9]

1024mb

我的思路

dp[i] = 激活i点以及某些i右侧点的最大代价

dp[i] = max(dp[j] + cnt( l <= i and i <= r < j ) * p[i])

O(n^2) 显然tle

题解

TODO

总结

注意到 $\le 2n$, 但是没有多次运用, 问题在这个合并并没有“降低多少复杂度”，甚至是不会算的复杂度

这里通过大于反过来$\min(x,\frac{?}{x})$是这里我自己完全没想到的关键一步,之前应该没见过这种技巧, 学了一手

哎div2里都有288人做出来了，自闭

首先这些基础的几点(catlan,交叉,包裹,ans=prod catlan[len/2])全部想到了，但是没有变成group的感觉，从而没有“被同样组区间覆盖的”属于同一个group的这个结论

xor hash，这个应该是之前学过且仅学过一次

感觉这里区间切割成更小的区间，可能就和 group 和 xor hash 关系应该更密切,应该建立想法联系

想到了二分，也想到了dp,

但是这个分析变化和同色连通块的步骤，完全没想到，从而没有利用二分去限制dp中参数的大小

另外一个点，就是 和根同色的路径数 = 和根同色的连通块点数 这个等式也没想到

最后就是空间限制，(Heavy-light Decomposition)不仅在一些题目中能解决时间问题，在这里还可以优化空间使用

参考

官方题解

codeforces blog 7:complexity of certain tree DPs

codeforces blog Using HLD to reduce memory