# Educational Codeforces Round 92 (CF1389) 题解

# Problem A - LCM Problem (opens new window)

# 题目描述

给定范围[L,R][L,R]L<RL<R),找出两个数xxyyLx<yRL\leq x<y\leq R),使得LLCM(x,y)RL\leq LCM(x,y)\leq R

# 题解

首先,我们有x<y,LCM(x,y)2x\forall x<y, LCM(x,y)\geq2x。证明很简单,设GCD(x,y)=gGCD(x,y)=gx=agx=agy=bgy=bg,显然有b2b\geq2,则LCM(x,y)=abg2ag=2xLCM(x,y)=abg\geq2ag=2x

那么就可以贪心地给出答案了,如果R2LR\geq2L,我们可以使用(L,2L)(L,2L)这组答案;否则无解。

时间复杂度O(1)O(1)

参考代码(C++)
#include <cstdio>
#include <iostream>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve() {
    int l, r;
    read(l), read(r);
    if (r >= l * 2)
      printf("%d %d\n", l, l * 2);
    else
      printf("-1 -1\n");
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# Problem B - Array Walk (opens new window)

# 题目描述

11NNNN个位置,从11开始,初始分数为a1a_1,每次可以向左或向右移动,并得到所在位置的分数,但不能连续两次向左移动。总共移动kk1kN11\leq k\leq N-1)次,其中至多左移zz0zmin(5,k)0\leq z\leq\min(5,k))次。求能够取得的最高分数。

# 题解

我们总可以把最后的总得分分为两部分,一部分是1,,E1,\cdots,E的总分(其中EE)是最远走到的位置,剩下的则是iali+ali1\sum_ia_{l_i}+a_{l_i-1},其中lil_i为第ii次向左走时所在的位置。假设向左走xx次,则我们向右的最远距离E=k+12xE=k+1-2x。另一方面,我们应当在ai+ai1a_i+a_{i-1}最大的位置来回左右走,这样一定优于在别的位置用掉向左的机会。所以我们可以预计算出ai+ai1a_i+a_{i-1}的前缀最大值LiL_i,最后的最高分数就是

maxx=0z(Lk+12xx+Sk+12x)\max_{x=0}^z(L_{k+1-2x}\cdot x+S_{k+1-2x})

其中SiS_i为前缀和。

时间复杂度O(n)O(n)

参考代码(C++)
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve() {
    int n, k, z;
    read(n), read(k), read(z);
    vector<int> a(n), s(n + 1), l(n);
    for (int i = 0; i < n; ++i) {
      read(a[i]), s[i + 1] = s[i] + a[i];
      if (i >= 1)
        l[i] = max(l[i - 1], a[i] + a[i - 1]);
    }
    int ans = s[k + 1];
    for (int j = 1; j <= z && 2 * j <= k; ++j)
      ans = max(ans, l[k + 1 - j * 2] * j + s[k + 1 - j * 2]);
    printf("%d\n", ans);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# Problem C - Good String (opens new window)

# 题目描述

左循环一位和右循环一位得到的字符串相同的字符串称为“好字符串”。问给定字符串至少删去几个字母可以变为“好字符串”?

# 题解

“好字符串”等价于i,si=si+2\forall i, s_i=s_{i+2}。所以我们可以枚举最后的循环节,然后看原始字符串中最多包含多少个这一循环节。

时间复杂度O(sc2)O(|s|c^2),其中cc为字母表中的字母数(本题为1010)。

参考代码(C++)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> cnt(10);
    for (char c : s)
      cnt[c - '0']++;
    int ans = n - *max_element(cnt.begin(), cnt.end());
    for (int i = 0; i < 10; ++i)
      for (int j = 0; j < 10; ++j) {
        vector<char> t{(char)(i + '0'), (char)(j + '0')};
        int tot = 0, idx = 0;
        for (char c : s) {
          if (c == t[idx]) {
            idx++;
            if (idx == 2)
              tot++, idx = 0;
          }
        }
        ans = min(ans, n - tot * 2);
      }
    printf("%d\n", ans);
  }
};

