前言

题目难度比较大，比较灵活，有不少数学处理。特别是第四题和第五题。其中第五题虽然是一个树形dp，但是重点并不在于树形dp，而在于其中的数学规律的处理

小美的数字

如果一个十进制数字只有0和1，那这就是一个类二进制数字。例如:101和1100都是类二进制数字，而 112和3001 则不是。

对于一个数n，小美想知道最少需要几个类二进制数字相加可以得到。

输入描述

输入一个正整数n。

1 ≤ n ≤ 10^10000

输出描述

输出一个正整数，表示最少需要的类二进制数字个数。

示例1

输入

10101

输出

1

思路与代码

这段代码的核心思想是遍历字符串中的每个字符，将字符转换为整数并比较大小，以找到最大的数字。然后将最大数字输出到标准输出。

#include<bits/stdc++.h>
using namespace std;
void solve() {
    string num;
    cin >> num;
    int mx = 0;
    for(int i = 0;i < num.size();i++) {
        mx = max(mx,num[i]-'0');
    }
    cout << mx << endl;
}
int main() {
    solve();
}

小美的宝藏

小美计划派遣一位勇敢的冒险家前往解开宝塔的秘密。宝塔中共保存着n个宝藏，价值分别为a1,a2，...an。每天冒险家可以进入宝塔，并选择一个价值不低于b的宝藏带出来。但是冒险家每天只能选择一个宝藏，而且每个宝藏只能被选择一次。

现在小美想知道，在这个过程中，最多可以拿出多少个宝藏

输入描述

一行一个整数 n，表示宝塔中的宝藏个数。
一行n 个整数a1,a2，...，an，表示宝塔中的宝藏价值。
一行n个整数b1,b2,...,bn，表示冒险家每天可以拿出的最低价值。
1<=n<=10^5
1<=ai,bi<=10^5

输出描述

输出一个整数，表示最多可以拿出的宝藏个数。

示例1

输入

5
1 2 3 4 1
3 1 2 3 2

输出

4

思路与代码

这段代码的核心思想是使用双指针方法，按顺序遍历两个数组，并选择数字以满足条件。最终输出选择的数字数量作为答案。

#include<bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    vector<int> a(n),b(n);
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    for(int i = 0;i < n;i++) {
        cin >> b[i];
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans = 0;
    for(int i = 0,j = 0;j < n;j++) {
        while(i < n && a[i] < b[j]) i++;
        if(i < n) {
            ans++;
            i++;
        }
    }
    cout << ans << endl;
}
int main() {
    solve();
}

小美的美丽串

小美定义一个字符串是”美丽串”，当且仅当该字符串包含”mei”连续子串。例如“meimei”、"xiaomeichan”都是美丽串，而”meeii"则不是美丽。

现在小美拿到了一个字符串，她准备删除一些字符，但不能删除两个连续字符。

小美希望最终字符串变成美丽串，她想知道有多少种删除方案?

输入描述

一个仅包含小写字母的字符串，长度不超过 20。

输出描述

删除的方案数。

示例1

输入

meili

输出

3

说明

方案 1: 什么都不删
方案 2: 删除第四个字符
方案 3: 删除第五个字符

思路与代码

这段代码通过使用位运算来生成字符串 s 的所有可能子集，然后检查每个子集是否满足条件，并统计符合条件的子集数量。如果子集中的字符不相邻且包含子字符串 "mei"，则增加计数器 ans。

import java.util.Scanner;

public class MT3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        int len = s.length();
        long ans = 0;
        for (int i = 0; i < 1 << len; i++) {
            boolean flag = true;
            for (int j = 0; j < len - 1; j++) {
                if ((i & (1 << j)) > 0 && (i & (1 << (j + 1))) > 0) flag = false;
            }
            if (!flag) continue;
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < len; j++) {
                if ((i & (1<<j)) == 0){
                    sb.append(s.charAt(j));
                }
            }
            if (sb.toString().contains("mei")) ans ++;
        }
        System.out.println(ans);
    }
}

小美的并集

小美拿到了n个集合。她随机取出两个集合准备计算它们的并集大小，请你帮小美计算这个并集大小的期望。

请注意，集合中是不存在两个相同元素的。例如[1,2]和[1,3,5]的并集为[1,2,3,5]

输出描述

第一行输入一个正整数n，代表集合的数量。
接下来的n行，每行描述一个集合:
每行的第一个元素为一个正整数m，代表集合的大小
接下来输入m个正整数aij，代表第i个集合的第j个元素。
保证每个集合中的元素不同
所有集合的大小之和不超过200000
2<=n<=200000
1<=aij<=10^9

输出描述

