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