Codeforces Round #385 (Div. 2) ABCD题解

如果说智商有颜色,那我一定是透明的~

快速版题解:
大概就是A题水题;B题勉强算个小模拟,还是水题;C题并查集上统计;D题二分。四道水题,目测算是手速场。

具体版:
A
题意:将字符串最后一个字母拿出来,放到头,称为一次操作。比如abcd进行了一次操作就是dabc。问,能搞出多少个不同的串。(阿弥陀佛,贫道没有读题,看样例看出来的,至于题意对不对,就只能上帝保佑了。)
思路:无
代码:385A

B
题意:就是用.表示虚的,x表示实的,这样他就给你了一个东西,问两个这样的东西能不能拼成一个长方形的东西,当然是包括正方形的。但是拼的时候,只能直接刚,不能旋转啊,翻转啊之类的。
思路:直接扫,看看这个图本身是不是方的。
代码:385B

C
题意:有n个节点,m条无向边。然后n个节点里有k个国家中心节点。然后呢,任何两个国家中心节点之间呢,不能有通路。现在呢,要你随便添边,但是呢,还是要保证没有通路。问你最多能加多少边。比如A到B有边,B到C有边,那么A到C就有通路啦,如果A、C都是国家中心节点,就不行。
思路:并查集,然后你就能得到若干个集合,这些集合要么最多含有一个中心节点,要么就没有中心节点。然后呢有中心节点的集合呢,先在内部全部连一遍,记个数。没有中心节点的全部连到一起,记个数。最后把没有中心节点的集合全部连到某一个有中心节点的集合上,好像要一个一个去试。
代码:385C

D
题意:

  • 这题有点新意。首先会给你输入一个n,告诉你这个矩阵有多大。然后输入就停了,等你输出了点东西,再有输入。比如样例,上手告诉你矩阵是3×3的,然后就没有了,你要去查询。
  • 查询规则如下:
    你先要输出一个k,表示你要查多少列,比如样例一里,你输出的3。然后换行,输出k个数,表示你具体哪些列。然后系统就会回给你每一行,这些列的最小值是多少。
  • 样例解析:别人告诉了你矩阵了,输入了3了,但是不会告诉你矩阵是[[0, 3, 2],[5, 0, 7],[4, 8 ,0],]。现在你输入3,然后1,2,3。然后系统就给你0,0,0。因为每一列都选了,所以每一行最小值都是0。又比如你又进行一次查询,查询2,然后1,2,表示你要查询只考虑每一行的第1、2列的情况下的最小值。那第1行就是min(0,3),第2行就是min(5,0),第3行是min(4,8),所以系统回你0,0,4。
  • 然后呢,题目要你求什么呢?排除对角元(aii)的每行的最小值。但是你的查询最多只能有20次。
  • 然后题干提示你了,你输出一次查询之后,记得刷新,怎么刷新看题目。

思路:

  • 首先呢,得有个二分的直觉。我第一直觉是,先查左半边(1n/2),再查右半边(n/2+1n)。这样呢,原矩阵就等分成了4份,左上角、右下角都有对角元,所以肯定是0,但是呢左下角,右上角的就都查询到了。然后呢,发现左上角,右下角都和原问题一个形式,就能递归形式求解啦。
  • 但是转念一想就发现不对,一层层递归下去,查询次数是n次。人家的n可是1000,但是你最多只能搞20次查询。
  • 然后呢,按这个思路,把查询区间展开一下。比如n=10,按直觉的做法,上手查1-5,然后查6-10。接着展开1-5,查1-3,再查4-5。再展开6-10,查6-8和9-10。然后你就发现其实1-3和6-8可以一起查。
    现在可能还不够明显,我们再展开一层。下一层就是查1-2和3-3(对就查着1列)和4-4和5-5和6-7和8和9和10,然后你就发现1-2、4-4、6-7、9可以一起查,剩下的也是可以一起查。
  • 所以,还是之前二分的直觉,一直拆下去,拆到只查1列的那一层,你就能得到一个二叉树。然后从底往上查,同一层的左儿子一起查,右儿子一起查。相当于每层查两次。
  • 然后你看1024这么拆下来也就10层,每层查2次,刚刚好20次。

代码:385D

E
没看,有生之年争取填坑。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,504评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,434评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,089评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,378评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,472评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,506评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,519评论 3 413
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,292评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,738评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,022评论 2 329
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,194评论 1 342
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,873评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,536评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,162评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,413评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,075评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,080评论 2 352

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,743评论 0 33
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 171,971评论 25 707
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,608评论 18 399
  • 一山桃花开,二月春风来。三人谈行笑,四海望升平。
    文澜海阁阅读 211评论 0 0
  • 坚持早起的第……天。 善于发现,其实很美好。 特别是清晨。 喜欢寺庙。 记忆中,有老和尚赠与我们的水果; 有僧侣的...
    米拉姑娘阅读 274评论 0 0