跳转至

ABC343(A-G)

A - Wrong Answer

题目大意

给你两个数 \(A\) 和 \(B\)，在 \(0\) 到 \(9\) 中任意输出一个不等于 \(A + B\) 的数。

参考代码 
#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    int x = 0;
    if(x == a + b)
        x++;
    cout << x << endl;
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int x = 0;
        if (x == a + b)
            x++;
        System.out.println(x);
        in.close();
    }
}

B - Adjacency Matrix

题目大意

给你一个无向图的邻接矩阵，输出每个点的邻居。

参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 100 + 10;
int n, g[maxn][maxn];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> g[i][j];
    for(int i = 1; i <= n; i++, puts("")) 
        for(int j = 1; j <= n; j++)
            if(g[i][j])
                printf("%d ", j);
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] g = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = in.nextInt();
        for (int i = 1; i <= n; i++, System.out.println())
            for (int j = 1; j <= n; j++)
                if (g[i][j] > 0)
                    System.out.printf("%d ", j);
        in.close();
    }
}

C - 343

题目大意

给你一个正整数 \(N(N \le 10^{18})\)，找到第一个小于等于 \(N\) 的完全立方数 \(K\)，使得 \(K\) 是一个回文数。

解题思路

直接枚举判断就好，唯一要注意的就是 pow(1, 1/3.0) 转化成整数的时候可能会有丢失精度，需要补一个 eps。

参考代码 
#include <iostream>
#include <cmath>

using namespace std;

typedef long long LL;

int s[20];

bool check(LL x)
{
    int idx = 0;
    while(x)
    {
        int t = x % 10;
        s[idx++] = t;
        x /= 10;
    }
    for(int i = 0, j = idx - 1; i < j; i++, j--)
        if(s[i] != s[j])
            return 0;
    return 1;
}

int main()
{
    LL n;
    cin >> n;
    LL x = floor(pow(n, 1/3.0)+1E-8);
    while(!check(x*x*x))
        x--;
    cout << x*x*x << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    private static int[] s = new int[20];

    private static boolean check(long x) {
        int idx = 0;
        while (x > 0) {
            int t = (int) (x % 10);
            s[idx++] = t;
            x /= 10;
        }
        for (int i = 0, j = idx - 1; i < j; i++, j--)
            if (s[i] != s[j])
                return false;
        return true;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long x = (long) (Math.pow(n, 1 / 3.0) + 1E-8);
        while (!check(x * x * x))
            x--;
        System.out.println(x * x * x);
        in.close();
    }
}

D - Diversity of Scores

题目大意

有一场比赛有 \(N(N \le 2 \times 10^5)\) 个队伍，初始的时候每个队伍得分都是 \(0\)。在接下来的 \(T\) 秒内，每一秒都有一个队伍增加一定的分数，用 \(A_i\ B_i\) 表示第 \(i\) 秒的时候第 \(A_i\) 个队伍的分数增加了 \(B_i\)。在每一秒有队伍的分数增加之后，回答场上有多少个不同的分数值。

解题思路

数组维护每个队伍的分数，哈希表维护每个分数有多少只队伍即可。

参考代码 
#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;
int n, T;
unordered_map<LL, int> cnt;
LL A[maxn];

int main()
{
    cin >> n >> T;
    cnt[0] = n;
    while(T--)
    {
        int i, x;
        scanf("%d %d", &i, &x);
        if(--cnt[A[i]] == 0)
            cnt.erase(A[i]);
        A[i] += x;
        if(cnt.count(A[i]) == 0)
            cnt[A[i]] = 1;
        else
            cnt[A[i]]++;
        printf("%ld\n", cnt.size());
    }
    return 0;
}

