家装网站建设预算,网站建设 文库,贵州seo技术查询,wordpress 产品缩略图题目链接#xff1a;牛客周赛 Round 77
A. 时间表
tag#xff1a;签到
B. 数独数组
tag#xff1a;签到
Description#xff1a;给定n个数#xff0c;每个数的范围为1-9#xff0c;问能否经过排列#xff0c;使其每个长度为9的连续子数组都包含1-9这9个数字。
Sol…题目链接牛客周赛 Round 77
A. 时间表
tag签到
B. 数独数组
tag签到
Description给定n个数每个数的范围为1-9问能否经过排列使其每个长度为9的连续子数组都包含1-9这9个数字。
Solution手模发现前面一定是每个数字都出现且次数相同最后后面再放一些数字只出现一次。 故只要判断数字的最少次数和最多次数差距不大于1即可。
C. 小红走网格
taggcd
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);vectorint 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, vectorint());vectorint 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;}vectorint num(n 1); // 记录每棵子树下有多少个目标节点functionvoid(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);vectorint cnt(n 1);functionvoid(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] ;}
}
