2018 TCO Semi 2 解题记录

### Easy NextLuckyNumber
题意：给定整数$x$，找到比$x$大的数字$d$出现了$a$次的最小的整数。$x\le 10^{17},d\in[0,9],a\le 17$

题解：直接做会很讨厌。考虑分两种情况：位数比$x$多的答案和位数与$x$一样的答案。第一种很简单，要么全部为$d$，要么高一位为$1$，后面的相当于随意填，我们考虑第二种。
类似数位$dp$讨论前$k$个位一样时$(k\in[0,|x|])$后面的情况，设$d$在后面还需要出现$y$次，如果$y=|x|-k$那么直接判是否可行然后$break$。否则把第一位$+1$(如果是$9$就直接到下一位)，然后后面的可以随意填。
现在我们考虑随意填怎么贪心，随意填相当于要让$d$出现$y$次且字典序最小的串(可以有前导0)。分情况讨论：
1、如果$d$是$0$，那么把$y$个$0$放在前面，后面全部填$1$
2、否则把$y$个$d$放后面前面全部填$0$。
大讨论，复杂度$O(17^2)$

### Medium VennDiagrams
题意：在网格上画出$N$个集合组成的韦恩图？？？？？$N\le 10$，格子限制$50\times 50$
看了半天的题，懵逼。
实际上只是要求包含任意集合的区域形成连通块。

题解：如果不限制格子的话，可以拉一条$2^n-1$然后在下一行放满所有的集合。因此，我们不拉一条，拉4条，然后用一个长条链接它们。

### Hard RearrangingBoxes
题意：有$A\times B\times H$个小方块组成一个长方体。在拿走$K$个后构造一个放置方案使得表面积与原来相等且所有小方块连通。

题解：不难发现首先可以拿走一个角上的所有方块只剩下三个面有小方块。
其次，我们还可以拿走所有的有三个面与其他方块相邻的方块。
最后的形状会是三面都被拿的只剩一些长条。
但是看了题解才知道实际情况复杂得多，我们需要对$A,B$进行讨论，每种讨论都要手玩最优情况……
1、$A-1,B-1$都是偶数：如下图左，最常规的方案。其中灰色代表一格高，深灰色代表$H$格高。
2、$A-1,B-1$都是奇数：如下图右，发现可以空出最右边一列达到可以再拿取一些三联通方块的效果
![图片标题](https://www.topcoder.com/wp-content/uploads/2018/11/image10-1.png)
3、一奇数一偶数：构造如下图：
![图片标题](https://www.topcoder.com/wp-content/uploads/2018/11/image42.png)
要手玩这么多情况玩对，怪不得当场没人$A$

Rockdu's Blog

导航

最近发表

大佬们的友链