qbxt 10 月模拟赛 Day4
A二分答案 $x$，加入所有 $\leq x$ 的边后判断图是否强连通即可。一种方法是判联通性+tarjan，但是可以建正向图和反向图分别从 $1$ 开始 dfs 。（这样说明 $1$ 和任何点都有两条路径，所以任意两点都有两条路径）有向图 tarjan 不要判 father，，一开始因为这个吃了罚时。#include <bits/stdc++.h> #define fi fi...
A二分答案 $x$，加入所有 $\leq x$ 的边后判断图是否强连通即可。一种方法是判联通性+tarjan，但是可以建正向图和反向图分别从 $1$ 开始 dfs 。（这样说明 $1$ 和任何点都有两条路径，所以任意两点都有两条路径）有向图 tarjan 不要判 father，，一开始因为这个吃了罚时。#include <bits/stdc++.h> #define fi fi...
A取 $\ln$，每次只需要判断 $\sum_{i=1}^k \ln(i) \geq \sum_{i=k+1}^n \ln(i)$ 即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<i...
总算是正常的普及组模拟赛难度了。。昨天的甚至算不上普及组模拟赛难度吧（A二分答案，我们肯定是贪心等到必须要选取某个点的时候再选取。可以每次二分判断，也可以开个指针维护中位数在哪里来判断。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned ...
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$ 的子问题）黑妞...