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$。

程序实现：

#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)$即可。

程序实现：

#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)$的空间复杂度，整个算法只用遍里一次原数组。

   程序实现：

   #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$正序做一次，逆序做一次然后比较长度就可以了。

程序实现：

#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上拿奖，但是总不能拉下太多吧。毕竟总不能刚开始来的时候大家一样菜，一年后人家摘金夺银你毫无进步吧。