unity中c#实现常见3D ACT 游戏主角镜头控制 首先需要明确这个镜头需要完成的工作(我实现的这个摄像机镜头逻辑是参考鸣潮在游戏中的表现实现的):
1.可以根据鼠标的左右上下滚动滚动视野,随鼠标滚轮缩放视野
2.防止出现摄像机穿模,摄像机不可以位于地面地下,同时摄像机不可以位于障碍中
同时需要实现配合相机的主角的基本移动方式,通常wasd代表前左下右的移动,这个方向是相对于摄像机器,所以通过RigidBody控制主角速度时速度方向的计算要结合摄像机。
我们还可以加入act常见的隐藏光标来优化游戏的表现，本脚本默认隐藏鼠标的光标，按ctrl会呼出鼠标的光标。
实现思路基本功能 首先是基础逻辑部分，相机的缩放和视野球状滚动，我们需要下面的基础数据。
12345678910111213141516[Header("目标与基础设置")]public Transform target; //主角的transformpublic Vector3 offset = new Vector3(0, 2, -5); //初始相对偏移public L ...
D2. Diadrash (Hard Version)题目翻译 这是一道交互题，题目中有一个隐藏的排列，我们得到了q组询问，每组询问[l, r]，我们需要求出所有询问中MEX[l, r]最大的是多少，我们可以进行提问 ? l r，交互其会返回区间[l, r]的MEX。我们需要在30次询问内找出答案。排列长度n <= 1e4, 询问q <= 3e5。
思路 首先本题根据MEX的性质，我们不难发现所有被完全包含的区间都没有意义，所以我们对区间进行区去包含的处理，此时最多只会剩下n个区间询问。我们要解决hard版的30次询问还需要注意到MEX的另外一个重要性质，对于MEX[l, r] = min(MEX[1, r], MEX[l, n])，这个性质的证明考虑第一个不在MEX[l, r]中的数位于其左侧或右侧就可以简单证明得到。
我们对去重后的区间按左端点进行排序，我们可以对这些区间进行二分，因为去了包含之后的区间一定满足l[i] < l[i + 1], r[i] < r[i + 1]。对于我们当前验证的区间media，若其为[l, ...
F. Anti-Theft Road Planning题目翻译 题目给我们一个n * n的矩阵，矩阵中的每个格子都是四联通的，有个小偷初始位于（0，0）要在这个矩阵中偷盗，我们有报警器，小偷每次经过报警器的数值都会异或上小偷经过的路径的长度，报警器的初始数值为0。当小偷进行盗窃时报警器会告诉我们数值并且将报警器数值重置为0，我们需要根据这个数值输出小偷具体的坐标。我们需要构造每个格子之间的距离，输出构造方案并完成交互，格子距离的和不可以超过48000。
思路 首先我们意识到我们要根据报警器确定小偷经过任何路径走到[x, y]的坐标，意味着从[0, 0]走到[x, y]的所有路径的边权异或和都是相同的，我们可以给每个坐标赋一个边权异或和的值，然后根据这个值我们就可以反推出所有的路径长度。我们首先想到可以令值为0到n * n，但是构造之后我们发现此时的边权和到达了1e5的级别，超出了限制。
我们注意到两个坐标的权值之间我们应该让其具备尽可能多的相同的位，这样我们就可以最小化边权的和。如果是一维的坐标问题，那么显然格雷码就是答案，其保证了每个元素不同且相邻两个元素之间只有1个位不相同 ...
F. Mice and Holes题目翻译 题目给我们n只老鼠在一个水平线上的坐标，这个水平线上还有m个洞，我们需要让每个老鼠都会到一个洞中，每个洞都有一个水平线上的坐标和容量，我们需要输出让所有老鼠到达洞的最小总移动距离，如果不可能让所有老鼠都到洞中则输出-1。
思路 首先本题我们容易发现我们将洞和老鼠都排个序按坐标从小到大来考虑比较简单，我们容易得到一个O（n ^ 3)的dp解法，我们可以定义dp[i] [j] [k]表示考虑到第i支老鼠第j个洞，第j个洞进了k只老鼠的最小代价。根据贪心策略我们容易证明坐标小的老鼠进的洞一定小于等于坐标大的老鼠进的洞的坐标。但是O(n ^ 3)的时间复杂度我们无法接受。
并且这个状态设计并不好优化，考虑转换状态，定义dp[i] [j]表示考虑到第i个洞进入了j只老鼠的最小代价。这个dp[i] [j] = Min(dp[i - 1] [j - k] + pre[i] [j] - pre[i] [j - k]) ，pre[i] [j]表示前j只老鼠进入第i个洞的代价。容易发现这个dp的j - k可以拎出来进行优化，于是每个转移实际上 ...
E. Maximum Monogonosity题目翻译 题目给我们两个长度为n的数组a和数组b，我们需要从1到n中挑选一些区间[L1, R1], [L2, R2]…满足这些区间没有相交，同时直接区间的贡献最大，定义每个区间[l, r]的贡献是std::abs(a[l] - b[r]) + std::abs(b[l] - a[r])。
思路 首先我们容易思考到一个O（n * k * k)的暴力dp，我们可以定义dp[i] [j]表示考虑了前i个数，线段总长度为j的最大贡献，转移时O（k）的向前枚举即可。但这样的时间复杂度无法接受，考虑是否能够优化这个dp，绝对值不是很好处理，我们可以先把绝对值拆开，实际上只有a[l] - b[r] + b[l] - a[r], b[r] - a[l] + b[l] - a[r], a[l] - b[r] + a[r] - b[l], b[r] - a[l] + a[r] - b[l]，这四种方式的转移，因为绝对值的性质，我们取其中最大的转移方式即可。
注意到此时我们暴力dp的状态转移方程从dp[i] [j] = dp[i - k] [j ...
E. Labeling the Tree with Distances题目翻译 题目给我们一个n个节点的树，还有n - 1个标签，我们还可以自由挑选一个任意数值的标签，当以某个节点为根时，树中每个节点的到根节点的距离能与n个标签一一对应，那么我们就称这个作为根节点的点为好点。我们需要求出所有的好点并按照升序输出。
思路 首先我们可以想到对于某个节点为根的树维护所有节点到他的距离可以考虑换根dp，但是此时我们还是无法很好的考虑距离为x的节点的数量，并且我们无法快速的对n个标签，其中还有一个不确定的标签进行快速判断是否符合要求。
我们重新思考我们的需求，我们需要判断一个数组每个元素的值的出现次数是否相同，我们发现这类似于字符串的一个个判断，考虑对这个数组进行类似进制哈希的做法，列入cnt0 * base0 + cnt1 * base1 + cnt2 * base2，这样的进制哈希我们也是可以换根dp来维护某个节点为根时所有到它距离的距离cnt的哈希数值的。同时我们注意到对于未确定的那个标签实际上只有n种可能，因为树的深度不超过n，所以我们可以每个都尝试一下，处理出哈希放到set里即 ...
E. XOR Matrix题目翻译 题目给我们n，m，A，B。我们需要确认有多少种不同的数组(a, b)对是好的，a，b均是数组，a中的元素在0到A之间，b中的元素在0到B之间。数组中a中的任意元素异或上b中的任意元素得到的结果最多只能有2种。输出多少种，在模998244353的意义下。
思路 首先我们发现可以分开来考虑相同结果为1种和相同结果为2种的情况，对于结果只有一种的数，一定是数组a中为i，数组b中为j，共两种不同的数。对于相同的结果为2的情况一定是数组a为i，数组b为j，k，或者反过来。结果为2还有可能是（i，j）for a， （k， l） for b，此时还要满足i ^ j ^ k ^ l == 0,我们发现只有最后一种情况我们比较难以完成计数，其余的情况我们都可以通过组合数学的公式快速推到出来。
考虑如何计算四个数字i，j，k，l满足异或和为0，且i != j 并且k != l,同时i，j属于[0, A] ，k，l属于[0, B]。我们发现我们可以拆成一位一位的看，每位中为1的位的个数一定要是偶数，这样的话我们可以使用类似数 ...
算法竞赛题解
未读G. Gangsta题目翻译 题目给我们一个长度为n的二进制字符串s，我们要计算s所有子数组中函数f值，f（s）的值是二进制字符串中最多的相同字符的个数。
思路 我们考虑如何暴力的做这道题目，定义状态dp[i][j]表示以i为结尾1的个数减去0的个数等于j的子段的数量，ans[i]表示以i为结尾的所有子段做的贡献。我们考虑拓展到i + 1,首先ans[i]的贡献在i + 1时一定会产生，然后考虑新增的贡献，假设此时s[i] == ‘1’，那么原先dp[i][j]中j >= 0的都会新增贡献，s[i] == ‘0’时也是同理。但是这个dp暴力维护的时间复杂度是O（n ^ 2)的。
考虑如何优雅的维护，我们发现遇到1时，实际上原先1的个数减去0的个数为-1的子段变成了为0的子段，我们可以标记一个offset来表示实际上此时为子段中1的个数减去0的个数的位置，我们注意到每次offset只会变动1个位置，我们可以O（1)的维护出大于它的（也就是上面dp中j >= 0）的个数，可以快速算出此时新增的贡献,注意别忘了还 ...
G. Cook and Porridge题目翻译 题目给我们n个排着队的学生，每个学生都有一个优先级和吃饭时间，初始时按照1到n排序，每一秒在最前面的学生可以得到吃的，然后他会花费s[i]的吃饭时间吃饭，记录当前时间为x，则他会在x + s[i]的时刻结束时回来排队，此时对尾所有优先即严格低于他的学生都会被他插队，直到遇到优先级大于等于他的。我们需要计算1到d秒内所有学生都吃过一回饭的最小时刻，或者报告不可能。
思路 注意到d的数据范围很小，同时每个时刻只有一个学生会吃饭，所以归队的学生也最多d个，考虑模拟这个过程。我们发现因为初始状态的优先级不是单调的我们很难处理，但是我们可以注意到每次插入后当前元素所在的那个小块一定是优先级别大到小的递减的。所以我们考虑维护初始状态的后缀最大值，我们每次学生归队时通过二分找出他会被拦截在哪个块的后面，然后在这个块的后面插入，此时每个块中的元素都是优先级单调的，我们可以直接使用set维护即可，每一块中优先级大的靠钱，相同则比较插入时间，插入时间小的考前。我们在开一个set维护哪几个块中有元素即可取出队首的元素。记录每个学生是否吃过饭，全吃过记录答 ...
E2. Rollbacks (Hard Version)题目翻译 初始有一个空的数组，我们需要对它进行q次操作，我们可以执行4种操作，操作+，添加一个元素x到数组后面。操作-，移除数组末尾的k个数字，操作！，撤回上一个操作，只会撤回+，-。操作？，输出数组种不同种类的数的个数。保证操作合法，hard版本要求强制在线。
思路 首先本题我们看见其回退操作自然考虑使用可持久化的数据结构进行维护，考虑可持久化线段树，发现我们可以维护一个权值线段树表示每个值得元素是否有贡献，添加操作实际上就是新版本新建一个单点处理，减去操作实际上就是创建一个当前版本的k级祖先的镜像版本，回退操作实际上就是直接删去一个版本即可。考虑如何快速回调k级版本的祖先，我们可以维护倍增，记录每个版本的父亲版本倍增状态。但这样写完之后我们发现会MLE，经过计算我们发现我们最多只有1.4e7的空间给可持久化线段树，这是不够的，考虑优化，我们只用标记某个值是否做了贡献，所以我们可以进行状态压缩，把所有长度为32的区间压缩到一个int里，这样我们线段树的值域范围可以/32，这样我们需要1.6e7的空间。我们发现还是不 ...
