牛客编程巅峰赛第7场钻石王者组题解

A题：
经过观察，发现答案具有单调性，所以就自然地想到了二分答案，判断是否可行也只需把字符串从头扫到尾即可。
（做的时候用了一个假的双指针，WA了3发，导致T3没调出来）
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param x string字符串 
     * @return int整型
     */
    bool check(int x,string str){
        char nw='a';
        int s=0;
        for(int i=1;i<=str.size()-1;i++){
            if(str[i]==nw)s++;
            if(s==x){
                nw++;
                s=0;
            }
            if(nw=='d')return true;
        }
        return false;
    }
    int f[1000010],g[1000010],h[1000010];
    int Maximumlength(string x) {
        int len=x.size();
        int l=1,r=len,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid,x)){
                l=mid+1;
                ans=mid;
            }
            else r=mid-1;
        }
        return ans*3;
    }
};

时间复杂度 O(|x|log|x|)

B题：
口胡结论题。
首先，当牛牛能够一步取完的时候，显然输出1。
然后，当p与q不相等时，发现，数值大的那一方必然可以使n变成n-max(p,q)-1,对方取不完，只能拿走1个，接着数值大的那一方可以拿完。
接着，当p与q相等时，只有当p+1|n的时候牛牛才会输，因为在此时牛牛取k(1<=k<=p)个,牛妹取p+1-k个，牛妹必然胜利。当p+1不能被n整除的时候，牛牛可以取n%(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(n<=p)return 1;
        if(p>q)return 1;
        else if(p<q)return -1;
        else{
            if(n%(p+1)==0)return -1;
            else return 1;
        }
    }
};

时间复杂度 O(1)

C题：
这题各位大佬各用妙招，作者在此提供一个好想的做法。
首先，确定根为1，建立有向有根树，这样后续处理会更方便。
接着用树形dp求出以各个节点为根的子树的直径，存入f，以及以各个节点为根的子树中的叶子节点距离根的最大距离和非严格次大距离），存入d和dd。
然后枚举各个根，自上而下处理，设y为x的儿子，当当前节点为根时，d[y]==d[x]-1或d[y]==dd[x]-1再继续搜索标记，其余的时候，d[y]==d[x]-1再继续搜索标记。（自己打草稿就能清楚原因了）
最后，统计标记的结点个数即为答案。
注意到这样的复杂度为O(n^2)，但是绝对跑不满，足以通过牛客的数据。但是我们离O(n)的复杂度只有一步之遥。
当当前节点不是枚举的根节点时，且当前节点已被标记，那么继续搜索到的点肯定都被标记过了，所以直接return。
这样一来，每个节点最多访问2次，所以时间复杂度为O(n)。
最终代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 节点个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @return int整型
     */
    int nxt[200010],fir[200010],v[200010],d[200010],f[200010],dd[200010],vis[200010],tot=0,anss=0;
    void add(int x,int y){
        nxt[++tot]=fir[x];
        v[tot]=y;
        fir[x]=tot;
    }
    void dfs(int x){
        for(int i=fir[x];i;i=nxt[i]){
            int y=v[i];
            dfs(y);
            f[x]=max(f[x],d[x]+d[y]+1);
            anss=max(anss,f[x]);
            if(d[y]+1>d[x]){
                dd[x]=d[x];
                d[x]=d[y]+1;
            }
            else if(d[y]+1>dd[x])dd[x]=d[y]+1;
        }
    }
    void dfs2(int x,int ye){
        if(ye==0&&vis[x])return;
        vis[x]=true;
        for(int i=fir[x];i;i=nxt[i]){
            int y=v[i];
            if(ye&&(d[y]==d[x]-1||d[y]==dd[x]-1))dfs2(y,0);
            if(!ye&&d[y]==d[x]-1)dfs2(y,0);
        }
    }
    int PointsOnDiameter(int n, vector<int>& u, vector<int>& v) {
        for(int i=0;i<n-1;i++){
            add(u[i],v[i]);
        }
        dfs(1);
        for(int i=1;i<=n;i++){
            if(f[i]==anss)dfs2(i,1);
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            if(vis[i])ans++;
        return ans;
    }
};

时间复杂度 O(n)

#题解#