2023牛客寒假算法集训营3

（数学场真折磨人）

A. 不断减损的时间（贪心）

题意：

给定一个数组，任意次操作，每次操作可以 选择一个偶数除以 2 2 2 。

求最终数组所有元素之和的最小值。

思路：

要使得所有元素之和最小，那肯定是只对 正偶数 进行操作，每次除以 2 2 2 ，直到为 0 0 0 或者不是偶数为止。

代码：

#include <bits/stdc++.h> #define ll long long #define endl '\n' #define PII pair<int, int> using namespace std; const int N = 1e5 + 10; ll a[N]; void solve() { int n; cin >> n; ll sum = 0; for (int i = 1; i <= n; i++){ ll x; cin >> x; if (x > 0){ while (x % 2 == 0){ x /= 2; } } sum += x; } cout << sum << endl; } int main() { ios:: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--){ solve(); } return 0; }

---

B. 勉强拼凑的记忆（思维 + 找规律）

题意：

给定 n 块矩形积木来搭建正方形，可以自由选择每块积木的大小，但长和宽必须符合 1 × k 1 × k 1×k ，其中 1 ≤ k ≤ ⌈ n 2 ⌉ 1≤k≤⌈\frac{n}{2}⌉ 1≤k≤⌈2n​⌉(向上取整).

问能否用恰好 n 块矩形拼成正方形，若可以，则输出所能搭建的最大正方形的边长，否则输出 -1.

思路：

要想拼出的正方形最大，每个矩形积木的边 k k k 就要尽可能的长。

因为 k k k 最大为 ⌈ n 2 ⌉ ⌈\frac{n}{2}⌉ ⌈2n​⌉，所以我们可以贪心地先拼一个边长为 最大的 k = n + 1 2 最大的k = \frac{n + 1}{2} 最大的k=2n+1​ 的正方形，消耗 n + 1 2 \frac{n + 1}{2} 2n+1​ 个矩形拼成一个基本的正方形，再考虑增加它的边长。

我们发现，后面正方形的边长每增加 1 1 1 ，就需要 3 3 3 个矩形。

证明：因为原来的正方形的边长已经是最大的 k k k 了，后面加上去的矩形长度不可能超过 k k k ，所以在长和宽两侧加上 2 2 2 个 1 × k 1 × k 1×k 的矩形后，在对角线位置还要加上个 1 × 1 1 × 1 1×1​ 的小正方形。

所以最后只需要 3 3 3 个一组，判断剩下的矩形能分成多少组，相加即为最大正方形的边长。

代码：

#include <bits/stdc++.h> #define ll long long #define endl '\n' #define PII pair<int, int> using namespace std; const int N = 2e5 + 10; void solve() { ll n; cin >> n; if (n == 2){ cout << -1 << endl; return; } ll res = (n + 1) / 2; cout << res + (n - res) / 3 << endl; } int main() { ios:: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--){ solve(); } return 0; }

---

C. 忽远忽近的距离（构造 + 找规律）

题意：

要求构造一个长度为 n 的序列，对于每一个 a i a_i ai​ ，满足 2 ≤ ∣ a i − i ∣ ≤ 3 2 \le |a_i - i| \le 3 2≤∣ai​−i∣≤3 .

注：数组下标从 1 1 1 到 n n n.

排列是指长度为 n n n 的数组， 1 1 1 到 n n n​ 每个正整数恰好出现一次。

【示例输入】

4

【示例输出】

3 4 1 2

思路：

从样例可以发现， [ 3 , 4 , 1 , 2 ] [3, 4, 1, 2] [3,4,1,2] 是一组合法解，那么可以以此构造出所有 n = 4 k n=4k n=4k 形式的情况： [ 3 , 4 , 1 , 2 , 7 , 8 , 5 , 6 ] [3,4,1,2,7,8,5,6] [3,4,1,2,7,8,5,6] 等。

之后我们可以尝试构造 n = 5 n=5 n=5 和 n = 6 n=6 n=6 的情况，发现有 [ 4 , 5 , 1 , 2 , 3 ] [4,5,1,2,3] [4,5,1,2,3] 和 [ 4 , 5 , 6 , 1 , 2 , 3 ] [4,5,6,1,2,3] [4,5,6,1,2,3]，

那么可以构造出 n = 4 k + 5 n=4k+5 n=4k+5 、 n = 4 k + 6 n=4k+6 n=4k+6 、 n = 4 k + 5 + 6 n=4k+5+6 n=4k+5+6 的情况，

以上分别对应 n   %   4 n \ \% \ 4 n % 4 等于 1 、 2 、 3 1、2、3 1、2、3 的情况，

加上之前的 n = 4 k n=4k n=4k​，那么就覆盖了几乎所有正整数。

此外，我们还可以发现，当 n = 7 n = 7 n=7 和 n < 4 n < 4 n<4 时是无解的，需要对其特判。

例如 n = 13 n=13 n=13 ，我们发现 13 = 4 × 2 + 5 13=4×2+5 13=4×2+5 ，那么可以构造成： [ 3 , 4 , 1 , 2 , 7 , 8 , 5 , 6 , 12 , 13 , 9 , 10 , 11 ] [3,4,1,2,7,8,5,6,12,13,9,10,11] [3,4,1,2,7,8,5,6,12,13,9,10,11] ，即 13 = 4 + 4 + 5 13=4+4+5 13=4+4+5 的情况。

