A.拼正方形
思路
这是一道纯数学题，也是同年 Python 省赛 A 组的 A 题。
方块共 $b = 10470245$ 个 $1 \times 1$。 方块共 $a = 7385137888721$ 个 $2 \times 2$。
1. 用 $2\times2$ 大方块
因为 $2\times2$ 方块占的面积大，更容易快速拼接出更大面积。因此我们先拼一个只用 $2\times2$ 方块组成的大正方形。
2. $2\times2$ 方块拼正方形
设正方形边长为 $2n$（即每边有 $n$ 个 $2\times2$ 方块），那么总共就需要 $n\times n$ 个 $2\times2$ 方块，面积为 $(2n)\times(2n) = 4n^2$，其中 $n^2\leq a$，且 $2n$ 是偶数。
因此，$n$ 最大取 $\lfloor \sqrt{a} \rfloor$。
代入： $n = \lfloor \sqrt{7385137888721} \rfloor = 2717561$
那么用 $2\times2$ 方块拼出的最大正方形边长就是 $2n=5435122$。
3. 用 $1\times1$ 小方块
用完了 $2\times2$ 方块，我们还剩 $1\times1$ 方块怎么办？那就在 $2n \times 2n$ 外，再用 $1\times1$ 方块围一圈，把边长扩大 $1$。
围一圈后，边长变成 $2n+2$。
那么外围一圈需要多少块 $1\times1$ 方块呢？ 求差 $diff = 8n+4$，就是需要的 $1\times1$ 数。
扩大一圈后：S = $(2n+2)^2 = 4n^2 + 8n + 4$ 原正方形：S = $(2n)\times(2n) = 4n^2$
计算一下： $8n+4=8\times2717561+4=21740488+4=21740492$
但题中只有 $10470245$ 块 $1\times1$ 方块，远远不够，那就...不管了。
综上，最终能拼出的最大正方形的边长就是 $2n=5435122$。
4. 一些疑虑
还有一件事，以上我们是先用 $2\times2$ 方块再用 $1\times1$ 方块围一圈，可是为什么不能围半圈，组成 $3\times3$ 方块呢？
先摆出结论，$2\times2$ 方块必须组合成偶数边长的正方形（如 $2\times2$, $4\times4$, $6\times6$，......），因为每块长宽都是 2，没有办法对半放出奇数边长的纯正方形。
假如我们拼好一个 $2\times2$ 的正方形了（用 1 块 $2\times2$ 方块），它覆盖了 4 个格子。再用 $1\times1$ 方块去补其他 5 个格子，也能构成一个 $3\times3$ 的正方形图像：
- $2\times2$ 覆盖左上角 4 格
- 用 $1\times1$ 补右下的 5 格
这样确实是填满了 3×3 的面积哈，但是题目要求的是所能拼成的单个正方形，其内部用什么方块都行，但整个形状必须是完整的正方形。
在拼出 $2n\times2n$ 的大正方形之后，用 $1\times1$ 再围一圈，目标是变成 $(2n+2)\times(2n+2)$ 正方形，要完整的外围一圈，数目是 $8n+4$。
可是如果只围半圈（比如只加一半的边），我们可能会残缺几条边，不是拼成一个边长更长的正方形，而是拼成了一个 L 型或者 T 型的缺角图形，不能算是正方形。
举个栗子： 一个 $4\times4$（由 $2\times2$ 组成）： 正常情况下围上一圈，变 $6\times6$，需要新加的 1×1 方块为 $8n+4=20$。
如果只围半圈，比如只在上面和右边各增加一排：
- 上下变成 6，中间还是 4、左右是 5 或者 6，中间不完整。
- 无法拼成一个边长为 6 的完整正方形，拼出来的肯定是缺角或突出部分。
如果不怕麻烦的话，我们也可以直接代整个题目的数据进去计算：
- 大方块能铺的最大正方形边长为
5434646（用完大方块） - 假设我们只围完整的上边和右边，每边长度都是
5434646 + 2 = 5434648 - 上边新加
5434648个格 - 右边新加
5434648个格 - 角落处交叉的那个格容斥（实际上只需 1 次）
- 一共需要：5434648 + 5434648 - 1 = 10869295
- 我们手上有的小方块只有
10470245块，穷的叮当响 - 所需的数量是
10869295，还差399050，显然也实现不了。
因此拼正方形需要保证每个边都长一样且被完整覆盖，只围半圈没法做到这一点，所以不能只靠补一半就让边长变大到奇数。要拼成更大正方形，外围那一圈必须全都围满。
#include<bits/stdc++.h> using namespace std; int main() { cout << "5435122\n"; return 0; }
B.劲舞团
这题就是一个纯粹的模拟，只是输入的样例比较唬人。
有一个比较需要注意的点，那就是每次判定成功之后都要更新，不然逻辑就乱了。
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { string a, b; int t, pre = -1, k = 0, ans = 0; while (cin >> a >> b >> t) { if (a != b) { k = 0; pre = t; continue; } if (pre == -1)k = 1; else { if (t - pre <= 1000)k++; else k = 1; } pre = t; if (k > ans)ans = k; } cout << ans << endl; return 0; }
时间复杂度是 O(n)，n 是输入次数，所以直接提交也不会爆，不用在编译器专门运出答案。
C.数字诗意
先摆出结论：一个正整数能表示为连续正整数和，除非它是 2 的幂次方。
两个方法可以得出。
一。推导
- 首先先拆解一下题目，我们要判断一个数 n 它是否存在正整数 k >= 2 且起始数 a >= 1，如下
$n = a + (a+1) + (a+2) + ...... + (a+k-1)$
等差求和后
$n = k \cdot a + \frac{k(k-1)}{2}$
稍微整理一下：
$a = \frac{n - \frac{k(k-1)}{2}}{k}$
如果要让 a 是正整数的话，那么
- 分子必须是 k 的倍数
- a ≥ 1
-
分析一下能不能写成连续和关键是找到整数 k >= 2 使 a 整除且正，这样子，n 才可以写成长为 k 的连续数列和。
-
我们对整个结论换个切入视角
- 如果是 2 的幂，不能写成至少两个连续正整数的和
- 如果不是 2 的幂，一定能写成连续正整数的和
把 n 写成奇数因子形式：
$N = 2^x \times m$（m 是奇数）
- 如 m = 1（n 是 2 的幂），就无法满足题中条件；
- 如 m > 1（n 含奇数因子），就存在合适的 k 值，可以表示成连续数之和。
- 举几个栗子
- 8 = 2³，是 2 的幂，不能
- 9 = 3²，奇数因子 3，2+3+4=9
- 12 = 2² × 3，含奇数因子 3，3+4+5=12
- 16 = 2⁴，是 2 的幂，不能
换个说法 (从二进制的视角，毕竟实现的时候是用的二进制)：
- 8 的二进制 1000（只有一个 1） → 是
- 9 的二进制 1001（两个 1） → 不是
我单拎 9 出来细讲一下： n = 9, k=3
$a = \frac{9 - \frac{3 \times 2}{2}}{3} = \frac{9 - 3}{3} = 2$
a = 2 >= 1，9 = $3^2$ = $2^3$ + 1，符合条件，且 2 + 3 + 4 = 9，正好对上了
综上：只有 2 的幂数字不能写成连续正整数和，删去即可
二。打表
第二种方法当然就是喜闻乐见的打表了，rt：
| 数字 | 质因数分解 | 是否为 2 的幂 | 连续正整数和示例 | 能否表示连续和 |
|---|---|---|---|---|
| 2 | 2 | √ | / | / |
| 3 | 3 | × | 1 + 2 | 是 |
| 4 | 2² | √ | / | / |
| 5 | 5 | × | 2 + 3 | 是 |
| 6 | 2 × 3 | × | 1 + 2 + 3 | 是 |
| 7 | 7 | × | 3 + 4 | 是 |
| 8 | 2³ | √ | / | / |
| 9 | 3² | × | 2 + 3 + 4 | 是 |
| 10 | 2 × 5 | × | 1 + 2 + 3 + 4 | 是 |
| 16 | 2⁴ | √ | / | / |
| 18 | 2 × 3² | × | 5 + 6 + 7 | 是 |
| 20 | 2² × 5 | × | 2 + 3 + 4 + 5 + 6 | 是 |
| 32 | 2⁵ | √ | / | / |
| 33 | 3 × 11 | × | 10 + 11 + 12 | 是 |
| 64 | 2⁶ | √ | / | / |
- 所有的 2 的幂数（2、4、8、16、32、64……）都不可以用两个或以上连续正整数之和表出
- 除 2 的幂以外的其他数字都至少有一种连续正整数和的表出方式
那么结果也就显而易见了
#include<bits/stdc++.h> using namespace std; #define ll long long ll n, m, ans; bool chk(ll k) { int s = 0; while(k) { s += k & 1; k >>= 1; } if(s == 1)return true; return false; } int main() { cin >> n; for(int i = 1;i <= n;i ++) { cin >> m; if(chk(m))ans ++; } cout << ans << endl; }
D.封闭图形个数
这题是也是一道模拟，结合了自定义的排序。
首先先根据题目中每个数字对应的封闭图形个数构造一个用于映射的数组，然后自定义优先排序图形数的排序 lambda 函数/cmp 比较函数，最后模拟进位处理即可。
这题两种解法都行，代码如下：
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 9; int D[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1}; struct mp { int a;//原数 int b;//图形数 }s[N];//全局数组 bool cmp(mp x, mp y)//总体是要升序排序 { if(x.b != y.b)//如果封闭图形的个数不同，那就比图形 return x.b < y.b; return x.a < y.a;//否则就比原数 } int f(int x) { int cnt = 0; while(x) { cnt += D[x % 10]; x /= 10; } return cnt; } int main() { int n;cin >> n; for(int i = 1;i <= n;i ++)//先输入原数然后调用 f 函数得到原数对应的图形数 { cin >> s[i].a; s[i].b = f(s[i].a); } sort(s + 1,s + 1 + n, cmp); for(int i = 1;i <= n;i ++) cout << s[i].a << ' '; return 0; }
这里定义了 cmp 是 bool 函数，在快排标准库里的比较函数返回的也是 bool 值（就是 true/false），所以直接在快排中加上，变为 sort(s + 1,s + 1 + n, cmp)，即可实现自定义排序。
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 9; int D[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1}; int f(int x) { int cnt = 0; while(x) { cnt += D[x % 10]; x /= 10; } return cnt; } int main() { int n;cin >> n; vector<pair<int, int>> mp;//左原数右图形数 for(int i = 0;i < n;i ++)//注意索引，vector 和静态数组不一样，它的索引必须从 0 开始 { int num;cin >> num; mp.push_back({num,f(num)}); } sort(mp.begin(),mp.end(),[](pair<int,int>& a, pair<int,int>& b) {if(a.second != b.second) return a.second < b.second; return a.first < a.first;}); for(int i = 0;i < n;i ++)cout << mp[i].first << ' ';//注意索引 return 0; }
这里面的 lambda 函数也可以按照第一个解法那样单独拎出来，变成比较函数 cmp，这里只是提供一个新的表现方式。
当然，其实这种解法也可以直接在 push_back 的时候直接把原数和图形数的位置顺序换一下
//像这样 mp.push_back({f(num)， num});
这样就可以省略 lambda 函数构造排序规则的部分，整个代码的呈现也会简洁一些，不过要是这样的话，记得在输出的时候把 mp[i].first 改成对应的 mp[i].second。
E.回文数组
思路
首先观察到一次操作可以改变两个数，也可以改变一个数，然后求最优操作方案（最值型），我们很快就可以判断这一题是一道思维 + 贪心的题目，那么我们该怎么对题设进行思维转化呢？
我们可以利用回文数组的特性。试想一下，如果我们同时调整左边和右边的数字，那么这两次操作就是相互抵消的，所以实际上，我们只要对其中的一遍进行操作即可。那么怎么作为其中衡量的指标呢？我们可以对回文数组的两边进行求差，用一个差值数组来判断怎么操作。
对两边求差值，也就是从首尾构建两个指针（也可以理解成下标），然后逐渐往中间遍历，直到两个指针对撞，即：
for(int i = 1;i <= n / 2;i ++)diff[i] = a[i] - a[n - i + 1];
除了这个构造，我们还有一个比较重要的信息没有用上，那就是我们一次加两个还是一次加一个的这个可控操作选择。正常来说肯定是优先操作两个的，这样就能更大程度上让我们整体最终的操作次数达到最小，但是肯定不可能说全部都是一次操作两个，那么我们又应该怎么判断这个取舍呢？
这时候就要引用闭区间上连续函数的零点定理的一个推论了，如图：
![f(x + 1) * f(x - 1) < 0]
其中 x 是零点，那么这个函数（暂且用一次函数表示毕竟比较直观）就有： f(x + 1) * f(x - 1) < 0
因为 x 的左边是负的而右边是正的，f(x + 1) 和 f(x - 1) 是异号的。我们稍微转化一下，也就是说只要两个元素相乘（其实减法也勉强能行但是乘法更便捷）的结果是大于零的，那么两者就是同号的。
我们借此判断相邻的两个贡献差值的数组的元素是否同号，这样就可以判断能不能进行两个一起加减的操作了。如果两者是异号的话，同增和同减都会导致抵消的效果，因为一个更趋近于期望值，但是另一个由于是异号所以反而偏离于期望值。
由上，我们对半个数组进行遍历就可以得到所有可以两个一起处理的元素并就地处理了：
if(diff[i] * diff[i - 1] > 0) { int x = min(abs(diff[i]), abs(diff[i - 1])); res += x; if(diff[i] > 0)diff[i] -= x, diff[i - 1] -= x; else diff[i] += x, diff[i - 1] += x; }
剩下的就差多少补多少，累计操作计数即可。
ad：因为贡献差值数组可能有正负，所以我们得用绝对值结合正负号的特判，做对应的处理，别漏了这一点
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 9; int a[N], diff[N]; signed main() { int n;cin >> n; for(int i = 1;i <= n;i ++)cin >> a[i]; for(int i = 1;i <= n / 2;i ++)diff[i] = a[i] - a[n - i + 1]; int res = 0; for(int i = 2;i <= n / 2;i ++) { if(diff[i] * diff[i - 1] > 0)//必须要保证整体的累加是同号的，如果是异号的，那么贡献的影响就会相互抵消趋近于 0 { int x = min(abs(diff[i]), abs(diff[i - 1]));//需要处理的次数（邻近的一起的） res += x; if(diff[i] > 0)diff[i] -= x, diff[i - 1] -= x; else diff[i] += x, diff[i - 1] += x; } } for(int i = 1;i <= n / 2;i ++)res += abs(diff[i]); cout << res << endl; return 0; }
F.商品库存管理
思路
首先看一下数据大小，3e5，如果是单纯暴力模拟的话绝对会爆时间复杂度。接着我们看到这题里面的出现了一些区间查询和修改的关键要素，因而我们比较容易就能想得出这是在考前缀和差分，当然也会有考虑数学构造的可能性，不过这种区间加减的操作，基本上就明摆着是为差分量身定做的，我们再回看一下测试数据的大小，也是前缀和差分能解决的，所以我们就现尝试从这个切口入手。
考虑到可能有些朋友对差分不是很熟悉，所以这里讲细一点，我们对于区间更新操作，要给 [l,r] 区间所有元素加 1，那就：
令 a[l] += 1；a[r+1] -= 1（r+1 ≤ n）
然后通过对差分数组求前缀和，进而就实现了整个区间的 +1 操作（差分和前缀和的关系可以拿导数与不定积分的关系来理解，两者是互逆的一个过程）
为方便区间的查询，我们就单独把前缀和的区间 [l,r] 查询封装成一个函数，往后直接调用即可：
int get(int l,int r){return o[r] - o[l - 1];}
最后还要统计一下刚好覆盖一次（用上前面差分操作过的数组）以及没有覆盖的元素，然后将它们加总即可。
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 3e5 + 10; int n, m, unc, a[N], l[N], r[N], o[N]; int get(int l,int r){return o[r] - o[l - 1];}//恰好被覆盖过一次的位置数 signed main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> m; for(int i = 1;i <= m; i++) { cin >> l[i] >> r[i]; a[l[i]]++,a[r[i] + 1]--;//标记区域内增量 } for(int i = 1;i <= n; i++) a[i] += a[i - 1]; for(int i = 1;i <= n; i++) { o[i] = o[i - 1] + (a[i] == 1);//恰好覆盖一次的 unc += (a[i] == 0);//没被覆盖的 } for(int i = 1;i <= m; i++) cout << get(l[i], r[i]) + unc << '\n'; return 0; }
G.挖矿
这是一道有一点小小贪心的模拟 + 枚举的题目，不过由于样例是 1e5，纯粹的遍历枚举时间复杂度会超出范围，所以我们就要考虑进行一些优化。
既然是涉及区间统计和计数求和，那我们不妨考虑一下前缀和优化。
思路
题目是经过就能获得一次性矿石，所以我们只需要维护正负半轴上出现矿石计数的前缀和即可。
那么负轴的前缀和怎么处理呢？另开一个前缀和数组并取正号即可，反正区间查询的复杂度也只有 O(1)，所以完全不用担心。
前缀和维护的预处理结束之后，整体操作分成两个情况，一种是一条路走到黑，另外就是进行一次折返。
1.一路走到黑
直接查询正负半轴的前缀和计数，然后取最值即可。如下：
for(int i = 1; i <= m; i++) { l[i] += l[i - 1]; r[i] += r[i - 1]; }
int cnt = max(l[m], r[m]);
2.一次折返
因为超过一半之后，折返就没有意义了，折回来走的都是重复的路。折返一次的意义是尽可能地在其中一个半轴得到尽可能多的矿石，然后牺牲部分的有效步数，得到另外一个方向的更多矿石。
实现方法也比较好推出来了，如下：
for(int i = 1; i <= m / 2; i++) { int bl = l[i] + r[m - 2 * i]; int br = r[i] + l[m - 2 * i]; cnt = max(cnt, max(bl, br)); }
ad.为什么是一次折返？
1) 证明
假设某路径存在两次折返（比如：正负正），轨迹可拆解成：
正走 i 步 → 负走 j 步 → 正走 k 步（i + j + k = m）
覆盖区间是：正轴 [0, i] ∪ 负轴 [0, j] ∪ 正轴 [0, k]
但是我们同等的步数转换成一次折返的话：
正走 (i+j) 步 → 调头后正走 k 步（总步数：(i+j) + k = m）
此时覆盖区间为：正轴 [0, i + j] ∪ 正轴 [0, k]，很显然，覆盖范围更广，两次折返的重复区间会抵消很多有效区间
2) 反证
假设有最优路径 P 包含 k 次折返（k>=2）
对比：
综上，P' 比 P 多出 2(k-1) 步，所以 P 不可能是最优解
P' 总消耗：x + y ≤ m（P 至少消耗 x + y + 2(k-1) 步，因每次调转需折返）
调头后负走 y 步（覆盖负轴 [0, y]）
直接正走 x 步（覆盖正轴 [0, x]）
新路径 P'：
设 P 在正轴最远到达 x，负轴最远到达 y
二。坑
- 矿石是一次性的，反复来回不能得到多个矿石
- 原点的矿石是一开始就有的，但是也要考虑
主要就是读题的问题，不过比较容易有疏漏
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e6 + 9;//注意这个存储的是矿石的计数，所以开的是 m 是常量而非 n 的常量 int l[N], r[N]; signed main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n, m;cin >> n >> m; int z = 0; for(int i = 0; i < n; i++) // 修改循环起始条件 { int x;cin >> x; if(abs(x) <= m && x < 0)l[-x] ++; else if(abs(x) <= m && x > 0)r[x] ++; else if(x == 0)z ++; } for(int i = 1; i <= m; i++) { l[i] += l[i - 1]; r[i] += r[i - 1]; } int cnt = max(l[m], r[m]); for(int i = 1; i <= m / 2; i++) { int bl = l[i] + r[m - 2 * i]; int br = r[i] + l[m - 2 * i]; cnt = max(cnt, max(bl, br)); } cnt += z; cout << cnt << endl; return 0; }
I.回文字符串
一、思路
通读全文之后我们可以发现，需要添加 l、q、b 这些字符让字符串回文，那么就意味着，我们可以直接剥去两端字符的 l、q、b 来直接判断。字符串左右两端凡是 l、q、b 这些字符，都先将它即忽略，找到第一个不是这些字符的位置。
剥离后，从第一个不是 l、q、b 这些字符的字符那里开始，检查中间剩余的子串是否是一个标准的回文串。如果中间子串是回文串，我们还需要从这个子串的左右两端，逐渐向外，也就是从之前剥离掉的那些字符中添加字符 l、q、b 匹配。每次向外一步，左右两边的字符必须相同。扩展持续到左边没有字符可以再添加了，而且这个时候右边刚好也用完或者还剩下一些字符（如果左边还没用完，但右边已经用完了，也就是右边的 l、q、b 这些字符比左边少，那么这个字符串就是不成立的）
举个例子：qbaca bqbqbqbq
- 剥掉两端
l、q、b这些字符后，得到aca，然后aca又是回文串，所以初判符合。 - 然后，从
aca向外扩展，左边的一个q，一个b，都是和右边匹配的，所以符合。 - 接着，剩下右边还有
bqbqbq就可以不管了，因为可以在左边插入。换言之只要左边能全部匹配完，即使右边还有多余的l,q,b字符，也过判（转换一下表述，就是左边可用于扩展的l,q,b数量必须小于等于右边可用于扩展的l,q,b数量）
另一个例子：qbqbqbaca bq
- 这个例子的
aca左边的l、q、b比右边的多，又不能删，所以就不通过，直接不符合就行
二。坑
- 思维转换上一个比较重要的点，题目说的是要从 S 的开头添加字符，也就是只能从字符串的左边补，如果直接把题目转化成两边互消的话，就错了。
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 9; int T, n; char s[N]; bool check(char c) {return c == 'l' || c == 'q' || c == 'b';} bool check(int l, int r) { while (l < r) if (s[l++] != s[r--]) return false; return true; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> T; while (T--) { cin >> (s + 1); n = strlen(s + 1); int l, r; for (l = 1; l <= n; ++l) if (!check(s[l])) break; if (l == n + 1) { cout << "Yes" << "\n"; continue; } for (r = n; r;r --) if (!check(s[r])) break; if (l - 1 > n - r || !check(l, r)) { cout << "No" << "\n"; continue; } l --, r ++; bool tag = true; while (l && r <= n) { if (s[l] != s[r]) { tag = false; break; } l --, r ++; } if (tag) cout << "Yes" << "\n"; else cout << "No" << "\n"; } return 0; }
时间复杂度为 O(n)，能 AC
