Neowise Labs Contest 1 (Codeforces Round 1018, Div. 1 + Div. 2)

A. Wonderful Sticks

题目大意

给你一个长度为n-1的字符串，每个字符为<或>，设索引从1开始
若字符串中第i个字符出现<则i+1个元素来说要小于1～i之间的所有元素
若字符串中第i个字符出现>则i+1个元素来说要大于1～i之间的所有元素
求满足要求的排列是什么样子的

思路

分析可以看出都是要满足前缀的所有要求，那么我们考虑从右往左开始遍历，我们用双指针l,r
若出现<则说明这个元素要小于之前的所有元素,当前元素为l++
若出现>则说明这个元素要大于之前的所有元素，当前元素为r–

// Author: zengyz
// 2025-07-15 19:17

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve()
{
  int n;
  cin >> n;
  vector<int> a(n + 1);
  string s;
  cin >> s;
  int idx1 = 1;
  s = " " + s;
  int idx2 = n;
  for (int i = s.size() - 1; i >= 1; i--)
  {
    int j = i + 1;
    if (s[i] == '<')
    {
      a[j] = idx1++;
    }
    if (s[i] == '>')
      a[j] = idx2--;
  }

  a[1] = idx1;
  for (int i = 1; i <= n; i++)
    cout
        << a[i] << " ";
  cout << endl;

  return;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _T = 1;
  cin >> _T;
  while (_T--)
  {
    solve();
  }
  return 0;
}

B. Wonderful Gloves

题目大意

给你n,k
代表抽屉里一共有n种不同的手套
称手套是配对的如果同时有相同颜色的左手套和右手套
给你长度为n的l数组和r数组代表对应颜色的左手套和右手套的个数
现在将它们全部放在一个抽屉里，问最少拿出多少手套才能保证存在有k对不同颜色的手套

思路

最坏的情况是对于每一种颜色，都取出了左手套和右手套中最大的所有手套，然后在剩下的较小的手套中取出了k-1种手套的全部以及再取出一只手套
所以简单判断一下即可

// Author: zengyz
// 2025-07-15 19:33

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve()
{
  int n, k;
  cin >> n >> k;
  vector<int> l(n), r(n);
  ll sum1 = 0, sum2 = 0;
  ll sum3 = 0;
  for (int i = 0; i < n; i++)
    cin >> l[i], sum1 += l[i];
  for (int i = 0; i < n; i++)
    cin >> r[i], sum2 += r[i];
  vector<int> res;
  for (int i = 0; i < n; i++)
  {
    if (l[i] > r[i])
    {
      sum3 += l[i];
      res.push_back(r[i]);
    }
    else
    {
      sum3 += r[i];
      res.push_back(l[i]);
    }
  }
sort(res.begin(), res.end());
reverse(res.begin(), res.end());
  
for(int i=0;i<k-1;i++)
{
  sum3+=res[i];
}
sum3++;
cout<<sum3<<endl;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _T = 1;
  cin >> _T;
  while (_T--)
  {
    solve();
  }
  return 0;
}

C. Wonderful City

题目大意

给你一个n*n的数组，要保证每个元素它上下左右相邻的四个元素和它本身都不相等
给你a,b两个数组
你可以进行如下操作：
对于数组的第i个行,可以将第i行所有元素都加一，代价是$a_i$
对于数组的第i个列,可以将第i列所有元素都加一，代价是$b_i$
每行或者每列最多加一次，问是否存在最小代价的操作方法，使得满足要求

思路

可以看出行和列之间都是相对独立的，我们可以将行和列分开判断
对于行来说
我们用dp来保存最优解，设f[i][0]为没有操作当前行，f[i][1]为操作当前行
如果这一行不存在和上一行相同的元素，也就是说和上一行保持一致的操作是满足要求的
$$f[i][0]=min(f[i][0],f[i-1][0])$$
$$f[i][1]=min(f[i][1],f[i-1][1]+a[i])$$
如果这一行不存在比上一行大一的元素，也就是说当前行不操作和上一行操作是满足要求的
$$f[i][0]=min(f[i][0],f[i-1][1])$$
如果这一行不存在比上一行小一的元素，也就是说当前行操作和上一行不操作是满足要求的
$$f[i][1]=min(f[i][1],f[i-1][0]+a[i])$$
然后取最后一行操作和不操作的最小值

列同样考虑，然后加上最后一列操作和不操作的最小值

// Author: zengyz
// 2025-07-15 19:51

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e3 + 10;
void solve()
{

  ll f1[N][2] = {};
  int n;
  cin >> n;
  vector<vector<int>> mp(n + 1, vector<int>(n + 1));
  vector<int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      cin >> mp[i][j];

  ll INF = 0;
  for (int i = 1; i <= n; i++)
    cin >> a[i], INF += a[i];
  for (int i = 1; i <= n; i++)
    cin >> b[i], INF += b[i];
  for (int i = 1; i <= n; i++)
    f1[i][0] = f1[i][1] = INF;
  f1[1][0] = 0;
  f1[1][1] = a[1];

  for (int i = 2; i <= n; i++)
  {
    bool flag1 = false, flag2 = false, flag3 = false;
    for (int j = 1; j <= n; j++)
    {
      if (mp[i][j] == mp[i - 1][j])
        flag1 = true;
      if (mp[i][j] == mp[i - 1][j] + 1)
        flag2 = true;
      if (mp[i][j] == mp[i - 1][j] - 1)
        flag3 = true;
    }
    if (flag1 && flag2 && flag3)
    {
      cout << -1 << endl;
      return;
    }
    if (!flag1)
    {
      f1[i][0] = min(f1[i][0], f1[i - 1][0]);
      f1[i][1] = min(f1[i][1], f1[i - 1][1] + a[i]);
    }
    if (!flag2)
      f1[i][0] = min(f1[i][0], f1[i - 1][1]);
    if (!flag3)
      f1[i][1] = min(f1[i][1], f1[i - 1][0] + a[i]);
  }
  ll ans = min(f1[n][0], f1[n][1]);
  for (int i = 1; i <= n; i++)
    f1[i][0] = f1[i][1] = INF;
  f1[1][0] = 0;
  f1[1][1] = b[1];
  for (int i = 2; i <= n; i++)
  {
    bool flag1 = false, flag2 = false, flag3 = false;
    for (int j = 1; j <= n; j++)
    {

      if (mp[j][i] == mp[j][i - 1])
        flag1 = true;
      if (mp[j][i] == mp[j][i - 1] + 1)
        flag2 = true;
      if (mp[j][i] == mp[j][i - 1] - 1)
        flag3 = true;
    }
    if (flag1 && flag2 && flag3)
    {
      cout << -1 << endl;
      return;
    }
    if (!flag1)
    {
      f1[i][0] = min(f1[i][0], f1[i - 1][0]);
      f1[i][1] = min(f1[i][1], f1[i - 1][1] + b[i]);
    }
    if (!flag2)
      f1[i][0] = min(f1[i][0], f1[i - 1][1]);
    if (!flag3)
      f1[i][1] = min(f1[i][1], f1[i - 1][0] + b[i]);
  }
  ans += min(f1[n][0], f1[n][1]);
  if (ans > INF)
    cout << -1 << endl;
  else
    cout << ans << endl;

  return;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _T = 1;
  cin >> _T;
  while (_T--)
  {
    solve();
  }
  return 0;
}