前言：第三场比前面两场难度下降了很多，打起来还算比较舒服，这场理论上来说应该可以开7题了，但是场上只写了5题，有两题是思路但是需要再仔细考虑一下的，没开出来有点可惜。D思路：签到题，范围挺小的，没多想，直接一发暴力。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; typedef long long int ll; int cal(int x){ int res = 0; while(x){ res += x % 10; x /= 10; } return res; } void ...

思路：三个for判断一下就好了。但是判断等比数列的时候不能直接除，因为不一定全部整除。a[2] / a[1] = a[i] / a[i - 1]a[2] * a[i - 1] = a[i] * a[1]变成乘法就行了。 #include<iostream> #include<queue> #include<string> #include<cstring> #include<algorithm> using namespace std; long long int a[200000]; void solved(){ int n;cin...

A 思路：看到两两联通就容易想到最小生成树，然后要黑边多，白边少，那只需要最小生成树改一下排序条件就行了。代码： #include<iostream> #include<vector> #include<algorithm> using namespace std; const int maxn = 2e7 + 10; struct edge{ int u,v,w; }e[maxn]; bool cmp(edge a,edge b){ return a.w < b.w; } int f[maxn]; int find(int x){ if(x != f...

思路：容易发现这个题要求的就是它的所有因子之和，所以唯一分解定理就可以用一个比较不错的复杂度切掉这题。代码： #include<iostream> #include<vector> #include<algorithm> using namespace std; typedef long long int ll; ll dcpSum(ll x){//所有因子的和（包括1） ll ans = 1; for(ll i = 2; i * i <= x; i++){ if(x % i == 0){ ll temp = 1; while(x % i == 0){...

A思路：这题我感觉写复杂了。我的思路是贪心：尽可能让所有的战机拿到贡献，并且在当前这辆战机在可以拿的贡献中拿最大的。那么，先对自己的战机和敌人的战机按照防御值升序。然后枚举自己的所有战机，因为敌人的战机已经排序了，我们二分出最后一个小于当前这辆战机的位置，然后在区间[1,index]找最大值。这就是一个区间最大值的问题了，可以用线段树来维护一下就行了。代码： #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<map> #...

题目大意：给你一颗树，你可以在树上进行两种操作1 x val,把val加到x节点上面去，然后-val加到x的第一层儿子节点，然后-(-val)加到第二层儿子节点，。。。等2 x,查询x节点的值。思路：这题看了大佬的思路才做出来的。  https://blog.nowcoder.net/n/d8f8de427aae4b65a43bf5383a75938b  这个题的关键就是先把每个节点是奇数层还是偶数层求出来，然后求一个dfs序，把每个节点为子树的儿子节点的范围求出来。对于1操作，该节点能够影响的范围有[l[x],r[x]]，那么对这个区间做一个加法，我们可以用线段树或者树状数组差分来实现s[l...

思路：这个题意我读了半年样例的3是这样的这里为什么不选4号节点呢，因为“如果在左子树选了一个点，在右子树中选的其他点要比它小。”，也就是左子树的值应该比右子树的值大，并且根节点的值最小，那么我们可以知道 根节点<右子树<左子树，那么我们可以根-右-左这样遍历这棵树，然后存他的dfs序，要使得选择的节点数量越多，就是在这个dfs序找一个最长上升子序列，这个长度就是答案。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; int G[maxn][2]; int w[maxn]...

题目大意：给你一棵树，然后有q个询问(u,k),问以u为根进行深度优先搜索第k个元素是多少？思路：朴素做法：对于q个询问，每个询问dfs一下求第k个元素即可。---超时正解：我们可以先求出以1为根的所有节点的dfs序，然后记录一下第i个dfs序是谁，然后对于q个询问输出第(dfn[u] + k - 1)个dfs序是谁即可。对于-1的情况，我们只需要开一个数组记录每颗子树儿子的数量，然后如果k > son[u]输出-1即可。代码： #include<iostream> #include<vector> #include<cstring> #include...