牛客编程巅峰赛S2第7场 - 钻石&王者 ABC

高级场A-B-C三题题解

A:

注意是子序列，也就是分三段，ABC段，结果为min(na,nb,nc)(na:A段中'a'的个数，nb:B段中'b'的个数，nc:C段中'c'的个数)

由于这里的特殊性，我们可以用双指针。

枚举a，c的个数。

然后l，r指针向中间移动，直到'a','c'都加1，预处理出'b'的个数，在指针移动时更新nb。

每次更新完求值即可。

const int M =1e6+7;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param x string字符串 
     * @return int整型
     */
    int a[M];
    int Maximumlength(string x) {
        // write code here
        int n=x.length(),mx=0;
        int na=0,nb=0,nc=0;
        for(int i=0;i<n;i++){
            if(x[i]=='b')nb++;
        }
        int l=0,r=n-1;
        while(l<=r){
            while(x[l]!='a'){
                if(x[l]=='b')nb--;
                l++;
            }
            while(x[r]!='c'){
                if(x[r]=='b')nb--;
                r--;
            }
            na++,nc++;
            mx=max(mx,min(na,min(nb,nc))*3);
            l++,r--;
        }
        return mx;
    }
};

B:分贝壳游戏

巴什博奕变形（可以不知道巴什博奕，直接分析即可）

显然，当p>=n时牛牛一次可以取完。

当p>q时，

牛牛可每次拿走贝壳，保证贝壳剩余量为：(q+1)*k （即q+1的倍数），则无论牛妹怎么取，牛牛总能取到。

显然(q+1)*k对牛妹来说是一个必败态。（当贝壳数是q+1时，牛妹取多少贝壳都不能直接赢，而牛牛一定能直接赢）

当q>p时，

同上，牛牛第一次无论怎么取，牛妹总能取贝壳使得贝壳剩余量为：(p+1)*k (即p+1的倍数)。

牛牛无法构造出牛妹的必败态，即使牛牛让贝壳变成q+1, 牛妹依然可以让贝壳变成 p+1 < q+1 使得牛牛必败。

当p==q时，

根据上述分析，如果刚开始贝壳数不是(p+1)的倍数，则牛牛必胜（每次构造出(p+1)的倍数即可），否则牛牛必败。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    int Gameresults(int n, int p, int q) {
        // write code here
        if(p>=n || p>q){
            return 1;
        } 
        if(q>p)return -1;
        if(p==q){
            if(n%(p+1)==0)return -1;
            return 1;    
        }
        return 0;
    }
};

C：经过直径的点

先两次DFS求出直径mx，p,q.

根据树上直径的性质，一个点x,树上距离其最远的点一定是直径的一个端点(任意直径的两个端点中必定至少有一个与x构成最远的距离，证明略)。

然后以p为根，找出所有到根节点距离为mx的点，标记其到根节点的所有点。（记忆化一下，每个点最多标记一次是On的）

以q为根同理做一次，（注意两次的标记要分开）

最后统计所有被标记过的点就是答案。

const int M = 1e5+7;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 节点个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @return int整型
     */
    vector<int>g[M];
    int p,q,mx,rt,f[M];
    void dfs(int x,int fa,int dep){
        if(dep>mx)p=x,mx=dep;
        for(auto y:g[x]){
            if(y==fa)continue;
            dfs(y,x,dep+1);
        }
    }
    void pre(int x,int fa){
        f[x]=fa;
        for(auto y:g[x]){
            if(y==fa)continue;
            pre(y,x);
        }
    }
    int vs[M],ts[M];
    void col(int x){
        while(x&&!vs[x]){
            vs[x]=1;
            x=f[x];
        }
    }
    void gao(int x,int fa,int dep){
        if(dep==mx){
            col(x);
        }
        for(auto y:g[x]){
            if(y==fa)continue;
            gao(y,x,dep+1);
        }
    }
    int PointsOnDiameter(int n, vector<int>& u, vector<int>& v) {
        // write code here
        for(int i=0;i<n-1;i++){
            g[u[i]].push_back(v[i]);
            g[v[i]].push_back(u[i]);

        }
        dfs(1,0,0);
        q=p,mx=0;
        dfs(p,0,0);
        pre(p,0);
        gao(p,0,0);
        for(int i=1;i<=n;i++)ts[i]=vs[i],vs[i]=0;
        pre(q,0);
        gao(q,0,0);
        int nm=0;
        for(int i=1;i<=n;i++)if(vs[i]||ts[i])nm++;
        return nm;
    }
};