牛客编程巅峰赛S2第9场 - 钻石&王者 题解

A题：
是道假题，这里先放上假做法。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
     * @param n int整型 代表题目中的n
     * @param a int整型vector 代表n个数的大小
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        sort(a.begin(),a.end());
        long long s=0,t=0;
        for(int i=0;i<n-2;i++)
            if(a[i]+a[i+1]>a[i+2]){
                s=a[i]+a[i+1]+a[i+2];
                break;
            }
        for(int i=n-1;i>=2;i--)
            if(a[i-2]+a[i-1]>a[i]){
                t=a[i-2]+a[i-1]+a[i];
                break;
            }
        return t-s;
    }
};

时间复杂度 O(n)

B题:
数据范围这么大，一看就是一道结论题，所以果断用dp打表，先放上打表代码。

#include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
int main(){
    for(int n=1;n<=1000;n++){
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++){
           if(j!=0)dp[i][j]=(dp[i-1][j]+dp[i][j-1])%2;
            else dp[i][j]=dp[i-1][j];
        }
        cout<<dp[n][n]%2<<" ";
    }
}

通过观察答案可以发现当且仅当存在正整数x，使得 时，答案才是true。所以先把n加上1，判断n是否是2的正整数次幂。代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n string字符串 三角形的长和高
     * @return bool布尔型
     */
    int f[1000010];
    bool judge(string n) {
        int len=n.size();
        for(int i=0;i<len;i++)
            f[i+1]=n[len-i-1]-'0';
        f[1]++;
        for(int i=1;i<=len;i++)
            if(f[i]==10){
                f[i]=0;
                f[i+1]++;
            }
            else break;
        if(f[len+1]==1)len++;
        while(len!=1||f[1]!=1){
            if(f[1]%2==0){
                int y=0;
                for(int i=len;i>=1;i--){
                    int x=(f[i]+y)/2;
                    y=f[i]%2*10;
                    f[i]=x;
                }
                if(f[len]==0)len--;
            }
            else return false;
        }
        return true;
    }
};

时间复杂度 O(log n)

C题：
n个点，n条边且连通的图就是基环树。
对于基环树的一般做法是先找环，缩成一个点进行处理。
可是这道题的n只有5000，可以暴力删边，用树形dp求树的直径。
即使删掉了某一条边不连通了也没关系，可以证明这种图得出来的答案肯定小于等于真正的树的直径。
注意，因为以上这种情况，就不能单纯地只记录父节点是哪个节点了，应该直接定义一个vis数组，判断是否经过该点。
数组要不断清空哦！！！
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @return int整型
     */
    int tot=0,ans=0,e[100010],fir[100010],nxt[100010],d[100010],vis[100010];
    void add(int x,int y){
        nxt[++tot]=fir[x];
        e[tot]=y;
        fir[x]=tot;
    }
    void dfs(int x){
        vis[x]=true;
        for(int i=fir[x];i;i=nxt[i]){
            int y=e[i];
            if(vis[y])continue;
            dfs(y);
            ans=max(ans,d[x]+d[y]+1);
            d[x]=max(d[x],d[y]+1);
        }
    }
    int MaxDiameter(int n, vector<int>& u, vector<int>& v) {
        for(int i=0;i<n;i++){
            memset(fir,0,sizeof(fir));
            memset(nxt,0,sizeof(nxt));
            memset(e,0,sizeof(e));
            memset(d,0,sizeof(d));
            memset(vis,false,sizeof(vis));
            tot=0;
            for(int j=0;j<n;j++){
                if(i==j)continue;
                add(u[j],v[j]);
                add(v[j],u[j]);
            }
            dfs(1);
        }
        return ans;
    }
};

时间复杂度 O( )