DUT"华为杯"第八届大工之星编程挑战赛第二周 题解

T1

送给新生的语言基础题

T2

送给新生的语言基础题二号

T3

送给新生的语言基础题第三题,然后我写跪了两发…

T4

Mgnfcnt最近迷恋上了川毅堂·成都味道。已知他这个月共吃了nn次成都味道,其中每一次都选择了鸡肉,猪肉和牛肉套餐中的一种。现在假设他共选择了xx次鸡肉,yy次猪肉和zz次牛肉套餐。又已知,xyzx,y,z均不是3的倍数,而且均为正整数。

    请给出一种可能的情况。

emmm这个讨论两种情况,给两个特殊解就行了….

T5

GG同学发明了一个新的游戏, 想要考考同样没有对象但是分数却很高的MM同学. 游戏规则是这样的: 最开始GG同学有一个 n×nn×n 的数组, 并且数组中的每一个元素都是0. 接下来GG同学会做若干次操作, 每次操作他会选择一行或者一列, 将他所选择的这一行(或者列)的所有元素都加上一个正整数. 经过几次操作之后, 他又将一个元素给隐藏了(即将该元素变为1−1). 现在他想要MM同学告诉他这个元素是多少?

emmm这题容易看出来个结论,任意一个2*2的格子,两个对角线的和是相同的…很好证明,大概是最近学行列式,所以对对角的元素比较敏感。然后注意下边角情况就好了。

 

T6

在众多DotA2战队中,王校长格外看好的有nn支队。他决定把其中kk支队买下来,来组建一支超级战队。

每支队都有5名选手,在团队中承担着不同的职责(比如中单、辅助、Carry),可以分别叫作一、二、三、四、五号位。每名选手都有一个能力值vv,代表着他的个人实力。组建超级战队的过程是这样的:对于某号位置,王校长会从已经买下的kk支队中,找出一名能力最强的选手来担任。

王校长想让这支超级战队的5名选手能力值之和尽量大。现在,让你来选择出kk支战队,从而得到这个最大值。

 

emmm就是个爆搜题,但是感觉这个爆搜不太好写,情况又很少,于是祭出了分类讨论加组合数的做法……..我们枚举下哪些位置来源于一个战队,这样子情况就少了很多,我们对1,2,3,4,5及5以上分别讨论即可…..代码有点长..

T7

菜鸡如我,考场上想到了,让格子延伸,以直线设出最后看落点的思路,但是没怎么转明白落在各个边分别对应原先格子哪个边……然后还已经被rank1大佬甩题加甩罚时,有点弃疗了…

 

T8

整个大工有nn个供暖区,标号1…n1…n。又有mm条供暖管道,每条管道连接uuvv两个供暖区。每个供暖区的面积是SiSi

改造的计划是这样的:首先,要保证宿舍区的供暖质量。假设宿舍区的标号是kk。现在要去掉一条供暖管道,使得宿舍区所处的联通块缩小,从而使其总面积变小。联通块的面积越小,供暖的质量越佳。(关于联通块的概念,请百度一下)

所以,请你求出:去掉一条供暖管道后,宿舍区所处联通块的最小总面积。

一道板子题,搞下双联通,缩一下点,然后dp一下就行,注意下可能询问重复,一直问你菊花图的菊花点…..被这个卡了很久 ,罚时也因此爆炸,把答案记忆化一下即可。

T9

给你一个包含 nn 个正整数序列 AA 和一个正整数 kk. 你的目标是将这 nn 个正整数划分成 kk 个不相交连续非空的子序列, 以至于每个元素都恰好属于一个子序列. 每个子序列可以有两个整数 ll 和 rr (lr)(l≤r) 描述, 其含义是 A[l],A[l+1],,A[r]A[l],A[l+1],…,A[r]. 这样的一个子序列的价值是所有元素的按位或, 即A[l]|A[l+1]||A[r]A[l]|A[l+1]|…|A[r] . 总的价值是所有的子序列的价值和. 现在你必须找道一种划分方式使得总的价值和最大.

如果你的不知道按位或的话, 你能了解更多关于[按位或](https://en.wikipedia.org/wiki/Bitwise_operation#OR).

总结

发表评论