程序员进阶之算法练习（九十四）
题目1
题目链接 题目大意： 有n个整数组成的数组a，现在可以对数组a的元素任意打乱顺序，要求满足： 假设打乱后的数组是b，要满足：𝑏1+𝑏2=𝑏2+𝑏3=…=𝑏𝑛−1+𝑏𝑛=k 也就是相邻两个数字的和相同。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例两行 第一行整数𝑛(2≤𝑛≤100) 第二行n个整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤1e5).
输出： 每个样例一行，通过打乱顺序生成满足要求的数组，如果有解，则输出YES；如果无解，则输出NO；
Examples input 5 2 8 9 3 1 1 2 4 1 1 4 5 5 2 3 3 3 3 4 100000 100000 100000 100000
output Yes Yes No No Yes
题目解析： 将两两相邻的数字相加，a1+a2, a2+a3... 全部累加，得到(a1+a2)+(a2+a3)+(a3+a4)... 最终就是a1+2x(a2+a3+...+a[n-1])+an 这样只要枚举a1和an的值，就可以通过数组和sum，快速得到(a2+a3+...a[n-1])=sum-a1-an； 那么两数相加和k = (a1 + 2x(sum-a1-an) + an) / (n - 1)；
a1是枚举，那么a2=k-a1，以此类推枚举a3，在这个过程中如果发现数组b不存在当前的数字，那么则无解。 但是走到这步的时候，发现了数组的规律： a1, k - a1, a1, k-a1 其实不用复杂计算，最终数组结果必然只有2个数字。 那么只需要统计数组a的元素，如果大于2个元素则必然无解。 只有1个元素，或者2个元素的数量相差不超过1，就有解。
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int sum = 0;
map<int, int> h;
vector<int> vec;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum += a[i];
h[a[i]]++;
if (h[a[i]] == 1) vec.push_back(a[i]);
}
int ans = 0;
if (vec.size() == 1) ans = 1;
else if (vec.size() == 2) {
if (abs(h[vec[0]] - h[vec[1]]) <= 1) ans = 1;
}
cout << (ans ? "YES" : "NO") << endl;
}
}
}
ac;题目2
题目链接 题目大意： 有两个0、1组成的字符串s和t，长度分别为n和m； 如果字符串a满足 对所有的 all 𝑖=1,2,…,𝑘−1 ，有 𝑎𝑖≠𝑎𝑖+1，则可以认为字符串a是good；
现在允许在字符串s中任意位置插入若干次字符串t，问最终能否生成一个good的字符串；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例3行 第1行整数𝑛 and 𝑚 (1≤𝑛,𝑚≤50 ) 第2、3行分别是字符串s和t
输出： 每个样例一行，如果可以生成good字符串，则输出YES；否则输出NO；
Examples input 5 1 1 1 0 3 3 111 010 3 2 111 00 6 7 101100 1010101 10 2 1001001000 10
output Yes Yes No No No
题目解析： 按照题目要求，good字符串就是字符0和1交替的字符串，比如说10101或者0101； 那么字符串中如果存在00或者11，就表示不满足要求；
由于题目可以插入字符串t，那么首先对字符串t做同样的检查，要求不含有00和11； 字符串t要插入到字符串s中，且只会插入到00和11，那么必然字符串首尾必然相同，要么都是0、要么都是1；
字符串s如果仅存在00或者11，那么可以考虑插入符合要求的字符串t； 00只会插入首尾都是1的good字符串t； 11只会插入首尾都是0的good字符串t；
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
int flag[2] = {0};
for (int i = 1; i < n; ++i) {
if (s[i] == s[i - 1]) flag[s[i] - '0'] = 1;
}
int ans = 0;
if (flag[0] + flag[1] == 0) ans = 1;
else if (flag[0] + flag[1] == 2) ans = 0;
else {
int sec[2] = {0};
for (int i = 1; i < m; ++i) if (t[i] == t[i - 1]) sec[t[i] - '0'] = 1;
if (sec[0] + sec[1] == 0 && t[0] == t[m - 1] && (flag[t[0] - '0']== 0)) {
// 不含00和11，并且头尾相同，并且互补
ans = 1;
}
}
cout << (ans ? "YES" : "NO") << endl;
}
}
}
ac;题目3
题目链接 题目大意： 有一堆石子，初始的时候有若干个； 有两个人在玩游戏，每个人轮流移除石子，每次可以移除a个石子或者b个石子，无法移除者失败； 假设两个都采用了理想最优策略，现在已知a和b，问最初的时候有多少个石子，能够保证后手者胜利。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例一行，整数𝑎 and 𝑏 (1≤𝑎<𝑏≤100)
输出： 每个样例一行，输出初始化状态的石子数量𝑛 (1≤𝑛≤1e6 )；
Examples input 3 1 4 1 5 9 26
output 2 6 3
题目解析： 只要让先手者不能取，那么后手者胜利。 a>1，则直接n=1，先手无解； a=1，则n=a+b，先手不管取a或者b，后手跟着取b或者a即可；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int x, y;
cin >> x >> y;
if (x > 1) cout << 1 << endl;
else cout << x + y << endl;
}
}
}
ac;题目4
题目链接 题目大意： 首先定义MEX，对于一个区间，这个区间内未出现过的最小正整数就是这个区间的MEX值； [2,3,1,5,4]的MEX值就是6；
现在需要构造一个的整数数组，要求满足： 1、数组的元素是由1到n的排列组成； 2、数组所有的子区间，MEX值是素数的尽可能多；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行，整数𝑛 (1≤𝑛≤200000).
输出： 每个样例一行，输出1到n的n个整数。
Examples input 3 2 1 5
output 2 1 1 5 2 1 4 3
题目解析： 根据题目的要求，如果某个区间中，数字1没有出现，那么必然MEX值为1，1不是素数； 那么1必然要被包括在区间内；
想要让区间的MEX为素数，那么这个区间内就不要包括某个素数，这里选择2和3；（因为最小，最容易满足） 只要2不出现在区间中，那么区间的MEX值必然为2； 比如说1xxx2，区间1x 1xx 1xxx都满足要求；
为了让结果尽可能大，应该要让数字均匀分布在1的左右两边； 形成 2 xxxx 1 xxxxx 3这样的布局，就可以让结果尽可能的多。
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
for (int i = 2; i < N; ++i) {
int m = sqrt(i) + 1, find = 0;
for (int j = 2; j <= m && j < i; ++j) {
if (i % j == 0) find = 1;
}
a[i] = !find;
}
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
if (n == 1) cout << "1" << endl;
else if (n == 2) cout << "2 1" << endl;
else {
vector<int> ans;
ans.push_back(2);
for (int i = 0; i < (n - 3) / 2; ++i) ans.push_back(4 + i);
ans.push_back(1);
for (int i = (n - 3)/ 2; i < n - 3; ++i) ans.push_back(4 + i);
ans.push_back(3);
// for (int i = 2; i <= n; ++i) if (!a[i]) ans.push_back(i);
for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";
cout << endl;
}
}
}
}
ac;题目5
题目链接 题目大意： 有n个整数的数组，现在可以对数组进行操作： 1、选择某个位置的元素； 2、移除该元素； 3、如果该元素原来左右两边均有数字，那么这两个数字也会移除，合并成一个新的数字；（如果左右两边只有1个数字，则不会触发合并） 如下图所示：
现在想知道，经过若干次操作后，数组剩下一个元素时，这个元素最大值为多少？
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例第一行整数𝑛 (1≤𝑛≤20000). 接下来n个整数 𝑐1,…,𝑐𝑛(−1e9≤𝑐𝑖≤1e9).
输出： 每个样例一行，输出结果的最大值。
Examples input 3 6 -3 1 4 -1 5 -9 5 998244353 998244353 998244353 998244353 998244353 1 -2718
output 9 2994733059 -2718
题目解析： 这个题目最终实现不复杂，但是在分析过程踩了一下坑，这里特意做一个记录，简单回顾下出问题点。
最开始的思路： 简化题目，只考虑有正数的情况，是否有简单的策略： 每次会发生可能两个行为，数字移除+数字合并，数字移除会减少一个数字并影响最终的和，数字合并不会直接影响最终的和，但是仍然会对结果有影响，因为我们减少了一个可移除的数字选择； 比如说【10，5，1，5，10】这样的数组，当我们先选择1时，剩下【10， 10，10】，最终结果是20；如果只选择移除整数5，那么最终结果是21； 那么就不能采用简单的从最小开始移除的合并策略（尤其此时还没引入负数）。 观察区间的特性，我们知道对于每一个新增的数字，有两个选择： 1、直接移除，此时在最右边，原来区间不会发生任何事情； 2、原区间右边最右整数被移除，当前数字被进行合并； 根据两个选择可以得到对应的状态转移方案。
到这里整体思路还算清晰，但是出现一个问题，当进行决策1之后，该位置的数字必须全部摒弃。 那么每个位置应该有两个状态： 1、当前数字是被移除；（dp[i][0]) 2、当前数字是保留的状态；(dp[i][1]) dp[i][0]可以由dp[i-1][1]转移，dp[i][1]可以由dp[i-1][0]转移，转移方程： dp[i][0] = dp[i-1][1]; dp[i][1] = max(0LL, dp[i-1][0]) + a[i];
看着一切美好，但是在遇到下面这串样例的时候，问题就出现了： 5 -1 -2 -3 6
这里动态规划会出问题，因为当a[i]=6时，我们选择保留元素6，那么就会remove -3，结果就是-2和6合并了。 我们知道最优解是先选择数字-2，生成5 -4 6；再选择-4，得到结果11； 因为这里的决策无后效性并不满足。
舍弃动态规划，从题目的操作特性来分析，对于相邻的两个数字，必然不能融合。 奇数位置的数字，只能和奇数位置融合； 偶数位置的数字，只能和偶数位置融合；
那么是否可以做到任意奇数位置的整数都能融合？ 首先，连续的奇数位置必然是可以融合，因为只间隔着1个数字，选择remove该整数即可； 对于不间断的奇数位置，我们只需考虑间隔1、2个整数的情况皆可，其他间隔情况都可以由这2个情况来推出。 间隔1个整数的情况，比如说 [1,-2,-2,-2,1]，奇数位置整数是[1,-2,1]，我们可以选择第一次remove最中间的-2，得到[1, -4, 1]，再选择中间的整数-4，即可得到2； 间隔2个整数的情况，比如说 [1,-2,-2,-3,-3,-1,1]，同样的操作，我们一直选择remove最中间的整数，由于每次我们remove1个整数，融合减少1个整数，最终一定会剩下[1, x, 1]这样的结果，也即是必然可以融合得到2；
那么这个题目就比较简单了，只需要考虑奇数位置、偶数位置上选择若干个整数，得到的最小和。
class Solution {
static const int N = 201010;
lld dp[N][2], a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
// if (i == 0) dp[0][1] = a[i];
// if (i == 1) {
// dp[1][0] = dp[0][1];
// dp[1][1] = a[1];
// }
// if (i >= 2) {
// dp[i][0] = dp[i-1][1];
// dp[i][1] = max(0LL, dp[i-1][0]) + a[i];
// }
// ans = max(ans, dp[i][1]);
// cout << i << " " << dp[i][0] << " " << dp[i][1] << endl;
}
if (n == 1) cout << a[0] << endl;
else {
lld ans[2] = {a[0], a[1]};
for (int i = 2; i < n; ++i) {
if (a[i] < 0) ans[i%2] = max(ans[i%2], a[i]);
else {
ans[i%2] = max(a[i], ans[i%2] + a[i]);
}
}
cout << max(ans[0], ans[1]) << endl;
}
}
}
}
ac;