武汉大学2020春校赛题解(ADEFGHIJ)

好久没有写题解了,因为最近在和队友一起做区域赛原题……就没打CF,每次做完区域赛题就自闭,自闭之后也不写题解……自裁谢罪
这次题出了一些锅,所以写了一个勘误文件,如果要从我这里下载题面的话一定要看喔……
题面+赛中勘误+官方题解:链接:https://pan.baidu.com/s/14AbF2LGexCWlo6npUAfHXA 密码:hv9a

A – A Simple Problem about Election

题意是说有n个人投票,自己是最后一个投的,而且自己必须投m票(而且是投给不同的人),问自己能达到的最好名次是多少
还有一个条件,在所有同分的人里,自己排最后
自己写的时候策略是:先给自己投一票,再把比自己成绩高的都投一票,如果还有剩下的,就从票最少的人开始从小到大投。O(nlogn)
官方题解:先给自己投一票,此时只有给比自己正好少一票的人投票会影响自己的最终排名,因此先投其它人再投这些人,排名也很好算。O(n)

D – Deploy the medical team

有n个人,其中有m个人有能力当队长。现在从里面选一些人组队,要保证有且仅有一个队长,问能组建多少不同的队伍。
先从m个人里面挑一个人当队长,C(1,m),再从剩下的n-1人里面挑1个/2个/……/n-1个,后面是二项式系数之和=2^(n-1)
所以答案=m*2^(n-1);
在算2^(n-1)的时候,有人用了1<<(n-1),这样会没法取模。如果循环n次每次左移一位再取模,复杂度还是O(n)的,不符合要求。
所以用快速幂算2^(n-1)。

E – Engage the Medical Workers

给一个二维方阵,要求得到它的一个简化版本,满足同行同列大小关系不变,且原图里若有两个位置数字相同,在新图也必须是相同的。
之前看到过类似的题,那个题是同行同列数字相同才有影响,感觉这题在这一点上还是简单多了
首先按照数字大小排序,先不考虑同样数字的情况,从小到大处理每个数字所在的位置,当前位置填的数字应该是新图里max(同行的最大的数字,同列的最大的数字)+1。
对于相同的数字,举例:如果有两个相同的数字,那么新图里这两个位置填入的一定是max(第一个位置可以填入的数字,第二个位置可以填入的数字)。所以直接把所有相同的数字一起处理,找到所有可填入数字的最大值,再填入所有这些位置。
最后输出新图里最大的数字,(我会说我是因为没看输出样例,输出了一遍新图结果WA了两发吗……

F – Figure out the sequence

两个字符串s和t
F[1]=s
F[2]=t;
F[3]=s+t;
F[4]=F[2]+F[3]……
求F[n]中各个字符的数量
不用得到最终的字符串,Fibonacci数列,n不大所以不用优化
看代码吧,dp第一维是各个字符,第二维是串编号

G – Game Strategy

其实还是不太懂原题目为啥能等价成每个人选择一个数留下
但是我代码就是这个思路
先把原题目等价为每个人留下一个数,其它的扔掉
假如A,B选完了,那么C选的数一定是固定的;
所以在A之前选了一个数,轮到B抉择的时候,他会想到自己选了每个数之后,C会出什么牌,以及最终结果是什么
所以他也能预见到自己选数之后的最终结果,会选择所有结果里面最小的那个。那么B选的数也是固定的。
所以同理,A也会预见到自己选择了某个数之后,B和C会出什么牌,因此他会选择最终结果最大的那个。
O(n^3)暴力

H – Hinnjaku

JO 厨 狂 喜

大模拟,理清楚了就好写了
jojo 和 dio 最开始都有H点血,每次 jojo 欧拉一下,dio 就掉一点血,每次 dio 木大一下,jojo 就掉一点血
他们都有大招 zawaluduo,当某个人使用这个大招的时候,另外一个人的招数(ora 或 muda)都会失效,而且对方会立即死亡。
如果他们同时使用大招,那么 dio 会赢。
如果时间结束了他们没有人死(血量降为0),那么谁的血多谁就赢了,一样多则平局。
只有 zawaluduo 的条件会难写一点,但其实很简单:先判断 dio 有没有发大招,如果他发了那他就赢了,再判断 jojo 有没有发大招,如果 jojo 发了 jojo 就赢了
//因为写反了Wryyyyyy而WA了qwq 太粗了

I – Interesting Matrix Problem

现学现卖的数论分块,感觉不简单啊= =
粘贴出题人题解  《武汉大学2020春校赛题解(ADEFGHIJ)》

《武汉大学2020春校赛题解(ADEFGHIJ)》

数论苦手表示学到了……

J – Jogging along the Yangtze River

题意很简单,每次可以向前走两步,或者向前一步向左一步,或者向前一步向右一步,求到达终点的方案数
看到“不能走到河里”,觉得是卡特兰数,但是卡特兰数没有“向前走两步”的操作。
那么可以枚举“向前走两步”的操作数,然后再将剩下的操作求卡特兰数,再将“向前走两步”的操作插进去就可以了
类似于往不同的盒中放相同小球,允许空盒的排列组合问题。
可以看这个: 排列组合 “n个球放入m个盒子m”问题 总结
把不同操作下的答案求和就可以得到公式了,需要一种O(n)逆元求组合数的奇技淫巧,板子在代码里

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注