【思维题】Codeforces 1560E Polycarp and String Transformation
|
374
|
思维题
|
tdiant

题意

对于两个字符串s1和s2。
先把s3和s4都设为s1，然后循环这样的操作：

  1. 对于第i次操作，从s3里把s2字符串的第i个字符全部删掉。
  2. 然后把s3加在s4的最后面。
  3. 知道s2里的字符全部都扫一遍结束。

举个例子：
s1是abacaba，s2是bac，那么步骤是这样的：

  1. 一开始，s4就是s1，也就是abacaba
  2. 第1次操作：把所有b删掉（s2第1个字符，结果即aacaa）加后面，s4变成abacabaaacaa
  3. 第2次操作，把所有a删掉（s2第1个字符，结果即c）加后面，s4变成abacabaaacaac
  4. 第3次操作，把所有c删掉，现在删干净了，把空串加到s4后面。
  5. s4最后就是abacabaaacaac了！

你以为这是个模拟，给你一个s1和一个s2让你求s4？NAIVE！
这个题给你t个s4，让你反求每个s4对应的s1和s2是什么。

如果推不出来，输出-1。

思路

关键点1：可以发现，如果我把s4从后到前扫一遍，看看每种字符第一次出现的次序是怎样的，把每种字符按次序写出来，这个写出来的字符串正好是s2倒过来

比如：abacabaaacaac，从后往前看，先看到c，再看到a，最后看到b，写出来就是cab，正好是bac反过来写的样子。

可以这样想想看，最后一次的操作一定会把这个字符串删成空串。倒数第二次呢？肯定要么是一个单独的字符，要么是若干个这个字符。
这样想是不是就可以想明白这个关键点为啥对了。倒过来看，我可以反推删除顺序。

关键点2：s1绝对是s4的前缀

这根据定义就看出来了，我一上来在s4前面放的就是s1，怎么可能不是前缀。
虽然很显然，但是很关键。

关键点3：如果能推出来的话，知道s2和s4，可以知道s1有多长

首先想一个问题，如果知道s1有多长，结合上面的关键点2，是不是可以直接获得s1是什么。
那如果我们知道s1是什么了，我们根据最上面的题目意思，拿s1和s2跑一遍模拟，看看是不是跟题目给我们的s4相同，我们就可以验证-1这种情况了。

对于关键点3怎么证明，看关键点4。

关键点4：s4里某一个字符出现的次数，与这个字符在s1里的出现次数成倍数关系，倍数就是这个字符在s2里的位置（第一个位置是1）

有了这个关键点4，s1真的就能求了，举个例子：

假设s4是abacabaaacaac，我们推出s2是bac了。
那么在s4里b出现了2次，a出现了8次，c出现了3次。
那么根据这个关键点，在s1里，b应该出现2/1=2次，a出现8/2=4次，c出现3/3=1次，s1长度就该是2+4+1=7，也就是s4前7个字符，得到如果存在的话，s1就是abacaba了。

这个关键点是为啥呢？很显然，出现的次数就是被删掉的次序，也恰好是s1里所有这种字符在s4里重复的遍数，这样就能想明白这个倍数关系是为啥了。

那么这样看来，s1和s2都可以反推，我们模拟验证一下能不能得出题目给的s4，能就直接输出s1 s2，不能输出-1就OK了。

代码

import java.util.*;

public class Main {

    private static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int t = scanner.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    public static void solve() {
        String s = scanner.next();
        Set<Character> set = new HashSet<>();
        StringBuilder s2 = new StringBuilder();
        Map<Character, Integer> mp = new HashMap<>();
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            mp.put(c, mp.getOrDefault(c, 0) + 1);
            if (set.contains(c)) continue;
            set.add(c);
            s2.append(c);
        }
        s2 = s2.reverse();

        int len = 0;
        for (int i = 1; i <= set.size(); i++) {
            char c = s2.charAt(i - 1);
            int p = mp.get(c);
            len += p / i;
        }
        String s1 = s.substring(0, len);

        StringBuilder sb = new StringBuilder(s1);
        char[] cs = s2.toString().toCharArray();
        String ts = s1;
        for (char c : cs) {
            ts = ts.replace("" + c, "");
            sb = sb.append(ts);
        }

        if (sb.toString().equals(s)) {
            System.out.println(s1 + " " + s2);
        } else {
            System.out.println(-1);
        }
    }

}
上一篇
下一篇