竞赛讨论区 > 2020 East Central North Americ

2020 East Central North Americ

头像
王清楚
编辑于 2021-08-30 10:49:03 APP内打开
赞 0 | 收藏 0 | 回复0 | 浏览716

A - All in the Family

树的根不确定所以要先找到根,不作为出现的就是根

然后每个点依次找齐所有祖先放入数组,判断两个点的关系时先判断是否是直接关系(child/grandchild),再判断关系即可


B - Kinky Word Searches

表示当前在第行第列目标串第位还剩次转向当前方向为时是否有可行方案,可行,为不可行。

对原图记忆化搜索,当等于原串长度时判断是否可行,时直接退出。

题面中However you cannot stay on a letter twice in a row后加(you can return to a letter and reuse it)


C - Math Trade

将人抽象成点,所有人被的物品所拥有的人连一条有向边

这样满足条件的传递关系肯定是以某人开头的一个简单环,枚举开头找最长环即可


D - Oreperations Research

从题目描述中我们可以理解,一节火车车厢是由来自一个(或两个)推车队列的连续序列填充的。我们首先沿着火车定义一条时间线,因为火车车厢是一个一个装满的。然后在两个推车队列上定义一对指针。这两个指针最开始是在两车队列的开头。

在每个时间点,这两个指针从它们的开始位置(称为 start configure)移动到停止位置(称为 next configure,也是下一个时间点的 start configure),分别沿着各自的两个连续序列。这两个连续序列的推车所装载的矿石,被倾倒到对应于当前时间点的火车车厢。可能没有或有多对序列可以完全填满车厢,所以一个start configure可能导致没有或有多个next configure。然后我们来到下一个时间点,next configure现在变成了start configure

重复上述过程,直到没有有效的next configure,或时间点到了最后一节车厢。

E - overhill1

加密方法如下:

Step1:给定阶数,和大小的加密矩阵A。

Step2:给定明文,明文只包含、空格“ ”。

Step3:明文的每个字符转化为一个数字;对应对应,空格“ ”对应,得到整数数组。

Step4:转化好的整数数组每个分为一组,最后不够的用空格即36补齐。

Step5:每组n个数字形成一个大小的矩阵,称为

Step6:,得到大小的矩阵。

Step7:得到若干矩阵,将它们按原来顺序还原,得到整数数组。

Step8:每个数组转化回字符并输出(对应对应对应空格“ ”)。

2.解法

按照以上步骤模拟即可。

3.时间复杂度:

F - overthehill2

题在题基础上,给出明文和密文以及加密矩阵的阶数,求加密矩阵。

​ 对于明文和密文转化后处理成E题题意中的矩阵形式。加密矩阵A,明文矩阵B,密文矩阵C,有A*B=C。

​ 对于加密矩阵的同一行来说,依次乘上的同一列,得到的对应一行。对应于与相同列数的n元方程组的求解,解即是的一行。这样矩阵的行,对应要解个方程组。
​ 使用高斯消元处理方程组,另外在模运算下计算,除以一个数需要转化成乘以这个数模的逆元,另外计算过程也要记得取模。

​ 求逆元用费马小定理或者逆元线性筛都可。

(逆元线性筛:inv[1]=1; (i=2->MOD-1) inv[i] = (Mod-Mod / i) * inv[Mod% i]%Mod; )

​ 时间复杂度:为阶数,为字符串长度。

G - Rankproblem

最开始,排名第i位的队伍名称为,排名顺序为

(原)排名的队伍打败了(原)排名的队伍,

,则排名不受影响;

,则y+1x 的队伍排名向前进一位,变为 yx-1​,原排名的队伍放在位;

即:变为

给出比赛胜负情况,按题意进行模拟即可。

3.时间复杂度

H - restroommonitor

思路:为了满足所有人的需要,我们总是优先满足更急的人的需要。所以容易想到吧这些人按照截止时间排序。然后我们遍历所有的人,如果他的时刻与前一个人不一样,那么就相当于转移到了一个新的时刻,否则保持在原来的时刻。而我们怎样判断当前的人能不能满足需求呢?我们发现,每分钟有s个新的坑位,而有一个新的纸位,我们只需要判断当前的坑位量和纸位量够不够就可以了。

时间复杂度


I - Scholar's Lawn

首先对于给出的路径建出图,并跑最短路。这样处理出了到达每个交点的最小距离。然后考虑枚举教授走过的路径和路的交点,教授花费的时间可以计算出来。现在需要计算学生走到交点的时间,交点肯定位于一条路径中的某个位置,于是通过之前的最短路得出走到交点位于的路径的两个端点的距离,然后计算从端点到达交点的时间即可。

时间复杂度


J - Simply Sudoku

暴力模拟,先枚举每个格子,判断是否唯一,如果唯一则填数。再按行、列、网格枚举是否存在唯一填入的数,存在则填入,直到不能填为止。最后判断是否填满即可。

时间复杂度


K - Weighty Tomes

假设当前最高的高度为,并且还剩。用个箱子试一次,如果坏了则说明最大高度,还剩;如果没坏则说明 最大高度,还剩。于是用转移即可。

考虑第二问,枚举答案,然后判断这个答案的次数是否等于第一问的答案即可。

时间复杂度


L - Workers of the World Unite! Just Not Too Close

由题目可得对于门肯定存在一个分界线,一边只能用门,另一边只能用门。于是枚举这个分界线,剩下的是一个带权匹配问题。考虑设立三层点,从左到右第一层共个点,表示个人;第二层个点,表示每个门;第三层个点,表示工作站。对于每个人和门建立边,再对于门和工作站建立边,然后使用带权匹配相关算法即可计算出最小时间,输出方案则看每条边匹配了哪个点即可。

时间复杂度

0条回帖

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

近期热帖

等你来战

查看全部

热门推荐