Atcoder abc252

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
G(树)Ex(Meet-in-middle)

https://atcoder.jp/contests/abc252/tasks

G - Pre-Order

给一个n点多叉树的前序遍历结果, 问有多少个树满足, mod 998244353

其中子节点多个时, 按子节点数字从小到大遍历

范围

n 500

2s

1024mb

我的思路

当成父子结构时候, 顺序显然

所以感觉主要在兄弟结构

也就是现在 f(序列a)的方案数

f(a) = a[0]为根, a[1]为第一个树的根, a[i]为第二个树的根

f(a) = g(a[1…])

g(a) = sum f(a[0…i-1]) * g(a[i..])

其中a[0] < a[i]

整合一下 g(a) = sum g(a[1…i-1]) * g(a[i..]), a[0] < a[i]

似乎就没了

代码

https://atcoder.jp/contests/abc252/submissions/35211784

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
#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++)
ll read(){ll r;scanf("%lld",&r);return r;}

// g(a) = sum g(a[1...i-1]) * g(a[i..]), `a[0] < a[i]`
int a[510];
mint mem[510][510];
bool vis[510][510];
mint g(int l,int r){ // [l..r] 构成多个兄弟子树
  if(l>=r)return 1;
  mint &v=mem[l][r];
  if(vis[l][r]) return v;
  vis[l][r] = true;
  v = g(l+1,r); // 1个子树
  // [l...i-1] 第一个子树, 后面[i...r]构成多个子树
  rep(i,l+1,r+1) if(a[l] < a[i]) v += g(l+1,i-1)*g(i,r);
  return v;
}

int main(){
  int n = read();
  rep(i,0,n) a[i] = read();
  printf("%d\n",g(1,n-1).val());
  return 0;
}

Ex - K-th beautiful Necklace

n个宝石

第i个颜色Di, 美丽值Vi

一共c个颜色, 每个颜色至少一个

要选C个两两不同颜色的宝石(顺序无关,顺序元素相同看作一种)

美丽值 = 它们的Vi的xor值

在所有有效的方案中对美丽值排序, 求第k大的美丽值

范围

1 <= c <= n <= 70

vi [0,2^60)

k [1,1e18]

2s

1024mb

我的思路

我好像, 连max都不会,怎么求k-th max

如果一个颜色只有一个,那么显然它被选,

显然 总方案数 = 每个颜色的个数 的乘积

问题是70能得到的最大乘积是啥?

2个一组的话

34359738368 = 2^35

125524238436 = 3^22 * 4

1000000000000000000 = 10^18

虽然没k上限那么大,但也不小

然后 还是从max开始考虑

xor + max

感觉只能从高到低贪心

可以容易计算出最高位, 为1的个数和0的个数

考虑为1的来源, 问题是

比如V为2 4和5 3 交叉

那么得到 7 1 1 7, 而并不能就划分成两块

因为 高位1 = 2x5, 4x3

按照高位划分, 会让记录的内容翻倍…

特别是当组不只两个的时候, 要按照高位为1/0 做切分

一个想法就是干脆不切分

直接统计 xor 高位是1和0的个数

如果确定要找的在1里面

再统计高位是10和高位是11的个数

假设在10里面,再100和101的个数

这样下降?

问题是 位多了以后,说是只统计10/11的个数,但在xor过程中依然需要记录01和00的个数

题解

Step1: 估计上限, 跟我上面做得一样 O(3^{N/3})

Step2: meet-in-the-middle

这… 1.3x1e11 叫faily small??????

哦 !!!!! 有道理

尽可能的对半分成 每个只需要O(3^{n/6}) 这样就大概,每个是1e5~1e6 个结果

Step3: 就是上面想的从高到低位做切割了, 这下只有两部分其实就好切割了

代码

https://atcoder.jp/contests/abc252/submissions/35213984

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
#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;)
#define sz(o) ((ll)(o).size())
ll read(){ll r;scanf("%lld",&r);return r;}

int main(){
  int n = read();
  vector<vector<ll> > V(read()); //
  ll K = read();
  rep(i,0,n){
    int c=read()-1; // 0-index
    V[c].push_back(read());
  }
  sort(V.begin(),V.end(),[](const auto&v0,const auto&v1){return sz(v0)>sz(v1);});
  array<vector<ll>,2> P{{ {0},{0} }}; // 尽量分成相等的两组, P 中是每组的xor结果
  rep(i,0,sz(V)){
    int flag=(sz(P[0])>sz(P[1]));
    vector<ll> arr={};
    for(auto v:V[i])for(auto x:P[flag]) arr.push_back(v^x);
    P[flag]=arr;
  }

  ll ans=0;
  vector<array<vector<ll>,2> > A = {{ P[0],P[1] }}; // 每次从高位到低位拆分
  per(B,0,60){
    vector<array<array<vector<ll>,2>,2> > arr={}; // [左侧/右侧][B位为0/1] = {值数组}
    ll cnt=0; // B位为1的个数
    for(auto ab:A){
      array<array<vector<ll>,2>,2> nab = {{ {{ {},{} }},{{ {},{} }} }}; // 按照B位分成 [0] 和 [1] 的两组
      rep(i,0,2)for(ll x:ab[i]) nab[i][(x>>B)&1].push_back(x); // [左侧/右侧][B位为0/1] = {值数组}
      arr.push_back(nab);
      rep(d,0,2)cnt+=sz(nab[0][d])*sz(nab[1][d^1]); // 计算B位乘法后为1的个数
    }
    A={};
    int bit;
    if(cnt<K){ // 高位为0
      K-=cnt;
      bit=0;
    } else {   // 高位为1
      ans+=(ll)1<<B;
      bit=1;
    }
    for(auto &[a,b]:arr)rep(d,0,2)if(sz(a[d]) and sz(b[d^bit]))A.push_back({a[d],b[d^bit]});
  }
  printf("%lld\n",ans);
  return 0;
}

总结

G

没卡黄题

Ex

meet-in-middle , 我都试出了1.3e11 了 却没想到meet-in-middle 真是太菜了

参考

官方题解