当前位置：首页 > news >正文

Codeforces Round 1019 (Div. 2)（ABCD）

news 2025/7/29 17:06:26

A. Common Multiple

翻译：

给你一个整数数组 a1,a2,...,an。如果存在一个数组 y1,y2,...,ym，且 y 的元素是不同的（换句话说，对于所有 1≤i<j≤m 的数组，yi≠yj），并且对于所有 1≤i≤m 的数组，xi 和 yi 的乘积是相同的（换句话说，对于所有 1≤i<j≤m 的数组，xi⋅yi=xj⋅yj），那么数组 x1,x2,...xm 就是优美的。

你的任务是确定数组 a 的子序列（不要求元素连续）的最大尺寸。

思路：

对于 a 的子序列 b 如果是优美的，它与y的每一位乘积必定为 b 所有数的公约数，那么如果b中有相同的数，那么它们对应的 y 一定相同。

综上：a的子序列要满足元素互不相同。（数学）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;void solve(){int num,n;cin>>n;unordered_set<int> st;while (n--){cin>>num;st.insert(num);}cout<<st.size()<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t;cin>>t;while (t--){solve();}return 0;
}

B. Binary Typewriter

翻译：

给你一个长度为 n 的二进制字符串 s 和一台带有 0 和 1 两个按钮的打字机。最初，你的手指放在 0 号按钮上：

按下手指当前所在的按钮。这将打出该按钮上的字符。
将手指移到另一个按钮上。如果手指在 0 号按钮上，则移动到 1 号按钮上，反之亦然。

        二进制字符串的代价定义为键入整个字符串所需的最少操作次数。

        在输入之前，您最多可以反转 s 的一个子串∗。更正式地说，您可以选择两个索引 1≤l≤r≤n，并反转子串 $s_{l...r}$ ，从而得到新的字符串 $s_1s_2...s_{l-1}s_rs_{r-1}...s_ls_{r+1}...s_n$ 。

        你的任务是在对 s 进行最多一次子串反转后得到的所有字符串中，找出可能的最小代价。

思路：

反转后会产生代价变化的部分在于边界即 (l 与 l-1),(r 与 r+1)。

分类讨论：

10...10的情况代价-2
10的情况代价-1

注意手指默认在按钮0。(思维)

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;
// 111000 -1
// 1101 -2
void solve(){int n;cin>>n;string s;cin>>s;int ans = 0,cnt = 0;char pre='0';for (int i=0;i<n;i++){if (pre!=s[i]){cnt++;ans+=2;pre = s[i];}else ans++;}if (cnt==2) ans--;else if (cnt>2) ans-=2;cout<<ans<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t;cin>>t;while (t--){solve();}return 0;
}

C. Median Splits

翻译：

数组 $b_1,b_2,...,b_m$ 的中位数写为 $med(b_1,b_2,...,b_m)$ ，是数组 b 的第 $\lceil \frac{m}{2}\rceil$ 个最小元素。

给你一个整数数组 $a_{1},a_{2},...,a_n$ 你需要确定是否存在一对索引 1≤l<r<n 那么

$med(med(a_1ma_2,...,a_l),med(a_{l+1},a_{l+2},...,a_r),med(a_{r+1},a_{r+2},...,a_n))\\ \leq k$

换句话说，确定是否有可能将数组分割成三个连续的子数组，使得三个子数组的中位数小于或等于 k。
.

思路：

直接分类讨论：将分割的三个子数组分为l，mid，r。

l与r都不大于k
l与mid都不大于k
mid与r都不大于k

怎么判断子数组的中位数是小于k的呢？

通过分别计数大于k（b_cnt）与不大于k（s_cnt）的数量判断。当s_cnt>=b_cnt时得到最小的左右边界。

