【前行&赛时总结】◇第4站&赛时9◇ CF Round 513 Div1+Div2

◇第4站&赛时9◇ CF Round 513 Div1+Div2

第一次在CF里涨Rating QWQ 深感不易……作blog以记之 (￣▽￣)"

+Codeforces 的门为你打开+

---

▶ 简单总结

莫名其妙打Atcoder比打CF要打得好些……以前CF打一场就掉一场分，直接爆炸，对CF都要绝望了。

终于这场比赛涨回来了（。＾▽＾）

看来比赛都向着思维难度进发了，代码实现已经不是考点了，以前背几个版就可以AK虐全场的时代也过去了，OI的路还很长，还得慢慢走…… (●'◡'●)

---

▶ 题目&解析&艰难坎坷的历程

「A题」Phone Numbers

〔题目〕

一个电话号码必须满足两个条件：①长度为11 ②开头为8(这是什么鬼) 。

你现在有n张数字牌（0~9），你现在需要从中选出一些，组成一个或多个电话号码（每张牌只能用一次）。求最多能够组成多少电话号码。

〔解析〕

根据题目要求的条件，我们可以知道有两种限制：

①长度限制：如果有n张牌，那么就注定了这些牌最多只能组成 n/11 向下取整这么多个电话号码；

②开头限制：如果n张牌里只有m个8，那么组成电话号码的个数最多只有m；

所以在 n/11 和 m 之间取一个min就好了

〔历程〕

网卡了一会，百无聊赖 -> 秒懂题意 -> 愉快砍掉

〔源代码〕

+Pastebin 的门为你打开+

「B题」Maximum Sum of Digits

〔题目〕

对于一个正整数x，定义S(x)为x的各数位之和（例如 S(17)=1+7=8）。

给定一个大于等于2的正整数n，求非负整数a,b，使得 a+b=n 且 S(a)+S(b) 最大，输出这个最大值。

〔解析〕

非常贪心的想法 (。・∀・)ノ

让a的每一位都是9，且在每一位都是9的情况下最大（不超过n，不然b就成负数了）。然后 b=n-a ，最后计算 S(a)+S(b) 就可以了。

〔历程〕

看完题目 -> 莫名开心 -> 莫名得到结论 -> 码完就交 -> 开心

〔源代码〕

+Pastebin 的门为你打开+

「C题」Maximum Subrectangle

〔题目〕

有两个长度分别为n,m的序列 A,B 。根据 A,B 构造出一个 n行m列的矩阵C ，C[i,j]=A[i]*B[j]。

在C中找出一个子矩阵，使得它所有元素的和不超过给定的数 X。求子矩阵的最大面积。

〔解析〕

设一个子矩阵左上角为 (x1,y1)，右下角为 (x2,y2) 。则它所有元素的和为：

C[i,j]=A[i]*B[j] (x1≤i≤x2,y1≤j≤y2) -> 合并一下就是 (A[x1]+A[x1+1]+...+A[x2])*(B[y1]+B[y1+1]+...+B[y2]) 。

可见如果我们确定了 x1,x2 就可以确定 y2-y1 的最大值。

那么我们可以先 O(n^2) 枚举A的每一个子串，存储每个子串的元素之和以及长度。可能出现有多个子串的元素之和相同的情况，我们默认对于两个元素之和相等的子串，取长度更大的那一个（实现时不需要这么做）。换句话说，我们通过限制元素之和求出长度（即限制子串的元素之和不超过某值，求出最大长度），这样的话很容易证明，随着限制的元素之和上升，子串的最大长度也应呈现出不降趋势。按理论，将每个子串按元素之和升序排列，最大长度也应该是不降序。

于是我就这样写了……毫无疑问地WA掉了。为什么呢？注意到我们这里只是将子串的元素之和存下来了，也就是只将元素之和与最大长度一一对应，并不是求不超过某元素之和的最大长度，所以很容易出现两个子串，一个的元素之和大于另一个，但长度却小于另一个。这是我打表发现的……如何解决？我们知道上述结论是正确的，那么在按元素之和排序后，再从头到尾遍历所有子串，并将第i个子串的长度强制与第i-1个子串的长度取 max ，这样对于一个子串变量，它所表示的就是不超过它的元素之和的子串的长度的最大值。这样就是真正的非降序了。

接下来再枚举B的一个子串，可以求出相应的A的子串的最大元素之和为多少，即 x/[B的子串的元素之和] ，根据最初推导的C的子矩阵元素之和的式子可以得出。这里要将 B的子串的元素之和大于x的情况舍去。由于我们以及把A的子序列按元素之和的大小排了序，且满足 A 的子序列元素大小越大，对应的子序列最长长度就越大，所以我们只需要找到元素之和不超过x/[B的子串的元素之和] 的A的子序列就可以找到最大长度了。

那么C的子矩阵的大小就是 [A的子序列的长度]*[B的子序列的长度]

〔历程〕

被某一种奇怪的思想误导，想了半天滑窗 -> 自闭 -> 开始分析时间复杂度 -> 猜是 O(n^2 log n) -> 想到了二分查找 -> 发现单调性 -> 码完代码 -> 真是愉快 -> 竟然WA了(。>︿<) ->（在这里卡了好多次，罚了很多分QwQ，差点放弃） 打了一个表 -> 发现什么不对劲的地方 -> 改掉 -> AC

〔源代码〕

+Pastebin 的门为你打开+

「D题」Social Circles

〔题目〕

n个人参加宴会。因为人们都比较害羞，对于第i个人，他希望在他左边至少有 l[i] 个空座位，右边至少有 r[i] 个空座位。你可以安排任意多张桌子（注意桌子是圆形的，即第一个人左边是最后一个人，且即使那张桌子只有一个人，他的左右也应该满足上述关系）。求满足所有客人的要求，最少需要多少座位。

〔解析〕

假设第i个人占据的区间为 [pos[i]-l[i],pos[i]+r[i]] 。当每个人所占据的区间不相交，则此时空座位的个数为 sigma{ l[i] + r[i] } ，记此数为 sum 。

我们知道更节约的做法是让两个人所占据的区间的交集尽可能的大。假设第 i 个人在第 j 个人左边，则他们相交区间的最大值为 del=min(r[i],l[i]) ，此时将会节约 del 个空座位。那么我们的目的就是让所有del的和最大。

所以就可以将 l[i] 和 r[i] 分别存储一个序列，并分别排序。

排序后对于所有i， l[i] 和 r[i] 的差之和最大，也就是相交区间最大，节约的空座位最多。

用sum减去这个值即可。

〔历程〕

听同学把题意讲了 -> hh -> AC

〔源代码〕

+Pastebin 的门为你打开+

---

The End

Thanks for reading!

- Lucky_Glass

（Tab：如果我有没讲清楚的地方可以直接在邮箱[e-mail] email我，在周末我会尽量解答并完善博客~