2021“MINIEYE杯”中国大学生算法设计超级联赛（7） AC代码 温暖人心签到场。 1003 Fall with Trees 容易发现是一系列的等腰梯形，并且底边的增长是等差数列，推个公式求解。 1004 Link with Balls 场上通过打表直接找到了规律。 1005 Link with EQ 先用dp推出式子，然后可以 $n^2$ …

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\times M$ 网格图上，两只乌龟分别从 $(0,0)$ 点爬到 $(N-1,M-1)$ 点，询问路径不相交的方案数。 $N,M\leq 3000$ 。 首先问题可以转化为：两个人分别从 $A_0(0,1)$ 和 $B_0(1,0)$ 点出发，分别走到 $A_1(N-2,M…

AC代码 C. Cells 给定大小为 $N$ 的数组 $A$ ，询问 $N$ 个人分别从点 $(0,A_i)$ 出发前往 $(i,0)$ 且路径不相交的方案数。 $N\leq 5\times 10^5, A_i\leq 10^6$ 。 光从题面考虑，这就是LGV引理的模板题，但是求行列式的复杂度高达 $N^2(N+\log MOD)$ ，因此难以…

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 已知：$s_2>s_1,n_2>n_1,u_2>u_1,k_2>k_1,e_2>e_1$ 且均为非负整数，计算： \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$ 范围大，无法直接模拟。考虑到…