Codeforces Round 991 (Div. 3)

Posted on Edited on In Word count in article: 3.7k Reading time ≈ 14 mins.

人与人的差距。。。
补下题，正好 12 月 8 号要去考 CCF-CSP

  • A. Line Breaks
  • B. Transfusion
  • C. Uninteresting Number
  • D. Digital string maximization
  • E. Three Strings
  • F. Maximum modulo equality
  • G. Tree Destruction

Codeforces Round 991 (Div. 3)

A. Line Breaks

Description

Kostya has a text consisting of words made up of Latin alphabet letters. He also has two strips on which he must write the text. The first strip can hold characters, while the second can hold as many as needed.

Kostya must choose a number and write the first words from on the first strip, while all the remaining words are written on the second strip. To save space, the words are written without gaps, but each word must be entirely on one strip.

Since space on the second strip is very valuable, Kostya asks you to choose the maximum possible number such that all words fit on the first strip of length .

Input

The first line contains an integer — the number of test cases.

The first line of each test case contains two integers and — the number of words in the list and the maximum number of characters that can be on the first strip.

The next lines contain one word of lowercase Latin letters where the length of does not exceed .

Output

For each test case, output the maximum number of words such that the first words have a total length of no more than .

Example

input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
5
3 1
a
b
c
2 9
alpha
beta
4 12
hello
world
and
codeforces
3 2
ab
c
d
3 2
abc
ab
a
output
1
2
3
4
5
1
2
2
1
0

Solution

模拟即可

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
void solve() {
  int n, m;
  cin >> n >> m;
  string s;
  int flag = 1;
  int count = 0;
  int ct = 0;
  for (int i = 0; i < n; ++i) {
    cin >> s;
    if (flag && count + int(s.size()) <= m) {
      ++ct;
      count += int(s.size());
    } else {
      flag = 0;
      continue;
    }
  }
  cout << ct << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

B. Transfusion

Description

You are given an array of length . In one operation, you can pick an index from to inclusive, and do one of the following actions:

  • Decrease by , then increase by .
  • Decrease by , then increase by .

After each operation, all the values must be non-negative. Can you make all the elements equal after any number of operations?

Input

First line of input consists of one integer — the number of test cases.

First line of each test case consists of one integer .

Second line of each test case consists of integers .

It is guaranteed that the sum of of all test cases doesn't exceed .

Output

For each test case, print "YES" without quotation marks if it is possible to make all the elements equal after any number of operations; otherwise, print "NO" without quotation marks.

You can print answers in any register: "yes", "YeS", "nO" — will also be considered correct.

Example

input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
8
3
3 2 1
3
1 1 3
4
1 2 5 4
4
1 6 6 1
5
6 2 1 4 2
4
1 4 2 1
5
3 1 2 1 3
3
2 4 2
output
1
2
3
4
5
6
7
8
YES
NO
YES
NO
YES
NO
NO
NO

Solution

失智题，没观察出来

常规做法

因为 ，所以对数组所有元素和没有影响，因此如果能成功，则
因此，首先判断均数是否为整数，其次模拟操作，看能否实现

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
typedef long long ll;
using namespace std;
ll a[(int)1e5 * 2 + 10];
void solve() {
  int n;
  ll sum = 0;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    sum += a[i];
  }
  if (sum % n != 0) {
    cout << "NO" << endl;
    return;
  }
  int avg = sum / n;
  for (int i = 2; i <= n - 1; ++i) {
    a[i + 1] += a[i - 1] - avg;
    a[i - 1] = avg;
  }
  for (int i = 1; i <= n; ++i) {
    if (a[i] != avg) {
      cout << "NO" << endl;
      return;
    }
  }
  cout << "YES" << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

tourist 的提交

-https://codeforces.com/contest/2050/submission/294989092

有一个观察是，对于每个操作，必定同时改变两个偶数/奇数位上的数字，因此偶数与奇数位上的均数，也应该与整体均数相等 (Guessforces)
并且，只要偶数与奇数位上均数相等且为整数，两边的 可以任意分配超过均值的差值到其他数字，因此这个算法是有效的 废话

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
/**
 *    author:  tourist
 *    created: 05.12.2024 19:36:28
 **/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<int> a(n);
    array<int64_t, 2> sum = {0, 0};
    array<int64_t, 2> cnt = {0, 0};
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      sum[i % 2] += a[i];
      cnt[i % 2] += 1;
    }
    if (sum[0] % cnt[0] == 0 && sum[1] % cnt[1] == 0 &&
        sum[0] / cnt[0] == sum[1] / cnt[1]) {
      cout << "YES" << '\n';
    } else {
      cout << "NO" << '\n';
    }
  }
  return 0;
}