例：考虑情况2，在左边界基础上，继续计数判断能否得到mid的右边界。注意要考虑l=0的情况，可以帮助mid多消耗一个s_cnt。情况3判断同理。（构造）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;
//  分类讨论：lr,lmid,rmid
void solve(){int n,k;cin>>n>>k;vector<int> nums(n);for (int num,i=0;i<n;i++) cin>>nums[i];int l=-1,l_cnt=0,b_cnt=0,s_cnt=0;for (int i=0;i<n;i++){if (nums[i]>k){b_cnt++;}else{s_cnt++;}if (s_cnt && s_cnt>=b_cnt) {l = i;l_cnt = s_cnt-b_cnt;break;}}int r=-1,r_cnt=0;b_cnt=0,s_cnt=0;for (int i=n-1;i>=0;i--){if (nums[i]>k){b_cnt++;}else{s_cnt++;}if (s_cnt && s_cnt>=b_cnt) {r = i;r_cnt = s_cnt-b_cnt;break;}}if (l!=-1 && r!=-1 && l<r){cout<<"YES"<<endl;return;}if (l!=-1){b_cnt=0,s_cnt=0;for (int i=l+1;i<n-1;i++){if (nums[i]>k){b_cnt++;}else{s_cnt++;}if (s_cnt && l_cnt+s_cnt>=b_cnt) {cout<<"YES"<<endl;return;}}}if (r!=-1){b_cnt=0,s_cnt=0;for (int i=r-1;i>0;i--){if (nums[i]>k){b_cnt++;}else{s_cnt++;}if (s_cnt && r_cnt+s_cnt>=b_cnt) {cout<<"YES"<<endl;return;}}}cout<<"NO"<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t;cin>>t;while (t--){solve();}return 0;
}

D. Local Construction

翻译：

数组 $b_1,b_2,...,b_m$ 中的元素 bi（1≤i≤m）是局部最小值，如果以下条件至少有一个成立：

2≤i≤m-1 且 $b_i<b_{i-1}$ 和 $b_i<b_{i+1}$ ，或
i=1 且 $b_1<b_2$ , 或
i=m 且 $b_m<b_{m-1}$ .

同样，如果以下条件至少有一个成立，那么数组 $b_1,b_2,...,b_m$ 中的元素 bi（1≤i≤m）就是局部最大值：

2≤i≤m-1 且 $b_i>b_{i-1}$ 和 $b_i>b_{i+1}$ ，或
i=1 且 $b_1>b_2$ , 或
i=m 且 $b_m>b_{m-1}$ .

请注意，只有一个元素的数组不定义局部最小值和最大值。

有一个长度为 n 的隐藏排列∗ p，从操作 1 开始，交替对排列 p 进行以下两个操作，直到 p 中只剩下一个元素：

操作 1 - 删除 p 中不是局部最小值的所有元素。
操作 2 - 删除 p 中不是局部最大值的所有元素。

更具体地说，操作 1 在每次奇数迭代中执行，操作 2 在每次偶数迭代中执行，直到 p 中只剩下一个元素。

对于每个索引 i（1≤i≤n），设 ai 为元素 pi
被删除的迭代次数，或-1（如果从未删除）。

可以证明，最多经过 ⌈log2n⌉ 次迭代后，p 中将只剩下一个元素（换句话说，ai≤⌈log2n⌉）。

给你数组 a1，a2，...，an。你的任务是构造出满足数组 a 的 n 个元素的任意排列 p。

思路：

先从局部思考。

对于迭代数为1时，排除非局部最小值，那么必定从最大的开始排除（最大的必定不构成局部最小值），那么对于迭代值为1的位置填的数就从大到小填满，而填的顺序如何构造呢？从迭代值为1的位置两侧开始从大到小填，中间的临界位置为迭代之-1的位置。这样保证第一次迭代必定消除这些数。

对于迭代数2，则从迭代值为2的位置两侧开始从小到大填，中间的临界位置为迭代之-1的位置。这样保证第2次迭代必定消除这些数。

接下来的奇偶迭代数以此类推即可。剩下的数给迭代值-1的位置。（构造，贪心）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;
//  分类讨论：lr,lmid,rmid
void solve(){int n;cin>>n;vector<vector<int>> steps(30);vector<int> ans(n,0);int beg;for (int flag,i=0;i<n;i++) {cin>>flag;if (flag>0) steps[flag].push_back(i);else beg = i;}int l=1,r=n;for (int i=1;i<30;i++){// rif (i&1){for (int j=0;j<steps[i].size();j++){if (steps[i][j]>=beg) break;ans[steps[i][j]] = r--;}for (int j=steps[i].size()-1;j>=0;j--){if (steps[i][j]<=beg) break;ans[steps[i][j]] = r--;}}else{for (int j=0;j<steps[i].size();j++){if (steps[i][j]>=beg) break;ans[steps[i][j]] = l++;}for (int j=steps[i].size()-1;j>=0;j--){if (steps[i][j]<=beg) break;ans[steps[i][j]] = l++;}}}for (int i=0;i<n;i++){if (!ans[i]) cout<<l<<" ";else cout<<ans[i]<<" ";}cout<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 四舍五入中间填保留几位小数，不填默认// cout.precision();int t;cin>>t;while (t--){solve();}return 0;
}