思路：最朴素的做法：维护一个dp[i]:以i为子树的所有结点和，然后对于每个节点更新，朴素的更新它父亲节点的值，但是，如果树是一个长链这个就超时了。正解：先dfs求一个dfs序，这样以i节点的子树都是在一段区间内，所以我们可以维护一下i的子树的数量，那么求以i为根的子树和就是[dfs(i) - 1,dfs(i) + son[i] - 1]区间和，dfs(i):i节点的dfs序。子树的和用一个区间和就解决了，那么修改节点i的值无非就是单点更新，树状数组维护一下即可。代码： #include<bits/stdc++.h> using namespace std; const int m...

思路：直接想怎么去加边可能比较难想。但是虽然欧拉路不太好求，我们可以从欧拉回路着手，因为这是一棵树，如果要找到一条路，必定是每条边都经过两次(因为是一棵树，不存在任何回路，所以回路必须原路返回，即再经过原来的边一次)，那么欧拉回路的权是 。欧拉回路必然满足欧拉路，接下来怎么从欧拉回路找一条最小权的欧拉路，因为欧拉回路必然是一个环，那么我们只需要在这个环上找到某一段权值和最大，并且每个点只经过一次，使得剩下的路满足欧拉路，那么剩下的路径就是最小权的欧拉路，并且找的一段路径就是树的直径。树的直径两次BFS即可。代码： #include<iostream> #include<cst...

题目大意：给你两个序列a,b,要你从b中找一个排列，使得bi oxr ai 最小，并且字典序最小。思路：先把要排列的b插入字典树中去，然后枚举a，一个一个去贪心的找最小值就行了。每次找的都是最小的xor值就保证了字典序最小。因为每个数只能被找一次，所以这个题难度在于，从字典树找最小异或值，并且每个数只能被找一次。最小异或值比较简单，贪心找，当前二进制为0就往0子树走，为1就往1走，实在走不了就计算异或值。每个数只能走一次，可以用一个数组记录每个节点被插入的次数，然后这题就没了。代码： #include<iostream> #include<vector> #includ...

题目大意：给你一个长度为n的序列，和m个操作，每个操作包含两部分：1)对序列(a1,a2,...,an) ^ x2)找出序列的。思路：如果按照题目要求去做，我们需要对字典树有修改，查询的操作。但是字典树好像没修改操作。(应该是我不会修改)。但是异或满足结合律，即 (a1,a2,a3,a4,..,an) ^ x ^ y ^ .. ^ z = (a1,a2,a3,a4,..,an) ^ (x ^ y ^ .. ^ z)这样对于m个询问我们可以用一个变量来存询问的前缀异或值，这样就可以不对字典树进行修改操作了。但是第二个问题是函数怎么求呢？当我们把插入字典树mex函数的值应该是除了这些数的其他数，所...

思路：一边插入前缀异或值，一边查询之前插入的哪个数可以与当前数组成最大异或值，这样就变成了两个异或最大值问题了，不过还要求一下区间，对于插入的每个数，用一个数字记录一下他所在的地方，为什么这样是正确的呢，因为一个数异或自己等于0，前缀异或值存的是[1,i]的异或和，我们在[i,i]再找一个j与他组成最大异或值，那么求的就是[j,i]的最大值[1,j - 1]异或了两次就是0了。有点细节需要注意，比如要先插入一个0，不然1 2 4 8就hack了代码： #include<iostream> #include<vector> #include<cstring> ...

随便说说：第一次发现字典树还能这样用，以前都是用字典树求一些最简单的'a'-'z'前缀相同的个数,直到看见这道题。。。。才发现数据结构用好了是真的可以无敌。。。 思路：暴力枚举两个数肯定是超时，那么我们希望有这样一种操作，我们枚举每个数，枚举到当前这个数，我们希望能够在一个很快的时间里(可以是或者)面求出前面与我们当前这个数异或的最大值，这样就相当于所有的数两两都异或了一次，然后我们取一个max就出来了。所以01trie这个数据结构就可以求出与前面所有数异或最大值。01trie就是只包含0和1的树，对于所有的数字，我们都可以转化为二进制处理,那么我们可以考虑用01trie存储这些二进制，然后枚...

