Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
2018 TCO Semi 2 解题记录
? 解题记录 ?
? Topcoder ?
? 贪心 ?
? 构造 ?
2019-03-01 19:55:13
356
0
0
rockdu
? 解题记录 ?
? Topcoder ?
? 贪心 ?
? 构造 ?
### 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$
上一篇:
2018 TCO Semi 1 解题记录
下一篇:
AGC025 解题记录
0
赞
356 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
没有帐号? 立即注册