C. Uninteresting Number

Description

You are given a number with a length of no more than .

You can perform the following operation any number of times: choose one of its digits, square it, and replace the original digit with the result. The result must be a digit (that is, if you choose the digit x, then the value of must be less than ).

Is it possible to obtain a number that is divisible by through these operations?

Input

The first line contains an integer — the number of test cases.

The only line of each test case contains the number , without leading zero. The length of the number does not exceed .

Output

For each test case, output "YES" if it possible to obtain a number divisible by using the described operations, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Example

input
1
2
3
4
5
6
7
8
9
10
9
123
322
333333333333
9997
5472778912773
1234567890
23
33
52254522632
output
1
2
3
4
5
6
7
8
9
NO
YES
YES
NO
NO
YES
NO
YES
YES

Note

In the first example, from the integer , it is possible to obtain only , , , and , none of which are divisible by .

In the second example, you need to replace the second digit with its square; then will equal .

In the third example, the integer is already divisible by .

Solution

做出来了，但是 brute force.
观察到，满足 的只有 ，而能够对数位产生影响的只有 ，对应的变化里量是 ，因而，统计串中 ， 的数量，然后尝试能否组合实现总和是 的倍数
而其中， 的倍数满足所有数位上的数字和为 的倍数，也就是: 

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
  string num;
  cin >> num;
  int ct2 = 0, ct3 = 0;
  int sum = 0;
  for (char d : num) {
    if (d == '2') {
      ++ct2;
    } else if (d == '3') {
      ++ct3;
    }
    sum += d - '0';
  }
  if (sum % 9 == 0) {
    cout << "YES" << endl;
  } else {
    // brute force --- 枚举
    for (int i = 0; i <= ct2; i++) {
      for (int j = 0; j <= ct3; j++) {
        if ((sum + i * 2 + j * 6) % 9 == 0) {
          cout << "YES" << endl;
          return;
        }
      }
    }
    for (int i = 0; i <= ct3; i++) {
      for (int j = 0; j <= ct2; j++) {
        if ((sum + i * 6 + j * 2) % 9 == 0) {
          cout << "YES" << endl;
          return;
        }
      }
    }
    cout << "NO" << endl;
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

D. Digital string maximization

Description

You are given a string , consisting of digits from to . In one operation, you can pick any digit in this string, except for or the leftmost digit, decrease it by , and then swap it with the digit left to the picked.

For example, in one operation from the string , you can get or .

Find the lexicographically maximum string you can obtain after any number of operations.

Input

The first line of the input consists of an integer — the number of test cases.

Each test case consists of a single line consisting of a digital string , where denotes the length of . The string does not contain leading zeroes.

It is guaranteed that the sum of of all test cases doesn't exceed .

Output

For each test case, print the answer on a separate line.

Example

input
1
2
3
4
5
6
7
6
19
1709
11555
51476
9876543210
5891917899
output
1
2
3
4
5
6
81
6710
33311
55431
9876543210
7875567711

Solution

做的时候想用贪心，但是没想明白，题解确实是 greedy + brute force。还是缺少 Guessforce，思维题练太少。

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
  string s;
  cin >> s;
  int n = s.size();
  int max, value;
  for (int i = 0; i < n; ++i) {
    max = i;
    for (int j = i + 1; j < n; ++j) {
      if (j - i >= 9) break;  // 差距达到 9 时，被一直前移的数字变为 0.
      value = s[j] - (j - i);
      if (value > s[max] - (max - i)) {
        max = j;
      }
    }
    // 前移最大数字，substr慢死了。。
    // s = s.substr(0, i) + char(s[max] - (max - i)) + s.substr(i, max - i) +
    //     s.substr(max + 1);
    if (i != max) {
      char tmp = char(s[max] - (max - i));
      for (int j = max; j > i; --j) {
        s[j] = s[j - 1];
      }
      s[i] = tmp;
    }
  }
  cout << s << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

E. Three Strings

Description

You are given three strings: , and , consisting of lowercase Latin letters. The string was obtained in the following way:

  1. At each step, either string or string was randomly chosen, and the first character of the chosen string was removed from it and appended to the end of string c, until one of the strings ran out. After that, the remaing characters of the non-empty string were added to the end of .
  2. Then, a certain number of characters in string were randomly changed.

For example, from the strings and , without character replacements, the strings , , could be obtained.

Find the minimum number of characters that could have been changed in string .

Input

The first line of the input contains a single integer — the number of test cases.

The first line of each test case contains one string of lowercase Latin letters — the first string, where denotes the length of string .

The second line of each test case contains one string of lowercase Latin letters — the second string, where denotes the length of string .

The third line of each test case contains one string of lowercase Latin letters — the third string.

It is guaranteed that the sum of across all test cases does not exceed . Also, the sum of across all test cases does not exceed .

Output

For each test case, output a single integer — the minimum number of characters that could have been changed in string .

Example

input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
7
a
b
cb
ab
cd
acbd
ab
ba
aabb
xxx
yyy
xyxyxy
a
bcd
decf
codes
horse
codeforces
egg
annie
egaegaeg
output
1
2
3
4
5
6
7
1
0
2
0
3
2
3

Solution

当时没看这题，现在看以为能做，写了个 BFS 上去。

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pb push_back
typedef long long ll;
const ll LLMAX = 9223372036854775807;
const double PI = acos(-1);
using namespace std;
int bfs(string &a, string &b, string c) {
  int mi = LLMAX, ct;
  int la = a.size(), lb = b.size(), lc = c.size();
  queue<tuple<int, int, string>> q;
  q.push({0, 0, ""});
  while (q.size()) {
    tuple<int, int, string> t = q.front();
    q.pop();
    if (get<0>(t) != la && get<1>(t) != lb) {
      q.push({get<0>(t) + 1, get<1>(t), get<2>(t) + a[get<0>(t)]});
      q.push({get<0>(t), get<1>(t) + 1, get<2>(t) + b[get<1>(t)]});
    } else {
      if (get<0>(t) == la) {
        get<2>(t) += b.substr(get<1>(t));
      } else {
        get<2>(t) += a.substr(get<0>(t));
      }
      ct = 0;
      for (int i = 0; i < (int)lc; ++i) {
        ct += c[i] != get<2>(t)[i];
      }
      mi = min(ct, mi);
    }
  }
  return mi;
}
void solve() {
  string a, b, c;
  cin >> a >> b >> c;
  cout << bfs(a, b, c) << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

不出意外 TLE
遂去看了tourist 的代码
其实是二维 dp ，计算 a 的前 i 个和 b 的前 j 个字符和 c 前 i+j 个字符的最小区别

于是所求的最小差是

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
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
  string a, b, c;
  cin >> a >> b >> c;
  int la = a.size(), lb = b.size();
  vector<vector<int>> dp(la + 1, vector<int>(lb + 1, la + lb));
  dp[0][0] = 0;
  for (int i = 0; i <= la; ++i) {
    for (int j = 0; j <= lb; ++j) {
      if (i < la)
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (int)(a[i] != c[i + j]));
      if (j < lb)
        dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + (int)(b[j] != c[i + j]));
    }
  }
  cout << dp[la][lb] << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  cin >> t;
  while (t--) solve();
  return 0;
}