题目大意：有n个操作(只包含&,|,^)，然后要你从0-m选一个数,使得这个数经过n个操作后数值最大。思路：考虑二进制，最后的答案转化为二进制，每一位要么选要么不选，然后我们贪心的从最高位选，能选则选。我们可以用一个全0bitset和全1bitset去经过n次操作，然后从2的最高位开始枚举，如果全0bitset这位等于1说明这位选0就能得到这个值，加入我们的答案，否则看一下全1bitset，如果这位等于1，说明我们选择的这个数的这位是1就能得到这个值，并且这个值不超过m的取值范围就加入答案。最终输出答案即可。代码： #include<iostream> #include&l...

题目大意：给你一棵树，树上有个特殊点，问有多少点到所有特殊点的距离小于d.思路：又是学习大佬题解的一天我好菜啊先对特殊点求一个树的直径，然后枚举所有点，如果它到直径两端的距离小于等于d，说明这些点满足题目要求。求特殊点的直径，三次DFS即可，先从根求一波最长的特殊点，然后从特殊的再求一波最长的另外一个特殊端点，最优另外一个特殊端点再求一下到各个点的距离，然后枚举一下就行了。这题一开始写了一个暴力，然后写树dp，苦于一个点到特殊点的最大距离不会求。。。。太菜了我。。还是这个做法香(逃)代码： #include<iostream> #include<cstring> #in...

题目大意：给你一个数,要你找个数，使得这个数的和是，并且这些数只能包含。思路：先把的只包含01的数打表出来，这部分BFS即可，可以发现数量并不多刚好255个。然后可以考虑背包dp求出最小的组成的方案，时间复杂度为不会超时。dp[i]:用只包含01的数组成数字i的最小组成数量。转移方程：dp[i] = min(dp[i],dp[i - res[j]] + 1)。因为还要输出方案，再开一个数组记录当前位置的上一步骤，并且记录一下当前最优选择，然后输出一下即可。代码： #include<iostream> #include<vector> #include<cstrin...

思路：先求每个节点的子树的个数，然后暴力枚举每个节点，找到左右子树对称的最多节点个数的就行。判断子树是否对称：先判断左右子树的值是否相同，然后递归判断左子树的左子树和右子树的右子树，和左子树的右子树和右子树的左子树是否相同即可。代码： #include<iostream> #include<vector> #include<cstring> #include<algorithm> using namespace std; const int maxn = 2e6 + 10; int va[maxn]; vector<int>G[max...

思路：假设我们要组合出来的数是，并且三个部分都是相同的那么总和就是，那么我们可以找到一种为的情况，即每个点的总和如果不是的倍数那么必然输出，如果是三个倍数如果找不到可以切割的两条边也是，注意到这是一棵树那么切割出来必然是类似于三个联通块，所以我们直接dfs计算以每个节点为子树的总和，如果找到满足答案的就记录答案并且它的父节点不记录这个子树的和(即切割),最后输出一下答案就行了。一开始我是用这个条件判断是否存在答案的，举个反例可以发现当全部节点为并且是可以划分的，把条件改就行了。代码： #include<iostream> #include<algorithm> #inc...

思路：很显然答案是(1-1/(n^m))%mod,因为是除法取模所以是(n^m - 1)*inv(n^m)即可。这题卡常，如果快速幂用两次必超时，用一次就可以过。代码： #include<iostream> #include<vector> #include<map> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<set> #include<stack> using name...

写了4题后注意力就没那么集中了，就感觉在划水一般~啊！！好菜啊我 A:Sumo and Keyboard-Cat;题意：思路：很显然就是求小写转大写或者大写变小写出现的次数。然后统计一下次数就行了，注意如果第一个字符是小写从1开始统计。代码： #include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; typedef long long int ll; void solved(){ string s;cin>>s; int ans = 0; if(s[0] >= 'a' &...

A:符合条件的整数题意：思路：求一段区间的个数，用前缀和的思想就是R - (L - 1),R表示[1,2^m - 1]有多少%7=1的数，L同理，那么关键就是给定一个n，怎么求[1,n]有多少%7=1的数了，通过观察可以发现就是(n - 1)/7。所以答案就是(2^m - 2) / 7 - (2^n - 2) / 7。注意开闭区间就行。但是好像会爆ll，所以我python写的。代码： n,m=map(int,input().split()) ans1 = 1 ans2 = 1 for i in range(0,m): ans1 *= 2 for i in range(0,n): ans2 *=...