天池×九章算法|超级码力在线编程大赛 决赛题解-阿里云开发者社区

开发者社区> 算法编程> 正文

天池×九章算法|超级码力在线编程大赛 决赛题解

简介: 本解析由九章算法旗下专业刷题平台领扣@lintcode.com提供

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. 超级源点与每一个食物相连接
  2. 每一个饮料和超级汇点相连接
  3. 食物和有关联的饮料相连接

对于容量,这里可以把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() - all

Java

// 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 -1

C++题解详见:九章solution

4. 点亮灯

算法思路

这是一个树上dp,一个很显然的结论是,每个灯只会操作一次。如果操作多次,每2次都会抵消。

那么我们让f[x][0/1][0/1]表示以x为根的子树,x灯亮(1)或灭(0)且其子树全亮,x是(1)否(0)进行操作,需要的最少操作次数。

我们分以下几种状态进行转移

  1. 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

  1. 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])

代码

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

C++题解详见:九章solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接