F. Maximum modulo equality

Description

You are given an array of length and queries , .

For each query, find the maximum possible , such that all elements are equal modulo . In other words, , where — is the remainder of division by . In particular, when can be infinite, print .

Input

The first line contains a single integer — the number of test cases.

The first line of each test case contains two integers , — the length of the array and the number of queries.

The second line of each test case contains integers — the elements of the array.

In the following lines of each test case, two integers , are provided — the range of the query.

It is guaranteed that the sum of across all test cases does not exceed , and the sum of does not exceed .

Output

For each query, output the maximum value described in the statement.

Example

input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
3
5 5
5 14 2 6 3
4 5
1 4
2 4
3 5
1 1
1 1
7
1 1
3 2
1 7 8
2 3
1 2
output
1
2
3
3 1 4 1 0
0
1 6

Solution

没做出来，只想到 gcd，数据结构没学，就这样了

线段树

看大佬bezime的代码，用了线段树，mark 一下，下次去学

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
#include<bits/stdc++.h>
#define ll long long
#define par pair<ll,ll>
#define prr pair<ll,par>
#define st first
#define nd second
#define ld long double
#define MX 1000000000000ll
#define MO 1000000007ll
// #define MO 998244353ll
#define MN 0.000001
#define MXM 2000002
#define MXN 200002
#define PP 131ll
#define LG 20
using namespace std;
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}
/*
BBBBBBB  ZZZZZZZZ MM         MM
BB    BB      ZZ  MMM       MMM
BB    BB     ZZ   MMMM     MMMM
BBBBBBB     ZZ    MM MM   MM MM
BB    BB   ZZ     MM  MM MM  MM
BB    BB  ZZ      MM   MMM   MM
BBBBBBB  ZZZZZZZZ MM    M    MM
*/
ll T=1,n,nl,q,a[MXN];
ll st[MXN][LG];
ll ask(ll l,ll r){
    if(l>r) return 0;
    ll x=log2(r-l+1);
    return __gcd(st[l][x],st[r-(1<<x)+1][x]);
}
void solve(){
    rd(n),rd(q);
    for(ll i=1;i<=n;i++)
        rd(a[i]),st[i][0]=abs(a[i]-a[i-1]);
    nl=log2(n);
    for(ll k=1;k<=nl;k++)
        for(ll i=1;i+(1<<(k-1))<=n;i++)
            st[i][k]=__gcd(st[i][k-1],st[i+(1<<(k-1))][k-1]);
    while(q--){
        ll l,r;
        rd(l),rd(r);l++;
        pt(ask(l,r)),putchar(' ');
    }
    puts("");
}int main(){rd(T);while(T--) solve();}

