牛客国庆集训派对Day4 Solution

A 深度学习

puts(n)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 int main()
 5 {
 6     double n;
 7     while (scanf("%lf", &n) != EOF)
 8         printf("%.10f
", n);
 9     return 0;
10 }

View Code

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)998244353;

int n;
int arr[N], prefix[30][2][30][2], suffix[30][2][30][2]; 
 
void Run()
{
    while (scanf("%d", &n) != EOF) 
    {
        for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
        bitset <30> b; 
        for (int i = 2; i <= n; ++i) 
        {
            b = arr[i];
            for (int j = 29; j >= 0; --j)
                for (int k = 29; k >= 0; --k)
                    ++suffix[j][b[j]][k][b[k]]; 
        }
        b = arr[1]; 
        for (int j = 29; j >= 0; --j)
            for (int k = 29; k >= 0; --k)
                ++prefix[j][b[j]][k][b[k]];
        ll ans = 0;
        for (int i = 2; i < n; ++i)
        {
            b = arr[i];
            for (int j = 29; j >= 0; --j)
                for (int k = 29; k >= 0; --k)
                    --suffix[j][b[j]][k][b[k]]; 
            for (int j = 29; j >= 0; --j) 
            {
                ll l = 0, r = 0;
                // enum 0 1
                for (int k = 29; k >= 0; --k)
                {
                    
                    l = (l + ((1ll << k) * prefix[j][0][k][b[k] ^ 1]) % MOD) % MOD;
                    r = (r + ((1ll << k) * suffix[j][1][k][b[k] ^ 1]) % MOD) % MOD;
                }
                ans = (ans + (1ll << j) * l % MOD * r % MOD) % MOD;
                l = 0, r = 0;
                // enum 1 0 
                for (int k = 29; k >= 0; --k)
                {
                    l = (l + ((1ll << k) * prefix[j][1][k][b[k] ^ 1]) % MOD) % MOD;
                    r = (r + ((1ll << k) * suffix[j][0][k][b[k] ^ 1]) % MOD) % MOD;
                }
                ans = (ans + (1ll << j) * l % MOD * r % MOD) % MOD; 
            }
            for (int j = 29; j >= 0; --j) 
                for (int k = 29; k >= 0; --k) 
                    ++prefix[j][b[j]][k][b[k]]; 
        }
        printf("%lld
", ans);
    }
}

int main()
{
    #ifdef LOCAL
        freopen("Test.in", "r", stdin);
    #endif

    Run();
    return 0;
}

View Code

C 异或计数

留坑。

D 最小生成树

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

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 #define N 100010
 5 #define ll long long
 6  
 7 int n;
 8  
 9 int main()
10 {
11     while (scanf("%d", &n) != EOF)
12     {
13         ll res = 0, num, Min = 0x3f3f3f3f3f3f3f3f;
14         for (int i = 1; i <= n; ++i)
15         {
16             scanf("%lld
", &num);
17             Min = min(Min, num);
18             res += num;
19         }
20         printf("%lld
", res + Min * (n - 2));
21     }
22     return 0;
23 }

View Code

E 乒乓球

留坑。

F 导数卷积

留坑。

G 区间权值

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

 1 #include<bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 typedef long long ll;
 6  
 7 const int maxn = (int)3e5 + 10;
 8 const ll MOD = 1e9 + 7;
 9 int n;
10 ll ans;
11 ll w[maxn];
12 ll val[maxn];
13  
14 int main()
15 {
16     while(~scanf("%d", &n))
17     {
18         for(int i = 1; i <= n; ++i)
19         {
20             scanf("%lld", val + i);
21         }
22         for(int i = 1; i <= n; ++i)
23         {
24             scanf("%lld", w + i);
25         }
26         for(int i = 1; i <= n; ++i)
27         {
28             val[i] += val[i - 1];
29             val[i] %= MOD;
30         }
31         ans = 0;
32         ll tmp = 0;
33         for(int i = 1; i <= n / 2; ++i)
34         {
35             tmp += (val[n - i + 1] - val[i - 1] + MOD) % MOD;
36             tmp %= MOD;
37             ans += (tmp * w[i] % MOD + tmp * w[n - i + 1] % MOD) % MOD;
38             ans %= MOD;
39         }
40         if(n & 1)
41         {
42             tmp += val[(n + 1) / 2] - val[n / 2];
43             tmp %= MOD;
44             ans += tmp * w[(n + 1) / 2] % MOD;
45             ans %= MOD;
46         }
47         printf("%lld
", ans);
48     }
49     return 0;
50 }

View Code

H 树链博弈

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

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

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

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

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 
 6 int n;
 7 int color[N], deep[N];
 8 vector <int> G[N];
 9 
10 void DFS(int u, int fa, int deepth)
11 {
12     deep[deepth] += color[u]; 
13     for (auto v : G[u])
14     {
15         if (v == fa) continue;
16         DFS(v, u, deepth + 1);
17     }
18 }
19 
20 void Run()
21 {
22     while (scanf("%d", &n) != EOF)
23     {
24         for (int i = 1; i <= n; ++i) scanf("%d", color + i);
25         for (int i = 1, u, v; i < n; ++i)
26         {
27             scanf("%d%d", &u, &v);
28             G[u].push_back(v);
29             G[v].push_back(u);
30         }
31         DFS(1, 1, 0);
32         int res = 0;
33         for (int i = 0; i < n; ++i) if (deep[i] & 1) res = 1;
34         puts(res ? "First" : "Second");
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

I 连通块计数

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

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 int main() {
 6     long long ans, t ,x, i, n, MOD;
 7     scanf("%lld
",&n);
 8     MOD = 998244353;
 9     ans = 0; t = 1;
10     for (i = 1; i <= n; ++i) {
11         scanf("%lld
",&x);
12         ans = (ans + (x * x + x) / 2) % MOD;
13         t = (t * (x + 1)) % MOD;
14     }
15     ans = (ans + t) % MOD;
16     printf("%lld
",ans);
17     return 0;
18 }

View Code

J 寻找复读机

按题意模拟即可

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3  
 4 #define N 1010
 5  
 6 int n, m;
 7 int used[N], vis[N];
 8 vector <int> ans;
 9 char s[N][110];
10  
11 int main()
12 {
13     while (scanf("%d%d", &n, &m) != EOF)
14     {
15         memset(vis, 0, sizeof vis);
16         memset(used, 0, sizeof used);
17         ans.clear();
18         for (int i = 1, x; i <= m; ++i)
19         {
20             scanf("%d %s", &x, s[i]);
21             if (i == 1) vis[x] = 1;
22             else if (strcmp(s[i], s[i - 1]) != 0) vis[x] = 1;
23             used[x] = 1;   
24         }
25         for (int i = 1; i <= n; ++i) if (!vis[i])
26             ans.push_back(i);
27         if (!ans.size()) puts("");
28         for (int i = 0, len = ans.size(); i < len; ++i) printf("%d%c", ans[i], " 
"[i == len - 1]);
29     }
30     return 0;
31 }

View Code