1. 权限

算法：贪心

算法思路

简单地将题目转换成一个图，可以发现这是一棵基环树。

由于丢失权限的服务器不会给另一台丢失权限的服务器发送信息，那么为了方便可以转换成最多有几台丢失权限的服务器，然么直接求最大独立集即可。

对于环外的点直接挑入度为零的点，很显然挑入度小的点更优。

然后按照这个步骤隔一个的挑点。若标到了环上的点，就剖环，最后把没剖开的环重新剖一次。

用一个数组去标记遍历过的点，然后再用一个参数表示这个点选不选。

最后计算答案即可。

复杂度分析

• 时间复杂度为$O(n)$

  • $n$为服务器数量

• 空间复杂度为$O(n)$

  • $n$为服务器数量

题解

C++

// This solution is powered by @lintcode.com
class Solution {
public:
    /**
     * @param nums: The label of the robber identified by each person (subscripts start from 1)
     * @return: Find the least number of innocents
     */
    void dfs(int u, bool f) {
        if (vis[u]){
            return ;
        }
        vis[u] = true;
        a[u] = f;
        if (!--in[x[u]] || f) {
            dfs(x[u], !f);
        }
    }
    int trial(vector<int> &nums) {
        int n = nums.size();
        x.resize(n + 1);
        in.resize(n + 1, 0);
        vis.resize(n + 1, false);
        a.resize(n + 1, false);
        for (int i = 1; i <= n; ++i) {
            x[i] = nums[i - 1];
            in[x[i]]++;
        }
        for (int i = 1; i <= n; ++i) {
            if (!in[i]) {
                dfs(i, true);
            }
        }
        for (int i = 1; i <= n; ++i) {
            dfs(i, false);
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += a[i];
        }
        return n - ans;
    }
private:
    vector<int> x;
    vector<int> in;
    vector<bool> vis;
    vector<bool> a;
};

Python

# This solution is powered by @lintcode.com
class Solution:
    """
    @param nums: The label of the robber identified by each person (subscripts start from 1)
    @return: Find the least number of innocents
    """
    def dfs(self,u,f):
        if self.vis[u] == True:
            return
        self.vis[u] = True
        self.a[u] = f
        self.In[self.x[u]] -= 1
        if self.In[self.x[u]] == 0 or f == True:
            self.dfs(self.x[u],not f)
    def trial(self, nums):
        n = len(nums);
        self.x = [0] * (n + 1)
        self.In = [0] * (n + 1)
        self.vis = [False] * (n + 1)
        self.a = [False] * (n + 1)
        for i in range(1,n + 1):
            self.x[i] = nums[i - 1]
            self.In[self.x[i]] += 1
        for i in range(1,n + 1):
            if self.In[i] == 0:
                self.dfs(i,True)
        for i in range(1,n + 1):
            self.dfs(i,False)
        ans = 0
        for i in range(1,n + 1):
            if self.a[i] == True:
                ans += 1
        return n - ans

Java题解详见：九章soulution

2. 吃鸡

算法：最小斯坦纳树

算法思路

这题其实就是求包含给定点的最小生成树，也就是最小斯坦纳树。

我们设$f[i][j]$表示节点目前正在转移的节点为i，节点i已经连通了状态为j的最小代价。

• 当i不变时：$fi=fi+fi,k∈j$.

  • 将k能取到的所有点都排除在外，保证答案尽可能优。
    当i变化时：$f[i][j]=min(f[k][j]+val(k,i))$
  • spfa加点优化跑最短路的求解即可。

复杂度分析

• 时间复杂度为$O(n*3^k)$

  • $n$为人数大小

• 空间复杂度为$O(n*40)$

  • $n$为人数大小

题解

C++

