【算法竞赛】CF Edu #134 (Rated for Div. 2) A - E Rethink

Livinfly

发布于 2022-10-26 16:22:47

2770

发布于 2022-10-26 16:22:47

文章被收录于专栏：Livinfly

闲言

好几天没打cf且没有打vp了qwq

这次个人感觉AB两题过得比之前快，C WA了一发，过了；D WA两发，没过。就润去睡觉了。

后续题解先咕一会儿。

代码附在后面

A

容易分析出题中的情况有1~4个字母（不同的）

1个，答案显然为0。
2个，一次最多能涂两个相同颜色的，所以答案显然为1。
3个，此时有一种字母有两个，分为两个相邻与两个相隔的情况，可以发现都只需要一步可以变为有三个相邻的状态，答案为2。
4个，只能一个一个变，答案为3。

我在实现代码稍微麻烦了点，jls就是直接set，SSRS_是分类了，但不是完全无脑分类，通过第一个和第二个的cnt来分类。（对于stl还是不熟练QnQ）

B

题意：求十字移动，有一片障碍的前提，从(1, 1)到(n, m)的最小步数。

因为求的是最小步数，我们只先考虑向下或向右的走法。

因为它只有一片是障碍，我们不难分析出，障碍只会严重影响一边的通行（靠左下的路线与靠右上的路线）。

容易发现，若靠左下的路线可以过的话，贴着左下边缘过的方式是绝对可以过得。同理可得靠右上的路线可过的话，贴着右上边缘过的方式亦可以过。

因为，障碍是以一个点为中心的范围。如果，边缘的走法可以过，那最小步数就为 n+m-2，否则若两边都不能过，容易想象出这是终点与起点被隔断的情况，即无解，也没有必要去分析其他的走法。

C

题意：有a,b,d两个序列，通过ai+di的方式得到bi，再 将bi排序得到我们输入的bi序列，求每个 个体 di的 可能的最大和最小值。

简单分析题意后，得知，我们需要找到每个ai可能匹配上（加上di后相等）的bj，di的最大最小值就是bj-ai的最大最小值。

bj >= ai
bj要是ai可以选择的。这里的可以选择是指，它没有被某一个ai，或者某一块a(l~r)绑定。（我WA1发交在这里了QnQ）

关于第二点，我举一个例子

10 25 30 40
22 33 33 55

我们不难发现，a40只能和b55匹配，如果前面的某个数和b55匹配，a40将无法匹配，是不合法的。

所以，a30只能与两个b33匹配，而a25只能和另一个b33匹配。

所以这一块就绑定死了，a10无法尝试与这些绑定一起的匹配。

（因为题中样例只能看出一个会绑定，而一堆会绑定我把原题样例的a20改成a25。）

在代码实现上，因为a，b都是非递减序列，我们需要统计的大于ai的bj就是连续的，可以采用多指针的方式，线性求解。

补充jls的做法，最大值最小值分开处理。

最小值就是能匹配的最小的值。
最大值就是在满足a[j+1] <= b[j]前的bj与ai的最大值。（这个条件就概括掉我前面这个绑定起来的问题，tql）因为a[j+1]>b[j]的话，a[j+1]就只能在j+1之后的b中匹配。

D

找到D和我思路相似的题解（但我实现能力有点弱）

题意：给出a, b两个序列, c序列为a, b两个序列的某种排列方式的 ci = ai^bi,求所以ci与的最大结果.

易得，想让某一位的与的结果为 1，某一位要全是 1才行。

然后为了结果最大，要从高位到低位进行，且再check低位的时候，要满足高位的限制，即，低位的ab的01匹配，要在之前高位的01匹配的基础上进行，即，一组和一组内匹配。

不难发现，每次的匹配要进行的操作都是一样的，只需要把分出来的组加进去，后面的低位匹配时也需要满足它即可。

jls的思路，check ans，按位下来尝试ans，如果这个ans是存在的，

ans & a的结果应该是与ans & b的结果取反相同的！

jls tql

E

学习的文章

题意：先给你s字符串，后面有q个询问。询问的内容为，把t接在s后面，那么对于接在里面的t的每一位来说，把它作为后缀的字符串，出现在前面的离它最近的地方在哪里，即kmp算法中next[i]。

直接进行前面s的预处理+后面的添加部分的t的kmp会TLE。

分析原因，发现在寻找到真正的ne的时候，跳了重复的多次。

因此，想到要快速查询，不妨设数组chi-1为，当为i-1上的字符时，下一个为j（小写）的位置。(如果i不是所需的字符，则变成前一个满足的位置)

此时，next数组的找寻就变成，next[i] = ch[next[i-1]][s[i]-'a']了。

CODE

A

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 200;

bool vis[N];

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    memset(vis, 0, sizeof vis);
    int cnt = 0;
    char ch[3];
    cin >> ch;
    for (int i = 0; i < 2; i++)
      if (!vis[ch[i]])
      {
        vis[ch[i]] = true;
        cnt++;
      }
    cin >> ch;
    for (int i = 0; i < 2; i++)
      if (!vis[ch[i]])
      {
        vis[ch[i]] = true;
        cnt++;
      }
    cout << cnt - 1 << '\n';
  }
  return 0;
}

