题目#

2019-icpc-徐州网赛

手速场，都是一些很经典的题目。

重新思考了一下二维偏序究竟是什么。

A. Who is better?#

生硬的套了两个知识点，扩展中国剩余定理和Fibonacci博弈。

套个板子就完事了。

1
def egcd(a, b):
2
    """扩展欧几里得"""
3
    if 0 == b:
4
        return 1, 0, a
5
    x, y, q = egcd(b, a % b)
6
    x, y = y, (x - a // b * y)
7
    return x, y, q
8

9
n = int(input())
10
flag = False
11

12
a1, r1 = map(int, input().split())
13

14
for _ in range(n-1):
15
    a2, r2 = map(int, input().split())
16
    R = r2-r1
17
    x, y, d = egcd(a1, a2)
18
    tmp = a2//d
19
    if R%d != 0:
20
        flag = True
21
    r1=((x*R//d)%tmp+tmp)%tmp*a1+r1
22
    a1=a1*(a2//d)
23

24
lcm = a1
25
ans = (r1%lcm+lcm)%lcm
26

27
if flag:
28
    print("Tankernb!")
29
    exit(0)
30

31
fac = [1, 2]
32
cur = 2
33
while True:
34
    tmp = fac[cur-1] + fac[cur-2]
35
    if tmp > ans:
36
        break
37
    fac.append(tmp)
38
    cur += 1
39

40
flag = False
41
for v in fac:
42
    if v == ans:
43
        flag = True
44
        break
45

46
if flag:
47
    print("Lbnb!")
48
else:
49
    print("Zgxnb!")

E. XKC’s basketball team#

一个比较有趣的题目。

考虑从后往前维护一个单调递增的队列，之所以这样维护是因为：

当 $i < j$ 且 $a[i] < a[j]$ 时 $a[i]$ 是没有任何用处的，因为它又小又靠前，在它前面的那些值如果比 $a[i]$ 小那么肯定也比 $a[j]$ 小，而且 $i < j$ 所以肯定会选择 $j$ 而不是 $i$ 。

然后我们二分单调队列就能得到最先进入队列的满足的那个值的位置，最先进入队列的当然是原序列中最靠后的满足要求的值。

时间复杂度： $O(n \cdot \log n)$

1
#include <bits/stdc++.h>
2
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
3
#define per(i, a, b) for(int i = (a); i >= (b); --i)
4
using namespace std;
5

6
typedef long long ll;
7
const int mod = 1e9+7;
8
const int MAXN = 5e5 + 7;
9

10
int a[MAXN], ans[MAXN];
11
int main(int argc, char const *argv[])
12
{
13
  int n, m;
14
  scanf("%d %d", &n, &m);
15
  rep(i, 1, n)  scanf("%d", &a[i]);
16
  vector<int> v, vp;
17
  v.push_back(a[n]); vp.push_back(n);
18
  ans[n] = -1;
19
  per(i, n-1, 1){
20
    auto it = lower_bound(v.begin(), v.end(), a[i]+m);
21
    if(it == v.end()){
22
      ans[i] = -1;
23
    } else {
24
      int pos = it - v.begin();
25
      pos = vp[pos];
26
      ans[i] = pos - i - 1;
27
    }
28
    if(a[i] > v.back()){
29
      v.push_back(a[i]);
30
      vp.push_back(i);
31
    }
32
  }
33
  rep(i, 1, n)  printf("%d%c", ans[i], i == n?'\n':' ');
34
  return 0;
35
}

I. query#

又是一道二维偏序的问题。

偏序关系是全序关系的子集。

全序关系是指对于一个集合，其中的所有对 $<i, j>$ 都会有这种关系，也就是两两可以比较，比如整数域上的大小关系。

偏序关系是指对于一个集合，其中存在一些（注意：不是所有）对 $<i, j>$ 有这种关系，也就是不需要两两可以比较，比如整数域上的整除关系。

偏序关系有严格偏序和非严格偏序两种，各有自己的三条基本性质。

回到这个问题， $min(p_i, p_j) = \gcd (p_i, p_j)$ 相当于 $p_i, p_j$ 存在整除关系。显然 $n$ 个数的全排列中满足整除关系的对数小于 $n\cdot \log n$ 对。

我们先将所有的满足条件的对数直接暴力筛出来，然后就抽象成了这样一个问题：

给出一些点，查询在区间 $[l, r]$ 内点的数量。

这就是一个经典的二位偏序问题了，直接对一维排序，二维用树状数组维护一下就好了。

时间复杂度： $O(n\cdot \log n)$

1
#include <bits/stdc++.h>
2
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
3
#define per(i, a, b) for(int i = (a); i >= (b); --i)
4
#define debug(x)  cerr << #x << ' ' << x << endl;
5
using namespace std;
6

7
typedef long long ll;
8
const int mod = 1e9+7;
9
const int MAXN = 2e5 + 7;
10

11
int a[MAXN], id[MAXN];
12
struct node{
13
  int l, r, val, id;
14
  friend bool operator <(const node &a, const node &b){
15
    if(a.r == b.r)  return a.l < b.l;
16
    return a.r < b.r;
17
  }
18
}s[MAXN];
19
struct BIT{
20
  int e[MAXN], n;
21
  int lowbit(int x){return x&-x;}
22
  void add(int x, int v){
23
    while(x <= n){
24
      e[x] += v;
25
      x += lowbit(x);
26
    }
27
  }
28
  int get(int x){
29
    int res = 0;
30
    while(x){
31
      res += e[x];
32
      x -= lowbit(x);
33
    }
34
    return res;
35
  }
36
}bit;
37

38
vector<int> v[MAXN];
39
int main(int argc, char const *argv[])
40
{
41
  int n, m;
42
  scanf("%d %d", &n, &m);
43
  rep(i, 1, n){
44
    scanf("%d", &a[i]);
45
    id[a[i]] = i;
46
  }
47
  rep(i, 1, n){
48
    for(int j = 2*a[i]; j <= n; j += a[i]){
49
      if(id[j] < i)  v[i].push_back(id[j]);
50
      else v[id[j]].push_back(i);
51
    }
52
  }
53
  rep(i, 1, m){
54
    scanf("%d %d", &s[i].l, &s[i].r);
55
    s[i].id = i;
56
  }
57
  sort(s + 1, s + 1 + m);
58

59
  bit.n = n;
60
  int cur = 1;
61
  rep(i, 1, n){
62
    rep(j, 0, (int)v[i].size()-1){
63
      bit.add(v[i][j], 1);
64
    }
65
    while(cur <= m && s[cur].r == i){
66
      s[cur].val = bit.get(i) - bit.get(s[cur].l-1);
67
      cur++;
68
    }
69
  }
70
  sort(s + 1, s + 1 + m, [](const node &a, const node &b){return a.id < b.id;});
71

72
  rep(i, 1, m)  printf("%d\n", s[i].val);
73
  return 0;
74
}

J. Random Access Iterator#

感觉这个题目属于很简单的树上递推的题目。

题目的意思就是从树的根结点出发，每次在节点的儿子中随机选择一个，递归，重复子节点个数次。

我们先一次 $DFS$ 更新出来子树的高度和节点的子节点树， $h[x]$ 和 $son[x]$ 。

首先当一个子节点子树的高度加一小于当前节点的高度的时候这个子节点是没用的，因为它更新不到最大值。

而如果可以的话就加上这个子树的递归求出最大值的概率。叶子节点概率为一。

形式化来说就是：

1
function DFS(x)
2
    k <- the number of sons of x
3
    if  k is 0 do
4
        return 1
5
    p <- 0
6
    for son of x do
7
        if h[x] equal to h[son] + 1 do
8
          p += DFS(son)
9
    p <- p divided by k
10
    res <- 1 - pow(1-p, k)
11
    return res

后半段的处理是基于这样一个原因：

假设节点取到最大值的概率为p，那么对于一个节点 $x$ 有：

$p[x] = 1 - (1 - \frac{\sum_{son \in sons[x]}p[son]}{|sons[x]|})^{|sons[x]|}$

就是这样一个公式。

1
#include <bits/stdc++.h>
2
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
3
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
4
#define debug(x) cerr << #x << ' ' << x << endl;
5
using namespace std;
6

7
typedef long long ll;
8
const ll MAXN = 1e6 + 7;
9
const ll mod = 1e9 + 7;
10
ll qpow(ll a, ll b){
11
    ll res = 1;
12
    while(b){
13
        if(b&1) res = 1ll * res * a % mod;
14
        a = 1ll * a * a % mod;
15
        b >>= 1;
16
    }
17
    res = res%mod + mod;
18
    return res%mod;
19
}
20

21
ll inv(ll x){return qpow(x, mod-2);}
22
vector<ll> G[MAXN];
23

24
ll cor[MAXN], son[MAXN];
25

26
void dfs(ll x, ll fa = 0){
27
    ll res = 0;
28
    for(ll p: G[x]){
29
        if(p == fa) continue;
30
        dfs(p, x);
31
        res = max(res, cor[p]);
32
        son[x]++;
33
    }
34
    cor[x] = res + 1;
35
}
36
ll dfs2(ll x, ll fa = 0){
37
    if(son[x] == 0) return 1;
38
    ll p = 0;
39
    for(ll pp: G[x]){
40
        if(pp == fa)    continue;
41
        if(cor[x] == cor[pp] + 1){
42
            p += dfs2(pp, x);
43
        }
44
    }
45
    p = p * inv(son[x]) % mod;
46
    return (1 - qpow(1-p+mod, son[x]) + mod) % mod;
47
}
48
int main() {
49
    ll n;
50
    scanf("%lld", &n);
51
    ll u, v;
52
    rep(i, 1, n-1){
53
        scanf("%lld %lld", &u, &v);
54
        G[u].push_back(v);
55
        G[v].push_back(u);
56
    }
57
    dfs(1);
58
    printf("%lld\n", dfs2(1));
59
    return 0;
60
}