// This solution is powered by @lintcode.com
struct edge{
    int t,nx,w;
}E[400040];
long long f[40][100010];
int cnt,G[100010];
int vis[100010];
class Solution {
public:
    deque<int> Q;
    void spfa(long long *f,int n) {
        for (int i = 1;i <= n; i++) {
            vis[i] = 0;
            if (f[i] != 0x3f3f3f3f3f3f3f) {
                Q.push_back(i);
            } 
        }
        while(!Q.empty()) {
            int x = Q.front(); 
            Q.pop_front(); 
            vis[x]=0;
            for (int i = G[x]; i ;i = E[i].nx) {
                if (f[E[i].t] > f[x] + E[i].w) {
                    f[E[i].t] = f[x] + E[i].w;
                    if (!vis[E[i].t]) {
                        vis[E[i].t] = 1;
                        (Q.empty() || f[E[i].t] <= f[Q.front()]) ? Q.push_front(E[i].t) : Q.push_back(E[i].t);
                    }
                }
            }
        }
    }
    inline void addedge(int x,int y,int z){
        E[++cnt].t = y; E[cnt].nx = G[x]; E[cnt].w = z; G[x] = cnt;
        E[++cnt].t = x; E[cnt].nx = G[y]; E[cnt].w = z; G[y] = cnt;
    }
    long long cost(int n, vector<int> &k, vector<vector<int>> &m) {
        cnt = 0;
        for(int i = 0;i < 40;i++){
            for(int j = 0;j < 100010;j++){
                f[i][j] = 0x3f3f3f3f3f3f3f;
            }
        }
        
        for(int i = 0;i < k.size();i++){
            f[1 << i][k[i]]=0;
        }
        
        for(int i = 0;i < m.size();i++){
            addedge(m[i][0],m[i][1],m[i][2]);
        }
        
        for(int S = 1;S < (1<<k.size()); S++){
            for(int i = 1;i <= n;i++)
                for(int ss=(S - 1) & S; ss; ss = (ss - 1) & S)
                    f[S][i] = min(f[S][i],f[ss][i] + f[S ^ ss][i]);
            
            spfa(f[S],n);
        }
        
        long long ans = 0x3f3f3f3f3f3f3f;
        for(int i = 1;i <= n;i++) 
            ans=min(ans,f[(1<<k.size())-1][i]);
        return ans;
    }
};

Python

# This solution is powered by @lintcode.com
import sys
import collections
class edge:
    pass
f = [[sys.maxsize for _ in range(100010)] for _ in range(40)]
G = [0] * 100010
vis = [0] * 100010
E = [edge() for _ in range(400040)]
class Solution:
    def spfa(self, f, n):
        Q = collections.deque()
        for i in range(1, n + 1):
            vis[i] = 0
            if f[i] != sys.maxsize:
                Q.append(i)
        while (len(Q) > 0):
            x = Q.popleft();
            vis[x] = 0
            i = G[x]
            while (i != 0):
                if (f[E[i].t] > f[x] + E[i].w):
                    f[E[i].t] = f[x] + E[i].w
                    if vis[E[i].t] == 0:
                        vis[E[i].t] = 1
                        if len(Q) == 0 or f[E[i].t] <= f[Q[0]]:
                            Q.appendleft(E[i].t);
                        else:
                            Q.append(E[i].t);
                i = E[i].nx

    def addedge(self, x, y, z):
        self.cnt += 1
        E[self.cnt].t = y
        E[self.cnt].nx = G[x]
        E[self.cnt].w = z
        G[x] = self.cnt
        self.cnt += 1
        E[self.cnt].t = x
        E[self.cnt].nx = G[y]
        E[self.cnt].w = z
        G[y] = self.cnt

    def plants(self, n, k, m):
        self.cnt = 0
        for i in range(40):
            for j in range(n + 5):
                f[i][j] = sys.maxsize
        for i in range(len(k)):
            f[1 << i][k[i]] = 0
        for i in range(len(m)):
            self.addedge(m[i][0], m[i][1], m[i][2])
        for S in range(1, (1 << len(k))):
            for i in range(1, n + 1):
                ss = ((S - 1) & S)
                while (ss != 0):
                    f[S][i] = min(f[S][i], f[ss][i] + f[S ^ ss][i])
                    ss = ((ss - 1) & S)
            self.spfa(f[S], n)
        ans = sys.maxsize
        for i in range(1, n + 1):
            ans = min(ans, f[(1 << len(k)) - 1][i])
        return ans

Java题解详见：九章soulution

3. 密钥

算法：dp

算法思路

枚举数字a，b和区间$[l,r]$，计算$[l,r]$中a和b的个数$cnt_a$和$cnt_b$，$ans=max(cnt_a−cnt_b)$

显然这样是$O(10^2n^2)$的，需要优化。

考虑换一种方式，先枚举a，然后同时对所有b做DP，定义$dp[b][i]$表示$[1,i]$的所有子段中，$cnt_a−cnt_b$的最大值，为了确保这当中的a,b数量均大于0，考虑记录两个东西：

• $dpb[0]：[1,i]$的所有子段中，$cnt_a−cnt_b$的最大值，要求$cnt_b$≠0
• $dpb[1]：[1,i]$的所有子段中，$cnt_a−cnt_b$的最大值，$cnt_b$可以为0

