前言

这个 $D1$,$D2$ 整整调了我一个下午和一个晚上,没想到是 $Manacher$ 的板子写错了。

比赛链接:Codeforces Global Round 7

正文

Problem A. Bad Ugly Numbers

简单考虑问题。

根据小学数学所学的知识,$2$ 和 $3$ 的整除判定是比较简单的,所以考虑用这两个数码来拼出答案。

比较明显的是,如果不能被 $2$ 整除,那么最后一位必须是 $3$。

如果不能被 $3$ 整除,那么必须满足各数位之和不是 $3$ 的倍数,暴力判定就可以了。

时间复杂度 $O(n)$

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define eb emplace_back
#define mp make_pair

using namespace std;

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    if (n == 1) {
      cout << -1 << '\n';
    } else {
      int cnt = n - 2;
      if (cnt % 3 == 0) {
        cnt++;
      }
      For (i, 1, cnt) cout << "2";
      For (i, 1, n - cnt) cout << "3";
      cout << '\n';
    }
  }
  return 0;
}

Problem B. Maximums

按照题意模拟即可。

时间复杂度 $O(n)$

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define eb emplace_back
#define mp make_pair

using namespace std;

const int N = 2e5 + 5;

template <class T> 
void chkMax(T& x, T y) {
  x = x > y ? x : y;
}

int n;
long long a[N], b[N];

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  cin >> n;
  For (i, 1, n) {
    cin >> b[i];
  }
  a[1] = b[1];
  long long pfx = max(0ll , a[1]);
  For (i, 2, n) {
    a[i] = b[i] + pfx;
    chkMax(pfx, a[i]);
  }
  For (i, 1, n) {
    cout << a[i] << ' ';
  }
  cout << '\n';
  return 0;
}

Problem C. Permutation Partitions

显然划分是按照前 $k$ 大值进行的。

所以统计方案只需要考虑在这些分割点之间的线段中的端点的位置即可。

时间复杂度 $O(nlog_2n)$

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define Dwn(i, s, t) for (int i = s; i >= t; i--)
#define eb emplace_back

using namespace std;

typedef pair<int, int> pii;

const int mod = 998244353;
const int N = 2e5 + 5;

pii a[N];
int n, k;

int main() {
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
#endif
  cin >> n >> k;
  For (i, 1, n) {
    cin >> a[i].first;
    a[i].second = i;
  }
  sort(a + 1, a + 1 + n, [](pii a, pii b) {
    return a.first > b.first;
  });
  long long ans = 0;
  vector<int> position;
  For (i, 1, k) {
    ans += a[i].first;
    position.eb(a[i].second);
  }
  sort(position.begin(), position.end());
  int res = 1;
  For (i, 0, (int)position.size() - 2) {
    res = (long long)res * (position[i + 1] - position[i]) % mod;
  }
  cout << ans << ' ' << res << '\n';
  return 0;
}

Problem D. Prefix-Suffix Palindrome

首先考虑到每一个答案一定存在一个前缀和后缀是回文的,所以其中多余出来的部分就是剩下的字符串的较长的前缀回文串或者后缀字符串。

这个过程用 $Manacher$ 实现即可。

