https://codeforces.com/contest/1358/ =====A Park Lighting===== ====题意==== $n \times m$个格子，规定灯只能放在每条街中间位置，求最少的灯来点亮所有的格子。 ====题解==== 没发现巧妙的解法，就直接暴力了。。。。 =====B Maria Breaks the Self-isolation===== ====题意==== Maria 邀请尽老奶奶聚会，要使得邀请的老奶奶尽可能的多，且第$i$个老奶奶能被邀请的条件是目前得有不少于$a$$i$个老奶奶已经被邀请 ====题解==== 排序后找到第一个 $i$ 满足 $a$$i$ $\leq i+1$ ，如果没有这样的情况的话，没有老奶奶被邀请，只有$1$人，输出$1$。 =====C Celex Update===== ====题意==== 求给定两点$(x$$1$,$y$$1$$)$,$(x$$2$,$y$$2$$)$间权值的可能情况. ====题解==== 可以看出来，$(x$$1$,$y$$1$$)$ $\rightarrow$ $(x$$2$,$y$$1$$) \rightarrow$ $(x$$2$,$y$$2$$)$ 这样的路径权值最小，同样，，$(x$$1$,$y$$1$$)$ $\rightarrow$ $(x$$1$,$y$$2$$) \rightarrow$ $(x$$2$,$y$$2$$)$ 权值最大。 那么总共的情况一共有 $(x$$2$$-x$$1$$)*(y$$2$$-y$$1$$)+1$种情况 =====D The Best Vacation===== ====题意==== 给出一串数，第$i$个数字为$a[i]$,表示第$i$月有$a[i]$天，某月第$j$天有$j$个拥抱，则连续x天能得到的拥抱最多是多少。 ====题解==== 月初的数字小，收益也就小，月末的数字大，收益也就大，如果能够满足月末到月末，可以保障头尾数字大，而中间都是完整的月份。进一步分析可以发现只要是开头是月末，后面都是完整的月份能够达到最大值。从某月月末开始往前数，数满x个数，找到其中的最大值 ps:可以跨年。 =====E Are You Fired?===== ====题意==== 给一个长度为$n$的数组，其中前$\lceil \frac{n}{2} \rceil$ 项中第$i$项的值为$a$$i$，后面所有项值都为$x$。欲确定整数$k$,使得数组中任意一个长度为$k$的子序列和大于零，不存在则输出$-1$。 ====题解==== 当存在$k' \leq \lfloor \frac{1}{n} \rfloor$时，对于$k = 2k'$亦成立，也就是说解只在$k > \frac{n}{2}$的情况下存在。 当$x \geq 0$时，判断 $k = n$是不是解。 若不是，则找出对每个$k$，出现的最小长度为$k$的子序列和。 记$p$为长度为$k$的子序列和$s$的差分数组，$s$$1$ $=$ $a$$1$ $+$ $a$$2$ $+ \ldots$ $+$ $a$$k$ 。 $s$$i+1$ $=$ $s$$i$ $+$ $a$$i+k$ $-$ $a$$i$. 由于$ k > \frac{n}{2}$ , 故$a$$i+k$ $ = x$. $p = [ $ $s$$1$ $,x-$ $a$$1$ $,x-$ $a$$2$ $, \cdots ,x-$ $a$$n$ $-k]$。 当$k$增加$1$，差分数组$p$首项加$x$，删除最后一项。任意长为$k$的数组的首项都可以用前缀和$sum$求出。 用一个数组$dp[i]$表示$\sum_{j = 1}^ i x-$ $a$$j$的最小值， 来表示$k = n - i$的差分数组中出现的最小差分前缀和。 最后枚举$k$, 找$sum[k] + dp[n-k] > 0$ 的情况。 =====F Tasty Cookie===== ====题意==== 有俩长度为$n$的数组$A,B$，数组元素都是正整数，现给出两种操作，让你把数组$A$变成数组$B$, 操作一：$R$操作，翻转(reverse). 操作二：$P$操作，将$A$数组变成$A$数组的前缀和数组,$a[i] = \sum a[j] ( 1 \leq j \leq i)$。 且如果$P$的操作超过$2 \times 10^5$，只需输出操作$P$的个数，否则需要输出所有操作的操作序列。 ====题解==== 先咕咕，会补的，别催了。