竞赛讨论区 > 【题解】牛客2021年儿童节比赛

【题解】牛客2021年儿童节比赛

头像
王清楚
编辑于 2021-06-05 14:25:39 APP内打开
赞 6 | 收藏 1 | 回复8 | 浏览943

A

思路:
显然只需要统计n的个数和"ya"子串的个数就可以了。
对于第一种操作,使ya的个数加上n的个数。
对于第二种操作,使n的个数加上ya的个数,然后将ya置零。
最后总长度为
代码:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47948881

B AC自动机fail树dfs序建可持久化线段树

显然只用看AC有没有输出就可以了。因此答案就是
代码
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47928563

C 卡其脱离太

必然是走到一个能够到达的最远的点,也就是在到达这个点之前不会与黑色轿车相遇,然后直接传送到离这个点最远的点。
思路1 首先进行两次BFS预处理出来黑色轿车和莱纳到达各点所需时间,取最大时间点然后在最大时间点处再次进行BFS找到最远的点,取最大值,复杂度
代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47932248

思路2 首先用换根DP求出以每个叶子为根时的最大深度,然后在用的代价枚举叶子计算到根节点的距离合并。
用multiset辅助转移的方法复杂度为
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47928097
可以将multiset优化掉变为O(n)

D

题意:求,然后估计有同学移项看见就直接上了,没管这个同余等号。

然后常用的套路,也就是同余方程改写为不定方程。

原式变为,利用裴蜀定理更进一步变形为,exgcd随便求一个p和一个k。因为,所以再套一层就求出来x,y了。然后因为x,y可能是负数,所以要处理一下,考虑最原本的式子即模n的模系,那么x,y在多走n的整倍数时无影响。所以做出如下处理

if(x<0)x+=(abs(x/n)+1)*n;
if(y<0)y+=(abs(y/n)+1)*n;

e.帮助走失儿童回家 easy version

按照顺序分别是

御坂美琴 出自《某科学的超电磁炮》

黑羽快斗 出自《名侦探柯南》

杰瑞 出自《猫和老鼠》

伊井野弥子 出自《辉夜大小姐想让我告白》

我老婆 出自《辉夜大小姐想让我告白》

石上优 出自《辉夜大小姐想让我告白》

艾莎 出自《冰雪奇缘》

帕克 出自《火影忍者》

白井黑子 出自《某科学的超电磁炮》

F

答案

RPJI
ENMK
TSGC
FADB
LQHO

按照行从小到大递增,列从小到大递增的顺序。

第一个是清楚姐姐前头像。
柏田——无口的柏田小姐与元气的太田君

第二个是小冠,虽然都是白毛萝莉,和智乃最大的区别在于发饰,智乃的发饰是一左一右两个X。(虽然作品名是Slow Start,但是由于老司姬车速极快,被吐槽应该叫Fast Start)
千石冠——Slow Start

第三个姬野星奏,清楚姐姐的现任头像
姬野星奏——想要传达给你的爱恋

第四个烟绯
烟绯——原神

第五个维包子,暴露年龄系列。
维多利加·德·布洛瓦——哥特萝莉侦探事件薄

第六个桐间纱路
香风智乃——请问您今天要来点兔子吗?

第七个群友友情提供的鸟(我根本认不出来好吧)
泠鸢yousa——B站:https://space.bilibili.com/282994

第八个是元起可爱的艾米丽可
艾米丽可——影宅

第九个丹特丽安,同样暴露年龄系列。“吾问汝,汝为人否? 否,吾乃天,壶中之天”
丹特丽安——丹特丽安的书架

第十个凯特,艾米丽可的主人,主角团的智商担当。(当时觉得放上来一坨黑,为了降低难度把艾米丽可也摆上来了)
顺便安利一下《影宅》的前作,《黑》。
凯特——影宅

第十一个猫羽雫,某不知名的四糸智乃经常用的表情包。
猫羽雫——P站 甘城なつき
id: 3036679
B站:https://space.bilibili.com/488732204

第十二个那月酱
南宫那月——噬血狂袭

第十三个猫猫,虽然看起来是国风,但是是实打实的日轻。故事背景是架空的中国,时间大概是唐朝。女主就叫猫猫 (マオマオ)日语读音也是maomao,后面养了只猫叫毛毛。有两版漫改,新版女主看起来更幼一点,建议看新版。
猫猫——药屋少女的呢喃

第十四个索菲,某四糸智乃的头像。
索菲·特瓦伊莱特——邻家索菲

第十五个香风智乃,点兔天下第一!芳文社就是宇宙的主宰!
香风智乃——请问您今天要来点兔子吗?

第十六个诺贝塔,就是那个刚出来的时候很火的小魔女之魂,在steam上有卖,游戏只做了一半,希望作者不要太监。
诺贝塔——小魔女诺贝塔

第十七个小梦,不会有人分不出小梦和纱路吧?
恋冢小梦——Comic Girls

第十八个小仓唯,某兰子塞的私货(请问你说的是这个有朋友的小仓唯,还是没朋友的小仓唯)
冰川镜华——公主连结!Re:Dive

第十九个拉菲,和小冠、康娜互为同分异构体,同样无口白毛萝莉,CV都是长绳麻理亚(考哥.jpg)
拉菲——碧蓝航线

