💭Codeforces Round 990 (Div. 2)

A. Alyona and a Square Jigsaw Puzzle

题意

Alyona按照顺时针围绕第一个拼图放置拼图，Alyona每天会按顺序放置一定数量的拼图，如果一天结束时拼图的组装部分没有任何已开始但未完成的层，Alyona会感到开心。给出每天放置拼图的数量，询问Alyona感到快乐的天数。

数据范围

$1\leq t\leq 500$
$1\leq n\leq 100$
$1\leq a_i\leq 100,a_1=1$

思路

检查每天完成添加拼图时的总拼图数是否恰好是一个奇数的平方数，若是则该天会感到快乐。

代码

1
void solve() {
2
  cin >> n;
3
  ll tot = 0, ans = 0;
4
  for (ll i = 1; i <= n; i++) {
5
    cin >> a[i];
6
    tot += a[i];
7
    ld t = sqrtl(tot);
8
    if ((ll)t & 1 && t == (ll)t) {
9
      ans++;
10
    }
11
  }
12
  cout << ans << '\n';
13
}

B. Replace Character

题意

在一个长度为$n$的字符串中，执行一次这样的操作：

选择两个索引$i,j(1\leq i,j\leq n)$，可以选择$i = j$。
进行赋值$s_i:=s_j$。

要求输出在进行该操作之后，字典序最小的那个字符串。

数据范围

$1\leq t\leq 500$
$1\leq n\leq 10$

思路

将其中一个数量最少的字母改成数量最多的字母，不过这个题数据范围很小，也可以直接暴力。

代码

1
void solve() {
2
  cin >> n;
3
  string s;
4
  cin >> s;
5
  map<char, ll> mp;
6
  for (auto c : s) {
7
    mp[c]++;
8
  }
9
  vector<pll> v;
10
  for (auto i : mp) {
11
    v.push_back({i.second, i.first - 'a'});
12
  }
13
  sort(v.begin(), v.end(), greater<>());
14
  v[0].first += 1, mp[v[0].second + 'a']++;
15
  char cc = v[0].second + 'a';
16
  v[v.size() - 1].first -= 1, mp[v[v.size() - 1].second + 'a']--;
17
  string ans;
18
  for (auto i : s) {
19
    if (mp[i]) {
20
      ans.push_back(i);
21
      mp[i]--;
22
    } else {
23
      ans.push_back(cc);
24
    }
25
  }
26
  cout << ans << '\n';
27
}

C. Swap Columns and Find a Path

题意

在一个$2\times n$的矩阵中，从$(1,1)$走到$(2,n)$点，只能向右和向下走，每个位置上有一个$a_{i,j}$的分数，需要最大化路径上的总分。可以支持任意次这样的操作：

选择两列$i,j$，将列$i$和列$j$进行交换，即$swap(a_{1,i},a_{1,j})$和$swap(a_{2,i},a_{2,j})$.

请执行最大化路径上的数之和，并输出这个总和。

数据范围

$1\leq t\leq 5000$
$1\leq n\leq 5000$
$-10^5\leq a_{i,j}\leq 10^5$

思路

观察可知，选择的路径长度固定是$n+1$，由于只能向右或者向下走，实际的路径的形状一定是在第一行取前一段，再再第二行取后一段，对每列进行排序后贪心的选择最大的一组合法的数即可。

书写的时候判断转折的一列时，也可以反向先算出$2\times n$个数的总和，再贪心的减掉$n-1$个较小的数，注意只有转折的地方一列的两个数都能取到，而其他位置的数只能取一个值。

代码

1
ll n, m;
2
ll a[5][maxn], pre[5][maxn], b[maxn];
3
bool vis[maxn];
4

5
void solve() {
6
  ll n;
7
  cin >> n;
8
  vector<pll> v1, v2;
9
  for (ll k = 1; k <= 2; k++) {
10
    for (ll i = 1; i <= n; i++) {
11
      cin >> a[k][i];
12
      vis[i] = false;
13
      if (k == 1) {
14
        v1.push_back({a[k][i], i});
15
      } else {
16
        v2.push_back({a[k][i], i});
17
      }
18
    }
19
  }
20
  sort(v1.begin(), v1.end(), greater<>());
21
  sort(v2.begin(), v2.end(), greater<>());
22
  ll ans = 0, cnt = 0;
23
  for (ll k = 1; k <= 2; k++) {
24
    for (ll i = 1; i <= n; i++) {
25
      ans += a[k][i];
26
    }
27
  }
28
  ll p1 = n - 1, p2 = n - 1;
29
  while (cnt < n - 1) {
30
    while (p1 >= 0 && vis[v1[p1].second]) {
31
      p1--;
32
    }
33
    while (p2 >= 0 && vis[v2[p2].second]) {
34
      p2--;
35
    }
36
    if (p1 != -1 && p2 != -1) {
37
      if (v1[p1].first < v2[p2].first) {
38
        ans -= v1[p1].first;
39
        vis[v1[p1].second] = true;
40
        p1--;
41
      } else {
42
        ans -= v2[p2].first;
43
        vis[v2[p2].second] = true;
44
        p2--;
45
      }
46
      cnt++;
47
    } else if (p1 != -1) {
48
      ans -= v1[p1].first;
49
      vis[v1[p1].second] = true;
50
      p1--;
51
      cnt++;
52
    } else if (p2 != -1) {
53
      ans -= v2[p2].first;
54
      vis[v2[p2].second] = true;
55
      p2--;
56
      cnt++;
57
    } else {
58
      break;
59
    }
60
  }
61
  cout << ans << '\n';
62
}

D. Move Back at a Cost

题意

给出一个长度为$n$的数组$a$，可以执行如下操作：

选择一个索引$i$，将$a_i+1$添加到数组的末尾，并删去$a_i$。

可以执行这样的操作任意次，请输出字典序最小的操作之后的数组$a$。

数据范围

$1\leq t\leq 10^4$
$1\leq n\leq 10^5$
$1\leq a_i\leq 10^9$

思路

尽量保留原数组中从小到达排列的数，将其中不符合单调性的点挪到数组的后面，不要让这些将挪到数组后面的数再次挪动。

维护一个全局的multiset，记录所有需要挪动的数字，将这些数+1 后依次添加到原来数组生成的有序序列的后面。

代码

1
void solve() {
2
  ll n;
3
  cin >> n;
4
  multiset<ll> st;
5
  for (ll i = 1; i <= n; i++) {
6
    cin >> a[i];
7
    st.insert(a[i]);
8
  }
9
  ll p = 1;
10
  multiset<ll> v;
11
  vector<ll> ans;
12
  while (p <= n && !st.empty()) {
13
    while (p <= n && a[p] != *st.begin()) {
14
      v.insert(a[p]);
15
      st.erase(st.find(a[p]));
16
      p++;
17
    }
18
    if (p > n)
19
      break;
20
    ans.push_back(a[p]);
21
    st.erase(st.find(a[p]));
22
    p++;
23
  }
24
  while (!v.empty() && ans.back() > *v.begin() + 1) {
25
    v.insert(ans.back());
26
    ans.pop_back();
27
  }
28
  for (auto i : v) {
29
    ans.push_back(i + 1);
30
  }
31
  for (auto i : ans) {
32
    cout << i << ' ';
33
  }
34
  cout << '\n';
35
}