牛客国庆集训派对Day2 Solution

时间：2020-12-19 14:56:05

A    矩阵乘法

思路：

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

 #include <bits/stdc++.h>

 using namespace std;

 #define N 5000

 int n, p, m;

 int a[N][], b[][N], ans[N][N];

 void Run()

 {

     while (scanf("%d%d%d", &n, &p, &m) != EOF)

     {

         for (int i = ; i <= n; ++i)

             for (int j = ; j <= p; ++j)

                 scanf("%X", &a[i][j]);

         for (int j = ; j <= m; ++j)

             for (int i = ; i <= p; ++i)

                 scanf("%1d", &b[i][j]);

         for (int i = ; i <= n; ++i)

             for (int j = ; j <= m; ++j)

                 for (int k = ; k <= p; ++k)

                     ans[i][j] += a[i][k] * b[k][j];

         int res = ;

         for (int i = ; i <= n; ++i)

             for (int j = ; j <= m; ++j)

                 res ^= ans[i][j];

         printf("%d\n", res);

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif

     Run();

     return ;

 }

2°

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

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

 #include <bits/stdc++.h>

 using namespace std;

 #define N 5000

 int n, p, m;

 int a[N][], b[][N], ap[N][][], bp[][N], ans[N][N];

 void Run()

 {

     while (scanf("%d%d%d", &n, &p, &m) != EOF)

     {

         for (int i = ; i < n; ++i)

             for (int j = ; j < p; ++j)

                 scanf("%X", &a[i][j]);

         for (int j = ; j < m; ++j)

             for (int i = ; i < p; ++i)

                 scanf("%1d", &b[i][j]);

         p = (p - ) /  + ;

         for (int i = ; i < n; ++i)

             for (int j = ; j < p; ++j)

                 for (int k = ; k < ; ++k)

                     for (int l = ; l < ; ++l)

                         if (k & ( << l)) ap[i][j][k] += a[i][j *  + l];

         for (int j = ; j < m; ++j)

             for (int i = p - ; i >= ; --i)

                 for (int k = ; k >= ; --k)

                     bp[i][j] = bp[i][j] *  + b[k +  * i][j];

         for (int i = ; i < n; ++i)

             for (int j = ; j < m; ++j)

                 for (int k = ; k < p; ++k)

                     ans[i][j] += ap[i][k][bp[k][j]];

         int res = ;

         for (int i = ; i < n; ++i)

             for (int j = ; j < m; ++j)

                 res ^= ans[i][j];

         printf("%d\n", res);

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif

     Run();

     return ;

 }

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$

 #include <bits/stdc++.h>

 using namespace std;

 using ll = long long;

 int n, d;

 ll f[];

 ll qpow(ll base, ll n)

 {

     ll res = ;

     while (n)

     {

         if (n & ) res *= base;

         base *= base;

         n >>= ;

     }

     return res;

 }

 ll work(int h)

 {

     if (h <= d)

         return max(h, );

     if (f[h]) return f[h];

     f[h] = work(h - ) + work(h - d - ) + ;

     return f[h];

 }

 void Run()

 {

     while (scanf("%d%d", &n, &d) != EOF)

     {

         memset(f, , sizeof f);

         printf("%lld\n", qpow(2ll, n - ) - work(n - d - ) - );

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif

     Run();

     return ;

 }

G    数组合并

留坑。

H    卡牌游戏

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

 #include <bits/stdc++.h>

 using namespace std;

 int t, n, m, k;

 int main()

 {

     scanf("%d", &t);

     for (int kase = ; kase <= t; ++kase)

     {

         scanf("%d%d%d", &n, &m, &k);

         double res = ;

         for (int i = ; i <= k; ++i, --n, --m)

             res += n * 1.0 / m;

         printf("Case #%d: %.10f\n", kase, res);

     }

     return ;

 }

I    游戏

留坑。

J    魔法阵

留坑。

K    排队

留坑。

相关文章