前言：

题目难度适中，最近的难度来看应该算是比较简单的了，大家且行且珍惜

第一题

小红有一个长度为n的数组a，她每次操作可以删掉一个三元组 (x,y,z)，要求x<y<z,y是x的倍数，z是y的倍数。小红想知道最多可以执行多少次操作。

输入描述

第一行一个整数几，表示数组的长度。

第二行n 个整数a1,a2，...,an，表示数组的元素

1<=n<=10^5

1<=ai<=6

输出描述

示例1

输入

7
1 1 2 3 4 5 6

输出

2

说明

先删除(1,2,4)，再删除(1,3,6)

思路和代码

全排列，把所有情况列举一遍存在数组里，把所有情况暴力枚举一遍，输出结果。

#include <bits/stdc++.h>
using namespace std;
int dir[3][3]={{1,2,4},{1,3,6},{1,2,6}};
int mp[6][3]={{0,1,2},{0,2,1},{1,2,0},{1,0,2},{2,1,0},{2,0,1}};
int main() {
    int n;
    scanf("%d",&n);
    vector<int> cnt(7);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        cnt[x]++;
    }
    int ans=0;
    for(int i=0;i<6;i++){
        vector<int> c(7);
        int sum=0;
        for(int k=1;k<=6;k++) c[k]=cnt[k];
        for(int j=0;j<3;j++){
            int id=mp[i][j];
            int minn=0x3f3f3f3f;
            for(int k=0;k<3;k++) minn=min(minn,c[dir[id][k]]);
            sum+=minn;
            for(int k=0;k<3;k++) c[dir[id][k]]-=minn;
        }
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
    
}

第二题

小红有一个字符串s，只包含小写字母。如果一个字符串中，不包含连续的三个相同的字母，并且不存在两个相同的字母紧挨着两个相同的字母，那么这个字符串就是合法的。例如，字符串“aaa”是不合法的，字符串"aabb"也是不合法的。字符串”aab”是合法的。

小红想知道，最少需要删除多少个字符，才能使得字符串变成合法的。

输入描述

第一行一个字符串s，长度不超过10^5，只包含小写字母。

输出描述

输出一个整数，表示最少需要删除的字符个数。

示例1

输入

aabbaa

输出

1

说明

删除一个字符b，得到 aabaa，是一个合法的字符串。

思路和代码

1、预处理字符串：为了方便后续的处理，代码将字符串s末尾添加了一个特殊字符'#'。2、遍历字符串：计算相同字符连续出现的次数，并将字符及其重复次数拼接到字符串t中。

3、构建向数组a：根据字符串t构建了一个整数向量a，其中向量中的每个元素表示相应位置的字符出现的次数。如果连续的字符出现两次（如"aa"），则将2添加到向量a`中，否则添加1。

4、处理连续的重复字符：如果向量a中的连续两个元素都是2（表示连续的字符出现了两次），则将第二个元素减少1，同时增加ans的值，以确保删除字符以最小化重复子串的数量。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int main() {
    string s;
    cin>>s;
    int n=s.size();
    s+='#';
    int cnt=0,ans=0;
    string t;
    for(int i=0;i<=n;i++){
        if(i==0 || s[i]==s[i-1]) cnt++;
        else{
            t+=string(min(2,cnt),s[i-1]);
            ans+=cnt-min(2,cnt);
            cnt=1;
        }
    }
    int m=t.size();
    vector<int> a;
    for(int i=0;i<m;i++){
        if(i!=m-1&&t[i]==t[i+1]){
            a.push_back(2);
            i+=1;
        }else{
            a.push_back(1);
        }
        int sz=a.size();
        if(sz>=2&&a[sz-1]==2&&a[sz-2]==2){
            a[sz-1]--;
            ans++;
        }
    }
    cout<<ans<<endl;
}

第三题

小红拿到了一个有根树，根节点为1号节点，每个节点到其每个孩子有条有向边。小红想取一条路径，满足路径上所有节点的权值都不相等。小红想知道，自己有多少种选择方案?

输入描述

第一行输入一个正整数n，代表节点的数量。

第二行输入n一1个正整数ai，代表2号节点到n号节点每个节点的父亲编号。

第三行输入n个正整数vi，代表1号节点到n号节点每个节点的权值。

2<=n<=2* 10^5
1<=ai<=i<2* 10^5
1<=vi<=10^9

输出描述

小红选择路径的方案数。

示例1

输入

5
1 1 1 2
1 1 2 2 2

输出

8

说明

路径上有一个节点，有5种取法。路径上有两个节点的取法有: 1-3、1-4、2-5

思路与代码

深度优先搜索（DFS）：程序通过dfs函数进行深度优先搜索，遍历树的每个节点，并计算节点的深度。

• dfs函数的参数包括当前节点u，其父节点fa，以及当前节点的深度dd`。

• 在进入当前节点u之前，记录节点u上一次出现的深度，即p[a[u]]，并将当前节点的深度dd保存在p[a[u]]中。

• 计算当前节点u与其最近出现的节点之间的深度差距，即gap = dd - near[u]，并将其加到结果res中。

• 遍历节点u的所有子节点，如果子节点不是其父节点fa，则递归调用dfs函数，并将深度加1。

• 在递归回溯时，将节点u上一次出现的深度还原回p[a[u]]。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
unordered_map<int,int> p;
vector<int> e[maxn];
int n;
int a[maxn],near[maxn];
void readIn(){
    cin>>n;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        e[x].push_back(i);
    }
    for(int i=1;i<=n;i++) cin>>a[i];
}
void dfs(int u,int fa,int dd);
long long res=0;
int main() {
    readIn();
    dfs(1,0,1);
    cout<<res<<endl;
}
void dfs(int u,int fa,int dd){
    int pre=p[a[u]];
    p[a[u]]=dd;
    near[u]=max(pre,near[fa]);
    int gap=dd-near[u];
    res+=gap;
    for(auto v:e[u]){
        if(v==fa) continue;
        dfs(v,u,dd+1);
    }
    p[a[u]]=pre;
}