Hello 2019 Solution

A. Gennady and a Card Game

签到.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 char s[5], t[5];
 5 
 6 bool solve()
 7 {
 8     int flag = false;
 9     for (int i = 1; i <= 5; ++i)
10     {
11         scanf("%s", t);
12         if (t[0] == s[0] || t[1] == s[1])
13             flag = true;
14     }
15     return flag;
16 }
17 
18 int main()
19 {
20     while (scanf("%s", s) != EOF) puts(solve() ? "YES" : "NO");
21     return 0;
22 }

View Code

B. Petr and a Combination Lock

二进制枚举

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n, a[20];
 5 bool solve()
 6 {
 7     for (int i = 0; i < (1 << n); ++i)
 8     {
 9         int res = 0;
10         for (int j = 1; j <= n; ++j) 
11         {
12             int vis = (i >> (j - 1)) & 1;
13             res += a[j] * (vis ? 1 : -1);
14         }
15         if (res % 360 == 0) return true;
16     }
17     return false;
18 }
19 
20 int main()
21 {
22     while (scanf("%d", &n) != EOF)
23     {
24         for (int i = 1; i <= n; ++i) scanf("%d", a + i);
25         puts(solve() ? "YES" : "NO");
26     }
27     return 0;
28 }

View Code

C. Yuhao and a Parenthesis

Solved.

题意：

给出n个括号序列，求两两匹配成合法序列的最多对数

思路：

