# 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

# 2. 吃鸡

### 算法：最小斯坦纳树

#### 算法思路

• 当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++){
}

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

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)):
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

# 3. 密钥

### 算法：dp

#### 算法思路

• $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。

#### 复杂度分析

• 时间复杂度为$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;

# 4. 健美

### 算法：枚举

#### 复杂度分析

• 时间复杂度为$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;


+ 订阅