（数学场真折磨人）

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

题意：

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

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

思路：

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

代码：

#include 
#define ll long long
#define endl '\n'
#define PII pair
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×k1 × k1×k ，其中 1≤k≤⌈n2⌉1≤k≤⌈\frac{n}{2}⌉1≤k≤⌈2n​⌉(向上取整).

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

思路：

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

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

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

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

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

代码：

#include 
#define ll long long
#define endl '\n'
#define PII pair
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 的序列，对于每一个 aia_iai​ ，满足 2≤∣ai−i∣≤32 \le |a_i - i| \le 32≤∣ai​−i∣≤3 .

注：数组下标从 111 到 nnn.

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

【示例输入】

4

【示例输出】

3 4 1 2

思路：

从样例可以发现，[3,4,1,2][3, 4, 1, 2][3,4,1,2] 是一组合法解，那么可以以此构造出所有 n=4kn=4kn=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=5n=5n=5 和 n=6n=6n=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=4k+5n=4k+5n=4k+5 、 n=4k+6n=4k+6n=4k+6 、 n=4k+5+6n=4k+5+6n=4k+5+6 的情况，

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

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

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

例如 n=13n=13n=13 ，我们发现 13=4×2+513=4×2+513=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+513=4+4+513=4+4+5 的情况。

代码：

#include 
#define ll long long
#define endl '\n'
#define PII pair
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 两人在玩一个游戏。规则如下：

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

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

思路：

【一】

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

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

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

【二】

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

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

代码：

#include 
#define ll long long
#define endl '\n'
#define PII pair
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. 公平守望的灯塔（计算几何）

题意：

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

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

思路：

【一】向量法

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

那么我们假设 ABABAB 向量为 (x,y)(x,y)(x,y) ，那么我们从 AAA 点为起点加上向量 (−y,x)(-y,x)(−y,x) 得到 CCC 点，那么 BCBCBC 的中点即为所求。

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

【二】坐标点计算

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

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

代码(思路二）：

#include 
#define ll long long
#define endl '\n'
#define PII pair
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)  //pcout << "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 
using namespace std;int main()
{cout << 42 << endl;return 0;
}