牛客国庆集训派对Day4 Solution

时间：2022-11-13 20:28:22

A    深度学习

puts(n)

 #include <bits/stdc++.h>

 using namespace std;

 int main()

 {

     double n;

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

         printf("%.10f\n", n);

     return ;

 }

B    异或求和

思路：  有一个$O(nlogn^2)$ 的做法，但是T了。

设$bit(x, i)$为 x在二进制下第i位为1还是0

考虑 $\sum_{1 <= i < j < k <= n}(a_i \oplus a_j)(a_j \oplus a_k)(a_i \oplus a_k)$

将最后一部分的 $(a_i \oplus a_k)$ 拆分成 $\sum_{l = 0}^{l = 29}(bit(a_i, l))(bit(a_k, l))$

那么我们再枚举j  就可以

T了的代码：

#include <bits/stdc++.h>

using namespace std;

#define N 100010

#define ll long long

ll MOD = (ll);

int n;

int arr[N], prefix[][][][], suffix[][][][]; 

void Run()

{

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

    {

        for (int i = ; i <= n; ++i) scanf("%d", arr + i);

        bitset <> b;

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

        {

            b = arr[i];

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

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

                    ++suffix[j][b[j]][k][b[k]];

        }

        b = arr[];

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

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

                ++prefix[j][b[j]][k][b[k]];

        ll ans = ;

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

        {

            b = arr[i];

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

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

                    --suffix[j][b[j]][k][b[k]];

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

            {

                ll l = , r = ;

                // enum 0 1

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

                {

                    l = (l + ((1ll << k) * prefix[j][][k][b[k] ^ ]) % MOD) % MOD;

                    r = (r + ((1ll << k) * suffix[j][][k][b[k] ^ ]) % MOD) % MOD;

                }

                ans = (ans + (1ll << j) * l % MOD * r % MOD) % MOD;

                l = , r = ;

                // enum 1 0

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

                {

                    l = (l + ((1ll << k) * prefix[j][][k][b[k] ^ ]) % MOD) % MOD;

                    r = (r + ((1ll << k) * suffix[j][][k][b[k] ^ ]) % MOD) % MOD;

                }

                ans = (ans + (1ll << j) * l % MOD * r % MOD) % MOD;

            }

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

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

                    ++prefix[j][b[j]][k][b[k]];

        }

        printf("%lld\n", ans);

    }

}

int main()

{

    #ifdef LOCAL

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

    #endif

    Run();

    return ;

}

C    异或计数

留坑。

D    最小生成树

思路：用最小的点权去连边

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 #define ll long long

 int n;

 int main()

 {

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

     {

         ll res = , num, Min = 0x3f3f3f3f3f3f3f3f;

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

         {

             scanf("%lld\n", &num);

             Min = min(Min, num);

             res += num;

         }

         printf("%lld\n", res + Min * (n - ));

     }

     return ;

 }

E    乒乓球

留坑。

F    导数卷积

留坑。

G    区间权值

显然可以发现长度为l和n-l的权值相同，然后枚举每个长度l，发现出现次数为两端向中间增加，然后中间不变，最后O(n)扫一遍即可

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = (int)3e5 + ;

 const ll MOD = 1e9 + ;

 int n;

 ll ans;

 ll w[maxn];

 ll val[maxn];

 int main()

 {

     while(~scanf("%d", &n))

     {

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

         {

             scanf("%lld", val + i);

         }

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

         {

             scanf("%lld", w + i);

         }

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

         {

             val[i] += val[i - ];

             val[i] %= MOD;

         }

         ans = ;

         ll tmp = ;

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

         {

             tmp += (val[n - i + ] - val[i - ] + MOD) % MOD;

             tmp %= MOD;

             ans += (tmp * w[i] % MOD + tmp * w[n - i + ] % MOD) % MOD;

             ans %= MOD;

         }

         if(n & )

         {

             tmp += val[(n + ) / ] - val[n / ];

             tmp %= MOD;

             ans += tmp * w[(n + ) / ] % MOD;

             ans %= MOD;

         }

         printf("%lld\n", ans);

     }

     return ;

 }

H    树链博弈

思路：每层上都有偶数个黑点，后手必胜，否则，先手必胜

假设所有点都是白点，是先手必败态

如果先手必胜，那么走一步，走到先手必败态

如果是先手必败态，走一步，可以走到先手必胜态

 #include <bits/stdc++.h>

 using namespace std;

 #define N 1010

 int n;

 int color[N], deep[N];

 vector <int> G[N];

 void DFS(int u, int fa, int deepth)

 {

     deep[deepth] += color[u];

     for (auto v : G[u])

     {

         if (v == fa) continue;

         DFS(v, u, deepth + );

     }

 }

 void Run()

 {

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

     {

         for (int i = ; i <= n; ++i) scanf("%d", color + i);

         for (int i = , u, v; i < n; ++i)

         {

             scanf("%d%d", &u, &v);

             G[u].push_back(v);

             G[v].push_back(u);

         }

         DFS(, , );

         int res = ;

         for (int i = ; i < n; ++i) if (deep[i] & ) res = ;

         puts(res ? "First" : "Second");

     }

 }

 int main()

 {

     #ifdef LOCAL

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

     #endif

     Run();

     return ;

 }

I    连通块计数

分两种情况考虑，一种是含根，一种是不含根，分别计数

 #include <bits/stdc++.h>

 using namespace std;

 int main() {

     long long ans, t ,x, i, n, MOD;

     scanf("%lld\n",&n);

     MOD = ;

     ans = ; t = ;

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

         scanf("%lld\n",&x);

         ans = (ans + (x * x + x) / ) % MOD;

         t = (t * (x + )) % MOD;

     }

     ans = (ans + t) % MOD;

     printf("%lld\n",ans);

     return ;

 }

J    寻找复读机

按题意模拟即可

 #include <bits/stdc++.h>

 using namespace std;

 #define N 1010

 int n, m;

 int used[N], vis[N];

 vector <int> ans;

 char s[N][];

 int main()

 {

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

     {

         memset(vis, , sizeof vis);

         memset(used, , sizeof used);

         ans.clear();

         for (int i = , x; i <= m; ++i)

         {

             scanf("%d %s", &x, s[i]);

             if (i == ) vis[x] = ;

             else if (strcmp(s[i], s[i - ]) != ) vis[x] = ;

             used[x] = ;

         }

         for (int i = ; i <= n; ++i) if (!vis[i])

             ans.push_back(i);

         if (!ans.size()) puts("");

         for (int i = , len = ans.size(); i < len; ++i) printf("%d%c", ans[i], " \n"[i == len - ]);

     }

     return ;

 }

相关文章