3.13携程笔试

日常C++选手。做第一题的时候我的答案和测试用例一模一样，但是oj说我答案是错的，我点了对比，甚至都没有标红。同样的逻辑我用python写了一遍，就ac了。这时候我就觉得很奇怪了。后面做第三题的时候，我的思路跟大家应该也是一样的，就是先用埃氏筛筛出质数，求出所有数的权重，然后用滑动窗口解决。我提交的时候只过了30%多的样例。我调试的时候，特意试了一下n==k的边界条件，照理来说应该答案是0，但是我输出0时，oj却判错，就感觉很奇怪。大家有遇到这样的情况吗。

思路：前提条件，两个数如果他们的最大公约数是偶数，则代表这两个数也一定是偶数。因此，只需要找出树上的偶数连通块，对于每个连通块可以任意选择其中的一个或者二个节点组成简单路径。使用并查集完成对连通块的维护。 #include <iostream> #include <vector> using namespace std; vector<int> g; int find(int x) { if (g[x] == x)return x; return g[x] = find(g[x]); } int main() { int n; ...

1.直接模拟2.从小到大排序，从后往前遍历i，每次取i~n这段数组看看答案会不会更大，即不断更新ans=max(ans, a[i] + n - i + 1)。3.先预处理每个数的质因子个数a[i]。对a数组求前缀和。然后枚举长度为k的滑动窗口往后移动，更新答案4.树形dp，记dp[i]为从结点i往下走的路径为偶数的方案数。可以发现，只有所有数都为偶数时，这些数的gcd才可能为偶数，因此只需要判断数的奇偶性就行，不用去算gcd。dfs每个结点u，枚举以u为路径最高点时路径为偶数的方案数，累加起来就是答案。对于每个偶数结点u，dp[u]=u的儿子的dp和 + 1，这样就完成了dp的更新；累加答案的话，就是枚举u的每个儿子dp[i]，和他左边儿子的dp和sum，ans+=sum*dp[i]，然后sum+=dp[i]，因为以u为最高点的话，u左边和u右边的路径是可以组合起来的；第四题可能讲的不是很清楚，但属于树形dp挺常见的类型

1. 字符串 100%2. 贪心+排序 100%每次选择数字应该选择最大的数字，这样确保了在挑选的数字个数相同的情况下，挑选的数字中的最小值就会尽可能地大。那么就先排序，依次选择最大的数字，然后遍历得到最大的结果3. 素数筛+滑动窗口 100%优化计算权值：先找到所有的质数（题目规定数字最大是 10^4），用埃氏素数筛优化，然后用所有的质数去找到所有数字的质因数，这样就减少了迭代的次数优化计算子数组之和：滑动窗口法，计算区间内的权值之和，这样就得到了剩下数字的权值之和4. 并查集 100%其实就是找路径上所有节点都是偶数，那么他们的最大公因数肯定是偶数，至少是 2这里我一开始使用递归的方式，递...