第二十个四糸(mi)乃,求求你们不要再念系(xi)了。四糸智乃这个ID的出处,四糸智乃=四糸乃+智乃。某四糸智乃本人特别喜欢兔兔。
冰芽川四糸乃——约会大作战

G 四则运算

根据每个字的汉语拼音的声调一声是"+",二声是"-",依此类推,根据声调得到一组四则运算的式子,题目中说“每次都会忘了先乘除后加减的运算顺序”,表明每次都是从左往右的顺序进行计算的

suī rán jīn tiān shì ér tóng jié dàn hái shì xū yào qù shàng yòu ér yuán lǎo shī mén jīn tiān gé wài qīn qiè gěi bān lǐ měi wèi xiǎo péng yǒu mǎi gēn bàng bàng táng jīn tiān xué xí dào sì zé yùn suàn kàn qǐ lái hǎo jiǎn dān dàn shì měi cì dōu suàn bù duì 
121142224241444422312112414313343233144211224424443233144341444

代码:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47928698

H 数码宝贝

B题解:
八神太一:勇气徽章(代表不怕困难,勇于面对的心)
石田大和:友情徽章(代表重视朋友的心)
武之内空(武之内素娜):爱心徽章(代表肯去付出,关怀他人的心)
泉光子郎:知识徽章(代表追求知识,寻找真相的心)
城户丈(城户助):诚实徽章(代表不讲大话的心)
太刀川美美:纯真徽章(代表不虚伪,流露真情的心)
高石武:希望徽章( 代表面对逆境仍不放弃的心)
八神光(八神嘉儿):光明徽章(代表为他人著想,像光一样照亮他人的心)

(0)D,54集
(1)A
(2)C
(3)B,阿武是二年级学生
(4)E,迪路兽是嘉儿的数码宝贝,成熟期
(5)E,A和B都是成熟期,C和D都是完全体,E中神圣天使兽是完全体,小丑皇是究极体
(6)D,亚古兽 - 暴龙兽;加布兽 - 加鲁鲁兽;巴达兽 - 天使兽;仙人掌兽 - 花仙兽
(7)C,狮子兽是成熟期,黄金剑狮兽是究极体,跳过了完全体阶段
(8)C
(9)B
(10)A

答案:
DACBEEDCCBA

I qcjj和yuju玩填充游戏

题解:
圆和正方形都是中心对称图形。所以,先手具有优势。先手在放置第一个正方形时,将正方形的中心和圆的圆心重合起来。那么,该图形剩下的区域也是中心对称图形。
对称意味着:如果后手能够在剩下的图形之中,放入一个新的满足条件的正方形;则,先手可以根据中心对称图形的性质,在圆之中找到该新正方形的中心对称的位置也放入一个正方形。
那么,是否后手必败呢?

结论:
当第一个正方形能够放进去的时候,先手必胜。
当第一个正方形都放不进去的时候,先手必败。
所以只需要比较圆的直径和正方形的边长大小即可。

注意:
题中说的是“任何交点”,所以圆和正方形不能相切。

J

这是一道线性代数经典题,问题来了,为什么儿童节要做线性代数呢。阿巴阿巴阿巴,我也不知道,可能就是想出个数学题吧。

首先肯定可以想到k很小,可以矩阵建图。考虑每一层网络之间的图都建成一个矩阵。

例如第一层网络到第二层网络。如果第i个开关链接下层的第j个接线柱,矩阵的第i行第j列就是1,反之就是0。

例如样例中的上层网络就是
这时候继续看样例,如果数理基础好的话其实立刻就反应过来了,为啥呢,因为样例中下层网络直接连上去的,不起任何作用。

我们要构造答案的中层网络为
然后进一步发现
它们做矩阵乘的结果是单位元e。它会是某种巧合么?当然不可能是什么巧合啊。这个题讲到这里估计有线代基础的同学就已经会了。

ok,现在回到问题本身,对于某一层矩阵,当我们定义矩阵的第i行第j列为第i个接线柱是否控制接下层的第j个接线柱。控制为1,不控制为0时。

考虑两层网络的影响如何合并,即假设现在有两张用矩阵建的图,第一个矩阵A表示第一层中第i行第k列为第i个接线柱是否控制接第二层的第k个接线柱。第二个矩阵B表示第二层中第k行第j列为第k个接线柱是否控制接第三层的第j个接线柱。

现在如果我问,第一层的第i个接线柱是否对第三场第j个接线柱有控制关系,记这个关系为,如何用数学公式表示?
你会发现合并两层控制网络这个操作的代数意义恰好是模二意义下的矩阵乘。

设上层网络为矩阵A,中间层网络为矩阵x,下层网络为矩阵B。

最终达到的效果“第i开关仅控制第i个灯泡”,为矩阵乘法单位元e。

则有方程式

利用逆元移项

最后再遍历邻接矩阵输出中层网络图即可。

本场比赛出题团共有5位(大概是愿意透露姓名?)的出题人
希望大家玩的开心~
出题人1
图片说明
出题人2
图片说明
图片说明
出题人3

出题人4
图片说明
出题人5
图片说明

8条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