Блог

Проблема состоит в том, чтобы найти для 1<=n Другими словами, если исходная последовательность была создана путем переплетения двух копий некоторой подпоследовательности. Если это так, мы должны дополнительно распечатать исходную подпоследовательность. Моя идея состояла в том, чтобы наивно разделить каждое другое число того же рода на две подпоследовательности. Так, например, первая подпоследовательность получит 1-ю 5, 3-ю 5 и 1-ю 4, а вторая-2-ю 5, 4-ю 5 и 2-ю 4. Я думал, что последовательность не может быть выражена как комбинация двух подобных копий, если в ней нечетное число некоторых чисел. Однако весь подход ошибочен и очень редко дает хорошие ответы;

Пожалуйста, помогите мне найти более умный алгоритм, который действительно решит проблему. Моя реализация наивного подхода для лучшего понимания (C ):

 #include<iostream> #include<string> #include<algorithm> #include<vector>  using namespace std;  int main() {  ios_base::sync_with_stdio(0);  cin.tie(0);   int n;  cin >> n;   vector<short> arr(n);  for (int i = 0; i < n;   i)  {  cin >> arr[i];  }   vector<vector<unsigned short>> positions(10001, vector<unsigned short>(0));   for (int i = 0; i < n;   i)  {  positions[arr[i]].push_back(i);  }   vector<unsigned short> out;   for (int i = 0; i <= 10000;   i)  {  if (positions[i].size() % 2)   {  cout << "NO" << "n";  return 0;  }   for (int j = 0; j < positions[i].size(); j  = 2)  {  out.push_back(positions[i][j]);  }  }   sort(out.begin(), out.end());   cout << "YES" << "n";  for (int i = 0; i < out.size();   i)  {  cout << arr[out[i]] << " ";  } }  

Вы можете решить эту проблему с помощью обратного отслеживания. Также возможна некоторая оптимизация. Вы знаете, что первое число должно быть первым номером последовательности. Таким образом, все буквы между первым и вторым появлением этого числа должны следовать в определенной последовательности. Аналогично для последнего числа в последовательности. Кроме того, вы можете проверить, осталось ли достаточно чисел для завершения последовательности.

 public int[] solve(int[] arr) {  if (arr.length % 2 != 0)  return null;  int[] solution = new int[arr.length / 2];  if (solve(arr, 0, 0, solution))  return solution;  return null; }  private boolean solve(int[] arr, int i, int j, int[] solution) {  if (i == j) {  solution[i] = arr[i   j];  return solve(arr, i   1, j, solution);  } else if (i == solution.length) {  for (int k = 0; k   i   j < arr.length; k  )  if (arr[k   i   j] != solution[j   k])  return false;  return true;  } else {  for (int k = 0; i   k <= solution.length; k  ) {  if (arr[i   j   k] == solution[j] amp;amp; solve(arr, i   k, j   1, solution))  return true;  if (i   k < solution.length)  solution[i   k] = arr[i   j   k];  }  return false;  } }  

Это проверка только слева направо, а не с обоих концов. Другие возможные улучшения:

• Проверьте, является ли количество для каждого числа четным в начале
• Следите за количеством чисел, чтобы раньше знать, когда число больше не может входить в первую последовательность, потому что в нем уже есть половина из них

Это код Java, но его можно легко перевести на C . Массивы передаются по ссылке. Я протестировал несколько простых случаев, и для них это сработало.

С помощью запоминания я мог бы легко решить проблемы до 50000 за несколько мс. Но мне пришлось увеличить размер стека до 100 метров. Возможно, вам захочется переписать это в итеративное решение вместо рекурсивного.

 public static int[] solve(int[] arr) {  if (arr.length % 2 != 0)  return null;  int[] solution = new int[arr.length / 2];  if (solve(arr, 0, 0, solution, new Node(null, null)))  return solution;  return null; }  private static boolean solve(int[] arr, int i, int j, int[] solution, Node node) {  if (node.checked)  return false;  if (i == j) {  if (node.children.containsKey(arr[i   j]))  node = node.children.get(arr[i   j]);  else  node = new Node(node, arr[i   j]);  if (node.checked)  return false;  solution[i] = arr[i   j];  Node n = new Node(node, solution[i]);  if (solve(arr, i   1, j, solution, n))  return true;  n.checked = true;  return false;  } else if (i == solution.length) {  for (int k = 0; k   i   j < arr.length; k  )  if (arr[k   i   j] != solution[j   k]) {  node.checked = true;  return false;   }  return true;  } else {  Node n = node;  for (int k = 0; i   k <= solution.length; k  ) {  if (arr[i   j   k] == solution[j] amp;amp; solve(arr, i   k, j   1, solution, n))  return true;  if (i   k < solution.length) {  if (n.children.containsKey(arr[i   j   k]))  n = n.children.get(arr[i   j   k]);  else  n = new Node(n, arr[i   j   k]);  if (n.checked)  return false;  solution[i   k] = arr[i   j   k];  }  }  node.checked = true;  return false;  } }  private static class Node {  public boolean checked;  public Map<Integer, Node> children = new HashMap<>();  public Node(Node parent, Integer value) {  if (parent != null)  parent.children.put(value, this);  } }