跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2020-2021
»
teams
»
manespace
»
codeforces_round_645_vp
2020-2021:teams:manespace:codeforces_round_645_vp
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
https://codeforces.com/contest/1358/ =====A Park Lighting===== ====题意==== $n \times m$个格子,规定灯只能放在每条街中间位置,求最少的灯来点亮所有的格子。 ====题解==== 没发现巧妙的解法,就直接暴力了。。。。 =====B Maria Breaks the Self-isolation===== ====题意==== Maria 邀请尽老奶奶聚会,要使得邀请的老奶奶尽可能的多,且第$i$个老奶奶能被邀请的条件是目前得有不少于$a$<sub>$i$</sub>个老奶奶已经被邀请 ====题解==== 排序后找到第一个 $i$ 满足 $a$<sub>$i$</sub> $\leq i+1$ ,如果没有这样的情况的话,没有老奶奶被邀请,只有$1$人,输出$1$。 =====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>$)$ $\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===== ====题意==== 给出一串数,第$i$个数字为$a[i]$,表示第$i$月有$a[i]$天,某月第$j$天有$j$个拥抱,则连续x天能得到的拥抱最多是多少。 ====题解==== 月初的数字小,收益也就小,月末的数字大,收益也就大,如果能够满足月末到月末,可以保障头尾数字大,而中间都是完整的月份。进一步分析可以发现只要是开头是月末,后面都是完整的月份能够达到最大值。从某月月末开始往前数,数满x个数,找到其中的最大值 ps:可以跨年。 =====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===== ====题意==== 有俩长度为$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.txt
· 最后更改: 2020/06/05 19:53 由
quantumbolt
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部