牛客寒假算法基础集训营6 题解

出题

显然，有解的充要条件为 。

若有解：

设有 道6分题，则剩下的m-x题共n-6x分，

则剩下的题有解的充要条件为 ，

解得 。

因此答案为max(0,7m-n)。

煤气灶

假设小 j 工作了 i 天，则总工资 。

二分答案，

判断 的时候可能会爆 ，

移项得： 。

因为 a*b>=c 等价于 ( 表示 x 上取整的结果)，

所以可以将乘法转化为除法，从而避免爆 。

项链

贪心，优先选喜爱度大的颜色。

具体来说，

将颜色按喜爱度从大到小排序，

从1到m枚举i，

每次答案加上b[i]*min(a[i],leave)，

其中leave表示还剩几个珠子，一开始leave=n，每次leave减去min(a[i],leave)。

美食

i从1到n枚举，依次贪心。

对于a[i]，

首先把答案加上a[i]/2，

如果a[i]是奇数且a[i+1]>0，则把a[i+1]减去1，答案加上1。

海啸

用 s[x][y] 表示 (1,1) 到 (x,y) 的答案，

则 (a,b) 到 (x,y) 的答案 =s[x][y]+s[a-1][b-1]-s[a-1][y]-s[x][b-1] 。

所以只用预处理 s[x][y] 即可。

而 s[x][y] 可以通过两次计算前缀和得到。

还有一个问题就是只保证了 ，怎么开数组？

只需要先开一个 的指针数组，然后new出来就好了。

石头剪刀布

根据获胜者的偏爱决策可以推出对战的两人的偏爱决策，所以枚举最终获胜者的偏爱决策判断一下就好了。字典序问题只需递归处理+暴力 cmp 。

时间

区间或和

如果 a=b ，那么答案 =a ；

否则 ，

考虑a和b的二进制表示从高到低第一个不同的位i，

必定b的第i位=1，a的第i位=0。

那么可以断定，对于答案的二进制表示，

(1) 比第i位更高的那些位一定跟a相同。

(2) 第i位及比第i位更低的那些位一定为1。

(1)是显然的，(2)是由于把a中比第i位更低的那些位都置为1得到的数一定在区间[a,b]中。

肥猪

从0到n-1枚举第二种操作的使用次数step，

那么对于最终得到的编号为i的肥猪，

假如它是召唤编号为j的肥猪然后进化多次得到的，

则一定有 ，

并且这是充要的，即它可以由这个区间的任何一个j召唤后进化多次得到。

因此只用这个区间的a[j]的最小值就是得到i的代价。

把所有i的代价相加再加上step*x就是step对应的最小代价。

注意，这个题目是一个环而不是链，这只需要将a复制一份即可。

求区间最小值有很多方法，比如单调队列。

时间复杂度 。

wzoi

令看题为左括号，做题为右括号，就可以用一个括号序列表示行动序列。

那么一个括号序列的价值就是，对于每个匹配的括号，如果他们推荐种类相同，+10分，否则+5分。

如果 s 中有两个连续的1或0，那么可以让他们匹配，然后删去他们，递归处理。

最终剩下来的一定是1,0交错，这时一定无法让两个相同种类匹配了，贡献可以直接算。

时间复杂度 O(n)

迷宫

注意到，对于从起始格子走到某个终止格子的方案，向右移动次数 (r) 和向左移动次数(l)的差就等于终止格子纵坐标和起始格子纵坐标的差(a)，因为每次向右移动纵坐标就会 +1 ，向左移动纵坐标就会 -1 。

已经知道了 r-l=a，设 r+l=b ，则 ， 。

因此当 b 取到最小值时，l 和 r 同时取到最小值。

那么对于一个格子，你只用求向右移动次数和向左移动次数的和(b)的最小值，然后解出 l,r 判断一下就好了。

从每个格子向左右的格子连边权为 1 的边，向上下的格子连边权为 0 的边，求最短路即可。

由于边权的特殊性，这个最短路可以用 bfs 来求。

就是如果用边权为 1 的边更新点，就放到队列的结尾；如果用边权为 0 的边更新点，就放到队列的开头。

时间复杂度 O(nm) 。

std

https://ac.nowcoder.com/acm/contest/332#submit/{%22searchUserName%22%3A%22kczno1%22}