牛客国庆集训派对Day2 Solution

分类: IT文章 • 2025-01-09 08:34:03

A 矩阵乘法

思路：

1° 牛客机器太快了，暴力能过。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 5000
 5 
 6 int n, p, m;
 7 int a[N][100], b[100][N], ans[N][N];
 8 
 9 void Run() 
10 {
11     while (scanf("%d%d%d", &n, &p, &m) != EOF)
12     {
13         for (int i = 1; i <= n; ++i)
14             for (int j = 1; j <= p; ++j)
15                 scanf("%X", &a[i][j]);
16         for (int j = 1; j <= m; ++j)
17             for (int i = 1; i <= p; ++i)
18                 scanf("%1d", &b[i][j]);
19         for (int i = 1; i <= n; ++i)
20             for (int j = 1; j <= m; ++j)
21                 for (int k = 1; k <= p; ++k)
22                     ans[i][j] += a[i][k] * b[k][j];
23         int res = 0;
24         for (int i = 1; i <= n; ++i)
25             for (int j = 1; j <= m; ++j)
26                 res ^= ans[i][j];
27         printf("%d
", res);
28     }
29 }
30 
31 int main()
32 {
33     #ifdef LOCAL
34         freopen("Test.in", "r", stdin);
35     #endif
36     
37     Run();
38     return 0; 
39 }

View Code

2°

考虑到p很小，可以将它分块，比如说分成8Bit一块，那么对应的只有256种情况，可以预处理一下，然后乘法变成取值

复杂度大概在(4096 * 4096 * 8) 左右

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 5000
 5 
 6 int n, p, m;
 7 int a[N][100], b[100][N], ap[N][10][256], bp[10][N], ans[N][N];
 8 
 9 void Run() 
10 {
11     while (scanf("%d%d%d", &n, &p, &m) != EOF)
12     {
13         for (int i = 0; i < n; ++i)
14             for (int j = 0; j < p; ++j)
15                 scanf("%X", &a[i][j]);
16         for (int j = 0; j < m; ++j)
17             for (int i = 0; i < p; ++i)
18                 scanf("%1d", &b[i][j]);  
19         p = (p - 1) / 8 + 1;
20         for (int i = 0; i < n; ++i)
21             for (int j = 0; j < p; ++j)
22                 for (int k = 0; k < 256; ++k) 
23                     for (int l = 0; l < 8; ++l)
24                         if (k & (1 << l)) ap[i][j][k] += a[i][j * 8 + l];
25         for (int j = 0; j < m; ++j)
26             for (int i = p - 1; i >= 0; --i)
27                 for (int k = 7; k >= 0; --k)
28                     bp[i][j] = bp[i][j] * 2 + b[k + 8 * i][j];
29         for (int i = 0; i < n; ++i) 
30             for (int j = 0; j < m; ++j)
31                 for (int k = 0; k < p; ++k)  
32                     ans[i][j] += ap[i][k][bp[k][j]]; 
33         int res = 0;
34         for (int i = 0; i < n; ++i)
35             for (int j = 0; j < m; ++j)
36                 res ^= ans[i][j];
37         printf("%d
", res);
38     }
39 }
40 
41 int main()
42 {
43     #ifdef LOCAL
44         freopen("Test.in", "r", stdin);
45     #endif
46     
47     Run();
48     return 0; 
49 }

View Code

B 字符串的幂

留坑。

C 生命游戏

留坑。

D 数格点

留坑。

E 数据排序

留坑。

F 平衡二叉树

思路：显然，答案最大肯定是根节点下左子树是满二叉树，右子树是最小平衡二叉树

深度为n的二叉平衡树的最小节点数 = 左平衡树的最小节点数 + 右平衡树的最小结点树 + 当前树的根节点树（1）

显然，右平衡树的高度可以比左平衡树少d

当$n <= d$ 的时候 $F[n] = max(n, 0)$

所以$F[n] = F[n - 1] + F[n - d - 1] +1$

满二叉树的结点个数是$2^n$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 using ll = long long;
 4 
 5 int n, d;
 6 ll f[100];
 7 
 8 ll qpow(ll base, ll n)
 9 {
10     ll res = 1;
11     while (n)
12     {
13         if (n & 1) res *= base;
14         base *= base;
15         n >>= 1;
16     }
17     return res;
18 }
19 
20 ll work(int h)
21 {
22     if (h <= d)
23         return max(h, 0);
24     if (f[h]) return f[h];
25     f[h] = work(h - 1) + work(h - d - 1) + 1;
26     return f[h]; 
27 }
28 
29 void Run() 
30 {
31     while (scanf("%d%d", &n, &d) != EOF)
32     {
33         memset(f, 0, sizeof f);
34         printf("%lld
", qpow(2ll, n - 1) - work(n - d - 1) - 1);
35     }
36 }
37 
38 int main()
39 {
40     #ifdef LOCAL
41         freopen("Test.in", "r", stdin);
42     #endif
43     
44     Run();
45     return 0; 
46 }

View Code

G 数组合并

留坑。

H 卡牌游戏

思路：考虑抽到一张卡片的概率是$frac{m}{n}$ 那么期望就是 $frac{n}{m}$ 抽到一张之后再抽一张的概率是$frac{m - 1}{n - 1}$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 int t, n, m, k;
 5  
 6 int main()
 7 {
 8     scanf("%d", &t);
 9     for (int kase = 1; kase <= t; ++kase)
10     {
11         scanf("%d%d%d", &n, &m, &k);
12         double res = 0;
13         for (int i = 1; i <= k; ++i, --n, --m)
14             res += n * 1.0 / m;
15         printf("Case #%d: %.10f
", kase, res);
16     }
17     return 0;
18 }

View Code

I 游戏

留坑。

J 魔法阵

留坑。

K 排队

留坑。

牛客国庆集训派对Day2 Solution

相关推荐