1485
NEFU OJ Problem1485 贪吃蛇大作战 题解
Problem:F Time Limit:1000ms Memory Limit:65535K 题目 Description 贪吃蛇大家一定都玩过吧,现在宋哥也要玩这个游戏,最初的时候贪吃蛇从屏幕的左下角出发,但是有一个非常不幸的事情,就是宋哥的游戏机的左键和下键坏掉了,这意味着什么?没错!他只能操 ......
CF1485F Copy or Prefix Sum 题解
思路 考虑 \(a_i\) 要么是 \(b_i\) 要么是 \(b_i - s\)。 考虑 \(s\) 代表着什么。 它是 \(a\) 的前缀和。 那么必然是往前一段 \(b\) 的和。 因为每个 \(b\) 代表着要么是这一位的 \(a\) 或者前面所有的 \(a\)。 考虑设 \(f_i\) 为 ......
CF1485E Move and Swap 题解
不要什么脑子的带 \(log\) 做法。 思路 考虑 \(dp_{i,j}\) 表示红点到 \(i\),蓝点到 \(j\) 的最大权值。 那么有: \[dp_{i,j}=\max(dp_{fa_i,pre},dp_{fa_j,pre})+|a_i-a_j| \]其中 \(pre\) 是任意一个上一层 ......
UVA1485 Permutation Counting
传送门 description 一个长度为 \(n\) 的排列 \(a\),其权值为满足 \(a_i>i\) 的位置的数量。 求权值恰为 \(k\) 的长度为 \(n\) 的排列的方案数。 \(n,k\leq 1000\) solution 设 \(f_{i,j}\) 表示考虑前 \(i\) 个数, ......
P1485 火枪打怪
二分 \(p\),因为只能溅射到左边,所以从右往左打,但 \(O(n^2\log(n+m)))\) 显然过不去。对于能溅射到位置 \(j\) 的子弹,拆式子: \[\sum p-(i_x-j)^2 \]\[\sum p-i_x^2+2\times i_x\times j-j^2 \]\[tot\ti ......