一个浮点数，代表最终并集的大小期望。如果你的答案和标准答案的相对误差不超过10^-7，则认为答案正确。

示例1

输入

2
2 1 2
3 1 3 5

输出

4.00000000000

说明

显然最终的期望大小是4。

思路与代码

这段代码的核心思想是遍历集合，统计整数出现的次数，并根据组合数的计算来得出最终的答案，然后将答案以浮点数的形式输出。

1. 使用一个循环，遍历每个集合，并进行以下操作：
• 读取集合的长度 len。
• 计算 tot 的增加值，将 len * (n - 1) 添加到 tot 中，表示每个整数在至少一个其他集合中出现。
• 遍历集合中的每个整数，将整数添加到 sets 中，并更新 mp 中整数的计数。
2. 使用另一个循环，遍历 mp 中的每个键值对，计算减去的值，将 (e.second * (e.second - 1)) / 2 减去 tot，表示对于每个整数，减去它在自己集合中出现的次数的组合数。
3. 计算 bottom 的值，表示底部值，即所有可能的不同整数对数。
4. 计算答案 ans，将 tot 除以 bottom 得到浮点数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve() {
    int n;
    cin >> n;
    vector<vector<int>> sets(n);
    unordered_map<int,int> mp;
    ll tot = 0;
    for(int i = 0;i < n;i++) {
        int len;
        cin >> len;
        tot += 1LL * len * (n - 1);
        for(int j = 0;j < len;j++) {
            int num;
            cin >> num;
            sets[i].push_back(num);
            mp[num]++;
        }
    }
    for(auto e : mp) {
        tot -= 1LL * e.second * (e.second - 1) / 2;
    }
    ll bottom = 1LL * n * (n - 1) / 2;
    double ans = tot / bottom;
    printf("%.10lf\n",ans);
}
int main() {
    solve();
}

小美的树上因子

小美拿到了一棵有根树，根为1号节点，共有n个节点。她定义一个节点是好节点，当且仅当该节点的子树的所有节点值乘积的因子数量不小于k。

小美想知道，这棵树有多少好节点?

输入描述

第一行输入两个正整数nk。
第二行输入n个正整数ai，代表每个节点的值。
接下来的n一1行，每行输入两个正整数u和v，代表节点u和节点u有一条边连接。
1<=n<=10^5
1<=k<=10^14
1<=ai<=100
1<=u,v<=n

输出描述

一个整数，代表好节点的数量。

示例1

输入

3 2
3 2 1
1 2
1 3

输出

2

说明

1号节点的子树所有节点乘积等于6，有4个因子，是好节点。

2号节点的子树所有节点乘积等于2，有2个因子，是好节点。

思路与代码

这段代码的核心思想是通过使用递归遍历树的节点，并计算每个节点的因子数量，然后检查是否满足条件 k。

1. 定义一个递归函数 dfs，用于遍历树的节点，并更新 sum 向量中的因子数量。在函数中：
• 遍历与当前节点相连接的节点。
• 递归调用 dfs 函数。
• 更新当前节点的因子数量，将与相邻节点的因子数量合并。
2. 调用 dfs 函数，从树的根节点开始遍历。
3. 初始化一个整数变量 ans 为 0，用于存储满足条件的子树数量。
4. 遍历每个节点，计算其因子数量的乘积 cur，并检查是否大于等于给定的值 k。如果满足条件，将计数器 ans 增加。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
vector<vector<int>> sum(N,vector<int>(101,0));
void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<int> val(n);
    for(int i = 0;i < n;i++) {
        cin >> val[i];
    }
    vector<vector<int>> g(n,vector<int>());
    for(int i = 0;i < n - 1;i++) {
        int u,v;
        cin >> u >> v;
        u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 0;i < n;i++) {
        int v = val[i];
        for(int j = 2;j <= v;j++) {
            if(v % j == 0) {
                while(v % j == 0) {
                    sum[i][j]++;
                    v /= j;
                }
            }
        }
    }
    auto dfs = [&](auto self,int cur,int f) -> void {
        for(int next : g[cur]) {
            if(next == f) continue;
            self(self,next,cur);
            for(int j = 2;j <= 100;j++) {
                sum[cur][j] += sum[next][j];
            }
        }
    };
    dfs(dfs,0,-1);
    int ans = 0;
    for(int i = 0;i < n;i++) {
        ll cur = 1;
        for(int j = 2;j <= 100;j++) {
            if(sum[i][j] > 0) {
                cur *= (1 + sum[i][j]);
                if(cur >= k) break;
            }
        }
        if(cur >= k) ans++;
    }
    cout << ans << endl;
}
int main() {
    solve();
}