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 - ansJava题解详见：九章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加点优化跑最短路的求解即可。
- 将k能取到的所有点都排除在外，保证答案尽可能优。
复杂度分析
-
时间复杂度为$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 ansJava题解详见：九章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;
