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跑網絡流即可。
# 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() - all // 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);
}
} 3. 小栖的擴音器
正解是高斯消元，我們一共設立
n+1
個方程，其中最後一個是麥克風的方程，麥克風音量我們可以任意假設，擴音器的音量和麥克風的音量是成正比的。
當然有部分同學使用了拓撲排序等錯誤算法通過了此題，非常抱歉，我們增加了部分卡拓撲排序的資料，但沒有卡住。這裡的擴音器之間的關系其實是有環的，如果有環，就可能會出現無窮大音量。而無窮大音量的豎線，其實并不需要一定有一個乘積>1的環。可能有多個環的和>1得到。
// 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;
}
} # 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 -1 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])
mn
f[x][w^a[x]][1]=sum+1+mn
最終的答案就是
min(f[rt][1][0],f[rt][1][1])
// 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;
}
} # 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 ![【python】【資料處理】畫多元資料分布圖[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)