比赛链接

Codeforces Round #631

Problem A. Dreamoon and Ranking Collection (Div. 2)

按照题意模拟皆可。

时间复杂度 $\Theta(n+x)$

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int n, x; 
int a[N << 1];

int main() {
  int t; 
  scanf("%d", &t);
  while (t--) {
    memset(a, 0, sizeof a);
    scanf("%d %d", &n, &x);
    for (int i = 1; i <= n; ++i) {
      int y; 
      scanf("%d", &y);
      a[y] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= 200; ++i) {
      if (!a[i] && !x)
        break;
      if (a[i])
        ans++;
      else 
        ans++, x--;
    }
    printf("%d\n", ans);
  }
  return 0;  
}

Problem B. Dreamoon Likes Permutations (Div. 2)

易得两个数列为排列的充要条件为

  • 每个数只出现一次,且最大数为数列的长度

接下来就是按照题意模拟即可。

时间复杂度 $\Theta (n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;

int n;
int a[N], buk[N];
int pt[2][N];

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
      pt[0][i] = pt[1][i] = 0; 
    for (int i = 1; i <= n; ++i)
      scanf("%d", &a[i]);
    int mx = 0;
    for (int i = 1; i <= n; ++i)
      buk[i] = 0;
    for (int i = 1; i <= n; ++i) {
      mx = max(mx, a[i]);
      buk[a[i]]++;
      if (buk[a[i]] == 2)
        break;
      if (mx == i)
        pt[0][i] = 1; 
    }
    mx = 0;
    for (int i = 1; i <= n; ++i)
      buk[i] = 0;
    for (int i = n; i >= 1; --i) {
      mx = max(mx, a[i]);
      buk[a[i]]++;
      if (buk[a[i]] == 2)
        break;
      if (mx == n - i + 1)
        pt[1][i] = 1; 
    }
    vector<pair<int, int>> ans; 
    for (int i = 1; i < n; ++i)
      if (pt[0][i] && pt[1][i + 1])
        ans.push_back(make_pair(i, n - i));
    printf("%d\n", (int)ans.size());
    for (auto it : ans)
      printf("%d %d\n", it.first, it.second);
  }
  return 0;
}

Problem A. Dreamoon Likes Coloring

考虑维护后缀和

  • 如果剩下的长度不会填颜色填到外部,那么就在 $i$ 号位置填色
  • 否则在 $n-sum+1$ 处填。

时间复杂度 $\Theta (n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;

int n, m;
int a[N];
ll sum;

int main() {
  scanf("%d %d", &n, &m);
  sum = 0;
  for (int i = 1; i <= m; i++) {
    scanf("%d", &a[i]);
    sum += a[i];
    if (n - i + 1 < a[i]) {
      printf("-1\n");
      return 0;
    }
  }
  if (sum < n) {
    printf("-1\n");
    return 0;
  }
  for (int i = 1; i <= m; i++) {
    if (i + sum - 1 >= n) 
      printf("%d ", i);
    else 
      printf("%d ", n - sum + 1);
    sum -= a[i];
  }
  return 0;
}

Problem B. Dreamoon Likes Sequences

你可以证明在二进制表示下 $h(x)$ 表示 $x$ 的总位数。

$$ h(a_i)=h(b_i)>h(a_{i-1})=h(b_{i-1}) $$

然后就是按照每一位能够有的数计数即可。

时间复杂度 $\Theta (logn)$

#include <bits/stdc++.h>

using namespace std;

int d, mod; 

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &d, &mod);
    int ans = 1; 
    for (int i = 1; i <= d; i <<= 1) 
      ans = 1ll * ans * (min(i * 2 - 1, d) - i + 2) % mod; 
    printf("%d\n", (ans -= 1) < 0 ? ans + mod : ans);
  }
  return 0;
}

Problem C. Drazil Likes Heap

考虑贪心,能删根就删根,每次更新子树的大小,判断下一步是否能够执行即可。

时间复杂度 $O(nlogn)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (1 << 22) + 5; 

int h, g;
int a[N], siz[N], goal[N];
bool flg;
vector<int> ans;

void del(int x) {
  int lc = x << 1, rc = x << 1 | 1; 
  if (a[lc] == 0 && a[rc] == 0) 
    a[x] = 0, siz[x] = 0; 
  else {
    if (a[lc] > a[rc]) 
      a[x] = a[lc], del(lc);
    else
      a[x] = a[rc], del(rc);
    siz[x] = 1 + siz[lc] + siz[rc];
  }
}

void check(int x) {
  if (siz[x] <= goal[x]) {
    flg = 0;
    return;
  } else if (!a[x << 1] && !a[x << 1 | 1]) 
    return;
  else 
    check(a[x << 1] > a[x << 1 | 1] ? x << 1 : x << 1 | 1);
}

void dfs(int x) {
  int lc = x << 1, rc = x << 1 | 1;
  while (true) {
    flg = 1; 
    check(x);
    if (!flg) 
      break;
    ans.push_back(x);
    del(x);
  }
  if (siz[lc] > goal[rc]) 
    dfs(lc);
  if (siz[rc] > goal[rc]) 
    dfs(rc);
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d %d", &h, &g);
    for (int i = 1; i < (1 << (h + 1)); i++)
      a[i] = 0, siz[i] = 0, goal[i] = 0; 
    for (int i = 1; i < (1 << h); i++) 
      scanf("%d", &a[i]), siz[i] = 1; 
    for (int i = 1; i < (1 << g); i++)
      goal[i] = 1; 
    for (int i = (1 << h) - 1; i >= 1; i--) {
      siz[i] += siz[i << 1] + siz[i << 1 | 1];
      goal[i] += goal[i << 1] + goal[i << 1 | 1];
    }
    ans.clear();
    dfs(1);
    ll sum = 0;
    for (int i = 1; i < (1 << g); i++) 
      sum += a[i];
    printf("%I64d\n", sum);
    for (auto it : ans) 
      printf("%d ", it);
  }
  return 0;
}

Problem D. Dreamoon Likes Strings

To be continued

Problem E. Dreamoon Loves AA

To be continued

最后修改:2020 年 04 月 10 日 08 : 48 PM
如果觉得我的文章对你有用,请随意赞赏