import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int T = in.nextInt();
        HashMap<Long, Integer> cnt = new HashMap<>();
        long[] A = new long[n + 1];
        cnt.put(0l, n);
        while (T-- > 0) {
            int i = in.nextInt();
            int x = in.nextInt();
            cnt.put(A[i], cnt.get(A[i]) - 1);
            if (cnt.get(A[i]) == 0)
                cnt.remove(A[i]);
            A[i] += x;
            cnt.put(A[i], cnt.getOrDefault(A[i], 0) + 1);
            System.out.println(cnt.size());
        }
        in.close();
    }
}

E - 7x7x7

题目大意

你有三个边长为 \(7\) 的正方体，你可以将他们放在坐标绝对值 \(100\) 以内的空间中，假设一个正方体占据的空间是 \((a \le x \le a+7) \land （b \le y \le b+7) \land （c \le z \le c+7)\)，则可以用一个三元组 \((a, b, c)\) 来表示这个正方体的位置。

给你三个整数 \(V_1 \ V_2 \ V_3\)，含义如下：

  • \(V_1\) 表示三个正方体互不相交的体积。
  • \(V_2\) 表示恰好有两个正方体相交的体积。
  • \(V_3\) 表示恰好有三个正方体相交的体积。

问：是否存在一种摆放方法，满足上述的三个数字？如果存在首先输出 Yes，然后输出三个正方体的位置。如果不存在输出 No。

解题思路

非常恶心的题目，理解原文的题意+对照样例就花了我很长时间。

首先考虑到边长只有 \(7\)，将其中一个正方体固定在 \((0, 0, 0)\)，则剩下的两个正方体只需要考虑 \([-7, 7]\) 这个坐标范围的就可以了。这样我们可以枚举出 \(14^6 \approx 7 \times 10^6\) 的所有情况。

下面考虑如何验证是否符合条件，首先算出 \(V_3\)，因为三个物体都是正方体，则相交的物体一定是长方体，其边的取值范围就是对应边的并集。例如 \((0 \le x \le 7) \land (2 \le x \le 9) \land (4 \le x \le 11) = 4 \le x \le 7\)，所以 \(V_3\) 是很容易算出来的。

至于 \(V_2\)，两两枚举并计算合并后的长方体，得到的体积需要减去 \(V_3\)。

\(V_1\) 的计算，不妨设两两相交的体积为 \(V_{1-2}\)，\(V_{1-3}\) 和 \(V_{2-3}\)，则正方体独占的体积为:

\[ V_{1'} = 7^3 - V_{1-2} - V_{1-3} - V_3 \\ V_{2'} = 7^3 - V_{1-2} - V_{2-3} - V_3 \\ V_{3'} = 7^3 - V_{1-3} - V_{2-3} - V_3 \\ \]

三者相加可得 \(V_1 = 7^3 \times3 - 2V_2-3V_3\)

参考代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int v[4];
struct Line {
    int l, r;
    Line() : l(0), r(7) {}
    Line(int x) : l(x), r(x + 7) {}
    Line(int x, int y) : l(x), r(y) {}
    int length() const {return r - l;}
};
Line merge(const Line &x, const Line &y)
{
    if(x.l > y.l)
        return merge(y, x);
    return Line(min(x.r, y.l), min(x.r, y.r));
}

struct Cube {
    Line x, y, z;
    Cube() : x(), y(), z() {}
    Cube(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
    Cube(const Line &a,const Line &b, const Line &c) : x(a), y(b), z(c) {}
    int volume() const {return x.length() * y.length() * z.length();}
};

Cube merge(const Cube &a, const Cube &b)
{return Cube(merge(a.x, b.x), merge(a.y, b.y), merge(a.z, b.z));}

Cube c[4];

int main()
{
    cin >> v[1] >> v[2] >> v[3];
    for(int x2 = -7; x2 <= 7; x2++)
        for(int y2 = -7; y2 <= 7; y2++)
            for(int z2 = -7; z2 <= 7; z2++)
            {
                c[2] = Cube(x2, y2, z2);
                Cube m12 = merge(c[1], c[2]);
                for(int x3 = -7; x3 <= 7; x3++)
                    for(int y3 = -7; y3 <= 7; y3++)
                        for(int z3 = -7; z3 <= 7; z3++)
                        {
                            c[3] = Cube(x3, y3, z3);
                            Cube m123 = merge(m12, c[3]);
                            if(m123.volume() != v[3])
                                continue;
                            Cube m13 = merge(c[1], c[3]);
                            Cube m23 = merge(c[2], c[3]);
                            if(m12.volume() + m13.volume() + m23.volume() - 3 * v[3] != v[2])
                                continue;
                            if(7*7*7*3 - 2*v[2] - 3*v[3] == v[1])
                            {
                                printf("Yes\n0 0 0 %d %d %d %d %d %d\n", x2, y2, z2, x3, y3, z3);
                                return 0;
                            }
                        }
            }
    puts("No");
    return 0;
}

import java.util.Scanner;

class Line {
    public int l, r;

    public Line() {
        l = 0;
        r = 7;
    }

    public Line(int x) {
        l = x;
        r = x + 7;
    }

    public Line(int x, int y) {
        l = x;
        r = y;
    }

    public int length() {
        return r - l;
    }

}

class Cube {
    public Line x, y, z;

    public Cube() {
        x = new Line();
        y = new Line();
        z = new Line();
    }

    public Cube(int _x, int _y, int _z) {
        x = new Line(_x);
        y = new Line(_y);
        z = new Line(_z);
    }

    public Cube(Line a, Line b, Line c) {
        x = a;
        y = b;
        z = c;
    }

    public int volume() {
        return x.length() * y.length() * z.length();
    }

}

public class Main {
    private static Line merge(Line x, Line y) {
        if (x.l > y.l)
            return merge(y, x);
        return new Line(Math.min(x.r, y.l), Math.min(x.r, y.r));
    }

    private static Cube merge(Cube a, Cube b) {
        return new Cube(merge(a.x, b.x), merge(a.y, b.y), merge(a.z, b.z));
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] v = new int[4];
        Cube[] c = new Cube[4];
        c[1] = new Cube();
        for (int i = 1; i <= 3; i++)
            v[i] = in.nextInt();
        for (int x2 = -7; x2 <= 7; x2++)
            for (int y2 = -7; y2 <= 7; y2++)
                for (int z2 = -7; z2 <= 7; z2++) {
                    c[2] = new Cube(x2, y2, z2);
                    Cube m12 = merge(c[1], c[2]);
                    for (int x3 = -7; x3 <= 7; x3++)
                        for (int y3 = -7; y3 <= 7; y3++)
                            for (int z3 = -7; z3 <= 7; z3++) {
                                c[3] = new Cube(x3, y3, z3);
                                Cube m123 = merge(m12, c[3]);
                                if (m123.volume() != v[3])
                                    continue;
                                Cube m13 = merge(c[1], c[3]);
                                Cube m23 = merge(c[2], c[3]);
                                if (m12.volume() + m13.volume() + m23.volume() - 3 * v[3] != v[2])
                                    continue;
                                if (7 * 7 * 7 * 3 - 2 * v[2] - 3 * v[3] == v[1]) {
                                    System.out.printf("Yes\n0 0 0 %d %d %d %d %d %d\n", x2, y2, z2, x3, y3, z3);
                                    return;
                                }
                            }
                }
        System.out.println("No");
        in.close();
    }
}

F - Second Largest Query

题目大意

给你 \(N(N \le 2 \times 10^5)\) 个数，第 \(i\) 个数是 \(A_i\)，有 \(Q(Q \le 2 \times 10^5)\) 个操作，操作有两种，第一种操作是单点修改，第二种操作是询问一个区间内第二大的数字出现的次数。

解题思路

如果会用线段树维护区间次大值的话，这道题只需要再加上出现次数就好。（实际就是模板提，私以为这道题比上一题简单。）

参考代码 
#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

const int maxn = 2E5 + 10;
int n, a[maxn];

struct Node {
    int num[2], cnt[2];
    Node() {num[0] = num[1] = cnt[0] = cnt[1] = 0;}
}t[maxn * 4];

Node pushup(const Node &x, const Node &y)
{
    map<int, int> mp;
    mp[x.num[0]] += x.cnt[0];
    mp[x.num[1]] += x.cnt[1];
    mp[y.num[0]] += y.cnt[0];
    mp[y.num[1]] += y.cnt[1];
    auto it = mp.rbegin();
    Node res;
    res.num[0] = it -> first;
    res.cnt[0] = it -> second;
    it++;
    res.num[1] = it -> first;
    res.cnt[1] = it -> second;
    return res;
}

void build(int p, int beg, int end)
{
    if(beg == end)
    {
        t[p].num[0] = a[beg];
        t[p].cnt[0] = 1;
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = 2 * p + 1;
    build(lch, beg, mid);
    build(rch, mid+1, end);
    t[p] = pushup(t[lch], t[rch]);
}

void update(int p, int beg, int end, int pos, int k)
{
    if(beg == end)
    {
        t[p].num[0] = k;
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = 2 * p + 1;
    pos <= mid ? update(lch, beg, mid, pos, k) : update(rch, mid+1, end, pos, k);
    t[p] = pushup(t[lch], t[rch]);
}

Node ask(int p, int beg, int end, int l, int r)
{
    if(end < l || beg > r)
        return Node();
    if(beg >= l && end <= r)
        return t[p];
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = 2 * p + 1;
    return pushup(ask(lch, beg, mid, l, r), ask(rch, mid+1, end, l, r));
}

int main()
{
    int t;
    cin >> n >> t;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    while(t--)
    {
        int op, p, x, l, r;
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d %d", &p, &x);
            update(1, 1, n, p, x);
        }
        else
        {
            scanf("%d %d", &l, &r);
            printf("%d\n", ask(1, 1, n, l, r).cnt[1]);
        }
    }
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.TreeMap;

class Node {
    public int[] num, cnt;

    Node() {
        num = new int[2];
        cnt = new int[2];
    }
}

public class Main {
    static FastReader in = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);

    private static Node[] t;
    private static int[] a;

    private static Node pushup(Node x, Node y) {
        TreeMap<Integer, Integer> mp = new TreeMap<>(Collections.reverseOrder());
        mp.put(x.num[0], mp.getOrDefault(x.num[0], 0) + x.cnt[0]);
        mp.put(x.num[1], mp.getOrDefault(x.num[1], 0) + x.cnt[1]);
        mp.put(y.num[0], mp.getOrDefault(y.num[0], 0) + y.cnt[0]);
        mp.put(y.num[1], mp.getOrDefault(y.num[1], 0) + y.cnt[1]);
        var it = mp.entrySet().iterator();
        Node res = new Node();
        var entry = it.next();
        res.num[0] = entry.getKey();
        res.cnt[0] = entry.getValue();
        entry = it.next();
        res.num[1] = entry.getKey();
        res.cnt[1] = entry.getValue();
        return res;
    }

    private static void build(int p, int beg, int end) {
        t[p] = new Node();
        if (beg == end) {
            t[p].num[0] = a[beg];
            t[p].cnt[0] = 1;
            return;
        }
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = 2 * p + 1;
        build(lch, beg, mid);
        build(rch, mid + 1, end);
        t[p] = pushup(t[lch], t[rch]);
    }

    private static void update(int p, int beg, int end, int pos, int k) {
        if (beg == end) {
            t[p].num[0] = k;
            return;
        }
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = 2 * p + 1;
        if (pos <= mid)
            update(lch, beg, mid, pos, k);
        else
            update(rch, mid + 1, end, pos, k);
        t[p] = pushup(t[lch], t[rch]);
    }

    private static Node ask(int p, int beg, int end, int l, int r) {
        if (end < l || beg > r)
            return new Node();
        if (beg >= l && end <= r)
            return t[p];
        int mid = (beg + end) / 2;
        int lch = p * 2, rch = 2 * p + 1;
        return pushup(ask(lch, beg, mid, l, r), ask(rch, mid + 1, end, l, r));
    }

    public static void main(String[] args) {
        int n = in.nextInt();
        int T = in.nextInt();
        t = new Node[4 * n];
        a = new int[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = in.nextInt();
        build(1, 1, n);
        while (T-- > 0) {
            int op, p, x, l, r;
            op = in.nextInt();
            if (op == 1) {
                p = in.nextInt();
                x = in.nextInt();
                update(1, 1, n, p, x);
            } else {
                l = in.nextInt();
                r = in.nextInt();
                out.printf("%d\n", ask(1, 1, n, l, r).cnt[1]);
            }
        }

        out.flush();
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

G - Compress Strings

题目大意

给你 \(N(N \le 20)\) 个字符串，第 \(i\) 个字符串是 \(S_i(\sum |S_i| \le 2 \times 10^5)\)。构造一个最短的字符串 \(T\) ，使得所有的 \(S_i\) 都是 \(T\) 的子串。

解题思路

如果 \(S_i\) 包含了 \(S_j\)，则可以不考虑 \(S_j\)，直接将其删除。

假设有字符串 \(X\) 和字符串 \(Y\)，要将其压缩成一个最短的字符串 \(Z\)，这个问题可以用 kmp 或者 字符串哈希 在 \(O(|X|+|Y|)\) 的时间内解决。以 kmp 为例：在求子串匹配时，我们将两个字符串拼接成 \(Y\#X\)，然后不断算出 前缀函数 的值，而 前缀函数 的定义 \(ne[i]\) 表示 \([0, i]\) 这段字符串中真前缀与真后缀相等的最大长度，这意味着匹配到最后时（假设此时的前缀函数值为 \(j\)，\(|X| = n\)，\(|Y| = m\)），此时有 \(Y_0Y_1\cdots Y_{j-1} = X_{n-j+1}X_{n-j+2}\cdots{X_n}\)，于是就可以压缩成 \(X_0X_1 \cdots X_{n-j+1}X_{n-j+2}\cdots{X_n}Y_jY_{j+1} \cdots Y_{m-1}\)，这样一定是最短的。

由于 \(N \le 20\)，我们可以两两处理字符串，处理出一个二维数组 \(cost[i][j]\)，表示将第 \(j\) 个字符串拼接在第 \(i\) 个字符串后所增加的字符个数，这个值在 kmp 结束时可以算出是 \(m-j\)。预处理出所有的 \(cost[i][j]\) 的时间复杂度是 \(O(N\times \sum|S_i|)\)

如何构造出最短的答案？考虑 状压dp，定义 \(dp[s][j]\)：已经构造出了集合 \(s\) 中的字符串，且最后一个字符串是 \(j\) 的所有方案中的最短长度，转移时只需要枚举上一步是哪个字符串 \(i\)，则有： $$ dp[s][j] = \min_{i \in s}{dp[s\backslash i][i]} $$ 其中，\(s\backslash i\) 表示 \(s\) 去掉第 \(i\) 个字符串之后的集合。这个 dp 的时间复杂度是 \(O(2^NN^2)\) 的。

因此总的时间复杂度为 \(O(N\sum|S_i|+N^22^N)\)。

参考代码 
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int maxn = 20 + 5;
const int maxs = (1 << 20) + 10;
const int inf  = 1E8;

int n;
vector<int> ne[maxn];
string str[maxn];
bool del[maxn];

int cost[maxn][maxn], dp[maxs][maxn];

int DP(int s, int j)
{
    if(dp[s][j] != -1)
        return dp[s][j];
    dp[s][j] = inf;
    int ls = s ^ 1 << j;
    for(int i = 0; i < n; i++)
        if(ls >> i & 1)
            dp[s][j] = min(dp[s][j], DP(ls, i)+cost[i][j]);
    return dp[s][j];
}

void getnext(const string &s, vector<int> &ne)
{
    int m = s.size();
    for(int i = 1, j = 0; i < m; i++)
    {
        while(j && s[i] != s[j])
            j = ne[j-1];
        if(s[i] == s[j])
            j++;
        ne[i] = j;
    }
}

int kmp(const string &p, const string &t, const vector<int> &ne)
{
    int n = t.size(), m = p.size(), j = 0;
    for(int i = 0; i < n; i++)
    {
        while(j && t[i] != p[j])
            j = ne[j-1];
        if(t[i] == p[j])
            if(++j == m)
                break;
    }
    return j;
}

int main()
{
    cin >> n;   
    for(int i = 0; i < n; i++)
    {
        cin >> str[i];
        ne[i].resize(str[i].size());
        getnext(str[i], ne[i]);
    }
    for(int i = 0; i < n; i++)
    {
        if(del[i])
            continue;
        for(int j = 0; j < n; j++)
        {
            if(i == j || del[j])
                continue;
            cost[i][j] = str[j].size() - kmp(str[j], str[i], ne[j]);
            if(!cost[i][j])
                del[j] = 1;
        }
    }
    int ans = inf, mask = 0;
    memset(dp, -1, sizeof dp);
    for(int i = 0; i < n; i++) 
        if(!del[i])
        {
            dp[1 << i][i] = str[i].size();
            mask |= 1 << i;
        }
    for(int i = 0; i < n; i++)
        if(!del[i])
            ans = min(ans, DP(mask, i));
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int inf = (int) 1E8;

    private static int n;
    private static int[][] ne, dp, cost;
    private static String[] str;

    private static int DP(int s, int j) {
        if (dp[s][j] != -1)
            return dp[s][j];
        dp[s][j] = inf;
        int ls = s ^ 1 << j;
        for (int i = 0; i < n; i++)
            if ((ls >> i & 1) > 0)
                dp[s][j] = Math.min(dp[s][j], DP(ls, i) + cost[i][j]);
        return dp[s][j];
    }

    private static int[] getnext(String s) {
        int m = s.length();
        int[] ne = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j))
                j = ne[j - 1];
            if (s.charAt(i) == s.charAt(j))
                j++;
            ne[i] = j;
        }
        return ne;
    }

    private static int kmp(String p, String t, int[] ne) {
        int n = t.length(), m = p.length(), j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && t.charAt(i) != p.charAt(j))
                j = ne[j - 1];
            if (t.charAt(i) == p.charAt(j))
                if (++j == m)
                    break;
        }
        return j;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        ne = new int[n][];
        str = new String[n];
        dp = new int[1 << n][n];
        cost = new int[n][n];
        for (int i = 0; i < n; i++) {
            str[i] = in.next();
            ne[i] = getnext(str[i]);
        }
        boolean[] del = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (del[i])
                continue;
            for (int j = 0; j < n; j++) {
                if (i == j || del[j])
                    continue;
                cost[i][j] = str[j].length() - kmp(str[j], str[i], ne[j]);
                if (cost[i][j] == 0)
                    del[j] = true;
            }
        }
        int ans = inf, mask = 0;
        for (int i = 0; i < (1 << n); i++)
            for (int j = 0; j < n; j++)
                dp[i][j] = -1;
        for (int i = 0; i < n; i++)
            if (!del[i]) {
                dp[1 << i][i] = str[i].length();
                mask |= 1 << i;
            }
        for (int i = 0; i < n; i++)
            if (!del[i])
                ans = Math.min(ans, DP(mask, i));
        System.out.println(ans);
        in.close();
    }
}
最后更新: 2024-03-08
创建日期: 2024-03-05