牛客小白月赛 43 题解

A 满意的数字

第 $mm$ 个因子就是 $nn$ 本身。

因此 $nn$ 能被所有因子整除。

据此，任何 $nn$ 都满足条件。

所以 $1\sim n1\backslash sim\; n$ 中满足条件的有 $nn$ 个，直接输出 $nn$ 即可。

C 木棍游戏

一看 $n\le 8n\backslash le\; 8$，直接暴力枚举 dfs 即可。

大致的思路就是把这 $nn$ 根棍子分成 $44$ 个集合，最终没有被选中的划分到第 $44$ 个集合。

D 有趣的区间

根据位运算基本知识可知，$[l,r][l,r]$ 有趣，当且仅当 $a_l\cdots a_{r}a\_l\backslash cdots\; a\_r$ 有一个是奇数。

那么显然可以考虑简单容斥一下，统计不有趣的区间个数。

那么连续一段区间全是偶数的区间个数，应该不用多说了吧：

双指针去扫描，遇到一个连续的偶数段，假设它的长度是 $lenlen$，答案就是 ${\displaystyle \frac{len(len+1)}{2}}\backslash dfrac\{len(len+1)\}\{2\}$ 呗。

F 全体集合

做这个题的那天晚上，刚好刷 QQ 看点刷到了一个叫什么奇偶的然后可以互换的点。

大致意思就是如果能找到一个环，使得奇偶能反转，整个图就是有解的。

那么这个题的话呢，首先我们对这个图是黑白染色，对于相同颜色的点，显然可以通过 u->v->u 这样的手段使得它们集合到一起。

最终原图至多剩下两个点。

另外，如果形成一个能反转的环，也就是形成一个无法黑白染色的环，就证明整个图必然有解。

否则根据是否有不同色的点判断即可。

详情见代码。

#include<cstdio>
#include<cstring>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 2e5 + 5;
int Col[N], ok = -1;
struct Node{
	int next, to;
}s[(int) 1e6 + 5]; int head[N], sLen;
void add(int u, int v){
	s[++sLen].next = head[u];
	s[sLen].to = v; head[u] = sLen;
	s[++sLen].next = head[v];
	s[sLen].to = u; head[v] = sLen;
}
void dfs(int u, int fa, int col){
	if (Col[u] != -1) {
		if (Col[u] != col) ok = 1;
		return;
	}
	else Col[u] = col;
	for (int i = head[u]; i; i = s[i].next) {
		int v = s[i].to;
		if (v == fa) continue;
		dfs(v, u, col ^ 1);
	}
}
int main(){
	int n = init(), m = init(), k = init();
    memset(Col, -1, sizeof(Col));
	for (int i = 1; i <= m; ++i)
		add(init(), init());
	dfs(1, 1, 1);
	if (ok == 1) { puts("YES"); return 0; }
	int pre = init();
	for (int i = 2; i <= k; ++i) {
		int x = init();
		if (Col[x] != Col[pre]) {
			puts("NO"); return 0;
		}
	}
	puts("YES");
}

由于本人最近实在是太忙了，因此有些简单的题目没有写代码，对实现有疑惑的同学可以看看别的题解或者牛客私信找我，如果看到的话会回。

读完题解的话点个赞再走吧 $\sim \backslash sim$