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

https://ac.nowcoder.com/acm/contest/9753#question

C题wa了一发，不然就是29min罚时，痛失rk1，心态爆炸呜呜。
欢迎喜欢刷题，比赛的hxd私信我~

A 牛牛的独特子序列

一个长度为的字符串，特殊的子序列长度是3的倍数，前是a，中间是b，后是c。问最长的特殊子序列额长度是多少。

.

思路

二分答案，然后数一下就好了，先数a，再数b最后数c就好了。

时间复杂度：.

当然也可以用先预处理一下b的个数，然后双指针搞一搞，就可以写了。

#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 1e3 + 5;
int ksm(int a, int64 b, int kmod = mod) {int res = 1;for(;b > 0;b >>= 1, a = (int64)a * a % kmod) if(b &1) res = (int64)res * a % kmod;return res;}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param x string字符串 
     * @return int整型
     */
    int Maximumlength(string x) {
        int n = x.length();
        auto check = [&] (int mid) {
            bool flag = true;
            int cnt = 0, now = 0;
            for(char c: x) {
                if(c - 'a' == now) {
                    ++ cnt;
                    if(cnt == mid) cnt = 0, ++ now;
                }
            }
            return now >= 3;
        };
        int L = 1, R = n / 3, mid, ans = 0;
        while(L <= R) {
            mid = (L + R) >> 1;
            if(check(mid)) ans = mid, L = mid + 1;
            else R = mid - 1;
        }
        return ans * 3;
    }
};

B 分贝壳游戏

一共由个石子，先手，轮流取。一次能取个石子，一次能取个石子，拿走最后一个石子的人获胜。

两人都足够聪明，问最后谁获胜。

.

思路

如果p==q的话，就是bash博弈，当n%(p+1)==0时先手必败，反之先手必胜。

如果一次能取完，那么必胜。

要不然的话，就是谁最大可以取的石子多谁就赢了。首先当前谁都不能一步获胜，能取石子范围大的人，可以将石子数量变成对方先手必败的状态。

时间复杂度：.

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) {
            if(n % (p + 1) == 0) return -1;
            return 1;
        }
        return p > q? 1: -1;
    }
};

C 经过直径的点

给你一棵树，问有多少个点在直径上。直径可能有很多条。

。

思路

树形求出距离每个点的不同子树内距离它最远点的距离和次远点的距离。两者的和如果等于直径长度，它就在直径上。

两遍即可。

我写过一篇题解：https://blog.csdn.net/qq_39599067/article/details/81124011

#define fi first
#define se second
#define mk make_pair
#define o2(x) (x) * (x)
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;// 998244353
const int MXN = 1e5 + 5;
int ksm(int a, int64 b, int kmod = mod) {int res = 1;for(;b > 0;b >>= 1, a = (int64)a * a % kmod) if(b &1) res = (int64)res * a % kmod;return res;}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 节点个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @return int整型
     */
    int n;
    int dp[MXN][3], fa[MXN];
    vector<pair<int,int> > mp[MXN];
    void dfs1(int u,int Fa){
        int len = mp[u].size();
        for(int i = 0; i < len; ++i){
            int v = mp[u][i].fi;
            if(v == Fa)continue;
            dfs1(v, u);
            if(dp[v][0] + mp[u][i].se > dp[u][0]){
              fa[u] = v;
              dp[u][1] = dp[u][0];
              dp[u][0] = dp[v][0] + mp[u][i].se;
            }else if(dp[v][0] + mp[u][i].se > dp[u][1]){
              dp[u][1] = (dp[v][0] + mp[u][i].se);
            }
        }
    }
    void dfs2(int u, int Fa){
        int len = mp[u].size();
        for(int i = 0; i < len; ++i){
            int v = mp[u][i].fi;
            if(v == Fa)continue;
            if(fa[u] == v){
              dp[v][2] = max(dp[u][2], dp[u][1])+mp[u][i].se;
            }else{
              dp[v][2] = max(dp[u][2], dp[u][0])+mp[u][i].se;
            }
            dfs2(v, u);
        }
    }
    int PointsOnDiameter(int n, vector<int>& u, vector<int>& v) {
        // write code here
        for(int i = 0; i <= n; ++i){
            mp[i].clear();
        }
        for(int i = 0; i < n - 1; ++i) {
            mp[u[i]].eb(mk(v[i], 1));
            mp[v[i]].eb(mk(u[i],1));
        }
        memset(dp, 0, sizeof(dp));
        memset(fa, 0, sizeof(fa));
        dfs1(1,-1);
        dfs2(1, -1);
        int cnt = 0, Mx = 0;
        for(int i = 1; i <= n; ++i){
            Mx = max(Mx, max(dp[i][0], dp[i][2]));
        }
        for(int i = 1; i <= n; ++i){
            std::vector<int> v = std::vector<int> {dp[i][0], dp[i][1], dp[i][2]};
            sort(all(v));
            if(v[1] + v[2] == Mx) ++ cnt;
        }
        return cnt;
    }
};