Codeforces Round 856 (Div. 2)

文章目录

• • • • A. Prefix and Suffix Array
      • • 题目大意
        • 题目分析
        • code
      • B. Not Dividing
      • • 题目大意
        • 题目分析
        • code
      • C. Scoring Subsequences
      • • 题目大意
        • 题目分析
        • code

A. Prefix and Suffix Array

题目大意

给出一个字符串所有的非空前后缀，判断原字符串是否为回文串。

题目分析

我们可以找到1-n-1的前缀和2-n的后缀，若原串满足回文串，则次两部分拼接成的字符串也应该满足回文串。

code

#includeusing namespace std;int n, m, k, t;void solve()
{cin >> n;string str = "";for(int i = 0; i < 2 * n - 2; i ++){string s;cin >> s;if(s.size() == n - 1) str += s;}bool flag = true;for(int i = 0; i < str.size() / 2; i ++){//cout << str[i] << "-----" << str[ (2 * n - 2) - i - 1] << "\n";if(str[i] != str[(2 * n - 2) - 1 - i]){flag = false;break;}}if(flag) puts("YES");else puts("NO");
}int  main()
{cin >> t;while(t --) solve();return 0;
}

B. Not Dividing

题目大意

已知n个正整数的数组。在一次操作中，您可以选择数组中的任意数字并向其添加1。最多做2n次操作，使数组满足以下性质:ai+1不能被ai整除。打印出经过操作后得到的数组。

题目分析

对于两个数 a 和 b 如果 a 能整除 b 则 a + 1 一定不能整除 b ，当然前提是a!=1。所以我们将所有数值为1的元素统一加一变成2，再遍历改数即可。对于 ai 和 ai-1 要注意不能修改 ai-1，可能会造成后续错误。

code

#includeusing namespace std;const int N = 1e4 + 10;int n, m, k, t;
int a[N];void solve()
{cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];if(a[i] == 1) a[i] ++;}for(int i = 2; i <= n; i ++)if(a[i] % a[i - 1] == 0) a[i] ++;for(int i = 1; i <= n; i ++) cout << a[i] << " ";puts("");
}int  main()
{cin >> t;while(t --) solve();return 0;
}

C. Scoring Subsequences

题目大意

一个序列的得分定义为序列数字的乘积除以序列元素个数的阶乘。题目要求分别找出a1~ai中是的得分最大的子序列的元素个数(1<=i

题目分析

最重要的一点是题目中所给的序列是非递增（从小到大），我们可以看某个元素是否对答案有贡献，如果有贡献的话，就累加到答案中。

首先我们肯定要从最后一个元素往前选，假设之前已经有 cnt 个元素，已经遍历到了第i个前缀，若a[i-cnt] > cnt则多选一个元素一定不会亏。

code

#includeusing namespace std;const int N = 1e5 + 10;int n, m, k, t;
int a[N];void solve()
{cin >> n;for(int i = 1; i <= n; i ++) cin >> a[i];int cnt = 1;cout << cnt << " ";for(int i = 2; i <= n; i ++){if(a[i - cnt] > cnt) cnt ++;cout << cnt << " ";}puts("");
}int main()
{cin >> t;while(t --) solve();return 0;
}