牛客周赛 Round 77

题目链接：牛客周赛 Round 77

A. 时间表

tag：签到

B. 数独数组

tag：签到

Description：给定n个数，每个数的范围为1-9，问能否经过排列，使其每个长度为9的连续子数组都包含1-9这9个数字。

Solution：手模发现，前面一定是每个数字都出现，且次数相同，最后后面再放一些数字只出现一次。 故只要判断数字的最少次数和最多次数差距不大于1即可。

C. 小红走网格

tag：gcd

Solution：上下和左右是独立的，根据裴蜀定理ax + by | gcd(a, b)。

void solve(){int x, y, a, b, c, d;cin >> x >> y >> a >> b >> c >> d;int t1 = gcd(a, b), t2 = gcd(c, d);if (y % t1 == 0 && x % t2 == 0){cout << "YES\n";}else{cout << "NO\n";}
}

D. 隐匿社交网络

tag：并查集 + 位运算

Solution：按位进行运算，将这一位为1的账号使用并查集进行合并。

void solve(){int n;cin >> n;DSU dsu(n + 1);vector<int> a(n + 1);for (int i = 1; i <= n; i ++){cin >> a[i];}for (int i = 0; i < 63; i ++){int t = -1;for (int j = 1; j <= n; j ++){if (a[j] >> i & 1){if (t == -1)t = j;else{dsu.merge(t, j);}}}}int ans = 1;for (int i = 1; i <= n; i ++){ans = max(ans, dsu.size(i));}cout << ans << endl;
}

E. 1or0

tag：线段树

F. 计树

tag：思维

Solution：考虑以u为目标lca的答案，num[i]记录以i为根的子树包含的目标节点的个数。

• 遍历u的子结点，已经遍历过的目标节点数为x，那么当前节点的贡献为x * num[i]。
• 当自己是目标节点时，x为1。

void solve(){int n;cin >> n;vector g(n + 1, vector<int>());vector<int> flag(n + 1);for (int i = 1; i < n; i ++){int a, b;cin >> a >> b;g[a].pb(b);g[b].pb(a);}int ans = 0;int k;cin >> k;for (int i = 0; i < k; i ++){int x;cin >> x;flag[x] = true;}vector<int> num(n + 1);  // 记录每棵子树下有多少个目标节点function<void(int, int)> dfs1 = [&](int u, int fa){if (flag[u])num[u] ++;for (auto v : g[u]){if (v == fa)continue;dfs1(v, u);num[u] += num[v];}};dfs1(1, 0);vector<int> cnt(n + 1);function<void(int, int)> dfs2 = [&](int u, int fa){int x = 0;if (flag[u]){cnt[u] ++;x = 1;}for (auto v : g[u]){if (v == fa)continue;cnt[u] += x * num[v] * 2;x += num[v];dfs2(v, u);}};dfs2(1, 0);for (int i = 1; i <= n; i ++){cout << cnt[i] << " ";}
}