CF 1893 A

题目描述

有以下操作：

• 选择数组 \(A\) 的一个固定点 \(x\)。固定点是指满足 \(A_x=x\) 的点。
• 令 \(A\) 循环左移 \(x\) 次。

求数组 \(B\) 有没有可能是通过某个 \(A\) 执行 \(k\) 次操作得到的。

思路

可以发现，上次选择的固定点 \(x\) 一定被转到了最后面。按题意模拟即可。

时空复杂度均为 \(O(N)\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200001;

int t, n, k, a[MAXN];
bool vis[MAXN];

void Solve() {
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    vis[i] = 0;
  }
  for(int i = 1, p = n; i <= k && !vis[p]; ++i) {
    if(a[p] > n) {
      cout << "No\n";
      return;
    }
    vis[p] = 1;
    p = p + n - a[p] - (p + n - a[p] > n) * n;
  }
  cout << "Yes\n";
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> t; t--; Solve()) {
  }
  return 0;
}

CF 1893 B

题目描述

给定数组 \(A,B\)，你要把 \(B\) 中的数字插入到 \(A\) 中使得最终的 \(\text{LIS}(A)\) 尽可能小。

思路

最终肯定是使最终的 \(\text{LIS}\) 与原来相同。很明显有以下构造方法：

• 从大到小枚举 \(B\) 中的数，找到 \(A\) 中第一个小于它的，并把它插在前面。

空间复杂度 \(O(N+M)\)，时间复杂度 \(O(M\log M)\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200001;

int t, n, m, a[MAXN], b[MAXN];

void Solve() {
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 1; i <= m; ++i) {
    cin >> b[i];
  }
  sort(b + 1, b + m + 1, greater<int>());
  int i = 1, j = 1;
  for(; i <= n; ++i) {
    for(; j <= m && b[j] >= a[i]; ++j) {
      cout << b[j] << " ";
    }
    cout << a[i] << " ";
  }
  for(; j <= m; ++j) {
    cout << b[j] << " ";
  }
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> t; t--; Solve()) {
  }
  return 0;
}