代码：

#include <bits/stdc++.h> #define ll long long #define endl '\n' #define PII pair<int, int> using namespace std; const int N = 2e5 + 10; int n; int a[N]; void solve() { cin >> n; if(n < 4 || n == 7){ cout << -1 << endl; return; } if(n % 4 == 0) { for(int i = 1; i <= n; i += 4) //构造一段循环序列[3, 4, 1, 2]，下面同理 { a[i] = i + 2, a[i + 1] = i + 3, a[i + 2] = i, a[i + 3] = i + 1; } } else if(n % 4 == 1) { a[1] = 4, a[2] = 5, a[3] = 1, a[4] = 2, a[5] = 3; for(int i = 6; i <= n; i += 4) { a[i] = i + 2, a[i + 1] = i + 3, a[i + 2] = i, a[i + 3] = i + 1; } } else if(n % 4 == 2) { a[1] = 4, a[2] = 5, a[3] = 6, a[4] = 1, a[5] = 2, a[6] = 3; for(int i = 7; i <= n; i += 4) { a[i] = i + 2, a[i + 1] = i + 3, a[i + 2] = i, a[i + 3] = i + 1; } } else if(n % 4 == 3) { a[1] = 4, a[2] = 5, a[3] = 1, a[4] = 2, a[5] = 3, a[6] = 9, a[7] = 10, a[8] = 11, a[9] = 6, a[10] = 7, a[11] = 8; for(int i = 12; i <= n; i += 4) { a[i] = i + 2, a[i + 1] = i + 3, a[i + 2] = i, a[i + 3] = i + 1; } } for (int i = 1; i <= n; i++) cout << a[i] << ' '; cout << endl; } int main() { ios:: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--){ solve(); } return 0; }

---

D. 宿命之间的对决（博弈 + 思维）

题意：

A 和 B 两人在玩一个游戏。规则如下：

给定一个正整数 n n n ，A 和 B 轮流操作，每次取 n n n 的一个因子 x x x ，用 n n n 减去 x x x ，后续的因子 x x x 变为每次减小后的数 n n n 的因子。谁先将 n n n 减到 0 0 0 谁输。

判断谁会获胜。若 A 获胜，输出 “kou”，否则输出 “yukari”.

思路：

【一】

显然 n = 1 n = 1 n=1 的话，先手必输。

结论：所有奇数都是先手必输。

证明：由于奇数只包含奇数的因子，那么只能取一个奇数变成偶数（或者变成0直接输掉），然后对方就可以直接取 1 1 1​ 变成奇数，仍然到必输的状态。因此 奇数先手必输，偶数先手必胜。

【二】

换一种思路，游戏规则不变，我们只关心游戏的结果，游戏的过程并不重要。

考虑到 1 1 1 ，因为 1 1 1 是所有正整数的因子，所以我们可以将游戏改为每次都减去一个 1 1 1 ，不影响游戏结果，得到同样的结论：奇数先手必输，偶数先手必胜。

代码：

#include <bits/stdc++.h> #define ll long long #define endl '\n' #define PII pair<int, int> using namespace std; const int N = 2e5 + 10; void solve() { ll n; cin >> n; ll cnt = dcpCount(n); if (cnt % 2) cout << "yukari" << endl; else cout << "kou" << endl; } int main() { ios:: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--){ solve(); } return 0; }

---

E. 公平守望的灯塔（计算几何）

题意：

在平面直角坐标系上给定两个不重合的点 A A A 和 B B B ，要求找到一个整数点 C C C ，使得满足三角形 A B C ABC ABC 是以 A B AB AB 为斜边的等腰直角三角形。

如果无解，输出 “No Answer!”，否则，输出任意一个符合条件的 C C C 点坐标。

思路：

【一】向量法

一个计算几何的常用知识：向量 ( x , y ) (x,y) (x,y) 和向量 ( − y , x ) (-y,x) (−y,x) 的夹角为 90 90 90 度（因为点乘为 0 0 0）。

那么我们假设 A B AB AB 向量为 ( x , y ) (x,y) (x,y) ，那么我们从 A A A 点为起点加上向量 ( − y , x ) (-y,x) (−y,x) 得到 C C C 点，那么 B C BC BC 的中点即为所求。

只需要判断是否是整数即可。（由于只有求中点时除2，所以只需要判奇偶）。

【二】坐标点计算

假设坐标点，联立方程组计算，如下图所示：

得到 C C C 点坐标后，判断其是否是整数即可。

代码(思路二）：

#include <bits/stdc++.h> #define ll long long #define endl '\n' #define PII pair<int, int> using namespace std; const int N = 2e5 + 10; void solve() { double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; int xx = x1 + y1 + x2 - y2; int yy = -x1 + y1 + x2 + y2; if (xx % 2 != 0 || yy % 2 != 0) //p cout << "No Answer!" << endl; else cout << xx / 2 << ' ' << yy / 2 << endl; } int main() { ios:: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--){ solve(); } return 0; }

---

F. 迎接终结的寂灭（签到）

题意：

签到题，宇宙终极答案是 42 .

思路：

输出 42 即可。

代码：

#include <iostream> using namespace std; int main() { cout << 42 << endl; return 0; }

---

G. 严肃古板的秩序

过年太忙了，后面三题过几天再写qwq

---

I. 灵魂碎片的收集

---

K. 永恒守候的爱恋

---