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

Codeforces Round 1022 (Div. 2)（ABC）

news 2025/5/3 10:27:16

A. Permutation Warm-Up

翻译：

对于长度为 n 的排列 p，我们定义函数：
$f(p)=\sum\limits_{i=1}^n|p_i-i|$
给你一个数 n。你需要计算函数 f(p) 在考虑从 1 到 n 的所有可能的数字排列时，可以取多少个不同的值。

思路：

按序排列时和为0，当有一端值+1，必有一端值-1即sum+2。由此会得到的和都为偶数。答案为sum_max/2+1。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;void solve(){int n;cin>>n;int res = 0;for (int l=n,i=1;i<=n;i++){res+=abs(l-i);l--;}cout<<res/2+1<<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. SUMdamental Decomposition

翻译：

在你最近的一个生日上，你的好朋友莫里斯送给你一对数字 n
和 x ，并要求你构造一个长度为 n 的正数数组 a ，使得 $a_1\oplus a_2 \oplus \cdots \oplus a_n=x$ 。

这个任务对你来说似乎太简单了，因此你决定给莫里斯一个回礼，在所有这样的数组中构造一个元素之和最小的数组。你马上想到了一个合适的数组；但是，由于写下来太费时间，莫里斯只能选择元素之和。

思路：

一个数可以被分成多个不同二的幂次相加。

要让和足够小，可先将 x 拆成不同的2的幂次数，再对还要填的数进行添加。设还要填 n 个数。

当 n 为偶数时，都为1。

带 n 为奇数时，先摘掉一个 num，其余都为1。num 对于被拆分的2的幂次数二进制有数位0为0情况，则可将该数与num都+1，否则num为2，找个数也+2。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;
void solve(){ll n,x;cin>>n>>x;if (n==1 && x==0){cout<<-1<<"\n";return;}ll res = x;ll tmp = x,cnt=0;// 有两个及以上的1吗while (tmp){if (tmp%2==1){cnt++;}tmp/=2;}n = max(0ll,n-cnt);if (n%2==0){res += n;}else if (n%2==1){res+=n-1;if (x==1 || x==0) res+=4;else res +=2;}cout<<res<<"\n";
}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. Neo's Escape

翻译：

        尼奥想要逃离母体。在他面前，有 n 个按钮排成一排。每个按钮的权重都是一个整数： $a_1,a_2,...,a_n$ 。

        尼奥无法移动，但他可以创造和移动克隆人。这意味着他可以以任意顺序执行以下两种类型的操作，数量不限：

在特定按钮前创建一个克隆体。
将现有克隆体向左或向右移动一个位置。

        只要克隆体出现在另一个尚未按下的按钮前，无论它是被创建还是被移动，它都会立即按下该按钮。如果按钮已经被按下，克隆人就什么也做不了--按钮只能按一次。

        要想让尼奥逃脱，他需要按顺序按下所有按钮，使它们的权重序列不递增--也就是说，如果   $b_1,b_2,...,b_n$ 是按顺序按下的按钮的权重，那么必须成立： $b_1\geq b_2\geq\cdots\geq b_n$ 。

        你的任务是确定尼欧需要创建的最小克隆数，以便按有效顺序按下所有按钮。

思路：

不考虑有权值相同点的情况下，当一个点值为局部最大值时，它是必定要被创建的，而不是的则可通过局部最大值的左右移动被合理按下。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 2e5+10;void solve(){int n;cin>>n;int pre = -1;vector<int> a={0};for (int num,i=0;i<n;i++){cin>>num;if (num!=pre){a.push_back(num);}pre = num;}a.push_back(0);int res = 0;for (int i=1;i<a.size()-1;i++){res+=(a[i]>a[i-1] && a[i]>a[i+1]);}cout<<res<<"\n";
}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;
}