int main() {
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# Problem D - Segment Intersections (opens new window)

# 题目描述

最开始有[al1,ar1]=[al2,ar2]==[aln,arn]=[l1,r1][al_1,ar_1]=[al_2,ar_2]=\dots=[al_n,ar_n]=[l_1,r_1]nn[bl1,br1]=[bl2,br2]==[bln,brn]=[l2,r2][bl_1,br_1]=[bl_2,br_2]=\dots=[bl_n,br_n]=[l_2,r_2]。每次可以选择任一区间[x,y][x,y],将其变为[x1,y][x-1,y][x,y+1][x,y+1]。定义区间总重叠长度

I=i=1nintersection([ali,ari],[bli,bri])I=\sum_{i=1}^n intersection([al_i,ar_i],[bl_i,br_i])

问最少操作多少次,可以使得IkI\geq k

# 题解

不妨假设l1<=l2l_1<=l_2(否则交换即可)。

第一种情况是r1<l2r_1<l_2,也即两段初始不相交。这就意味着对于每一对区间,最开始有l2r1l_2-r_1次操作是不提升总和的。之后有r2l1r_2-l_1次操作可以以11的代价提升总和,再之后需要以22的代价提升总和。令p=r2l1p=r_2-l_1。如果np<knp<k,那么我们即使把每一对区间都变成[l1,r2][l_1,r_2]也不够,总需要使用到代价为22的操作。否则,假设m=kpm=\left\lceil\frac{k}{p}\right\rceil,我们需要比较对mm对区间进行操作(激活,再进行代价为11的操作),以及对m1m-1对区间进行操作(激活,进行代价为11的操作,剩余次数用代价为22的操作完成)。为什么不需要考虑m2m-2以及更小的值呢?因为激活的花费l2r1l_2-r_1总小于代价为11的操作比起代价为22的操作所能够节省的r2l1r_2-l_1

第二种情况是r1l2r_1\geq l_2,也即两段初始相交,这样就没有激活的代价,之后有l2l1+r2r1l_2-l_1+|r_2-r_1|次代价为11的操作,再之后是代价为22的操作。注意有两种特殊情况需要单独考虑:

  • I0kI_0\geq k,也即一开始已经满足条件。
  • l1=r1,l2=r2l_1=r_1,l_2=r_2,此时l2l1+r2r1=0l_2-l_1+|r_2-r_1|=0,只能进行代价为22的操作。

对于一般情况,因为没有激活成本,所以一定先用代价为11的操作,如果还不够,再用代价为22的操作。

时间复杂度O(1)O(1)

参考代码(C++)
#include <cstdio>
#include <iostream>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve() {
    int n, k;
    read(n), read(k);
    int l1, r1, l2, r2;
    read(l1), read(r1), read(l2), read(r2);
    if (l1 > l2) {
      swap(l1, l2);
      swap(r1, r2);
    }
    ll ans;
    if (r1 < l2) {
      int start = l2 - r1, supply = r2 - l1;
      int need = (k - 1) / supply + 1;
      if (need > n) {
        ans = (ll)n * (start + supply) + 2 * (k - n * supply);
      } else {
        ans = (ll)need * start + k;
        if (need > 1)
          ans = min(ans, (ll)(need - 1) * (start + supply) +
                             (k - (need - 1) * supply) * 2);
      }
    } else {
      ll current = (ll)n * (min(r1, r2) - l2);
      if (current >= k) {
        ans = 0;
      } else {
        k -= current;
        int supply = l2 - l1 + abs(r2 - r1);
        if (supply == 0) {
          ans = 2 * k;
        } else {
          int need = (k - 1) / supply + 1;
          if (need <= n)
            ans = k;
          else
            ans = (ll)n * supply + 2 * (k - n * supply);
        }
      }
    }
    printf("%lld\n", ans);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

# Problem E - Calendar Ambiguity (opens new window)

# 题目描述

某个国家,一年有mm个月,每个月有dd天,每个星期有ww天(1m,d,w1091\leq m,d,w\leq10^9)。每年的第一天也一定是星期一(最后一个星期可能是不完整的)。一个数对(x,y)(x,y)x<yx<y)被称为“混淆对”,当且仅当xxyy天和yyxx天是一个星期中的同一天。问一共有多少“混淆对”。

# 题解

不妨翻译一下,xxyy天和yyxx天是一个星期中的同一天,其实就是说(x1)d+y((y1)d+x)=(yx)(1d)0modw(x-1)d+y-((y-1)d+x)=(y-x)(1-d)\equiv0\mod w

GCD(w,d1)=gGCD(w,d-1)=g,则yx0modwgy-x\equiv0\mod\frac{w}{g}。因为x<ymin(m,d)x<y\leq\min(m,d),所以在y=yiy=y_i时,xxyi1w/g\left\lfloor\frac{y_i-1}{w/g}\right\rfloor种取法。不妨假设wg=3\frac{w}{g}=3,我们尝试写出yi1w/g\left\lfloor\frac{y_i-1}{w/g}\right\rflooryiy_i的变化。

yi=1,2,3,4,5,6,7,8,9,10,y_i=1,2,3,4,5,6,7,8,9,10,\cdots

yi1w/g=0,0,0,1,1,1,2,2,2,3,\left\lfloor\frac{y_i-1}{w/g}\right\rfloor=0,0,0,1,1,1,2,2,2,3,\cdots

显然可以分组聚合后再进行等差数列求和。

参考代码(C++)
#include <cstdio>
#include <iostream>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

class Solution {
public:
  void solve() {
    int m, d, w;
    read(m), read(d), read(w);
    if (m == 1 || d == 1) {
      printf("0\n");
      return;
    }
    int g = gcd(d - 1, w);
    int k = w / g;
    int t = min(m, d);
    int t0 = t / k * k, t1 = t % k;
    ll ans = (ll)t0 * (t0 / k - 1) / 2 + t1 * (t0 / k);
    printf("%lld\n", ans);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  while (t--) {
    Solution solution = Solution();
    solution.solve();
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

# Problem F - Bicolored Segments (opens new window)

待补做。

# Problem G - Directing Edges (opens new window)

待补做。