手搓一个DSU的板子，根据题意合并类型相同的点，最后找到并查集中集合的最大siz，满足最大siz的都放进答案数组中，最后输出答案数组的大小和内容即可。 #include <iostream> #include <vector> #include <numeric> struct DSU{ std::vector<int> f, siz; DSU(int n){ f.resize(n + 1); std::iota(f.begin(), f.end(), 0); siz.assign(n + 1, 1); } int find(int x){ if...

枚举其中一种可乐的数量（此处为蜂蜜可乐）记为j，另一种可乐的数量即为k = N - j，模拟直至无法进行兑换，取最大值即为答案。粗略估一下时间复杂度为O(T * N * log)，此处的log应该是与a和b相关的一个对数常数。最大的数据量大概在1E6到1E7左右，因此不会超时。 #include <iostream> void solve(){ int n, a, b; std::cin >> n >> a >> b; int ans = 0; for(int i = 0; i <= n; i++){ int j = i; int k = ...

Modern Cpp欧拉筛是可以用最小质因子筛的，jiangly老师的欧拉筛模板就是如此。然后累加1到n的最小质因子即可。 #include <iostream> #include <vector> #include <numeric> std::vector<int> minp, primes; void sieve(int n){ minp.assign(n + 1, 0); primes.clear(); for(int i = 2; i <= n; i++){ if(!minp[i]){ minp[i] = i; primes.pu...

Modern Cpp写法结论就是与第一个大于1的数的下标位置有关，记该位置为idx（下标从0开始），观察样例就知道，如果idx是偶数，那么答案是"Alice"，否则答案是"Bob"。另外，若ai全为1，即不存在大于1的数，此时手动造几组n比较小的样例就会发现，若n为奇数，则答案为"Alice"，否则答案为"Bob"，此时不难发现，若往数组a的最后添加一组{1, 2}，再按照存在大于1的数处理也是对的，这样就不需要特判了。具体查找可以使用find_if函数。 #include <iostream> #in...

考虑二分查找，枚举a[i]，贪心地找到第一个大于a[i] + p * 2的下标j，max(j - i)就是答案。 #include <iostream> #include <vector> #include <algorithm> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n, p; std::cin >> n >> p; std::vector<int> a(n); f...

考察容斥原理，直接看不出来的建议画个图显然7等于(a + b + c - n - d) / 2 #include <iostream> void solve(){ int n, a, b, c, d; std::cin >> n >> a >> b >> c >> d; std::cout << (1LL * a + b + c - n - d) / 2 << "\n"; } int main() { std::ios::sync_with_stdio(false); std::...

枚举三种情况，取个最小值就是答案。第一种情况：每次只买单个竹鼠（a * x）。第二种情况：买x / 3组3个竹鼠，买x % 3个组1个竹鼠（b * (x / 3) + a * (x % 3)）。第三种情况：买x / 3 + 1组3个竹鼠（b * (x / 3 + 1)）。注意中间计算会爆int，需要转成i64。 #include <iostream> #include <vector> #include <algorithm> using i64 = long long; int main() { std::ios::sync_with_stdio(fals...

方法一：模拟、贪心、差分先考虑暴力，由于有区间修改，想到使用差分进行模拟。模拟的时候可以贪心地想到： 若当前的最小值是负数，为了最小化最后的结果，就将后续的所有数全都加上这个负数；若当前的最小值不是负数，那么只找一个数加上，为了方便，就找第一个大于等于它的数即可。因此需要先对数组a排序，且中间加的过程应该使用差分，边修改边计算，最后遍历到的数a[i]就是答案。总时间复杂度为O(n * logn)，瓶颈主要在排序上，遍历加差分的时间复杂度仅为O(n)。 #include <iostream> #include <vector> #include <algorithm...

方法一：二分答案估一下二分的范围，a + b <= 2E9，那么n二分的上界限定到ceil(sqrt(2E9))即可，我这里直接取了45000，它的平方也不会爆int；由于a + b > 0，那么二分的下界即为1。思考check函数，观察样例和说明，发现边长为n的棋盘，最多可以同时放下一种数量为ceil((n * n) / 2)的棋子和另一种数量为floor((n * n) / 2)的棋子。不妨分别记为cnt1和cnt2（显然cnt1 >= cnt2）。当然对于读入的数据a和b，我们也要保证a >= b，然后check的时候判断cnt1 >= a且cnt2 &gt...

方法一：使用C语言的内建函数__builtin_popcountll #include <iostream> using i64 = long long; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); i64 x; std::cin >> x; std::cout << __builtin_popcountll(x) << "\n"; return 0; } 方法二：模拟 #includ...

方法众多，以下给出五种。方法一：完全背包 #include <iostream> #include <vector> #include <algorithm> constexpr int inf = 1E9; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n; std::cin >> n; std::vector<int> dp(n + 1, inf); dp[0] = 0; for(i...

由于n比较大，因此考虑矩阵快速幂，具体推导过程见代码的注释昨天的每日一题也可用矩阵快速幂（不过有点大炮打蚊子了），贴一个昨天每日一题我的题解（矩阵快速幂在方法三）：https://www.nowcoder.com/discuss/856068762758311936方法一：使用行向量 #include <iostream> #include <vector> using i64 = long long; constexpr int P = 1E9 + 7; using Matrix = std::vector<std::vector<int>>;...

方法一：循环枚举（也可理解为滚动数组（变量）优化DP），时间复杂度O(k)，空间复杂度O(1) #include <iostream> constexpr int P = 1E9 + 7; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int k; std::cin >> k; if(k < 3){ std::cout << "1\n"; return 0; } int cur = 1, pr...

多源bfs（Modern Cpp） #include <iostream> #include <vector> #include <queue> #include <algorithm> constexpr int inf = 1E9; void solve(){ int n; std::cin >> n; std::vector<std::vector<int>> adj(n + 1); for(int i = 0; i < n - 1; i++){ int u, v; std::cin >&gt...