搜索结果
查询Tags标签： 2019.7，共有 12条记录-
2019.7.18 义乌模拟赛 T3 占领
首先第一问的树形换根dp是很显然的。 首先一次dp算出一个点子树内的答案，然后再一次换根把儿子什么的排个序就好了。 考虑第二个怎么做。 我们考虑\(a\)到\(b\)之间的路径，这中间肯定有一条边是不被走到的，然后感性理解一下这个东西具有可二分性。 就是大概要找到一个两…
2021/7/20 6:05:45 人评论 次浏览 -
2019.7.18 义乌模拟赛 T3 占领
首先第一问的树形换根dp是很显然的。 首先一次dp算出一个点子树内的答案，然后再一次换根把儿子什么的排个序就好了。 考虑第二个怎么做。 我们考虑\(a\)到\(b\)之间的路径，这中间肯定有一条边是不被走到的，然后感性理解一下这个东西具有可二分性。 就是大概要找到一个两…
2021/7/20 6:05:45 人评论 次浏览 -
2019.7.16 义乌模拟赛 T4 老鼠进洞
很妙的一道题。 首先我们考虑将所有老鼠都进左边能进的且最优的洞。 然后有些老鼠其实是可以反悔的去选右边的洞，如果设第\(i\)只老鼠原来连\(j\)，反悔去连\(k\)，那么对答案的贡献就是\(p_k-2x_i+p_j\) 可以发现这个东西对\(k\)独立，那么我们用一个堆维护即可。 但是一…
2021/7/17 6:35:16 人评论 次浏览 -
2019.7.16 义乌模拟赛 T4 老鼠进洞
很妙的一道题。 首先我们考虑将所有老鼠都进左边能进的且最优的洞。 然后有些老鼠其实是可以反悔的去选右边的洞，如果设第\(i\)只老鼠原来连\(j\)，反悔去连\(k\)，那么对答案的贡献就是\(p_k-2x_i+p_j\) 可以发现这个东西对\(k\)独立，那么我们用一个堆维护即可。 但是一…
2021/7/17 6:35:16 人评论 次浏览 -
2019.7.16 义乌模拟赛 T3 白兔的子序列
卡常题差评。 首先这个东西我们可以枚举中间那个然后扫描线，那么就变成右边不超过某个值的对左边的逆序对个数这个东西可以直接线段树\(O(nlogn)\)搞。 但是这样常数大的和*一样，我们考虑换一种方法。 我们枚举第一个点，那么其实后面的方案数就是大于第一个点随意排列的…
2021/7/17 6:35:07 人评论 次浏览 -
2019.7.16 义乌模拟赛 T3 白兔的子序列
卡常题差评。 首先这个东西我们可以枚举中间那个然后扫描线，那么就变成右边不超过某个值的对左边的逆序对个数这个东西可以直接线段树\(O(nlogn)\)搞。 但是这样常数大的和*一样，我们考虑换一种方法。 我们枚举第一个点，那么其实后面的方案数就是大于第一个点随意排列的…
2021/7/17 6:35:07 人评论 次浏览 -
2019.7.9 义乌模拟赛 T2 B
首先根据四色定理这个颜色肯定不超过\(4\) 然后题目中给了\(7\)的样例是4，然后手推一下\(1\)到\(6\)即可。 然后考虑\(4\)怎么构造。 容易发现除了\(2\)其它都是奇数。 然后我们对这个东西奇偶染色容易发现上下只要颜色不同即可。 所以上面\(12\)下面\(34\)就好了。 code…
2021/7/9 23:20:39 人评论 次浏览 -
2019.7.9 义乌模拟赛 T2 B
首先根据四色定理这个颜色肯定不超过\(4\) 然后题目中给了\(7\)的样例是4，然后手推一下\(1\)到\(6\)即可。 然后考虑\(4\)怎么构造。 容易发现除了\(2\)其它都是奇数。 然后我们对这个东西奇偶染色容易发现上下只要颜色不同即可。 所以上面\(12\)下面\(34\)就好了。 code…
2021/7/9 23:20:39 人评论 次浏览 -
2019.7.9 义乌模拟赛 T4 D
我真是tcl居然没有调出来。 首先套路地拆成上行和下行两端。 先考虑上行，对于一个点\(u\)如果满足条件那么它一定满足\(d_l-d_{u}=u\) 移项得到\(d_l=d_u+u\) 这不是链上数一个数的个数吗，dfs的时候差分询问开桶记录即可。 然后下行也是一样的。 总的时间复杂度\(O(mlog…
2021/7/9 23:17:44 人评论 次浏览 -
2019.7.9 义乌模拟赛 T4 D
我真是tcl居然没有调出来。 首先套路地拆成上行和下行两端。 先考虑上行，对于一个点\(u\)如果满足条件那么它一定满足\(d_l-d_{u}=u\) 移项得到\(d_l=d_u+u\) 这不是链上数一个数的个数吗，dfs的时候差分询问开桶记录即可。 然后下行也是一样的。 总的时间复杂度\(O(mlog…
2021/7/9 23:17:44 人评论 次浏览 -
2019.7.8 义乌模拟赛 T2 B
我们发现每个值的贡献其实是独立的。 所以这启发我们对于每个值单独计算。 题目中真正有意义的合并只有\(O(n)\)次，每次暴力归并所以是\(O(n^2+m)\)的。 但是这个显然不够优。 我们考虑启发式合并。 这样再用个set维护就可以了。时间复杂度\(O(nlog^2n)\) 用线段树合并可…
2021/7/9 6:35:49 人评论 次浏览 -
2019.7.8 义乌模拟赛 T3 C
为什么我的\(O(n)\)做法比\(O(nloglogn)\)做法跑得还慢啊！ 首先S1的长度为\(i\)的子串有\(n-i+1\)个。 然后全部长度为\(i\)的子串有\(2^i\)个。 \(i\)成为答案长度的一个充分条件为\(2^i>n-i+1\) 带个\(i=log(n+1)\)进去发现成立。这启发我们将长度小于\(i\)的全部打…
2021/7/9 6:35:42 人评论 次浏览
