2021“MINIEYE杯”中国大学生算法设计超级联赛(7)
2021 “MINIEYE 杯” 中国大学生算法设计超级联赛(7) AC 代码 温暖人心签到场。 1003 Fall with Trees 容易发现是一系列的等腰梯形,并且底边的增长是等差数列,推个公式求解。 1004 Link with Balls 场上通过打表直接找到了规律。 1005 Link with EQ 先用 dp 推出式子,然后可以 n2
2021“MINIEYE杯”中国大学生算法设计超级联赛(5)
2021 “MINIEYE 杯” 中国大学生算法设计超级联赛(5) 很辣鸡的一场比赛,题面谜语恶心人。 AC 代码 1003 VC Is All You Need 求多维空间中一个高维平面所能分割不共面的点的最大数量。 可以推出 k 维所能容纳的最大数量为 k+1 。 1006 Cute Tree 直接模拟题目中的三叉树,求出节点数量。 1007 …
2021牛客暑期多校训练营6
2021 牛客暑期多校训练营 6 AC 代码 C. Delete Edges 构造题,要求在点数为 n 的完全图上选出三角形,使得剩余边数小于 n 。在比赛过程用想出了一种构造方法,但在几种特殊取值的情况下会发生错误。赛后在结合相关的构造论文,找到了最大匹配数的解法。 D. Gambling Monster FWT 与分治结合题。在比赛时求出了题目…
2021“MINIEYE杯”中国大学生算法设计超级联赛(8)
2021 “MINIEYE 杯” 中国大学生算法设计超级联赛(8) AC 代码 1002 Buying Snacks 1003 Ink on paper 二分最短距离,然后用并查集暴力维护联通性。有亿点卡常。 1004 Counting Stars 考虑到两种操作分别为将该数最高位左移一位和删除最低位的 1,询问与修改都是区间操作,很容易想到需要使用线段树维…
LGV引理
问题引入 问题来源:CF348D Turtles。 一个有障碍物的 N×M 网格图上,两只乌龟分别从 (0,0) 点爬到 (N1,M1) 点,询问路径不相交的方案数。 N,M3000 。 首先问题可以转化为:两个人分别从 A0(0,1)B0(1,0) 点出发,分别走到 $A_1 (N-2,M…
2021牛客暑期多校训练营9
AC 代码 C. Cells 给定大小为 N 的数组 A ,询问 N 个人分别从点 (0,Ai) 出发前往 (i,0) 且路径不相交的方案数。 N5×105,Ai106 。 光从题面考虑,这就是 LGV 引理的模板题,但是求行列式的复杂度高达 N2(N+logMOD) ,因此难以…
2021牛客暑期多校训练营5
2021 牛客暑期多校训练营 5 AC 代码 B. Boxes 箱子中有黑或白的球,开箱需要花费,也可以花费一定代价询问剩余箱子中黑白球的数量,求解要知道所有球颜色的代价的期望。首先考虑把所有箱子打开的代价,其次考虑一开始进行询问后代价花费的期望。通过找规律可以得到询问后每个箱子需要打开的几率,然后取两种方式较小值的答案。 C. Cheating and…
2021“MINIEYE杯”中国大学生算法设计超级联赛(4)
2021 “MINIEYE 杯” 中国大学生算法设计超级联赛(4) AC 代码 1001 Calculus 给定一个函数求函数极限是否存在,如果所有系数均为 0 极限存在,否则不存在。 1002 Kanade Loves Maze Designing 给定一棵树,需要求出任意两点直接不同元素的数量。直接进行 n 次 dfs 即可。 1004 Display S…
2021暑期训练dp优化题解
2021 暑假训练 dp 优化题解 AC Codes A - GTY's birthday gift 矩阵优化 dp 给出序列 a ,每次从序列选两个数相加后,将新数加入序列 a 问操作 k 次后序列的和最大为多少 序列和最大,每次选当前最大和次大相加, dp[i]=d[i1]+dp[i2] ,由于 k 范围大,无法直接模拟。考虑到…