Codeforces Round 1019 (Div. 2) A-D

A. Common Multiple

题目大意

给你一个长度为n的数组a,让你求a的最长子数组，假设长度为m，使得对于每个元素$a_i$，都存在有另一个同样长度m的数组b,数组b的每个元素都不相同,其对应位置的$b_i$有$a_i\ast b_i=a_j\ast b_j(1<=i<j<m)$

思路

对于一个元素$a_i$，若要满足条件，应该使得$a_i\ast b_i=a数组的最小公倍数$，那么最长子数组应该是a中不同元素的个数，若有相同元素，则不满足b数组中每个元素都不相同的条件

// Author: zengyz
// 2025-07-14 09:45#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;vector<int> a(n);set<int> s;for (auto &x : a)cin >> x, s.insert(x);cout << s.size() << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}

B. Binary Typewriter

题目大意

给你一个01串，你有一个打字机，上面有两个按键0和1 ，现在你的手指放在0上，你可以进行如下操作：
按下当前手指放在的按键上，并打出一个对应按键的自负
将手指移到另一个按键上

你可以进行最多一次操作，使得其中的一个子串进行翻转
问打出对应01串的最小的操作次数是多少

思路

首先至少需要n次操作才能打出长度为n的串，然后我们考虑将手指移动的操作，可以把连续的0和1进行压缩，例如110011我们只需要分析101的情况，我们设压缩后的数组为v,
如果数组v大小为1，那么答案就是n+(第一个字符是不是1)
如果数组大小为2或3，那么一定会操作一次移动手指，可以通过反转将0放到前面，1放到后面，那么操作次数就是n+1
如果数组大小大于3 ，那么就会出现0 1 0 1或者1 0 1 0的情况，我们可以通过翻转他们得到连续的1和0 例如0 0 1 1或1 0 0 1，就可以减少两次翻转操作 那么答案就是n+(第一个字符是不是1)+(v数组大小-1[需要翻转的次数])-2

// Author: zengyz
// 2025-07-14 09:58#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;string s;cin >> s;int last = -1;vector<int> v;for (int i = 0; i < n; i++){int tmp = s[i] - '0';if (last != tmp){last = tmp;v.push_back(tmp);}}
if(v.size()==1)
{cout<<n+(s[0]=='1')<<endl;
}
else  if(v.size()<=3)
{cout<<n+1<<endl;
}
else 
{int ans=(s[0]=='1');cout<<ans+n+v.size()-1-2<<endl;
}return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}

C. Median Splits

题目大意

给你一个长度为n的数组和k
分能否通过将数组分为连续的三段，使得三段的中位数的中位数小于等于k

思路

统计前缀和后缀中存在一段的中位数小于等于k的情况，如果前缀之后或者后缀之前还能塞一个大于k的元素，我们也给他放进去，如果是<=k的我们留给之后的两段一定是最优的
然后我们考虑前缀存在的情况，那么我们通过遍历后续的两段长度，通过统计数组中小于等于k的元素个数和数组长度的情况可以得出是否存在满足小于等于k的情况，如果还存在一段这样的数组，那么有两段数组小于等于k,满足题意
后缀同理

// Author: zengyz
// 2025-07-14 10:40#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n, k;cin >> n >> k;vector<int> b(n + 1), pre(n + 2), suf(n + 2);for (int i = 1; i <= n; i++)cin >> b[i];for (int i = 1; i <= n; i++)pre[i] = pre[i - 1] + (b[i] <= k ? 1 : 0);for (int i = n; i >= 1; i--)suf[i] = suf[i + 1] + (b[i] <= k ? 1 : 0);int idx1 = 0, idx2 = 0;for (int i = 1; i <= n; i++){if (!idx1)if (pre[i] >= (i - 1) / 2 + 1)idx1 = i;}for (int i = n; i >= 1; i--){int j = n - i + 1;if (!idx2)if (suf[i] >= (j - 1) / 2 + 1)idx2 = i;}if (idx1 % 2 == 1 && b[idx1 + 1] > k && n - idx1 > 2)idx1++;if ((n - idx2 + 1) % 2 && b[idx2 - 1] > k && idx2 > 3)idx2--;// cout << idx1 << " " << idx2 << endl;if (idx1){for (int i = idx1 + 1; i < n; i++){int res1 = i - idx1;int res2 = n - i;if (pre[i] - pre[idx1] >= (res1 - 1) / 2 + 1 || pre[n] - pre[i] >= (res2 - 1) / 2 + 1){cout << "YES" << endl;return;}}}if (idx2){for (int i = idx2 - 1; i > 1; i--){int res1 = idx2 - i;int res2 = i - 1;if (suf[i] - suf[idx2] >= (res1 - 1) / 2 + 1 || suf[1] - suf[i] >= (res2 - 1) / 2 + 1){// cout << suf[1] << " " << suf[i] << " " << suf[idx2] << " " << res1 << " " << res2 << endl;cout << "YES" << endl;return;}}}cout << "NO" << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}

D. Local Construction

题目大意

对于一个数组，定义局部最大值和局部最小值
给你每个元素在第几轮被删除，让你求一个排列满足在
奇数轮删除排列内不是局部最小值的所有元素
偶数轮删除排列内不是局部最大值的所有元素
一定存在解法，让你求出排列

思路

开始容易构造一些不存在解法的排列把自己迷住，其实在当前轮没被删除的数一定是满足他们时当前的局部最小值（最大值）所以他们应该是和当前轮的元素穿插着放的，设最后剩下的元素位置为idx:
对于奇数轮应该删除的元素，在idx左边的我们从大到小放，idx右边的我们从小到大放
对于偶数轮应该删除的元素，在idx左边的我们从小到大放，idx右边的我们从大到小放
那么为什么呢？试想idx,在奇数轮我们要让它作为局部最小值，在偶数轮我们要让它作为局部最大值，那么idx左右两边一定要对称放，同时在奇数轮左边从大到小以及右边从小到大我们才能保证边缘不会出现局部最小值的情况，偶数轮同理！
如此构造一定能满足答案：

// Author: zengyz
// 2025-07-14 13:58#include <bits/stdc++.h>using namespace std;
typedef long long ll;void solve()
{int n;cin >> n;vector<int> a(n+1), f(n+1);vector<vector<int>> b(n+1);int idx = -1;int maxx=0;for (int i = 1; i <= n; i++){cin >> a[i];maxx=max(a[i],maxx);if (a[i] == -1){idx = i;continue;}b[a[i]].push_back(i);}int now = 1;int tmp = 1;int count = 1;int l=1,r=n;while (maxx--){now ^= 1;if (now == 0){for (int i = 1; i<idx; i++){if ( a[i] == count)f[i] = r--;}for (int i = n; i >idx; i--){if ( a[i] == count)f[i] = r--;}}else{for (int i = 1; i < idx; i++){if (a[i] == count)f[i] = l++;}for (int i = n; i>idx; i--){if ( a[i] == count)f[i] =l++;}}count++;}f[idx]=l;for(int i=1;i<=n;i++)cout<<f[i]<<" ";cout<<endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T = 1;cin >> _T;while (_T--){solve();}return 0;
}