题解与反思

仔细读题呀！！！不会的多读两遍题目

小红的素数合并

1、猜结论：举个样例猜一下结论即可。

2、呜呜呜，两个小时没看懂题，以为要合并的只剩下两个元素。题目的意思是，操作要选两个素数，两个素数相乘的结果肯定是和数，所以每个元素至多操作一次。

3、主要是分数组是奇数个元素还是偶数个，偶数比较好猜。

4、奇数个元素的话，我们俩俩乘起来，肯定有一个元素剩余，肯定剩大的元素才能缩小差距，所以奇数数个元素时最大值不参与合并。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int a[N];
int main()
{

    int n;
    cin >> n;
    for(int i = 0; i <  n; i ++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    LL mi = 1e9 + 10, ma = -1e9;
    for(int i = 0, j = n - 1 - (n % 2); i < n / 2; i ++, j --)
    {

        LL x = (LL)a[i] * a[j];
        mi = min(mi, x);
        ma = max(ma, x);
        //cout << a[i] << endl << a[j] << endl;
    }
    if(n % 2)
    {
        mi = min(mi, (LL)a[n - 1]);
        ma = max(ma, (LL)a[n - 1]);
    }
    cout << ma - mi << endl;
    return 0;
}

D 小红的树上删边

基础的树的遍历，图论的基础太差了，要多练！！！

1、节点个数为奇数肯定不能完成

2、节点个数为偶数的时候，因为求最多删几条边，所以当子树的节点树为偶数时我们就删除盖子树与其父节点的边。

3、无向树的dfs(), 我们应该传如父节点，防止向上搜索。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> g[N];
int cnt_son[N];//以i为节点的子树的节点个数
int res; 
void dfs(int u, int fa)
{
    cnt_son[u] = 1;
    for(auto x : g[u])
    {
        if(x != fa)
        {
            dfs(x, u);
            cnt_son[u] += cnt_son[x];//u为根的树的节点数等于所有子树的节点数之和
        }
    }
    if(u != 1 && cnt_son[u] % 2 == 0) res ++;//注意根节点没有边可以删
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n - 1; i ++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1, 0);
    if(n % 2 == 1) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

E 小红的子序列求和

这题有点可惜，刚做的atcodr考了贡献法

1、分析每一位在最后答案中的贡献。

2、要会组合数的求法，n <= 1000 直接递推就行。

3、每位数字可以作为子序列中的1~K位，我们算一下其在每个位上的贡献即可。

4、计算在每个位置上的贡献的时候，要计算包含这一位的子序列有多少个，我们可以用组合数求得。

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 1005;
typedef long long LL;
int C[N][N];
int qmi(int a, int k)//快速幂，用来计算10的次方
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = (LL) res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}
int main()
{
    C[0][0] = 1;
    int n, k;
    string s;
    cin >> n >> k >> s;
    for(int i = 1; i < N; i ++)
    {
        for(int j = 0; j <= i; j ++)
        {
            if(j == 0 || j == i) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
    LL res = 0;
    for(int i = 0; i < n; i ++)
    {
        LL x = s[i] - '0';
        for(int j = 1; j <= k; j ++)
        {
            LL xx = qmi(10, k - j);//x在第k位的权重
            LL yy = C[i][j - 1];//前面可以组合的数
            LL zz = C[n - i - 1][k - j];//x后面可以组合的数
            res += x * xx % mod * yy % mod * zz % mod;//贡献累加
            res %= mod;
        }
    }
    cout << res << endl;
    return 0;
}