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

牛牛的独特子序列

https://ac.nowcoder.com/acm/contest/9753/A

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

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

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

A 牛牛的独特子序列

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

$1\le n\le 10^6$ .

思路

二分答案，然后 $O(n)check$ 数一下就好了，先数a，再数b最后数c就好了。

时间复杂度： $O(nlog(n))$ .

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

#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 分贝壳游戏

一共由 $n$ 个石子， $A$ 先手，轮流取。 $A$ 一次能取 $[1,p]$ 个石子， $B$ 一次能取 $[1,q]$ 个石子，拿走最后一个石子的人获胜。

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

$1\le n\le 10^9,1\le p,q\le 10^9$ .

思路

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

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

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

时间复杂度： $O(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) {
            if(n % (p + 1) == 0) return -1;
            return 1;
        }
        return p > q? 1: -1;
    }
};

C 经过直径的点

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

$2\le n\le 10^5$ 。

思路

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

两遍 $dfs$ 即可。

我写过一篇题解：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;
    }
};