Description 给出一个出入栈顺序和一堆数字，构造一个序列满足任意时刻入栈时序列都是唯一的。 Solution Code https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48581485

Description 给出一棵树， 个查询，每次查询给出 代表病毒在 点爆发，在 的温度可以传播根节点为 ，保证离根节点越近，温度越高，根节点温度最高。 Solution 我们知道，对于一个初始节点，它的子树必定温度小于它本身，所以设当前温度为 , 中 的这一部分可以直接查询子树里有多少符合的，但是 的在祖先上，无法解决。显然保证离根节点越近，温度越高，根节点温度最高。对于解决问题具有重大的意义，这说明我们可以树上倍增跳到最高可行的祖先（满足 ），然后直接用划分树查询子树，查询子树需要懂得如何将子树关系用 序转换成区间。树上倍增的做法模仿了倍增求LCA，划分树是复制 的模板，...

Description 给两棵树，选取一系列编号的节点，需要满足 在树1中节点联通，且互为祖先关系 在树2中节点互不为祖先关系 Solution 看了题解，不会他讲的主席树做法，还是感觉树上滑窗的思路好理解。但是很多人说树上滑窗可能会被卡，不是很懂。。。不过仔细一想，如果树上滑窗能被卡，这题应该没那么多人过，可能就被我定义为不可补的题了( 依据题意，在树1中显然是选取一条连续的链，对于树2，可以跑一个 序得到子树的 ，那么可以把子树问题转换成区间相交问题，用线段树来维护。如果加入当前这个点，就等价于加入一个区间。那么就在线段树上区间加 ，如果要查询是否有重合，只需要查询区间最大值，如果大...

Description 数据结构 区间减去 区间加上 区间求和 Solution 难度比较适中的一道题，注意到操作1最多减去 次， 个数字需要的操作次数数量级为，考虑用线段树维护区间，可以 完成操作1，最终用一个 代表这个区别是不是全为 ，因为 就不需要再操作了。对于操作2，每次只是对最高位进行修改，不妨将最高位和其他位分离开来维护，操作2就是对最高位做一次乘以2的操作，可以单点修改完成。 Code /* * @Author: Kurisu */ #include<bits/stdc++.h> const int N = 1e5 + 5; const int ...

Description 一只兔子在草原上跳来跳去,草原上有猎人布下的n个陷阱.现在将草原看作一个二维直角坐标系,兔子看作一个点,陷阱看作一个矩阵(且它的边必定与x轴或y轴平行),兔子每次会沿x轴或y轴方向移动距离d(即如果兔子在,它跳一次后在四个点中的一个.问在坐标系中是否存在一个点,使兔子无论怎么跳都不会掉进陷阱. Solution 扫描线裸题，由于兔子的运动具有周期性，只能在 上，不妨把所有矩形都平移到 的平面上，然后利用扫描线对每个 进行扫描，如果存在一个 ，在这一行中有点没有被覆盖，那么就可以选取这个点。以下图来自官方题解，如图所示：注意到有一些矩形可能很大，或者可能在平移的时候...

Description 给出一个随机生成器，每次生成 ，当且仅当生成的 为不小于前面生成的所有值才能继续生成，否则结束。求生成数字的个数平方的期望值。 Solution Code https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48457126

1. 165E - Compatible Numbers Compatible Numbers 由于 , 那么显然找 的子集必然满足条件。不妨令 表示 的子集里存在于所给序列中的某一个，枚举子集即可。 /* * @Author: Kurisu */ #include<bits/stdc++.h> const int mod = 1e9 + 7; const int N = (1 << 23) + 5; int a[N], dp[N]; void solve() { int n; std::cin >> n; int bits =...

Description 打捞 个货物，货物会动，每一个时刻只能打捞一个，货物会动，打捞的代价是三维空间上的距离平方。 Solution 个货物只需要 时刻就能全部打捞，对于每个货物在每一个时刻都有相应的代价，可以构建二分图，左边是时刻，右边是货物，做带权二分图的最优匹配（KM算法）即可。 听说网上假的 KM 板子假的满天飞，于是偷了 roundgod giagia 的板子封装一下，以后我也有KM板子啦！时间复杂度 Code https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48398426

谨以本文纪念我两小时的青春，如有错误请指出~ Description 个汉堡， 个锅，汉堡制作耗时 ，允许拆分时间，由 制作得到。 Solution 首先思考最终需要多少时间? 思维误区：Max足够大时，需要 时间 1 2 100 ans: 100 //虽然有两个锅，但是不能拆成[0, 50] 和 [0, 50]，因为一个汉堡不能同时在两个锅上制作正确的所需时间为 构造方案 按时间排序，从大往小构造，对于当前段，能塞进去就塞进去，不能塞进去的话就把后半部分塞进去，最后记得排序即可。 正确性证明 假设现在有两端长度分别为，满足 ，如果 能够放到 里面，且放 时会超出 ，可以将 ...

Description 难以描述，看图： Solution 简单的来说就是 在 区间里找一个公共子序列 在 这个点 后面的可以任意取。 方案统计 对于公共子序列部分，显然对于公共子序列可以做一次 统计方案数, 令 表示 串遍历到 ， 串遍历到 时有多少个公共子序列，类似于最长公共子序列那样去做就行了。对于后面部分可以 任意取，假设当前 串剩下 个字母可以取， 串剩下 个字母可以取，显然方案数是 。对于上式(1)有结论 结论证明(摘自百度)： 等式右边等价于：从 个不同的球中任意取出 个球，一共有的方法数。等式左边 等价于：把个不同的球分成两块，从 个球中选出 个球...

Description 给出一棵树，权值未知，但是给出每条边两个端点权值的异或值，求原来的权值。 Solution 假设权值 ，那么从它开始进行一遍 赋值可以得到所有点当前的权值 。当然 不一定等于 ，假设 ，那么真实的 。 现在给出每个 的范围满足 ，即 ，设 ，等式两边异或上 得到 ，于是 满足 。 于是现在转化成考虑以下问题： 给出 个限制条件，求出它们之间的交集。(转换成求被覆盖 次的线段长度) 对于每个能够取到符合条件的数字。我们可以用线段差分表示，例如 区间如果满足某个限制条件，那么标记 ,, 这样在遍历 区间的时候得到的权值都是 ，到了 这个点就变成...

D.哥三好 Solution 容易想到用 三维 加记忆化搜索得到答案，但是 ，不能开这么大的数组，考虑如何压缩数据。注意到每次花费分别为 ，不难证明对花费和金额同时做乘法除法后与原问题等价，先分别乘2，此时花费为 ，金额，再同时除以100，花费变为 ，此时金额为 。金额均满足 ，做朴素的记忆化搜索即可。 Code #include<bits/stdc++.h> const int mod = 1e9 + 7; const int N = 1e5 + 5; long long dp[205][205][205]; int table[3] = {6, 9, 15}; long...

Description 有一个排列 , 令 表示 中满足 的 的个数，现在给出 个不重复的 和 ，问能否构造一个 排列 符合条件。 Solution (这个做法感觉比拓扑排序好理解)显然对于每一个 ，必须满足 ，那么对于未给出数值的 ，可以考虑先给它们填充上数值，不妨令 ，这样构造能够满足的条件，随后只需要从后往前构造即可。从后往前构造时，假如当前 ，那么最理想的情况下是 ，但是可能在前面的构造里已经填充了 等值，所以需要用一个树状数组维护前面已经用的值，再二分找到符合条件的最小数值填到当前位置。例如 ，前面已经用了 ，那么 ，构造出来的样子就是 。 Code #include&...

Description 给出一个有向图，提供两种操作： 将当前点加入到最短路规划中 计算当前点到 的距离 Solution 数据范围满足 ，操作1最多只会执行 次，考虑每次都使用 进行 的任意两点最短路径计算，总体时间复杂度 ，那么对于操作2，每次只需要 判断并输出答案即可。注意到 的遍历特点： for k in [1, n]: for i in [1, n]: for j in [1, n]: Graph[i][j] = min(Graph[i][j], Graph[i][k] + Graph[k][j] 最外层的 作为中转点...