Codeforces Global Round 7 Solution

  Codeforces Global Round 7比赛练习题解,个人使用,参考自官方题解。

A. Bad Ugly Number

描述:

  给定$n$($0 \leq n \leq 10^5$),找到任意一个数整数$s$,满足:

  • $s > 0$
  • $s$由$n$个数字组成
  • $s$中的任意一位数不等于$0$
  • $s$不能被它的各位整除

  每个输出包括$t$组,若存在这样的$s$则输出一个,否则输出$-1$。

解题思路:

  构造题,当$n=1$时显然是找不到$s$的,输出$-1$,否则输出$22…223$,一共$n-1$个$2$。

程序实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int main(){
int t, n;
cin >> t;
while (t--){
cin >> n;
if (n == 1){
cout << -1 << endl;
continue;
}
for(int i = 1;i < n;i++)
cout << '2';
cout << 3 << endl;
}
return 0;
}

B. Maximums

描述:

  你有一个非负整数数组 $a_1,a_2,…,a_n$ ,对于每一个 $1 \leq i \leq n$,令$x_i = \max(0,a_1,…,a_{i-1})$。特别的,$x_1 = 0$。现在令$b_i = a_i - x_i$。给定$b[]$数组,要求输出$a[]$数组。

解题思路:

  由于$x_1 = 0$,那么显然有$a_1 = b_1$。显然由$a_1,…,a_i$已知,可以推出$x_{i+1}$,进而推出$a_{i+1}$,如此反复,直到推出所有的$a_i$。考虑到$x_i = \max(0,a_1,…,a_{i-1})$,我们可以令$ma = x_1$,这样每次迭代更新$ma = \max(ma, a_i)$即可。

程序实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<cmath>
using namespace std;

int main(){
long long n, ma = 0;
cin >> n;
for(int i = 1, x;i <= n;i ++){
cin >> x;
cout << x + ma << " ";
ma = max(x + ma, ma);
}
return 0;
}

C. Permutation Partitions

描述:

  给你一个由$1到n$组成的序列,现给定$k(k\leq n)$,要求将原序列分割成不重合的k段(这k段必须包含整个序列)。定义每段分区最大值的和为分区值,求:

  1. 最大分区值
  2. 使分区值取得最大的分区有多少种情况

    解题思路:

      对于第一个问题,显然的最大分区值就是从$n$向$n-k+1$求和的值。那么分区有多少种情况呢?我们考察$n$到$n-k+1$分割的$k+1$段序列长度。令$d_i = length\ of\ section\ i$,那么显然答案应该为$\prod_{i=1}^{k-1}{d_i+1}$。在实际处理种可以简单优化使得$d_i$的储存为$O(1)$的空间复杂度,整个算法只用遍里一次原数组。

    程序实现:

    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
    #include<iostream>
    using namespace std;
    typedef long long ll;
    const ll MAXN = 200005;
    const ll MOD = 998244353;
    int main(){
    ll n, k, ans1 = 0, ans2 = 1;
    ll dis = 0;
    cin >> n >> k;
    for(ll i = 0;i < k;i++)
    ans1 += n - i;
    k = n - k + 1;
    for(ll i = 1, x;i <= n;i++){
    cin >> x;
    if (x >= k){
    if (dis != 0){
    ans2 *= (i - dis);
    ans2 %= MOD;
    }
    dis = i;
    }
    }
    cout << ans1 << " " << ans2;
    return 0;
    }

D. Prefix-Suffix Palindrome

描述:

给定字符串$s$,要求求它的一个最长字串$t$,满足:

  1. $t$是回文串
  2. $t$由$s$的前缀和后缀拼接而成(前缀和后缀可为空串)

    解题思路:

      我们将$t$分成两部分,一个是前后缀中共同组成回文的部分,另一个是中间部分的回文串。对于前者我们直接逐个比较$s[i]==s[n-i-1]$即可。对于中间部分,我们将中间部分取出,设为$x$,现在的问题是求$x$的最大回文前缀或者最大回文后缀。

  令我没有想到的是这个可以利用前缀数组求,即构造$x’=x+”*”+\check{x}$,然后求一下前缀数组即可,最后一位前缀值就是最长的前缀回文长度。然后我们对$x$正序做一次,逆序做一次然后比较长度就可以了。

程序实现:

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 2e6 + 5;
int pi[MAXN], j;

inline string solve_mid(const string s){
string str = s;
reverse(str.begin(), str.end());
str = s + "#" + str;
int n = str.size();
pi[0] = 0, j = 0;
for(int i = 1;i < n;i++){
while (j > 0 && str[j] != str[i]) j = pi[j - 1];
if(str[j] == str[i]) j++;
pi[i] = j;
}
return str.substr(0, j);
}

inline void solve(){
string s;
cin >> s;
int n = s.size();
int i = 0;
while (s[i] == s[n - i - 1] && i < n - i - 1) i++;
if(i > 0) cout << s.substr(0, i);
if(2 * i < n){
string sub = s.substr(i, n - 2 *i);
string a = solve_mid(sub);
reverse(sub.begin(), sub.end());
string b = solve_mid(sub);
cout << (a.size() > b.size() ? a : b);
}
if(i > 0) cout << s.substr(n - i, i);
cout << endl;
}

int main(){
int t;
cin >> t;
while (t--)
solve();
return 0;
}

总结

  因为之前时间安排问题,这是我的第一篇题解(其实CF一直在打)。虽然自己很菜,也没想过能够在ACM上拿奖,但是总不能拉下太多吧。毕竟总不能刚开始来的时候大家一样菜,一年后人家摘金夺银你毫无进步吧。