每天坚持写三道题第七天：

Problem - A - Codeforces 1200

Problem - B - Codeforces 1300

Problem - A - Codeforces 1500

目录

题目一:

题目大意:

解题思路:

代码(C++):

题目二:

题目大意:

解题思路:

代码(C++):

题目三:

题目大意:

解题思路:

代码(C++):

Python写法:

题目一:

题目二:

题目三:

---

题目一:

Problem - 27A - Codeforces

题目大意:

现在有一个数组a, 在数组a中添加一个0后，你需要找出数组a中的最小排除数MEX。

MEX的定义：

最小的并且不在集合中的最小非负整数

解题思路:

我们把数组从小到大进行排序，从前往后找。

代码(C++):

void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}//排序std::ranges::sort(a);//不断的检查是否有1，2，3...int x = 1;for (int& v : a) {if (v != x) {std::cout << x << "\n";return;}x++;}std::cout << x << "\n";
}

题目二:

Problem - B - Codeforces

题目大意:

现在给你一个长度为n的排列P，再给你一个长度为m的数组a。

保证m大于等于2且小于等于n，并且数组a中的值在1到n之间，并且各不相同。

我们定义pos(x)表示元素x在排列P中的下标。

现在你可以进行下面的操作若干次：

交换排列P的两个相邻的元素。

再给你一个整数d。

我们的目标是，使用尽可能少的操作，使得存在一个下标i，满足pos(a[i]) >= pos(a[i + 1]) 或者满足pos(a[i + 1])  > pos(a[i]) + d。

输出最少的操作次数。

解题思路:

这题主要是需要我们理解清楚题目意思。

我们的目标就是只需要有一个下标满足题目条件pos(a[i]) >= pos(a[i + 1])或者pos(a[i + 1]) > pos(a[i]) + d即可。

也就是我们遍历数组a，检查一遍相邻的下标，对于这一对下标的a[i], a[i + 1]。找出对应的pos(a[i]), pos(a[i + 1])。

然后判断两种条件是否可以实现，和实现的次数。

对于条件pos(a[i + 1]) > pos(a[i]) + d这个操作需要的操作次数跟d有关，所以具体实现的时候，可能的操作次数需要看能不能在数组n的范围内实现。

具体实现细节可以看代码。

代码(C++):

void solve() {int n, m, d;std::cin >> n >> m >> d;//我们只需要关注排列P的每一个元素所在的下标,//所以输入的时候直接用pos数组存位置即可std::vector<int> pos(n + 1);for (int i = 1; i <= n; i++) {int num;std::cin >> num;pos[num] = i;}std::vector<int> a(m);for (int i = 0; i < m; i++) {std::cin >> a[i];}int ans = 1e9;for (int i = 0; i < m - 1; i++) {//如果已经存在了满足题目条件的相邻下标,那么就不需要操作次数if (pos[a[i]] >= pos[a[i + 1]] || pos[a[i + 1]] > pos[a[i]] + d) {ans = 0;break;}//使得条件一满足的情况需要的操作次数int cnt1 = pos[a[i + 1]] - pos[a[i]];//使得条件二满足“可能”需要的操作次数int cnt2 = d - cnt1 + 1;//如果这个可能性无法满足if (cnt2 > (pos[a[i]] - 1) + (n - pos[a[i + 1]])) {cnt2 = 1e9;}ans = std::min({ans, cnt1, cnt2});}std::cout << ans << "\n";
}

题目三:

Problem - A - Codeforces

题目大意:

现在有一个数组a，你必须不断的进行下面的操作，直到无法进行：

选择数组a最前面的两个数字x, y，然后把gcd(x, y)加到分数上。

然后删除这两个数字。

数组中的数字不足两个的时候，无法操作。

现在你需要重新给数组进行赋值，保证每个数字都不相同，并且保证进行操作后，也就是不断取数字后，最终的得分为k。

现在给你数组的长度n和k，输出你重新赋值后的数组。

解题思路:

每次操作都是取两个数字，并且取到数组中数字不足两个

那么也就是说，如果数组长度n为奇数，那么我们不需要关注最后一个数字。

可以进行这个操作后把n -= 1，保证现在的n为偶数。

现在我们有 n / 2对数字，现在我们需要把每一对的数字的gcd的和加上等于k。

我们可以注意到

每一对数字的gcd的最小值是1，那么n / 2对数字的gcd的和的最小值为n / 2

如果k < n / 2，则无法实现，输出-1。

可以想到一个简单方案：

n / 2 - 1对数字的gcd都设置成1，那么我们还需要凑下x = k - n / 2 - 1才能到k，

我们可以把剩下的一对的数字的gcd设置成x即可。

具体实现方法参考代码

代码(C++):

void solve() {int n, k;std::cin >> n >> k;//特判,当n == 1的时候,也就是只有一个元素,无法进行取数字的操作if (n == 1) {//k == 0的时候,那这个元素任意都行,k不等于0为-1std::cout << (k == 0 ? 1 : -1) << "\n";return;}std::vector<int> ans(n);//如果n为奇数先把最后一个元素填上//然后把n变成偶数if (n % 2) {ans[n - 1] = 1e9;n -= 1;}//现在n为偶数,并且取两个数字的gcd最小值为1,也就是此时的分数最小值为n / 2if (k < n / 2) {std::cout << "-1\n";return;}//我们可以把后面的n - 2个数字的每一对数字的gcd变成1,总共的得分也就是(n - 2) / 2//现在我们还需要k - (n - 2) / 2才能凑到k,那么我们用下面的操作即可int x = k - (n - 2) / 2;ans[0] = x;ans[1] = x * 2;int num = x * 2 + 1;for (int i = 2; i < n; i += 2) {ans[i] = num;ans[i + 1] = num + 1;num += 2;}for (int& v : ans) {std::cout << v << " ";}std::cout << "\n";
}

Python写法:

题目一:

def solve():n = II()a = LII()a.sort()x = 1for v in a:if x != v:print(x)returnx += 1print(x)

题目二:

def solve():n, m, d = MII()P = LII()pos = [0] * (n + 1)for i in range(n):pos[P[i]] = ia = LII()ans = int(1e9)for i in range(0, m - 1):if pos[a[i]] >= pos[a[i + 1]] or pos[a[i + 1]] > pos[a[i]] + d:ans = 0breakcnt1 = pos[a[i + 1]] - pos[a[i]]cnt2 = d - cnt1 + 1if cnt2 > (pos[a[i]] - 1) + (n - pos[a[i + 1]]):cnt2 = int(1e9)ans = min([ans, cnt1, cnt2])print(ans)

题目三:

def solve():n, k = MII()if n == 1:print(1 if k == 0 else -1)returnans = [0] * nif n % 2:ans[n - 1] = int(1e9)n -= 1if k < n // 2:print(-1)returnx = k - (n - 2) // 2ans[0] = xans[1] = x * 2num = x * 2 + 1for i in range(2, n, 2):ans[i] = numans[i + 1] = num + 1num += 2print(' '.join(map(str, ans)))