标签: 题解

43 篇文章

周赛 – 203
1. 圆形赛道上经过次数最多的扇区给出一个圆形赛道,共被分为 n 段区域。再给出一个数组 rounds ,代表马拉松的各个阶段。n 和 |rounds| 数据范围都为 1e2 。例如 rounds=[1,3,1,2] 代表:赛道共分为 4 段,赛程共分为 3 段,第一段是 [1,3] , 第二段是 [4,1] ,第三段是 [2,2] 。以数组形式返…
双周赛 – 29 – 并行课程 II
4. 并行课程 II思路【状态压缩】看到数据范围很小,考虑状态压缩。再加上在枚举某一门课是否可以上的时候,确实需要其他课的信息才能判断。【整体思路】dp[state] 表示上课状态为 state 时所需要的最少学期数。第一维枚举当前状态 state ,对于这个状态开始暴搜,暴搜前统计在当前 state 下可以上的课程(去除掉 state 中已有的课…
双周赛 – 28 – 安排邮筒
4. 安排邮筒分析如果数据范围比较小的话,可以枚举 dp[now_pos][pre_pos][num] 做。但是虽然房屋数是 1e2 的,但是位置是 1e4 的。观察可以发现,如果已经给出了一个区间 [i, j] 并且只放一个邮筒,那么邮筒放在 house[(i+j)/2] 的位置上是最优的,与具体坐标无关,这是可以预处理出来的。状态表示根据分析,…
周赛 – 193 – 树节点的第 K 个祖先
4. 树节点的第 K 个组先给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。请你设计并实现 getKthAncestor(int node, int k) 函数,函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点…
Codeforces Round #647 (Div. 2) – Johnny and Contribution
因为这道题昨晚被zz鄙视了好久,不过我觉得的确不简单啊。唉。题意我觉得题意蛮复杂的,然而zz却无法理解为什么我看了这么久都没看懂题。给出 m 个点和 n 条边,一个长度为 m 的序列表示每个点的权值。现在需要你给出一个标注各个点权值的顺序,要求:对于每个点,标注的权值和给出的权值相同,否则输出 -1 。如果需要给某个点标注权值 x ,那么考虑所有已…
Leetcode – 周赛 – 191 – 两个盒子中球的颜色数相同的概率
4. 两个盒子中球的颜色数相同的概率桌面上有 2n 个颜色不完全相同的球,球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ,其中 balls[i] 是颜色为 i 的球的数量。所有的球都已经 随机打乱顺序 ,前 n 个球放入第一个盒子,后 n 个球放入另一个盒子(请认真阅读示例 2 的解释部分)。注意:这两个盒子是不同的。例如,两…
周赛 – 190 – 两个子序列的最大点积
4. 两个子序列的最大点积给你两个数组 nums1 和 nums2 。请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。数组的非空子序列是通过删除原数组中某些元素(可能一个也不删除)后剩余数字组成的序列,但不能改变数字间相对顺序。比方说,[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。…
周赛 – 189 – 收藏清单
又是气死我的一题TAT,我连暴力都写不对。3. 收藏清单给你一个数组 favoriteCompanies ,其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单(下标从 0 开始)。请找出不是其他任何人收藏的公司清单的子集的收藏清单,并返回该清单下标。下标需要按升序排列。样例示例 1:输入:favoriteCompanie…
Codeforces Round #647 (Div. 2) – Johnny and Contribution
今天真是不适合写题的一天,不适合打周赛也不适合补cf,我哭哭。不过确实也学到了许多,比如说我终于知道了cf是可以看测试数据的,我微笑。浪费了好久……第一个AC是我快晕倒了去网上找了份代码交了一下。E. K-periodic Garland题意给出一串01串和一个数字 $k$,一次翻转记为一次操作。使用最少的操作,使串中相邻的 $1$ 之间间隔为 $…
Codeforces Round #641 (Div. 2) – Orac and LCM
C. Orac and LCM题意给出长度为 $n$ 的数组,求 $gcd(lcm(a_i, a_j), i<j)$。思路患有质数恐惧症的我又不会做了。其实主要还是因为没有想到点子上。每一个数都可以质因数分解为 $p_1^ap_2^b \dots$ 这样的形式,我们考虑单个质因子 $p_i$ 。假设有两个数分别有因子 $p_i^{m_1}$ …