ST表

  • 官方题解

2050F - Maximum modulo equality

Let's look at two arbitrary integers and . Now we want to find the maximum , which satisfies . We know that x    m = y    m, then , because they have the same remainder by . That means that any which is a divisor of will satisfy the required condition.

Now let's generalize the idea we've obtained to the segment: means that , and , and , and . So, must be a divisor of , , , at the same time. That means that should be , where is the greatest common divisor. , when all the elements on the segment are equal.

Let's build an array consisting of differences of adjacent elements; now we can use sparse table to find GCD on the segments efficiently.

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
#include <bits/stdc++.h>
using namespace std;
const int LOGN = 20;

vector<vector<int>> stGCD;
int get_gcd(int l, int r) {
  int k = __lg(r - l + 1);
  return __gcd(stGCD[k][l], stGCD[k][r - (1 << k) + 1]);
}

void solve() {
  stGCD.clear();
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (int &x : a) cin >> x;

  vector<int> b;
  for (int i = 1; i < n; i++) b.push_back(abs(a[i - 1] - a[i]));

  stGCD.resize(LOGN, vector<int>(b.size(), 1));
  for (int i = 0; i < b.size(); i++) stGCD[0][i] = b[i];
  for (int i = 1; i < LOGN; i++)
    for (int j = 0; j + (1 << (i - 1)) < b.size(); j++)
      stGCD[i][j] = __gcd(stGCD[i - 1][j], stGCD[i - 1][j + (1 << (i - 1))]);

  while (q--) {
    int l, r;
    cin >> l >> r;
    if (l == r) {
      cout << 0 << " ";
      continue;
    }
    l--;
    r -= 2;
    int gcd = get_gcd(l, r);
    cout << gcd << " ";
  }
}

int main() {
  int TESTS = 1;
  cin >> TESTS;
  while (TESTS-- > 0) {
    solve();
    cout << "\n";
  }
  return 0;
}