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手玩，发现 $n =2$ 很特殊：因为谁先手谁就能赢。读入这么大，肯定之和数的性质有关，由于这是 NOIP 模拟赛，猜一发奇偶性。当 $n$ 为偶数时：黑妞必胜。（等价于有最大的牌的人必胜）黑妞后手时：先手出 $i$ 他跟 $i+1$，一直到对手只剩一张牌的时候出最大的牌，然后就可以跑了。（即使中间用了最大的牌也没关系：因为这样等价于化为了 $n-2$ 的子问题）黑妞...
A手玩一下样例，我们从大到小确定每个数：将确定的数挪到序列的最前面，设确定了 $x$ 个数，那么 $x \times x$ 的方格的数都没用了，并且剩下的是一个 L 形方格。剩下的 L 形方格内对角线一定是最大值，所以我们只需要每次取最大值，将这个数和已经确定的数的 $\gcd$ 删掉即可。注意要删两次。B可以猜测一下选择方案一定是前面可能有某些增加值的地方，后面值就一直不变了。所以我们先一...
A两人策略不会互相造成影响，最优策略是每个人每次拿一个。判断是否 $n_1 \leq n_2$ 即可。B先考虑如何计算一个排列的 $f$：设一个位置左边和右边第一个比他小的位置为 $ls_i,rs_i$，答案就是 $\sum_{i=1}^n a_i(rs_i-ls_i-1)$。另一种思考思路是从小往大放，每次相当于将选出的位置分成左右两个连通块，每次得到的贡献是它所在的连通块跨过它的区间个数...
A如果满足条件可以注意到一定有 $a_i = a_{i+k} = a_{i+2k} = \ldots$，所以先判断这个，然后只需要判断 $[1 \ldots k]$ 能否被填成平衡的串即可。B如果先手一步能抓住后手，那么先手必胜。如果 $db \leq 2da$，那么一定存在一个时间后手被先手逼到角落里但是后手无法通过向先手的范围跳跃而跳出攻击范围。那么按照后手的意愿，先后手最后的稳定状态一...