Educational Codeforces Round #148 (Rated for Div.2) A~C

xumaolin / 2023-05-16 / 原文

A

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

#define endl '\n'
#define LL long long
#define ph push_back
#define INF 0x3f3f3f3f
#define PII pair<int, int>
int t;
int a[26];
void solve()
{
  set<char> mp;
  memset(a, 0, sizeof a);
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++)
  {
    mp.insert(s[i]);
    a[s[i] - 'a']++;
  }
  sort(a, a + 26);

  // cout << a[24] << ' ' << a[25] << ' ' << endl;
  if (mp.size() == 1)
  {
    cout << "NO" << endl;
    return;
  }
  else if (s.size() % 2)
  {
    if (mp.size() == 2 && (a[24] == 1 && a[25] > 1))
    {
      cout << "NO" << endl;
      return;
    }
  }
  cout << "YES" << endl;
}

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

B

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

#define endl '\n'
#define LL long long
#define ph push_back
#define INF 0x3f3f3f3f
#define PII pair<int, int>
const int N = 2e5 + 10;
int t;
int n, k;
int a[N];
LL s[N];
void solve()
{
  memset(a, 0, sizeof a);
  memset(s, 0, sizeof s);
  LL ans = 0;
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++)
  {
    s[i] = s[i - 1] + a[i];
  }
  for (int i = 0; i <= k; i++)
  {
    ans = max(ans, s[n - k + i] - s[2 * i]);
  } //枚举的是i次操作1（将最小的两个元素删去),一共有k次操作，那么操作2为k-i次
  cout << ans << endl;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cin >> t;
  // t = 1;
  while (t--)
  {
    solve();
  }
  return 0;
}

C

//贪心，脑子没转过来
//悟了为什么能转化为寻找单增和单减序列的数目，比如说 1，2，3，4的相邻差值之和为3其实等价于1，4之间的差值是不，单减同理
//我们要一个b数组能使得相邻差值之和等于a的那么我们是不是不需要1，2，3，4里 的2，3啊，那么我们只要1，4就行，这便是最优解，那么我们的答案就是size为1的情况加上单调序列数目的情况
//那么我们只要遍历一边数组找到所有单增单减的数量加上1就是我们要的最优解
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 3e5 + 10;

int n;
int a[N];

void solve()
{
  cin >> n;

  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
  }

  int ans = 1;
  int f = -1;
  for (int i = 2; i <= n; i++)
  {
    if (f != 1 && a[i - 1] < a[i])
    { // f=1代表单调递增
      ans++;
      f = 1;
      continue;
    }
    if (f != 0 && a[i - 1] > a[i])
    { // f=0代表单调递减
      ans++;
      f = 0;
      continue;
    }
  }
  cout << ans << endl;
}

int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    solve();
  }

  return 0;
}