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


闲言

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

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

后续题解先咕一会儿。

代码附在后面

A

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

  1. 1个,答案显然为0。
  2. 2个,一次最多能涂两个相同颜色的,所以答案显然为1。
  3. 3个,此时有一种字母有两个,分为两个相邻与两个相隔的情况,可以发现都只需要一步可以变为有三个相邻的状态,答案为2。
  4. 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的最大最小值。

  1. bj >= ai
  2. 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的做法,最大值最小值分开处理。

  1. 最小值就是能匹配的最小的值。
  2. 最大值就是在满足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优化
*/

声明:残城三梦|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 【算法竞赛】CF Edu #134 (Rated for Div. 2) A - E Rethink


Live In Fly && Live Infinitely