考虑单个括号序列最后一定可以化简成 ))) 或者 ((( 或者)))(((这三种形式

或者本身就是合法的

发现第三种)))(((不可能和别人两两匹配成合法序列

只需考虑))) 和 ((( 的配对以及本身就是合法序列的配对即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 500010
 5 int n;
 6 int l[N], r[N], good;
 7 char s[N];
 8 
 9 int main()
10 {
11     while (scanf("%d", &n) != EOF)
12     {
13         memset(l, 0, sizeof l);
14         memset(r, 0, sizeof r);
15         good = 0;
16         for (int i = 1; i <= n; ++i)
17         {
18             scanf("%s", s + 1);
19             int len = strlen(s + 1);
20             int left = 0, right = 0;
21             for (int i = 1; i <= len; ++i)
22             {
23                 if (s[i] == '(') ++left;
24                 else
25                 {
26                     if (left > 0) --left;
27                     else ++right;
28                 }
29             }
30             if (left > 0 && right > 0) continue;
31             if (left == 0 && right == 0) ++good;
32             else if (left == 0) ++r[right];
33             else ++l[left];
34         }
35         int res = 0;
36         for (int i = 1; i <= 500000; ++i) res += min(l[i], r[i]);
37         res += good / 2;
38         printf("%d
", res);
39     }
40     return 0;
41 }

View Code

D. Makoto and a Blackboard

Upsolved.

题意：

$刚开始黑板上有一个n,我们假定此时在黑板上的数是v$

那么每次可以取$v的一个因数去替换这个数，求最后留下的数的期望$

思路：

我们假定$n一共有p个因数，以及dp[x][j] 表示进行n为x，并且进行j轮的期望$

易得转移方程

$dp[x][j] = frac{sum_{i = 1}^{i = p} dp[y][j - 1]}{p}$

那么很显然的一个递推就出来了，每次枚举n的每个因子，再枚举n的每个因子的每个因子，递推上去

T了，喵喵喵，(觉得个数会很少？

后来发现我们要求的只是 $dp[n][k]$

而且后面那部分的转移其实是可以拆的，拆成若干个因子期望的和/个数再乘起来

那么我们质因子相同的放在一起做

这样就有前缀和性质

假设$n = x_1^{p_1} cdot x_2 ^ {p_2} cdots$

复杂度就是$O(p * k)$ 因为p不会太大

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 10010
 6 #define pli pair <ll, int>
 7 const ll MOD = (ll)1e9 + 7;
 8 ll n; int k;
 9 ll inv[N];
10 
11 vector <pli> getfact(ll n)
12 {
13     vector <pli> res; 
14     for (ll i = 2; i * i <= n; ++i)
15     {
16         int need = 0;
17         while (n % i == 0)
18         {
19             ++need;
20             n /= i;
21         }
22         if (need) res.emplace_back(i, need);
23     }
24     if (n != 1) res.emplace_back(n, 1);
25     return res;
26 }
27 
28 ll f(ll x, ll p)
29 {
30     vector <ll> dp(p + 1, 0);
31     dp[0] = 1;
32     for (int i = 1; i <= p; ++i) 
33         dp[i] = (dp[i - 1] * x) % MOD;
34     for (int rep = 0; rep < k; ++rep)
35     {
36         for (int i = 1; i <= p; ++i) dp[i] = (dp[i - 1] + dp[i]) % MOD;
37         for (int i = 1; i <= p; ++i) dp[i] = (dp[i] * inv[i + 1]) % MOD;
38     }
39     return dp[p]; 
40 }
41 
42 int main()
43 {
44     inv[1] = 1;
45     for (int i = 2; i < N; ++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
46     while (scanf("%lld%d", &n, &k) != EOF)
47     {
48         ll ans = 1;
49         for (auto p : getfact(n))
50             ans = (ans * f(p.first, p.second)) % MOD;
51         printf("%lld
", ans);
52     }
53     return 0;
54 }

View Code

F. Alex and a TV Show

Unsolved.

题意：

$有n个可重集，有四种操作$

$1 ;;x;; v;; 表示将第;x;个集合设为;;{v}$

$2 ;;x ;;y;; z;; 表示将;y;和;z;两个集合并起来赋给 ;;x$

$3 ;;x ;;y ;;z;; 表示将;;y;;和 ;;z;;两个集合求乘积，乘积的定义为;; {gcd(a, b | a in A, ; b in B)} ;;赋给;;x$

$4 ;; x;; v;; 表示询问;;v;;在;;x;;中出现的次数 ;;MOD ;;2$

思路：

对每一个可重集维护$f[i]表示i的倍数出现的次数的奇偶性，用bitset维护$

那么

对于1操作，我们只需要根号暴力就可以了

对于2操作，本来是相加，但是只关心奇偶性的话就是半加就好，即异或

对于3操作，本来是相乘，对应的位运算就是与

对于4操作，反演一下

我们令$F[n] 表示n倍数的出现次数$

那么有$F[n] = sumlimits_{n | d} f[d]$

反演之后便是

$f[n] = sumlimits_{n | d} mu(frac{d}{n}) cdot F[d]$

这里的莫比乌斯函数1和-1没有区别，我们只关心奇偶性

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 100010
 5 #define M 7010
 6 #define D 7000
 7 int n, q, mu[M];
 8 bitset <M> a[M], b[M], s[N];
 9 
10 int main()
11 {
12     for (int i = 1; i <= D; ++i) mu[i] = 1;
13     for (int i = 2; i <= D; ++i) for (int j = i * i; j <= D; j += i * i) mu[j] = 0;
14     for (int i = 1; i <= D; ++i) for (int j = i; j <= D; j += i)
15     {
16         a[j][i] = 1;
17         if (mu[j / i]) b[i][j] = 1;
18     }        
19     while (scanf("%d%d", &n, &q) != EOF)
20     {
21         for (int i = 1; i <= n; ++i) s[i].reset();
22         for (int i = 1, op, x, y, z, v; i <= q; ++i)
23         {
24             scanf("%d%d", &op, &x);
25             if (op == 1 || op == 4)
26             {
27                 scanf("%d", &v);
28                 if (op == 1) s[x] = a[v];
29                 else putchar(((s[x] & b[v]).count() & 1) + '0');
30             }
31             else
32             {
33                 scanf("%d%d", &y, &z);
34                 if (op == 2) s[x] = s[y] ^ s[z];
35                 else s[x] = s[y] & s[z]; 
36             }
37         }
38         putchar('
');
39     }    
40     return 0;
41 }

View Code