Codechef October Challenge 2018 游记

时间:2022-06-03 05:49:19

Codechef October Challenge 2018 游记

CHSERVE - Chef and Serves

题目大意:

乒乓球比赛中,双方每累计得两分就会交换一次发球权。

不过,大厨和小厨用了另外一种规则:双方每累计得 K 分才会交换发球权。比赛开始时,由大厨发球。

给定大厨和小厨的当前得分(分别记为 P1 和 P2),请求出接下来由谁发球。

思路:

\((P1+P2)\%K\)判断奇偶性即可。

代码链接

BITOBYT - Byte to Bit

题目大意:

在字节国里有三类居民:

  • 比特:在比特出现 2 毫秒后,它会变成一个半字节;
  • 半字节:在半字节出现 8 毫秒后,它会变成一个字节;
  • 字节:在字节出现 16 毫秒后,它会变成两个比特。

在第 0 毫秒时,字节国里只有一个比特。大厨想知道第 N 毫秒之前(即介于第 N − 1 和第 N 秒之间)字节国的人口。请求出 N 毫秒之前字节国的每类居民各有多少。
\(N\le10^4\)

思路:

按题意模拟即可。
代码链接

MINDSUM - Minimize Digitsum

题目大意:

给定正整数 N 和 D。你可以进行下面两种操作:

  • 令 N 加上 D;
  • 令 N 为 digitsum(N)。

其中,digitsum(x) 代表 x 的各位数之和。例如,digitsum(123) = 1 + 2 + 3 = 6,digitsum(100) =
1 + 0 + 0 = 1。

你可以以任意顺序进行任意次操作。请求出 N 可以达成的最小值,以及达成该最小值所需的最少操作次数。

\(1\le N,D\le10^{10}\)

思路:

最小值可以通过\(N,D\)的\(\operatorname{digitsum}\)来确定。而最少操作次数相当有限,BFS即可。

代码链接

HMAPPY - Appy and Balloons

题目大意:

Appy 最喜欢气球!她想要你连续 N 天(编号 1 ∼ N)都送她气球,第 i 天 Appy 想要 Ai 个气球。不巧的是,你只有 M 个气球。幸运的是,你可以用糖果代替气球送给她。在第 i 天,你每少给 Appy 一个气球,Appy 就会找你要 Bi 颗糖果。具体地,如果第 i 天你给了 Xi 个气球,那么你还需要给她 Ci = max(0, Ai − Xi) · Bi 颗糖果。

你的目标是最小化一天之内给 Appy 的糖果数量,换言之,最小化 max(C1, . . . , CN )。

  • 1 ≤ N ≤ \(10^5\)
  • 0 ≤ M ≤ \(10^{18}\)
  • 0 ≤ Ai ≤ \(10^9\)
  • 0 ≤ Bi ≤ \(10^9\)

思路:

二分答案。二分上界取\(10^{18}\)。

(讲道理最大会达到10^{23}左右,但是不知道为什么一直WA,最后改成\(10^{18}\)就过了。)

代码链接

CCIRCLES - Chef and Circles

题目大意:

平面上有 N 个圆。我们称圆 i 和 j (i ̸= j) 形成一个好的二元组,当且仅当可以在圆 i 上选择一点 P1,圆 j 上选择一点 P2,使得 P1 和 P2 的欧氏距离恰好为 K。注意 P1 和 P2 可以不是整点。

你需要回答 Q 个询问。每个询问给定目标距离 K,你需要求出此时有多少好的二元组。请注意,可能有多个圆重合。

思路:

将所有圆对间最远、近点对处理出来,排序。线性扫一遍,遇到近点对+1,远点对-1。

代码链接

SURCHESS - Chef and Surprise Chessboard

题目大意:

大厨喜欢下国际象棋,所以他买了一块 N 行 M 列的新棋盘。
大厨认为行列数相等,且相邻(即有公共边)的格子颜色不同(也就是所谓的“棋盘格”)的棋盘才是正确的棋盘。不过,大厨新买的这块棋盘未必是正确的。

一块棋盘的子棋盘定义为原棋盘中以任意格子作为左上角,任意格子作为右下角的部分。原棋盘本身也是自己的子棋盘。

大厨可以改变一些格子的颜色,即从白变黑或者从黑变白。在完成改变之后,大厨想从原棋盘上切出面积最大的正确的子棋盘。

大厨还没想好要改变几个格子的颜色。于是,他有 Q 个询问,第 i 个询问中大厨最多改变 ci 个格子的颜色(也可以不改变)。请你告诉大厨,在每个询问的限制下,能切出的面积最大的正确子棋盘的边长。

  • 1 ≤ N, M ≤ 200
  • 1 ≤ Q ≤ \(10^5\)
  • 0 ≤ ci ≤ \(10^9\)

思路:

对于点\((i,j)\),若\(i+j\)为奇数则将该格子颜色翻转,题目就变成了求最大同色矩阵。

动态规划前缀和优化求出每个矩阵至少需要多少步能够同色。然后求出翻转\(i\)步能翻转出多大的矩阵,最后对于每次询问可\(\mathcal O(1)\)回答。

代码链接

BBRICKS - Beautiful Bricks

题目大意:

大厨决定装修自己的餐厅。顾客进入餐厅,需要走过一段笔直的走廊。走廊两侧贴了瓷砖,
每侧有 N 块。所有瓷砖大小相同,且两块瓷砖之间没有缝隙。
不巧的是,所有瓷砖颜色相同,看着有些乏味。大厨想让走廊变得五彩斑斓,为此他准备替
换恰好 K 块瓷砖,而且任意两块替换的瓷砖都不能相邻。
大厨现在要解决一个很复杂的问题:有多少种替换瓷砖的方案数?由于答案可能很大,请输
出其对 \(10^9 + 7\) 取模的结果。

  • 1 ≤ T ≤ 5
  • 1 ≤ N ≤ \(10^9\)
  • 1 ≤ K ≤ 1, 000

思路:

OEIS得到答案为\(\mathrm A104698(n-1,k-1)\times2\)。

对阶乘分段打表即可。

代码链接