B

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    int n, m, sx, sy, d;
    cin >> n >> m >> sx >> sy >> d;
    if (sx + d < n && sy - d > 1 || sx - d > 1 && sy + d < m)
      cout << n + m - 2 << '\n';
    else
      cout << -1 << '\n';
  }
  return 0;
}

C

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1), d1(n + 1), d2(n + 1);
    for (int i = 1; i <= n; i++)
      cin >> a[i];
    for (int i = 1; i <= n; i++)
      cin >> b[i];
    for (int i = n, l = n - 1, r = n; i > 0; i--)
    {
      while (l && b[l] >= a[i])
        l--;
      d1[i] = b[l + 1] - a[i], d2[i] = b[r] - a[i];
      if (l + 1 == i)
        r = l;
    }
    for (int i = 1; i <= n; i++)
      cout << d1[i] << " \n"[i == n];
    for (int i = 1; i <= n; i++)
      cout << d2[i] << " \n"[i == n];
  }
  return 0;
}

D-1

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;

vector<int> ga[N], gb[N];

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    ga[0].clear(), gb[0].clear();
    for (int &x : a)
      cin >> x, ga[0].emplace_back(x);
    for (int &x : b)
      cin >> x, gb[0].emplace_back(x);
    int res = 0, g_cnt = 1;
    for (int i = 29; i >= 0; i--) // bit
    {
      bool is_legal = true;
      for (int j = 0; j < g_cnt; j++)
      {
        int a0 = 0, b1 = 0;
        for (int &x : ga[j])
          if (!(x >> i & 1))
            a0++;
        for (int &x : gb[j])
          if (x >> i & 1)
            b1++;
        if (a0 != b1)
        {
          is_legal = false;
          break;
        }
      }
      if (!is_legal)
        continue;
      // update answer
      res += 1 << i;
      // divide into new group
      int ng_cnt = g_cnt;
      for (int j = 0; j < g_cnt; j++)
      {
        int a0 = 0, a1 = 0;
        for (int &x : ga[j])
          if (x >> i & 1)
            a1++;
          else
            a0++;
        if (!a0 || !a1) // no need for divide
          continue;
        vector<int> t_ga = ga[j], t_gb = gb[j];
        ga[j].clear(), gb[j].clear(), ga[ng_cnt].clear(), gb[ng_cnt].clear();
        for (int &x : t_ga)
          if (x >> i & 1)
            ga[j].emplace_back(x);
          else
            ga[ng_cnt].emplace_back(x);
        for (int &x : t_gb)
          if (x >> i & 1)
            gb[ng_cnt].emplace_back(x);
          else
            gb[j].emplace_back(x);
        ng_cnt++;
      }
      g_cnt = ng_cnt;
    }
    cout << res << '\n';
  }
  return 0;
}
/*
  观看wangxueyi的题解
  思路很像
  死于代码实现（（
*/

D-2

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T; // scanf("%d", &T);
  while (T--)
  {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int &x : a)
      cin >> x;
    for (int &x : b)
      cin >> x;
    auto check = [&](int x)
    {
      // 这边选用vector判等
      vector<int> ta(n), tb(n);
      for (int i = 0; i < n; i++)
      {
        ta[i] = a[i] & x;
        tb[i] = ~b[i] & x;
      }
      sort(all(ta));
      sort(all(tb));
      return ta == tb;
    };
    int ans = 0;
    for (int i = 29; i >= 0; i--)
      if (check(ans | (1 << i)))
        ans |= 1 << i;
    cout << ans << '\n';
  }
  return 0;
}
/*
  jls YYDS
*/

E

#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 20;

int ne[N], ch[N][26];
char str[N];

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  cin >> str + 1;
  int slen = strlen(str + 1);
  ne[1] = 0, ch[0][str[1] - 'a'] = 1;
  for (int i = 2; i <= slen; i++)
  {
    ne[i] = ch[ne[i - 1]][str[i] - 'a'];
    ch[i - 1][str[i] - 'a'] = i;
    for (int j = 'a'; j <= 'z'; j++)
    {
      if (j == str[i])
        continue;
      ch[i - 1][j - 'a'] = ch[ne[i - 1]][j - 'a'];
    }
  }
  int q;
  cin >> q;
  while (q--)
  {
    cin >> str + slen + 1;
    int tlen = strlen(str + slen + 1);
    for (int i = slen + 1; i <= slen + tlen; i++)
    {
      ne[i] = ch[ne[i - 1]][str[i] - 'a'];
      ch[i - 1][str[i] - 'a'] = i;
      for (int j = 'a'; j <= 'z'; j++)
      {
        if (j == str[i])
          continue;
        ch[i - 1][j - 'a'] = ch[ne[i - 1]][j - 'a'];
      }
    }
    for (int i = slen + 1, j = slen - 1; i <= slen + tlen; i++)
      cout << ne[i] << " \n"[i == slen + tlen];
  }
  return 0;
}
/*
  kmp优化
*/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年08月29日，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度