然后对当前字符分两种情况转移：

• $s_i=a$，所有$dp[c][i][0/1]$的值+1

• $s_i≠a$，那么更新$dp[s_i][i][0/1]$的值：

  • $dps_i[0]=dps_i[1]−1$，将$s_j$加入最优解，这样还是最优解，因为$dps_i[1]$是所有情况的最优解；
  • $dps_i[1]=max{dps_i[1]−1,0}$，如果小于0了，重新计数，因为$cnt_b$可以为0。

注意一下初值：$dpc=−∞,dpc=0$。然后时刻更新答案即可。

复杂度分析

• 时间复杂度为$O(10^2n)$

  • $n$为字符串长度

• 空间复杂度为$O(20)$

  • $n$为人数大小

题解

C++

// This solution is powered by @lintcode.com
class Solution {
public:
    int key(string &s) {
        int dp[11][2];
        int ans = 0;
        for (int x = 0; x < 10; x++) {
            for (int y = 0; y < 10; y++) {
                dp[y][0] = INT_MIN;
                dp[y][1] = 0;
            }
            for (int i = 0; i < s.size(); i++) {
                if (s[i] == x + '0') {
                    for (int y = 0; y < 10; y++) {
                        dp[y][0]++;
                        dp[y][1]++;
                        ans = max(ans, dp[y][0]);
                    }
                }
                else {
                    int y = s[i] - '0';
                    dp[y][0] = dp[y][1] - 1;
                    dp[y][1] = max(0, dp[y][1] - 1);
                    ans = max(ans, dp[y][0]);
                }
            }
        }
        return ans;
    }
};

Python

# This solution is powered by @lintcode.com
import sys
class Solution:
    def key(self, s):
        dp = [[0 for _ in range(2)] for _ in range(11)]
        ans = 0
        for x in range(10):
            for y in range(10):
                dp[y][0] = -sys.maxsize
                dp[y][1] = 0
            for i in range(len(s)):
                if ord(s[i]) == x + ord('0'):
                    for y in range(10):
                        dp[y][0] += 1
                        dp[y][1] += 1
                        ans = max(ans, dp[y][0])
                else:
                    y = ord(s[i]) - ord('0')
                    dp[y][0] = dp[y][1] - 1
                    dp[y][1] = max(0, dp[y][1] - 1)
                    ans = max(ans, dp[y][0])
        return ans;

Java题解详见：九章soulution

4. 健美

算法：枚举

算法思路

枚举$1-log_2n$作为最后剩下的组

对于组内分组计数,即每次翻倍，列如最后剩下两组，不断翻倍，直到大于总人数，这个翻倍过程就是组内分组的次数，然后按照p,v计算时间花费

更新每次枚举的花费求得最小花费

复杂度分析

• 时间复杂度为$O(logn)$
• 空间复杂度为$O(1)$

题解

C++

// This solution is powered by @lintcode.com
class Solution {
public:
    long long n,p,v;
    long long pw(long long a,long long b){
        long long res = 1;
        while(b){
            if(b & 1){
                res *= a;
            }
            a *= a;
            b >>= 1;
        }
        return res;
    }
    long long f(int k){
        long long sz = pow(n, 1.0 / k);
        long long tot = 0;
        while(pw(sz + 1, tot) * pw(sz, k - tot) < n) {
            tot++;
        }
        return (k * sz + tot) * p + k * v;
    }
    long long shortestTime(long long nn, int pp, int vv) {
        n = nn;p = pp; v = vv;
        long long ans;
        if(n == 1) {
            return 0;
        }
        ans = f(1);
        for(int i = 2; (1LL << i) <= n; i++) 
            ans = min(ans, f(i));
        return ans;
    }
};

Python

# This solution is powered by @lintcode.com
class Solution:
    def pw(self,a,b):
        res = 1
        while b > 0:
            if b & 1:
                res *= a
            a *= a
            b >>= 1
        return res
    def f(self,k):
        sz = pow(self.n, 1.0 / k)
        sz = int(sz)
        tot = 0
        while(self.pw(sz + 1, tot) * self.pw(sz, k - tot) < self.n):
            tot += 1
        return (k * sz + tot) * self.p + k * self.v
    def shortestTime(self, nn, pp, vv):
        self.n = nn
        self.p = pp
        self.v = vv
        if(nn == 1):
            return 0
        ans = self.f(1)
        i = 2
        while((1<<i) <= nn):
            ans = min(ans, self.f(i));
            i += 1
        return ans;

Java题解详见：九章soulution