时间复杂度 $O(n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 1e6 + 5;

string s, s1, s2;
int n;

int manacher(string t) {
  string s = "~#";
  for (int i = 0; i < t.size(); i++) {
    s += t[i], s += "#";
  }
  int mid = 0, ans = 0, rht = 0;
  vector<int> rad(s.size(), 0);
  for (int i = 1; i < (int)s.size(); i++) {
    rad[i] = i < rht ? min(rht - i, rad[mid * 2 - i]) : 1;
    while (s[i + rad[i]] == s[i - rad[i]]) {
      rad[i]++;
    }
    if (i + rad[i] > rht) {
      rht = i + rad[i];
      mid = i;
    }
    if (i == rad[i]) {
      ans = max(ans, rad[i] - 1);
    }
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    cin >> s;
    int n = s.length();
    int l = -1, r = n, x, y;
    while (l + 1 < r - 1 && s[l + 1] == s[r - 1]) {
      l++, r--;
    }
    s1 = s.substr(l + 1, r - l - 1);
    s2 = s1;
    reverse(s2.begin(), s2.end());
    cout << s.substr(0, l + 1);
    x = manacher(s1), y = manacher(s2);
    if (x > y) {
      cout << s1.substr(0, x);
    } else {
      cout << s2.substr(0, y);
    }
    cout << s.substr(r, n - r) << '\n';
  }
  return 0;
}

Problem E. Bombs

这道题目非常容易脑补出假算法,笔者想假了一百次,最后看了题解才觉得非常的秒。

首先有一个比较容易证明的,用于判定答案合法性的结论。

如果存在某一个位置 $i$ 满足在其右边大于 $Ans$ 的 $\geq$ 其右边的炸弹的个数,那么答案 $Ans$ 成立。


UPD 2020-04-10 21:45
关于上述结论的详细描述:
笔者冷静了一下之后发现自己并不是特别明白这个结论是否成立。
可能笔者现在的思路还不是特别的清晰,但是稍微有了一些正确的思路。
首先答案一定是连续不增的,这毫无疑问。
对于验证答案 $ans$ 是否成立,那么首先需要保证 $(ans,n]$ 的所有答案全都不合法。
一定存在从右边开始遍历到的数,第 $i$ 个 $\leq ans$ 的数之后一定满足后面至少有 $i$ 个炸弹,才能保证这个数会被炸掉。
那么所有的 $(ans,n]$ 都满足这个性质,但是 $ans$ 不满足,也就是至少不满足其中的一个条件,这就和前面的不合法相矛盾。
以上可能是对的吧


然后比较容易得到答案不增,所以直接考虑从大到小枚举答案,然后判定其合法性。

线段树维护右边的数$\geq Ans$的个数减去右边的炸弹个数,这样就只需要实现区间修改操作即可。

时间复杂度 $\mathcal O(nlog_2n)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int N = 3e5 + 5;

struct SegmentTree {
  struct Node {
    int mx, tag;
  } tr[N << 2];

  SegmentTree() { 
    memset(tr, 0, sizeof tr); 
  }

  void pushup(int x) {
    tr[x].mx = max(tr[x << 1].mx, tr[x << 1 | 1].mx);
  }

  void pushdown(int x) {
    if (tr[x].tag) {
      tr[x << 1].mx += tr[x].tag;
      tr[x << 1 | 1].mx += tr[x].tag;
      tr[x << 1].tag += tr[x].tag;
      tr[x << 1 | 1].tag += tr[x].tag;
      tr[x].tag = 0;
    }
  }

  void modify(int x, int l, int r, int ql, int qr, int v) {
    if (ql <= l && r <= qr) {
      tr[x].mx += v;
      tr[x].tag += v;
      return;
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (ql <= mid) {
      modify(x << 1, l, mid, ql, qr, v);
    } 
    if (qr > mid) {
      modify(x << 1 | 1, mid + 1, r, ql, qr, v);
    }
    pushup(x);
  }
} sgt;

int n;
int a[N], back[N], b[N];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    back[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &b[i]);
  }
  int ans = n;
  printf("%d ", ans);
  sgt.modify(1, 1, n, 1, back[ans], 1);
  for (int i = 1; i < n; i++) {
    sgt.modify(1, 1, n, 1, b[i], -1);
    while (sgt.tr[1].mx <= 0) {
      ans--;
      sgt.modify(1, 1, n, 1, back[ans], 1);
    }
    printf("%d ", ans);
  }
  return 0;
}

后言

  • 考虑问题尽可能要向简单的方向考虑,否则会把自己绕进去。
  • 千万不要对 $c++$ 中 $string$ 进行过多的遍历,特别是内嵌了 $string$ 拼接的过程,尽量使用 $STL$。
最后修改:2020 年 04 月 10 日 10 : 42 PM
如果觉得我的文章对你有用,请随意赞赏