1. LaTex 公式
算法思路
题目定位为较复杂的签到题，由于n很小，只有100，我们可以直接暴力枚举}加的位置，然后写一个spj判断。当然也可以用正常的表达式解析的思路，用栈来处理，找到缺失的右括号。题解的代码就是用的后者的方式用的栈处理的。只要在这个代码上稍作修改，就是本题的spj。
代码
Java
// This solution is powered by @lintcode.com
import java.util.Stack;
public class Solution {
/**
* @param s: the latex formula
* @return: fix the latex formula
*/
public String latexFormula(String s) {
int brackets = 0;
Stack<Integer> need = new Stack<Integer>();
for (int i = 0; i < (int) s.length(); i++) {
if (s.charAt(i) == '\\' || s.charAt(i) == '_' || s.charAt(i) == '^') {
if (s.charAt(i) == '\\')
i++;
switch (s.charAt(i)) {
case 'a':
case 'g':
i += 5;
break;
case 'b':
i += 4;
break;
case 'v':
case 'i':
need.push(1);
i += 2;
break;
case 'f':
need.push(2);
i += 3;
break;
case '_':
if (s.charAt(i - 1) == 't') {
need.pop();
need.push(3);
} else {
need.push(1);
}
break;
case '^':
if (s.charAt(i - 1) == 't') {
need.pop();
need.push(2);
} else {
need.push(1);
}
break;
}
} else if (s.charAt(i) == '{') {
brackets++;
if ((need.peek() == 2 || need.peek() == 3) && (s.charAt(i - 1) != 'c' && s.charAt(i - 1) != '_' && s.charAt(i - 1) != '^')) {
StringBuilder ans = new StringBuilder(s);
ans.insert(i, "}");
return ans.toString();
}
} else if (s.charAt(i) == '}') {
if (need.peek() == 2) {
if (i + 1 < s.length() && s.charAt(i + 1) == '{') {
need.pop();
need.push(1);
brackets--;
} else {
}
} else if (need.peek() == 1) {
need.pop();
brackets--;
} else if (need.peek() == 3) {
if (i + 1 < s.length()) {
if (s.charAt(i + 1) == '{') {
need.pop();
need.push(1);
brackets--;
} else if (s.charAt(i + 1) == '^') {
i += 1;
need.pop();
need.push(2);
brackets--;
} else {
}
} else {
}
}
}
}
if (brackets == 0)
return s;
return s + "}";
}
}Python
# This solution is powered by @lintcode.com
class Solution:
"""
@param s: the latex formula
@return: fix the latex formula
"""
def latexFormula(self, s):
need = []
brackets = 0
for i in range(len(s)):
if s[i] == '\\' or s[i] == '_' or s[i] == '^':
if s[i] == '\\':
i += 1
if s[i] == 'a':
i += 5
elif s[i] == 'b':
i += 4
elif s[i] == 'g':
i += 5
elif s[i] == 'v':
need.append(1)
i += 2
elif s[i] == 'f':
need.append(2)
i += 3
elif s[i] == 'i':
need.append(1)
i += 2
elif s[i] == '_':
if s[i - 1] == 't':
need.pop()
need.append(3)
else:
need.append(1)
elif s[i] == '^':
if s[i - 1] == 't':
need.pop()
need.append(2)
else:
need.append(1)
elif s[i] == '{':
brackets += 1
if (need[-1] == 2 or need[-1] == 3) and (s[i - 1] != 'c' and s[i - 1] != '_' and s[i - 1] != '^'):
s = s[:i] + '}' + s[i:]
return s
elif s[i] == '}':
if need[-1] == 2:
if i + 1 < len(s) and s[i + 1] == '{':
need.pop()
need.append(1)
brackets -= 1
elif need[-1] == 1:
need.pop()
brackets -= 1
elif need[-1] == 3:
if i + 1 < len(s):
if s[i + 1] == '{':
need.pop()
need.append(1)
brackets -= 1
elif s[i + 1] == '^':
i += 1
need.pop()
need.append(2)
brackets -= 1
if brackets == 0:
return s
return s + '}'C++题解详见：九章solution
2. 小栖的暑假
算法思路
网络流，应用了网络流的最大权闭和子图，本题的难点难在建图，我们这一题可以这样建图：
- 超级源点与每一个食物相连接
- 每一个饮料和超级汇点相连接
- 食物和有关联的饮料相连接
对于容量，这里可以把1类边的边权设置为Inf - weight_i，2类边设置为Inf，3类边设置为INF。然后我们是使用Dinic跑网络流即可。
代码
Python
# This solution is powered by @lintcode.com
import queue
class Edge:
def __init__(self, to, dis, nex):
self.to = to
self.dis = dis
self.nex = nex
class Solution:
"""
@param drink: the drinks
@param weight: the weight
@return: return the min added weight
"""
def __init__(self):
self.INF = 3000000
self.t = 0
self.s = 0
self.n = 0
self.distance = [-1 for _ in range(605)]
self.edges = [Edge(0, 0, 0) for _ in range(605 * 605)]
self.edge_num = -1
self.cur = []
self.head = []
def addEdge2(self, come, to, dis):
self.edge_num += 1
self.edges[self.edge_num].to = to
self.edges[self.edge_num].dis = dis
self.edges[self.edge_num].nex = self.head[come]
self.head[come] = self.edge_num
def addEdge(self, come, to, dis):
self.addEdge2(come, to, dis)
self.addEdge2(to, come, 0)
def dfs(self, u, flow):
if u == self.t:
return flow
flow1 = 0
c_e = self.cur[u]
while c_e != -1:
v = self.edges[c_e].to
if self.distance[v] == self.distance[u] + 1 and self.edges[c_e].dis > 0:
flow2 = self.dfs(v, min(flow, self.edges[c_e].dis))
flow -= flow2
self.edges[c_e].dis -= flow2
flow1 += flow2
self.edges[c_e ^ 1].dis += flow2
if flow == 0:
break
c_e = self.edges[c_e].nex
if flow1 == 0:
self.distance[u] = -1
return flow1
def bfs(self):
self.distance = [-1 for _ in range(605)]
que = queue.Queue(605*605)
que.put(self.s)
self.distance[self.s] = 0
while not que.empty():
u = que.get()
c_e = self.head[u]
while c_e != -1:
_new = self.edges[c_e].to
if self.distance[_new] == -1 and self.edges[c_e].dis > 0:
self.distance[_new] = self.distance[u] + 1
que.put(_new)
c_e = self.edges[c_e].nex
return self.distance[self.t] != -1
def dinic(self):
max_flow = 0
while self.bfs():
for i in range(2 * self.n + 2):
self.cur[i] = self.head[i]
max_flow += self.dfs(self.s, self.INF)
return max_flow
def solve(self, drink, weight):
self.n = len(weight)
self.INF = 3000000
self.edges = [Edge(0, 0, 0) for _ in range(605 * 605)]
self.cur = [0 for _ in range(605)]
self.head = [-1 for _ in range(605)]
self.distance = [-1 for _ in range(605)]
self.edge_num = -1
self.s = 0
self.t = 2 * self.n + 1
for i in range(1, self.n + 1):
for x in drink[i - 1]:
self.addEdge(i, x + self.n, self.INF)
all = 0
for i in range(1, self.n + 1):
all += self.INF - weight[i - 1]
self.addEdge(self.s, i, self.INF - weight[i - 1])
self.addEdge(i + self.n, self.t, self.INF)
return self.dinic() - allJava
// This solution is powered by @lintcode.com
import java.util.LinkedList;
import java.util.Queue;
class Edges {
public Edges() {
this.dis = 0;
this.to = 0;
this.next = 0;
}
int to;
int dis;
int next;
}
public class Solution {
/**
* @param drink: the drinks
* @param weight: the weight
* @return: return the min added weight
*/
public final int INF = 3000000;
int[] cur = new int[605];
int[] head = new int[605];
int[] d = new int[605];
Edges[] edges = new Edges[605 * 605 + 1];
int edge_num;
int n, s, t;
public void addEdge2(int from, int to, int dis) {
edge_num += 1;
edges[edge_num] = new Edges();
edges[edge_num].to = to;
edges[edge_num].dis = dis;
edges[edge_num].next = head[from];
head[from] = edge_num;
}
public void addEdge(int from, int to, int dis) {
addEdge2(from, to, dis);
addEdge2(to, from, 0);
}
public int DFS(int u, int flow) {
if (u == t) return flow;
int flow1 = 0, flow2;
for (int c_e = cur[u]; c_e != -1; c_e = edges[c_e].next) {
int v = edges[c_e].to;
if (d[v] == d[u] + 1 && edges[c_e].dis > 0) {
flow2 = DFS(v, Math.min(flow, edges[c_e].dis));
flow -= flow2;
edges[c_e].dis -= flow2;
flow1 += flow2;
edges[c_e ^ 1].dis += flow2;
if (flow == 0)
break;
}
}
if (flow1 == 0) d[u] = -1;
return flow1;
}
public boolean BFS() {
for (int i = 0; i <= 2 * n + 2; i++) d[i] = -1;
Queue<Integer> que = new LinkedList<Integer>();
que.add(s);
d[s] = 0;
int u, _new;
while (!que.isEmpty()) {
u = que.remove();
for (int c_e = head[u]; c_e != -1; c_e = edges[c_e].next) {
_new = edges[c_e].to;
if (d[_new] == -1 && edges[c_e].dis > 0) {
d[_new] = d[u] + 1;
que.add(_new);
}
}
}
return (d[t] != -1);
}
public long dinic() {
long max_flow = 0;
while (BFS()) {
for (int i = 0; i <= 2 * n + 1; i++) cur[i] = head[i];
max_flow += DFS(s, (int) INF);
}
return max_flow;
}
public int solve(int[][] drink, int[] weight) {
n = weight.length;
s = 0;
edge_num = -1;
t = 2 * n + 1;
for (int i = 0; i <= 2 * n + 2; i++) head[i] = -1;
for (int i = 0; i <= 2 * n + 2; i++) cur[i] = d[i] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < drink[i - 1].length; j++) {
addEdge(i, drink[i - 1][j] + n, INF);
}
}
long all = 0;
for (int i = 1; i <= n; i++) {
all += INF - weight[i - 1];
addEdge(s, i, (int) (INF - weight[i - 1]));
addEdge(i + n, t, INF);
}
return (int) (dinic() - all);
}
}C++题解详见：九章solution
3. 小栖的扩音器
算法思路
正解是高斯消元，我们一共设立n+1个方程，其中最后一个是麦克风的方程，麦克风音量我们可以任意假设，扩音器的音量和麦克风的音量是成正比的。
当然有部分同学使用了拓扑排序等错误算法通过了此题，非常抱歉，我们增加了部分卡拓扑排序的数据，但没有卡住。这里的扩音器之间的关系其实是有环的，如果有环，就可能会出现无穷大音量。而无穷大音量的竖线，其实并不需要一定有一个乘积>1的环。可能有多个环的和>1得到。
代码
Java
// This solution is powered by @lintcode.com
public class Solution {
/**
* @param n: the number of loudspeaker
* @param minVolume: the minVolume the micro
* @param maxVolume: the maxVolume the micro
* @param edges: the edges
* @param times: the times of edge
* @param s: the volume you need
* @return: return the min volume the micro need
*/
final static double eps = 1e-6;
final static int maxn = 330;
int n, m, l, r;
double[][] a = new double[maxn][maxn];
double[] ans = new double[maxn];
int Gauss() {
for (int i = 1; i <= n; ++i) {
int r = i;
for (int j = i + 1; j <= n; ++j)
if (Math.abs(a[j][i]) > Math.abs(a[r][i]))
r = j;
if (Math.abs(a[r][i]) < eps) {
return 1;
}
if (r != i) {
//swap(a[i], a[r]);
for (int pos = 1; pos <= n; pos++) {
double tmp = a[i][pos];
a[i][pos] = a[r][pos];
a[r][pos] = tmp;
}
}
double div = a[i][i];
for (int j = i; j <= n + 1; ++j)
a[i][j] /= div;
for (int j = i + 1; j <= n; ++j) {
div = a[j][i];
for (int k = i; k <= n + 1; ++k)
a[j][k] -= div * a[i][k];
}
}
ans[n] = a[n][n + 1];
for (int i = n - 1; i >= 1; --i) {
ans[i] = a[i][n + 1];
for (int j = i + 1; j <= n; ++j)
ans[i] -= a[i][j] * ans[j];
}
return 0;
}
public double minMicro(int nn, int minVolume, int maxVolume, int[][] edges, double[] times, double s) {
n = nn;
m = edges.length;
l = minVolume;
r = maxVolume;
for (int i = 0; i < m; i++)
a[edges[i][1]][edges[i][0]] = times[i];
for (int i = 1; i <= n; ++i)
a[i][i] = -1;
a[1][n + 1] = 1;
a[n + 1][n + 1] = 1;
a[n + 1][n + 2] = l;
n++;
if (Gauss() != 0) return -1;
n--;
boolean flag = false;
double minv = 1e16;
for (int i = 1; i <= n; ++i) {
if (ans[i] < 0 || ans[i] > s) {
flag = true;
break;
}
if (ans[i] > eps) {
double tmp = s * l / ans[i];
if (tmp >= l && tmp <= r && tmp < minv)
minv = tmp;
}
}
if (flag)
return l;
else if (minv < 1e16)
return minv;
return -1;
}
}Python
# This solution is powered by @lintcode.com
class Solution:
"""
@param n: the number of loudspeaker
@param minVolume: the minVolume the micro
@param maxVolume: the maxVolume the micro
@param edges: the edges
@param times: the times of edge
@param s: the volume you need
@return: return the min volume the micro need
"""
def Gauss(self):
for i in range(1, self.n + 1):
rr = i
for j in range(i + 1, self.n + 1):
if abs(self.a[j][i]) > abs(self.a[rr][i]):
rr = j
if abs(self.a[rr][i]) < self.eps:
return 1
if rr != i:
self.a[i], self.a[rr] = self.a[rr], self.a[i]
div = self.a[i][i]
for j in range(i, self.n + 1 + 1):
self.a[i][j] /= div
for j in range(i + 1, self.n + 1):
div = self.a[j][i]
for k in range(i, self.n + 1 + 1):
self.a[j][k] -= div * self.a[i][k]
self.ans[self.n] = self.a[self.n][self.n + 1]
for i in range(self.n - 1, 0, -1):
self.ans[i] = self.a[i][self.n + 1]
for j in range(i + 1, self.n + 1):
self.ans[i] -= self.a[i][j] * self.ans[j]
return 0
def minMicro(self, nn, minVolume, maxVolume, edges, times, s):
self.n = nn
self.m = len(edges)
self.l = minVolume
self.r = maxVolume
self.eps = 1e-8
self.ans = [0 for _ in range(220)]
self.a = [[0 for __ in range(220)] for _ in range(220)]
for i in range(self.m):
self.a[edges[i][1]][edges[i][0]] = times[i]
for i in range(1, self.n + 1):
self.a[i][i] = -1
self.a[1][self.n + 1] = 1
self.a[self.n + 1][self.n + 1] = 1
self.a[self.n + 1][self.n + 2] = self.l
self.n += 1
if self.Gauss():
return -1
self.n -= 1
f = 0
min_val = 1e16
for i in range(1, self.n + 1):
if self.ans[i] < 0 or self.ans[i] > s:
f = 1
break
if self.ans[i] > self.eps:
tmp = s * self.l / self.ans[i]
if self.l <= tmp <= self.r and tmp < min_val:
min_val = tmp
if f != 0:
return self.l
elif min_val < 1e16:
return min_val
return -1C++题解详见：九章solution
4. 点亮灯
算法思路
这是一个树上dp，一个很显然的结论是，每个灯只会操作一次。如果操作多次，每2次都会抵消。
那么我们让f[x][0/1][0/1]表示以x为根的子树，x灯亮(1)或灭(0)且其子树全亮，x是(1)否(0)进行操作，需要的最少操作次数。
我们分以下几种状态进行转移
- x灯不进行操作，即求出
f[x][0/1][0]
子树必须全部取f[son][1][0/1]，我们每次都取较小的那一个得到所有儿子总操作数为sum。
假设每次取较小的那一个，得到所有儿子的总操作次数为w次
我们只关心w的奇偶，w=1(奇),0(偶)
f[x][w^a[x]][0]=sum
我们找到abs(f[son][1][0]-f[son][1][1])最小的记为mn
f[x][w^a[x]^1][0]=sum+mn
- x灯进行操作，即求出
f[x][0/1][1]
子树必须全部取f[son][0][0/1]，我们每次都取较小的那一个得到所有儿子总操作数为sum。
假设每次取较小的那一个，得到所有儿子的总操作次数为w次
我们只关心w的奇偶，w=1(奇),0(偶)f[x][w^a[x]^1][1]=sum+1
我们找到abs(f[son][0][0]-f[son][0][1])最小的记为mnf[x][w^a[x]][1]=sum+1+mn
最终的答案就是min(f[rt][1][0],f[rt][1][1])
代码
Java
// This solution is powered by @lintcode.com
public class Solution {
public long[][][] f;
public void dfs(int x,int fa,boolean[] a,ArrayList<ArrayList<Integer>> g){
long sum0 = 0, sum1 = 0;
int cnt0 = 0, cnt1 = 0;
long mn0 = Integer.MAX_VALUE, mn1 = Integer.MAX_VALUE;
for (int i = 0; i < g.get(x).size(); i++) {
int q = g.get(x).get(i);
if (q == fa)
continue;
dfs(q, x, a, g);
if (f[q][0][0] <= f[q][0][1]) {
sum0 += f[q][0][0];
mn0 = Math.min(mn0, f[q][0][1] - f[q][0][0]);
} else {
sum0 += f[q][0][1];
mn0 = Math.min(mn0, f[q][0][0] - f[q][0][1]);
cnt0 ^= 1;
}
if (f[q][1][0] <= f[q][1][1]) {
sum1 += f[q][1][0];
mn1 = Math.min(mn1, f[q][1][1] - f[q][1][0]);
} else {
sum1 += f[q][1][1];
mn1 = Math.min(mn1, f[q][1][0] - f[q][1][1]);
cnt1 ^= 1;
}
}
f[x][0][0] = f[x][0][1] = f[x][1][0] = f[x][1][1] = Integer.MAX_VALUE;
int tem = a[x - 1] == true?1:0;
f[x][tem ^ cnt1][0] = Math.min(f[x][tem ^ cnt1][0], sum1);
f[x][tem ^ cnt1 ^ 1][0] = Math.min(f[x][tem ^ cnt1 ^ 1][0], sum1 + mn1);
f[x][tem ^ cnt0 ^ 1][1] = Math.min(f[x][tem ^ cnt0 ^ 1][1], sum0 + 1);
f[x][tem ^ cnt0][1] = Math.min(f[x][tem ^ cnt0][1], sum0 + mn0 + 1);
}
public int solve(int[][] edges, boolean[] light) {
int n = light.length;
ArrayList<ArrayList<Integer>> G = new ArrayList<ArrayList<Integer>>();
for(int i = 0;i<=n;i++){
G.add(new ArrayList<Integer>());
}
for (int i = 0; i < n - 1; i++) {
G.get(edges[i][0]).add(edges[i][1]);
G.get(edges[i][1]).add(edges[i][0]);
}
f = new long[100005][2][2];
dfs(1, 0, light, G);
int ans = (int)Math.min(f[1][1][0], f[1][1][1]);
if (ans > n)
return -1;
return ans;
}
}Python
# This solution is powered by @lintcode.com
import sys
f = [[[0 for _ in range(2)] for _ in range(2)] for _ in range(100005)]
class Solution:
def dfs(self,x,fa,a,g):
sum0,sum1 = 0,0
cnt0,cnt1 = 0,0
mn0,mn1 = sys.maxsize,sys.maxsize
for i in range(len(g[x])):
q = g[x][i]
if q == fa:
continue
self.dfs(q, x, a, g)
if f[q][0][0] <= f[q][0][1]:
sum0 += f[q][0][0]
mn0 = min(mn0, f[q][0][1] - f[q][0][0])
else:
sum0 += f[q][0][1]
mn0 = min(mn0, f[q][0][0] - f[q][0][1])
cnt0 ^= 1
if f[q][1][0] <= f[q][1][1]:
sum1 += f[q][1][0]
mn1 = min(mn1, f[q][1][1] - f[q][1][0])
else:
sum1 += f[q][1][1]
mn1 = min(mn1, f[q][1][0] - f[q][1][1])
cnt1 ^= 1
f[x][0][0],f[x][0][1] = sys.maxsize,sys.maxsize
f[x][1][0],f[x][1][1] = sys.maxsize,sys.maxsize
f[x][a[x - 1] ^ cnt1][0] = min(f[x][a[x - 1] ^ cnt1][0], sum1)
f[x][a[x - 1] ^ cnt1 ^ 1][0] = min(f[x][a[x - 1] ^ cnt1 ^ 1][0], sum1 + mn1)
f[x][a[x - 1] ^ cnt0 ^ 1][1] = min(f[x][a[x - 1] ^ cnt0 ^ 1][1], sum0 + 1)
f[x][a[x - 1] ^ cnt0][1] = min(f[x][a[x - 1] ^ cnt0][1], sum0 + mn0 + 1)
def solve(self, edges, light):
n = len(light)
G = [[] for _ in range(n + 1) ]
for i in range(n-1):
G[edges[i][0]].append(edges[i][1])
G[edges[i][1]].append(edges[i][0])
self.dfs(1, 0, light, G)
ans = min(f[1][1][0],f[1][1][1])
if (ans > n):
return -1
return ans
