高质量补题记录集 2022牛客第一场 J Serval and Essay 一道不错的图论题 比较有价值的部分是图的合并,类似并查集,合并两点时可以使用其中一个点编号作为合并后的点集编号。 用启发式合并思想,让小集合向大集合合并,合并时将小集合上的连边转移到大集合上。 int n; int fa[maxn], siz[maxn], cnt[maxn]; set<int> nt[maxn], 2022-09-28 题解 #题解 #牛客多校 #杭电多校
Codeforces Round 814 div.1 ABC 录播讲解链接(AB) A2. Burenka and Traditions (hard version) 只会进行长度为2或1的区间操作,因为更大的可以分解成小的且不会更劣。 考虑从左到右依次两两进行异或操作,每次都使得左侧数变为0,那么总操作次数最多是 \(n\) 如果其中包含一段异或和为0的区间,就可以省下一次操作,且仅有这种方式可以省操作,故目标变为划分出最多的异或为0的子段个数 2022-08-18 题解 #题解 #codeforces
Codeforces Round 810 div.1 ABC A. Color the Picture 观察发现同一个颜色必须呈整行或整列才能满足条件,且至少需要连续两行,计算一下每个颜色最多可以涂几行/列即可,特判奇数行/列时,所有颜色都仅能涂2行/列的情况。 ll n, m, k; ll a[maxn]; void solve(){ cin >> n >> m >> k; for(ll 2022-07-26 题解 #题解 #codeforces
Educational Codeforces Round 131 D-F D. Permutation Restoration 题意:原先有一个排列 \(a(1...n)\),令 \(b_i=\lfloor i/a_i \rfloor\)。现在给出序列 \(b\),要恢复排列 \(a\) 首先可以根据 \(b_i\) 得出 \(a_i\) 的范围是 \((i/(b_i+1), i/b_i]\),由此得到了每个 \(a_i\) 的取值区间,接下来要将 \(1 2022-07-09 题解 #题解 #codeforces
Codeforces Global Round 20 A-F,H 连续一个月掉小分,这把终于上大分了 好耶! A. Log Chopping 题意:现在有 \(n\) 个木棍,第 \(i\) 根长度为 \(a_i\),Alice和Bob两人轮流操作,可以选择一根木棍将其切成两半,且两半的长度都需要是>1的整数。最后无法操作的人失败,问谁获胜。 虚假博弈,显然能切的次数是固定的,最终会全变成长度为1的木棍,判断能切的奇偶性即可。 int n, 2022-04-23 题解 #题解 #codeforces
Codeforces Round 783 div.1 ABC (div2.CDE) A. Make it Increasing 题意:给出一个整数序列 \(a\),现有另一个全为0的序列 \(b\),每次操作可以选取一个位置,使得 \(b_i\) 加上或减去 \(a_i\),问最少多少次操作可以使得 \(b\) 序列严格递增。数据范围 \(n\le10^3\) 数据范围允许我们考虑 \(n^2\),首先可以贪心地想到,肯定会有一个位置保持为0,那么就可以枚举这个0的位 2022-04-20 题解 #题解 #codeforces