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

【CF】Day70——Codeforces Round 896 (Div. 2) CD1 (排列 + 构造 | ⭐思维 + 数学)

backend 2025/7/18 19:56:11

C. Fill in the Matrix

题目：

思路：

感觉似曾相识

对于这种排列+构造的题目，我们肯定是先找规律然后再想构造（虽然我结论想出来但没找到一般构造方法）

由于这一题是求 mex ，那我们可以尝试看看能不能构造出最大的的答案，就对于 4 3 这个例子，我们看看能不能使得每列的 mex 分别为 0 1 2，这样最后答案就是 3，答案是显然的，手动画画就知道是可行的，那我们继续尝试 n = 3 2 1 时的情况，我们可以发现一个结论，即答案是 min(n+1,m)，那么如何构造呢？

这里直接给出cf官方的方法

我们可以发现其中大多是一个循环的左移，这启示我们没思路的时候可以尝试某些有规律的方法来写，比较这是C题，不会特别考验代码

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n, m;cin >> n >> m;if (m == 1){cout << 0 << "\n";for (int i = 0; i < n; i++){cout << 0 << endl;}return;}int res = min(n + 1, m);cout << res << endl;res--;for (int i = 0; i < res; i++){for (int j = i; j < m; j++){cout << j << " ";}for (int j = 0; j < i; j++){cout << j << " ";}cout << endl;}for (int i = 0; i < n - res; i++){for (int j = 0; j < m; j++){cout << j << " ";}cout << endl;}
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D1. Candy Party (Easy Version)

题目：

思路：

数学题，学到小技巧

首先搞清楚最后的数组都会变成什么，显然是平均数

证明：设最后的数是 s，那么就有 s * n = sum，即 s = sum / n

那么就有一个非法情况，即 sum 不能被 n 整除时，此时平均数不是整数，那么肯定无法构造

那么看看剩下的如何构造呢？

我们令 b = a[i] - s，即 b 是与平均数还差多少，由于题目说了我们一定要给出以及收入，那么就可以写出以下式子 $b = 2^{x} - 2^{y}$ ，当 b > 0 时，前者代表收入的数量，后者代表给出的数量， b < 0时反之

也就是我们现在转化为了两个子问题：

① b 能否表示为上述形式 ②.如果能，那么如何判断最后是否真的可以

我们来解决第一问，将原式移项，可得： $2^{x} = b + 2^{y}$ ，说明 2的x次方一定大于 b，则我们可以取 x = log2(b) + 1，即大于 b 的最小二次幂，则 y 可以表示为 y = log2(1<<x - b)，那么如果 b 能表示，那么就有上述式子，如果不满足就直接输出no，特别的，由于 b 不能是负数，所以我们要取 abs(b)

接下来看第二问，由于 b 能被拆分，那么就要满足一个条件，即给出 x 的人数和收入 x 的人数一定要一样，否则肯定不能构造出来，这还是很好想到的，具体的我们使用cnt代表 x 的数量，如果cnt[x] != 0，那么就无法构造出来

特别的，由于取了 Abs(b)，如果b<0，那么 x y 就要交换，因为此时是给出的多

对于b=0的情况有些特殊，由于题目说了必须要给出，但是又不能给自己，那么 b=0如何处理呢？我们可以这样想，既然它的变化值是 0，那么我们其实可以把它当成一个中介，即 a <-> b <-> c这样，这样的话就能解决了，由于题目并不要我们输出具体的操作步骤，所以直接跳过即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "Yes\n"
#define no cout << "No\n"void solve()
{int n;cin >> n;vector<int> a(n), cnt(33, 0);int avg = 0;for (int i = 0; i < n; i++){cin >> a[i];avg += a[i];}if (avg % n){no;return;}avg /= n;for (int i = 0; i < n; i++){int b = a[i] - avg;if (b == 0){continue;}int c = abs(b);int x = log2(c) + 1, y = log2((1LL << x) - c);if ((1LL << x) - (1LL << y) != c){no;return;}if (b < 0){swap(x, y);}cnt[x]++, cnt[y]--;}for (int i = 0; i < 32; i++){if (cnt[i] != 0){no;return;}}yes;
}signed main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}

查看全文

http://www.xdnf.cn/news/10192.html