跃迁引擎启动

Hello 2019

发表于 更新于 分类于 阅读次数：

Candidate Master！

A Gennady and a Card Game

模拟。

B Petr and a Combination Lock

差点不会 dfs 了。

C Yuhao and a Parenthesis

给 $n$ 个括号序列，两两配对，每个最多出现在一对里面，求最多能匹配上多少对。

将所有括号序列转成 $l$ 个左括号和 $r$ 个右括号。当且仅当，左右括号至少一个为 $0$ 才对答案有贡献，统计每种左右括号个数的出现次数，左右括号相等时才能凑成一对，已经平衡的序列个数除二加到答案里面。

D Makoto and a Blackboard

给出一个数 $n$ 和次数 $k$，每次将这个数随机变成他的一个因子，这个操作恰好执行 $k$ 次，求最后出现的数的期望。

大力猜了一发，只需要求 $n$ 的所有素因子 $p^\alpha$ 的期望 $f_p(\alpha, k)$，全部乘起来即可。

实际上，从每个素因子里面取这个事件之间相互独立，乘积的期望等于期望的乘积。

下面求这个 $n=p^\alpha$ 的期望，有递推式

$$
f_p(\alpha, k) = \frac{1}{\alpha + 1}\sum_{i=0}^\alpha f_p(i, k-1) \
f_p(\alpha, 0) = p^\alpha, f_p(0, k) = 1
$$

推了半天推不出公式，直接记忆化搜索，复杂度不知道。

出题人是不是弹丸粉？

F Alex and a TV Show

维护 $n$ 个多重集合，有 $4$ 种操作：

  1. 第 $x$ 个集合变成 ${v}$；

  2. 第 $x$ 个集合变成第 $y,z$ 两个集合的多重集的并集；

  3. 第 $x$ 个集合变成第 $y,z$ 两个集合的积集元素的 gcd；

  4. 询问第 $x$ 个集合内有多少个 $v$，模 $2$ 输出答案。

分析

询问要求模 $2$，考虑用 bitset 进行维护，如果我们维护的是每个数的出现次数，操作三将难以维护。

转化为维护集合内每个数是多少个数的因子，记集合内有 $a(d)$ 个数含有因子 $d$，$x$ 的出现次数为 $f(x)$，那么

$$
a(d)=\sum_{i=1}^\infty f(id) \
f(n)=\sum_{i=1}^\infty \mu(i) a(in)
$$

下面那个是我抖机灵凑出来的。

因子和询问系数可以预处理得到。

对于操作一，直接将因子集合赋值，操作二等价于按位异或，操作三等价于按位且，操作三等价于用预处理的容斥系数作用在 bitset 上，即按位且后 $1$ 的个数。

对于操作三，单独考虑某一个因子，他对积集的这个因子出现次数的贡献为另一个集合含有这个因子的个数，最终这个因子出现次数就是两个集合内出现次数的乘积。

数论场Orz。

代码

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

char s[10], t[10];

int main(){
    cin >> s;
    for (int i = 0; i < 5; i++) {
        cin >> t;
        if (s[0] == t[0] || s[1] == t[1]) return puts("YES"), 0;
    }
    puts("NO");
    return 0;
}

B

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

int n, a[maxn];

int dfs(int p, int t) {
    if (p > n) return t % 360 == 0;
    if (dfs(p + 1, t + a[p])) return 1;
    if (dfs(p + 1, t - a[p])) return 1;
    return 0;
}

int main(){
    cin >> n; for (int i = 1; i <= n; i++) cin >> a[i];
    if (dfs(1, 0)) puts("YES");
    else puts("NO");
    return 0;
}

C

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <map>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

int n, l[maxn], r[maxn];
char s[maxn * 5];
map<int,int> mp1, mp2;

int main(){
    scanf("%d", &n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        vector<char> st;
        int len = strlen(s), l = 0, r = 0;
        for (int i = 0; i < len; i++) {
            if (s[i] == '(') {
                st.push_back('(');
                r++;
            } else if (s[i] == ')') {
                if (st.size() && st.back() == '(') st.pop_back(), r--;
                else l++;
            }
        } 
        if (l && r) continue;
        if (l) mp2[l]++;
        else if (r) mp1[r]++;
        else ans++;
    }
    ans /= 2;
    for (auto& x: mp1) {
        ans += min(x.second, mp2[x.first]);
    }
    cout << ans;
    return 0;
}

D

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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define assert(x) do{int a=1,b=0;if(!(x))printf("%d",a/b);}while(0)
#ifdef XLor
  #define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
  #define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;

ll qpow(ll x, ll n) {
    ll r = 1;
    while (n) {
        if (n & 1) r = 1ll * r * x % mod;
        n >>= 1; x = 1ll * x * x % mod;
    }
    return r % mod;
}
ll inv(ll x) { return qpow(x, mod - 2); }

ll n, k;

ll f[100][50000];
ll dp(ll p, int a, int k) {
    if (f[a][k] > -1) return f[a][k];
    if (k == 0) return qpow(p, a);
    ll ans = 0;
    for (int i = 0; i <= a; i++) ans = (ans + dp(p, i, k - 1)) % mod;
    // dbg(a, k, ans, inv(a + 1));
    return f[a][k] = ans * inv(a + 1) % mod;
}
ll cal(ll p, int a) {
    for (int i = 0; i <= a; i++) for (int j = 0; j <= k; j++) f[i][j] = -1;
    return dp(p, a, k);
}

int main(){
    cin >> n >> k;
    ll ans = 1;
    for (ll i = 2; 1ll * i * i <= n; i++) {
        if (n % i) continue;
        int cnt = 0;
        while (n % i == 0) cnt++, n /= i;
        ll x = cal(i, cnt);
        ans = ans * x % mod;
        // dbg(x);
        // ans = ans * cal(i, cnt) % mod;
        // dbg(i, cnt, cal(i, cnt));
    }
    if (n > 1) ans = ans * cal(n, 1) % mod;
    // dbg(n, cal(n, 1));
    cout << ans;
    return 0;
}

F

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 100000 + 5;
const int maxv = 7000 + 10;

bitset<maxv> fac[maxv], mul[maxv], a[maxn];
int n, q;
int mu[maxv];

int main(){
    for (int i = 1; i < maxv; i++) mu[i] = 1;
    for (int i = 1; i < maxv; i++) {
        for (int j = 2; j * j <= i; j++) {
            if (i % (j * j)) continue;
            mu[i] = 0; break;
        }
    }
    for (int i = 1; i < maxv; i++) {
        for (int j = 1; j <= i; j++) {
            if (i % j) continue;
            fac[i][j] = 1;
            mul[j][i] = mu[i / j];
        }
    }

    scanf("%d%d", &n, &q);
    int op, x, y, z;
    while (q--) {
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) {
            a[x] = fac[y];
        } else if (op == 2) {
            scanf("%d", &z);
            a[x] = a[y] ^ a[z];
        } else if (op == 3) {
            scanf("%d", &z);
            a[x] = a[y] & a[z];
        } else if (op == 4) {
            printf("%d", (a[x] & mul[y]).count() % 2);
        }
    }
    return 0;
}
  • 本文作者： XLor
  • 本文链接： https://xlor.cn/2019/1/h2019/
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！