2020-2021:teams:manespace:codeforces_round_645_vp
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:codeforces_round_645_vp [2020/06/05 18:57] quantumbolt |
2020-2021:teams:manespace:codeforces_round_645_vp [2020/06/05 19:53] (当前版本) quantumbolt |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| Maria 邀请尽老奶奶聚会，要使得邀请的老奶奶尽可能的多，且第$i$个老奶奶能被邀请的条件是目前得有不少于$a$<sub>$i$</sub>个老奶奶已经被邀请 | Maria 邀请尽老奶奶聚会，要使得邀请的老奶奶尽可能的多，且第$i$个老奶奶能被邀请的条件是目前得有不少于$a$<sub>$i$</sub>个老奶奶已经被邀请 | ||
| ====题解==== | ====题解==== | ||
| - | 排序后找到第一个 $i$ 满足 $a$<sub>$i$</sub> $\leq i+1$ ，如果没有这样的情况的话，没有老奶奶被邀请，只有一人。 | + | 排序后找到第一个 $i$ 满足 $a$<sub>$i$</sub> $\leq i+1$ ，如果没有这样的情况的话，没有老奶奶被邀请，只有$1$人，输出$1$。 |
| =====C Celex Update===== | =====C Celex Update===== | ||
| ====题意==== | ====题意==== | ||
| 求给定两点$(x$<sub>$1$</sub>,$y$<sub>$1$</sub>$)$,$(x$<sub>$2$</sub>,$y$<sub>$2$</sub>$)$间权值的可能情况. | 求给定两点$(x$<sub>$1$</sub>,$y$<sub>$1$</sub>$)$,$(x$<sub>$2$</sub>,$y$<sub>$2$</sub>$)$间权值的可能情况. | ||
| ====题解==== | ====题解==== | ||
| - | 可以看出来，$(x$<sub>$1$</sub>,$y$<sub>$1$</sub>$)$ $\rightarrow$ $(x$<sub>$2$</sub>,$y$<sub>$1$</sub>$) \rightarrow$ | + | 可以看出来，$(x$<sub>$1$</sub>,$y$<sub>$1$</sub>$)$ $\rightarrow$ $(x$<sub>$2$</sub>,$y$<sub>$1$</sub>$) \rightarrow$ $(x$<sub>$2$</sub>,$y$<sub>$2$</sub>$)$ 这样的路径权值最小，同样，，$(x$<sub>$1$</sub>,$y$<sub>$1$</sub>$)$ $\rightarrow$ $(x$<sub>$1$</sub>,$y$<sub>$2$</sub>$) \rightarrow$ $(x$<sub>$2$</sub>,$y$<sub>$2$</sub>$)$ 权值最大。 |
| + | 那么总共的情况一共有 $(x$<sub>$2$</sub>$-x$<sub>$1$</sub>$)*(y$<sub>$2$</sub>$-y$<sub>$1$</sub>$)+1$种情况 | ||
| =====D The Best Vacation===== | =====D The Best Vacation===== | ||
| ====题意==== | ====题意==== | ||
| + | 给出一串数，第$i$个数字为$a[i]$,表示第$i$月有$a[i]$天，某月第$j$天有$j$个拥抱，则连续x天能得到的拥抱最多是多少。 | ||
| ====题解==== | ====题解==== | ||
| + | 月初的数字小，收益也就小，月末的数字大，收益也就大，如果能够满足月末到月末，可以保障头尾数字大，而中间都是完整的月份。进一步分析可以发现只要是开头是月末，后面都是完整的月份能够达到最大值。从某月月末开始往前数，数满x个数，找到其中的最大值 ps:可以跨年。 | ||
| =====E Are You Fired?===== | =====E Are You Fired?===== | ||
| ====题意==== | ====题意==== | ||
| + | 给一个长度为$n$的数组，其中前$\lceil \frac{n}{2} \rceil$ 项中第$i$项的值为$a$<sub>$i$</sub>，后面所有项值都为$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$<sub>$1$</sub> $=$ $a$<sub>$1$</sub> $+$ $a$<sub>$2$</sub> $+ \ldots$ $+$ $a$<sub>$k$</sub> 。 | ||
| + | $s$<sub>$i+1$</sub> $=$ $s$<sub>$i$</sub> $+$ $a$<sub>$i+k$</sub> $-$ $a$<sub>$i$</sub>. | ||
| + | 由于$ k > \frac{n}{2}$ , | ||
| + | |||
| + | 故$a$<sub>$i+k$</sub> $ = x$. | ||
| + | $p = [ $ $s$<sub>$1$</sub> $,x-$ $a$<sub>$1$</sub> $,x-$ $a$<sub>$2$</sub> $, \cdots ,x-$ $a$<sub>$n$</sub> $-k]$。 | ||
| + | 当$k$增加$1$，差分数组$p$首项加$x$，删除最后一项。任意长为$k$的数组的首项都可以用前缀和$sum$求出。 | ||
| + | 用一个数组$dp[i]$表示$\sum_{j = 1}^ i x-$ $a$<sub>$j$</sub>的最小值， 来表示$k = n - i$的差分数组中出现的最小差分前缀和。 | ||
| + | 最后枚举$k$, 找$sum[k] + dp[n-k] > 0$ 的情况。 | ||
| =====F Tasty Cookie===== | =====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$的个数，否则需要输出所有操作的操作序列。 | ||
| ====题解==== | ====题解==== | ||
| + | 先咕咕，会补的，别催了。 | ||
| + | |||
2020-2021/teams/manespace/codeforces_round_645_vp.1591354661.txt.gz · 最后更改: 2020/06/05 18:57 由 quantumbolt
