本文共 850 字,大约阅读时间需要 2 分钟。
昨晚打了一场CF,战绩不太好,只写了ABCFG,赛后更正了E
在这里写一下题解二分答案,直接判断
直接模拟即可
考虑到连续一段1里面事可以互换的,暴力扫一次即可
没做
题意:给你一个完全图,删去若干跳变,询问有多少个联通块
思路比较好的一道题,考试的时候没有想出来 对于每一个点,扫所有点,如果它们之间有边,就合并成一个联通快 扫的时候就扫没有合并的点 考虑到每一次合并,点数会少1,所以这个过程是O(n)的 然后再考虑点数不会边的情况,就是有边,这个过程是O(m)的 于是总体复杂度是O(n+m)的 CODE:#include#include #include #include #include #include using namespace std;const int N=200005;int n,m;vector e[N];int f[N];//并查集bool vis[N];int cnt;vector ans[N];int find (int x){ return f[x]==x?x:f[x]=find(f[x]);}void dfs (int x){ /*printf("%d\n",x); system("pause");*/ vis[x]=true; ans[cnt].push_back(x); f[x]=x+1; int i=0; for (int u=find(1);u<=n;u=find(u+1)) { while (i
这题的话,先线性筛出所有数的约数个数
然后考虑到,一个数n的约数个数是不超过 n−−√ n 的 所以修改的次数不会很多,就5,6次左右 变到2,1就不会变了 再线段树上打标记即可先分解质因数
二分答案,然后容斥得到个数就可以了转载地址:http://ppcq.baihongyu.com/