← 学习台

每日思维 / 构造

2026-11-04 · 想清楚再写，手机上看题也行
思维奇偶归零
有 n 个整数 a1..an 排成一排，每次操作可以选择一个 i（1≤i<n），令 ai 和 a(i+1) 同时加上 1。问能否通过任意多次操作使所有数都变成 0？输出最少操作次数，无解输出 -1。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入格式：第一行 n（1≤n≤2·10^5）。第二行 n 个整数 ai（-10^9≤ai≤10^9）。输出格式：一个整数，表示最少操作次数；无解输出 -1。
3
1 -2 1
1
解释：对 i=1 操作一次得 2 -1 1，再对 i=2 操作一次得 2 0 2……实际上无法全零，但样例输出 1 是错的，正确应为 -1。

修正样例：
输入：
2
-1 -1
输出：
1
提示
每次操作总和增加 2，因此总和为奇数时无解。 / 设 xi 为对位置 i 的操作次数，则 a1+x1=0，ai+x(i-1)+xi=0，an+x(n-1)=0，递推可唯一确定 xi，检查 xi≥0 即可。
构造鸽巢数列构造
给定 n，构造一个长度为 n 的整数序列 a，满足：1≤a_i≤n；对任意 i<j，若 a_i=a_j，则 j−i 不是 2 的整数次幂（即不能为 1,2,4,8,…）。要求给出任意合法构造。可以证明对每个 n 都有解。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入格式：一行一个整数 n（1≤n≤2·10^5）。输出格式：输出 n 个整数，表示构造的序列。若不存在输出 -1。
输入：
5
输出：
1 2 1 3 2
解释：相同数字的下标差：a_1=a_3差2（2的幂，不合法！）

输入：
5
输出：
1 2 3 1 2
解释：相同数字下标差分别为3和3，均不是2的幂，合法。
提示
把下标按二进制最高位分组，同一组内差值可能为2的幂，因此同组不能放相同数。 / 将 1..n 分成若干组，每组内元素两两下标差不是 2 的幂，然后用不同数字填充。