正睿Day5题解

color

我们可以把染黑看成删掉这条边，那么每次相当于是，如果存在一个点有且仅有一条出边，那么把这条边也删掉，最后要删完所有的边。
那么我们考虑一个环，可以发现这个环如果一条边都不删，那么最后一定会被留下来，因为每个点都至少有两个出边。
所以，在初始的边删完之后，图一定得要无环。我们考虑一个无环的图，可以发现他就是一个森林。考虑森林的叶子节点，可以发现每次叶子节点的父边都会被删掉，而删掉之后森林还是森林。因此，在有限步操作之后，所有的边都会被删掉，所以无环就一定合法了。
因此我们最后的答案就是，给每个联通块都保留一个生成树，其他边全都删掉。
考虑这个东西怎么算。因为一棵生成树的边数是点数减一，所有联通块的总点数是 n，所以如果设联通块数为 C，则最后剩下的边个数就是 n - C，因此答案就是$m - n + C$。
时间复杂度： $Θ(nα(n) + m)$

其实就dfs出一棵树然后统计dfs树之外有多少边没有被遍历好了……

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register

using namespace std;

int read()
{
    register int x = 0,f = 1;register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}

int n,m,x,y,ans,cnt,d[100005],du[100005],vis[100005];

struct edge{
	int to,nex,del,fro;
}e[500005];

struct node{
	int u,du;
	bool operator < (const node &x) const {return x.du < du;}
};

void add(int x,int y)
{
	e[++cnt].to = y;
	e[cnt].fro = x;
	e[cnt].nex = d[x];
	d[x] = cnt;
}

int E(int x)
{
	if(x & 1) return x + 1;
	return x - 1;
}

void dfs(int u)
{
	vis[u] = 1;
	for(int i = d[u]; i; i = e[i].nex)
	{
		if(vis[e[i].to]) continue;
		ans++;
		vis[e[i].to] = 1; dfs(e[i].to);
	}
}

int main()
{
	n = read(); m = read();
	for(int i = 1; i <= m; i++)
	{
		x = read(); y = read();
		add(x,y); add(y,x);
		du[x]++; du[y]++;
	}
	for(int i = 1; i <= n; i++) if(!vis[i]) dfs(i);
	printf("%d\n",m - ans);
    return 0;
}

power

考虑二分答案，则问题变为了求 [1, M] 内有多少个数字在至少一个 S(ni) 里面。
考虑容斥：我们考虑先计算出有多少个 [1, M] 中的数在 S(n1), S(n2), · · · , S(nk)中，然后把它们都加起来。
显然这样算多了：如果某个数字同时在多个 S(ni) 里面，那么他就重复了。于是我们考虑再去掉在至少两个 S(ni) 中的，然后加上至少三个 S(ni) 中的，去掉至少四个 S(ni) 中的……
那么我们现在相当于是需要考虑一个 {n1, n2, · · · , nk} 的子集 N，计算有多少个数字 x ∈ [1, M]，满足 ∀t ∈ N，有 x ∈ (t)。可以发现， ∪t∈NS(t) = S(lcmt∈N(t))，因此可以直接二分得到这样的 x 个数。
直接枚举 S 进行计算的时间复杂度为 Θ(q · 2k · log2 2 M)，可以通过子任务 3。
注意到我们最终的答案只与 lcmt∈N(t) 有关，因此我们可以考虑 DP：设 fi,t 表示考虑 n1, n2, · · · , ni，从中选出一个子集，满足他们的 lcm 是 t 的容斥系数之和。
注意到当 lcmt∈N(t) ≥ 60 时，一定不存在这样的 x（因为答案不超过 1017，所以M ≤ 1017）。于是在 DP 的第二个维度只保留不超过 60 的那些值即可。
时间复杂度： Θ(q(k log2 M + log3 2 M))。

bitop

3.1 按位与
我们按照从高位到低位的顺序进行贪心，如果当前位有至少两个数字是 1，那么我们可以让这一位是 1，因此最终答案的这一位一定是 1。
那么如果我们确定了某一位是 1，我们最后选择的两个数的这一位都得是 1，所以我们可以去掉所有这一位为 0 的数字，然后继续向下贪心即可。最后的方案数就是剩余的数字中选出两个的方案数。
时间复杂度： Θ(n log2 ai)。
3.2 按位异或
同样地从高到低贪心，逐位确定。但是直接确定下来某一位是 1 并不能和按位与那样减少候选范围。
考虑先确定最后选择的一个数字 ai，考虑如何求出另一个 aj 使得 ai xor aj 最大。
考虑将所有数字建出一个 trie 树，然后同样从高到低进行贪心：如果当前位可以取得和 ai 这一位不一样，那么就取不一样的，否则取一样的。方案数可以在 trie 树的每个节点上存储对应数字个数得到。
时间复杂度： Θ(n log2 ai)。
3.3 按位或
同样地在确定了一个数之后从高到低贪心。但是这里又多了一个问题：如果这个数字的当前位是 1，那么我们仍然没法减少候选范围。
那么在贪心到某一步之后，相当于是给定一个位的集合 S，判断是否一个数的这些位都是 1，其余位不管。接下来我们用 Ai 表示数字 ai 中 1 的位置集合。
考虑 DP（事实上，这个 DP 方法叫做高维前缀和）：设 fi,S 表示使得 S ⊆ At 且At \ S ⊆ {1, 2, · · · , i} 的 t 的个数。那么转移时，考虑 at 的当前位是 0 还是 1，然后可以变成 fi-1,S 以及 fi-1,S{i} 两种，直接相加即可。
那么我们就可以判断是否存在一个合法的数字了。最后的方案数同样可以使用这个 DP 数组求出。
时间复杂度： Θ(ai log2 ai)。