2020.09.26【NOIP提高组】模拟
A. 旅游设连通块的大小为 $sz_i$，要求计算 $\sum sz_i(sz_i-1)$。离线，排序，并查集维护。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> ...
A. 旅游设连通块的大小为 $sz_i$，要求计算 $\sum sz_i(sz_i-1)$。离线，排序，并查集维护。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> ...
A手玩一下样例，我们从大到小确定每个数：将确定的数挪到序列的最前面，设确定了 $x$ 个数，那么 $x \times x$ 的方格的数都没用了，并且剩下的是一个 L 形方格。剩下的 L 形方格内对角线一定是最大值，所以我们只需要每次取最大值，将这个数和已经确定的数的 $\gcd$ 删掉即可。注意要删两次。B可以猜测一下选择方案一定是前面可能有某些增加值的地方，后面值就一直不变了。所以我们先一...
上午打比赛的时候感冒了十分难受。。于是发挥非常差。A如果偶数层也是确定的话直接让 $a_i = h_i-h_{f_i}$ 就好了。否则我们考虑偶数层是干什么的：它可以让它所有儿子统一减少一个数。于是对于每个点统计出儿子节点的最小值，将这个点赋成最小值即可。B考虑如果确定了左上角 $2 \times 2$ 的矩阵，那么前两行剩下的格子的每一列的字符集就确定了，贪心分配一下。然后剩下的行每个 $...
A设点 $i$ 有 $a_i$ 个糖果。对于每个起点 $s$ ，只需要能计算出对于每个点 $t$，完成所有任务所需要的最短时间，取 max 即可。而计算这个时间相当于是先转几圈，然后找一个距离它最近的当做最后一次的任务。可以加强到 $10^5$，观察一下 $s \to s+1$ 的变化即可。B这个程序相当于每次取这个点最前面的保证和是非负的一段区间。所以想让它掉进坑一定是前面一堆 $0$，然...
A两人策略不会互相造成影响，最优策略是每个人每次拿一个。判断是否 $n_1 \leq n_2$ 即可。B先考虑如何计算一个排列的 $f$：设一个位置左边和右边第一个比他小的位置为 $ls_i,rs_i$，答案就是 $\sum_{i=1}^n a_i(rs_i-ls_i-1)$。另一种思考思路是从小往大放，每次相当于将选出的位置分成左右两个连通块，每次得到的贡献是它所在的连通块跨过它的区间个数...