牛客练习赛128补题

Natural-TLP / 2024-09-17 / 原文

A. Cidoai的幂次序列

思路

思维题
题面看着复杂，但只需输出 $n-1$ 和 $1$ 即可。

代码

#include <iostream>

using namespace std;

typedef long long ll;

ll n, k;

int main()
{
    cin >> n >> k;
    
    cout << 2 << '\n';
    cout << n - 1 << ' ' << 1;
    
    return 0;
}

B. Cidoai的平均数对

思路

01背包

根据题意有

\[\frac {\sum_{i=1}^n b_i}{n} \le k \]

将 $n$ 移到右边

\[\sum_{i=1}^n b_i \le n*k \]

再将 $n * k$ 移到左边

\[\sum_{i=1}^n b_i - n * k \le 0 \]

将 $k$ 放入 $b_i$ 求和的式子中

\[\sum_{i=1}^n (b_i - k) \le 0 \]

所以要满足最终和小于等于0，可以将所有$b_i-k$，显然结果为负数的一定可选，结果为正数的可选可不选，这样就转为一个典型的01背包问题，我先将结果为负的都选上求和为背包容量，结果为正的作为体积，对应的$a_i$为价值。

代码

#include <iostream>

using namespace std;

const int N = 500 + 10, M = N * N;

int n, k, sum;
int a[N], b[N];
int dp[M];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i];
        b[i] -= k;
        if (b[i] < 0) {
            sum -= b[i];
            b[i] = 0;
        }
    }
    
    for (int i = 1; i <= n; i ++)
        for (int j = sum; j >= b[i]; j --)
            dp[j] = max(dp[j], dp[j - b[i]] + a[i]);
    
    cout << dp[sum];
    
    return 0;
}

C. Cidoai的树上方案

思路

树形dp模板

简单图就是不含自环和重边的图。
树外一个点连接树内任意点，求不构成三元环的方案数。可以知道构成三元环，除树外的点与树内两个点相连，还有一个条件是树内两个点要相连，即相邻的两个点，由此题目转为，找不相邻的任意个点的方案数，就是一个树形dp的模板了。

代码

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int mod = 998244353;
const int N = 2e6 + 10;

int n;
vector<int> g[N];
ll dp[N][2];

void dfs(int u)
{
    dp[u][0] = dp[u][1] = 1;
    for (int v : g[u])
    {
        dfs(v);
        dp[u][0] = dp[u][0] * (dp[v][0] + dp[v][1]) % mod;
        dp[u][1] = dp[u][1] * dp[v][0] % mod;
    }
}

int main()
{
    cin >> n;
    
    for (int i = 2; i <= n; i ++)
    {
        int x;
        cin >> x;
        g[x].push_back(i);
    }
    
    dfs(1);
    
    cout << (dp[1][0] + dp[1][1]) % mod;
    
    return 0;
}

D. Cidoai的字符集合

思路

并查集模板

题目是求两个分类的总和，一个是有歌曲是相似的集合数1加上独立歌曲的数量n。
用map记录一下每个旋律对应哪首歌，快速判断这首歌是不是可能相似了，再用并查集找出相似的两首歌，将相似的两首歌放入集合0中。最后枚举一下0~n首歌，它父节点是它本身的数量就是答案。

代码

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 1e6 + 10;

int n;
unordered_map<string, int> mp;
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n;
    
    for (int i = 1; i <= n; i ++) p[i] = i;
    for (int i = 1; i <= n; i ++)
    {
        int k;
        cin >> k;
        while (k --)
        {
            string s;
            cin >> s;
            if (mp.count(s)) {
                int pi = find(i), ps = find(mp[s]);
                if (pi == ps) continue;
                p[pi] = 0;
                p[ps] = 0;
            }
            else mp[s] = i;
        }
    }
    
    int res = 0;
    for (int i = 0; i <= n; i ++)
        if (p[i] == i) res ++;
    
    cout << res;
    
    return 0;
}

E. Cidoai的映射数列

矩阵快速幂优化状态压缩，听牛客官方补的题。

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 128;
const int mod = 998244353;

struct Matrix {
    int n, m;
    ll mat[N][N];
    
    Matrix() {}
    Matrix(int _n, int _m): n(_n), m(_m) {}
    Matrix(int _n, int _m, bool flag) : n(_n), m(_m) {
        memset(mat, 0, sizeof mat);
        if (flag) 
            for (int i = 0; i < n; i ++) mat[i][i] = 1;
    }
    
    Matrix(int k) {
        n = m = 1 << k;
        memset(mat, 0, sizeof mat);
        for (int st = 0; st < n; st ++)
        {
            mat[st][st >> 1] = 1;
            if (st & 1) continue;
            for (int i = 0; i < k; i ++)
                mat[st][(st >> 1) | (1 << i)] = 1;
        }
    }
    
    friend inline Matrix operator * (Matrix x, Matrix y) {
        Matrix tmp = Matrix(x.n, y.m, 0);
        for (int i = 0; i < tmp.n; i ++)
            for (int k = 0; k < x.m; k ++) {
                if (x.mat[i][k]) {
                    for (int j = 0; j < tmp.m; j ++)
                        tmp.mat[i][j] = (tmp.mat[i][j] + x.mat[i][k] * y.mat[k][j] % mod) % mod; 
                }
            }
        return tmp;
    }
} f[N >> 4][N >> 1];

void init()
{
    for (int k = 0; k <= 7; k ++)
    {
        f[k][1] = Matrix(k);
        for (int i = 2; i <= 60; i ++)
            f[k][i] = f[k][i - 1] * f[k][i - 1];
    }
}

void solve()
{
    ll n, k;
    cin >> n >> k;
    
    k = min(n, k);
    Matrix ans = Matrix(1, 1 << k, 0);
    ans.mat[0][0] = 1;
    
    for (ll i = 1, j = 1; j <= n; i ++, j <<= 1)
        if (n & j) ans = ans * f[k][i];
    
    cout << ans.mat[0][0] << '\n';
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    init();
    int t;
    cin >> t;
    while (t --) solve();
    
    return 0;
}

F. Cidoai的数论求和

这个也是看官方题解补的，一堆数学公式，推公式+莫比乌斯反演。

代码

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 4e6 + 10;

int prime[N], mu[N], cnt;
bool st[N];
ll n;

void get_mu(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) {
            prime[++ cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; prime[j] <= n / i; j ++)
        {
            st[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
}

int main()
{
    get_mu(N - 1);
    cin >> n;
    
    ll res= 0;
    ll m = sqrtl(n);
    for (ll i = 1; i <= m; i ++)
    {
        ll d = sqrtl(n / i / i / 2);
        res += mu[i] * d * d;
    }
    
    for (ll i = 1; i <= m; i ++)
    {
        ll t = n / i / i;
        ll u = sqrtl(t);
        ll d = sqrtl(t / 2);
        ll sum = 0;
        for (ll j = d + 1, ne; j <= u; j = ne + 1)
        {
            ne = t / (t / j);
            ne = min(ne, u);
            sum += t / j * (ne - j + 1);
            sum -= (ne - j + 1) * (j + ne) / 2;
        }
        res += mu[i] * sum * 2;
    }
    cout << res;
    
    return 0;
}