A. Park Lighting
题意：
用 1 * 2 的方格去填充 n * m 的格子，可以重叠摆放，至少需要多少个
分析：
不重叠的情况下，横着摆与竖着摆的最少数量是一样的，贡献为
\(\lfloor \frac{n}{2} * m\rfloor\)，对于 1 * n 的格子，需要竖着摆放，贡献为\(\lceil \frac{m}{2}\rceil\)
void solve()
{
int res = 0;
cin >> n >> m;
res += floor(n * 1.0 / 2) * m;
if (n % 2 == 1)
res += ceil(m * 1.0 / 2);
cout << res << endl;
}
B. Maria Breaks the Self-isolation
题意：
有 n 个朋友，每个朋友有个标记 a[i]，初始只有一个人在院子里，想邀请朋友来。朋友接受邀请的条件是：当邀请第 i 个朋友时，院子里已有的人和同时被邀请的其他人的数量和必须大于等于a[i]（可以同时邀请多个人）问能聚集的最多的人数
分析：
一次性将x人同时邀请，此时一定满足 \(x>=a[x]\)，问题答案就是满足 \(x>=a[x]\) 的最大的 x ；只需要考虑邀请人数 x 与排序后最大的 \(a[x]\) 的关系即可
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
int res = 1;
for (int i = 1; i <= n; i++)
{
if (a[i] <= i)
res = i + 1;
}
cout << res << endl;
}
C. Celex Update
题意：
在给出的矩阵上只能向 下/右 走，求从起始点到终点累加数字后有多少中不同的和
分析：
和最小时：先向右直走，再向下直走
和最大时：先向下直走，再向右直走
可以发现从和最小的方式开始，一直到和最大的方式都不同：
例如 3 * 3：
从最小的开始：
\[\begin{array}{|c|c|c|} \hline 一&二&三&四&五&和\\ \hline 1&2&4&8&13&28\\ \hline 1&2&5&8&13&29\\ \hline 1&2&5&9&13&30\\ \hline 1&3&5&9&13&31\\ \hline 1&3&6&9&13&32\\ \hline \end{array} \]计算可改变次数即可，发现只能在 [3 5 6 9] 上发生改变才会改变总和
void solve()
{
cin >> x1 >> y1 >> x2 >> y2;
int t1 = abs(x1 - x2);
int t2 = abs(y1 - y2);
cout << t1 * t2 + 1 << endl;
}
D. The Best Vacation
题意:
一年 n 个月，每个月 \(a[i]\) 天，每天的贡献为该天是该月的第几天，连续选择 k（可以跨年）天，求最大贡献
分析：
双指针暴力 + 前缀
void solve()
{
res = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i + n] = a[i];
}
for (int i = 1, x; i <= 2 * n; i++)
{
d[i] = d[i - 1] + a[i]; // 天数前缀
s[i] = s[i - 1] + (a[i] * (a[i] + 1) / 2); // 拥抱数前缀
}
for (int i = 2 * n, j = 2 * n; i; j--)
{
while (d[j] - d[i - 1] < k && i)
{
i--;
// cout << i << " " << j << endl;
}
int need = s[j] - s[i - 1];
if (d[j] - d[i - 1] > k)
{
int tmp = d[j] - d[i - 1] - k;
int del = (tmp + 1) * tmp / 2;
need -= del;
}
res = max(res, need);
}
cout << res << endl;
}