Educational Codeforces Round 152 A~D

A

#include <bits/stdc++.h>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
int T;
void solve()
{
  int b, c, h;
  cin >> b >> c >> h;
  if (c + h < b - 1)
  {
    cout << 2 * (c + h) + 1 << endl;
  }
  if (c + h >= b - 1)
  {
    cout << 2 * (b - 1) + 1 << endl;
  }
}
signed main()
{
  ios;
  int T = 1;
  cin >> T;
  while (T--)
  {
    solve();
  }
}

B

#include <bits/stdc++.h>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
#define int long long
typedef pair<int, int> PII;
#define int long long
const int N = 3e5 + 10;
const int MOD = 1e9 + 7;
int T;
int n, k;
#define int long long
typedef pair<int, int> PII;

bool cmp(PII a, PII b)
{
  if (a.first != b.first)
    return a.first > b.first;
  else
    return a.second < b.second;
}
void solve()
{
  cin >> n >> k;
  vector<PII> a;
  for (int i = 1; i <= n; i++)
  {
    int x;
    cin >> x;
    if (x > k)
    {
      if (x % k == 0)
        a.push_back({k, i});

      else
        a.push_back({x % k, i});
    }
    else
      a.push_back({x, i});
  }
  sort(a.begin(), a.end(), cmp);
  for (auto x : a)
  {
    cout << x.second << ' ';
  }
  // for (int i = 1; i <= n; i++)
  // {
  //   cout << a[i].second << ' ';
  // }
  cout << endl;
}
signed main()
{
  ios;
  int T = 1;
  cin >> T;
  while (T--)
  {
    solve();
  }
}

C

#include <bits/stdc++.h>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
int T;

int n, m;
char str[N];
int l[N], r[N];

void solve()
{
  cin >> n >> m >> str + 1;

  int last = 0;
  for (int i = 1; i <= n; i++)
  {
    if (str[i] == '0')
      last = i;
    l[i] = last;
  }

  last = n + 1;
  for (int i = n; i; i--)
  {
    if (str[i] == '1')
      last = i;
    r[i] = last;
  }

  set<PII> S;
  while (m--)
  {
    int x, y;
    cin >> x >> y;
    if (r[x] > y || l[y] < x) //这是每个询问右端点前面最近的0都在区间左边（区间里全为1）或者最近离左端点后面的1在区间右边（区间全为0）这种情况不会改变区间，也就是原来状态
      S.insert({0, 0});
    else
    {
      x = r[x], y = l[y];
      if (x > y)
        S.insert({0, 0}); //当为类似000111情况时，排序也没有变化序列，仍为原序列
      else
        S.insert({x, y}); //每一个区间的排序都和l[y]和r[x]的组合 一 一对应
    }
  }

  cout << S.size() << endl; // set的size就是我们排序的所有的
}

int main()
{
  ios;
  T = 1;
  cin >> T;
  while (T--)
    solve();
  return 0;
}

D

 先将2的向两遍扩展再将1向一边扩展（尽量向有1的地方扩展）每一次扩展完成需要一代价，剩下的只能花费代价

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int a[N], vis[N]; // vis数组判断是否被扩展过

inline void solve()
{
  int n, ans = 0;
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  for (int i = 1; i <= n; i++)
  {
    if (a[i] == 0)
      continue;
    int j = i, flag = 0;
    while (j <= n && a[j] != 0)
    {
      if (a[j] == 2)
        flag = 1;
      j++;
    }
    if (flag)
    {
      vis[i - 1] = vis[j] = 1; //当有数为2时，我们将第一个2的左边和类似21121这类不含0的连续串的右边都扩展；
    }
    else
    {
      if (i - 1 >= 1 && !vis[i - 1]) //当该数为1时，若前面有未扩展过的1，我们向前面的1扩展，否则我们向后面扩展
        vis[i - 1] = 1;
      else
        vis[j] = 1;
    }
    ans++;
    i = j - 1;
  }
  for (int i = 1; i <= n; i++)
    if (a[i] == 0 && !vis[i])
      ans++;
  cout << ans << endl;
}

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