题意 给定一颗二叉树，每个节点上有一个数字，计算每一条从根节点到叶子节点的路径组成的数字的和。 思路 由于二叉树的左右子树也都是二叉树，我们只需要对其递归操作就能得到结果，这里我们使用深度优先搜索的方法，从根节点开始，分别计算左右子树路径和，每到一个叶子节点说明已经找到了一条路径，将总和sumTotsumTotsumTot加上这次的路径值，最后就能得到结果。 例如对于如图二叉树，根节点为1，其右子树的路径为1−3−71-3-71−3−7,故右子树路径和就是137，左子树有两条路径分别为1−2−4−51-2-4-51−2−4−5和1−2−4−61-2-4-61−2−4−6,故左子树路径和为124...

题意 编写程序将一串阿拉伯数字转化为符合英语语法的写法，n≤2000000n≤2000000n≤2000000。 解答 依据题目说明，我们可以发现数字在英语读法中三位数字看成一整体，后面再加一个计数单位。而相同部分的英语读法相同，由此我们可以想到利用递归将大数字分为几个三位的数字，再拼接在一起即可。 #include<bits/stdc++.h> using namespace std; int n; string a[] = {"a0", "one", "two", "three", "four", "five", "six", "seven","eight", "nine", ...

题意 在一个迷宫中，只能上下左右走，找出从左上角到右下角的路线。 解答：DFS 对于迷宫类题目，由于题目保证了有且只有一条通道，因此我们可以用深度优先搜索（DFS）解决这个问题。 #include<bits/stdc++.h> using namespace std; int mp[11][11],used[11][11];//mp数组存储地图，used数组存储当前该位置是否已经走过 int n,m; const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//dx和dy分别代表上下左右方向 int isValid(int posx,int posy...

#include<bits/stdc++.h> using namespace std; int mp[11][11],used[11][11]; int n,m; const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; int isValid(int posx,int posy) { if(posx>=0&&posx<n&&posy>=0&&posy<m&&!used[posx][posy]&&!mp[posx][posy]) return 1...

题意 给出一个由小写字母组成的字符串，找到一个数组{a1...a26}={1,2...261,2...261,2...26},使得∑i=1nai∗pi\sum_{i=1}^n a_i*p_i∑i=1n​ai​∗pi​最大，其中pip_ipi​是第i个字母出现的次数。 解答 容易发现由排序不等式，只需要让出现次数最多的字母对应26，次多的字母对应25....以此类推，即可以得到最大的答案[1]。 代码如下。 #include<bits/stdc++.h> using namespace std; int p[30];//存储字母出现次数的数组 bool cmp(int a,int b...

题意 给出一个未解的数独谜题，解这个数独。 解答 这是一道搜索的基础题，我们用深度优先搜索解决它。 代码如下： #include <bits/stdc++.h> using namespace std; int sd[11][11];//数独方阵定义 bool p[11][11],l[11][11],fz[11][11];//行，列与方阵是否满足数独条件 void _init() { for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { int t; cin>>t; if(t!=0) p[i][t]=l[j][t]=fz...

题意 输出某字符串的前n位。 解答 代码如下 #include<bits/stdc++.h> using namespace std; string a; int n; int main() { while(cin >> a >> n) { for(int i=0;i<n;i++) cout << a[i]; puts("");//换行 } }  时间复杂度：O(nQ)O(nQ)O(nQ),QQQ为数据组数。 空间复杂度：O(1)O(1)O(1)，常数级别。

题意 有n种数，第i种数有ai个，求取得的数的总和的数量。 分析 问题可以转化为两步： 1.存储所有不同选数方案的总和。2. 对总和去重并算出总和数目。 我们可以考虑使用C++语言中自带的STL容器set，利用set存储所得答案并去重。 #include<bits/stdc++.h> using namespace std; set <int> ans,p; int n,m[11][2]; int main() { while(~scanf("%d",&n))//读取砝码数量 { ans.clear();//对答案集合初始化 for(int i=1;i<=...

题意 有n根火柴，可以用其中长度相同的火柴拼成正方形或正三角形，求能拼成的最大面积。 100分做法：暴力枚举 对于每一种不同长度的火柴，枚举组成正方形和三角形的个数，并计算最大面积。 class Solution { public: void calc(int l,int t,vector<long> &ans) { int Sqa=0; int Tri=0; const double a=sqrt(3)/4; double maxx=0.0; int maxSqa=0; int maxTri=0;//存贮组成最大面积时的三角形和正方形个数 for(Sqa=0;Sqa&lt...

题意 一棵树节点初始权值为0，每次增加一个节点及其子树的权值，求最后每个节点的权值。 20分做法：暴力计算 直接按照题意暴力模拟，每次寻找要增加的节点及其子树。 80分做法：邻接矩阵+预处理 先用邻接矩阵把树变为方便处理的形式，再预处理节点和子树。预处理找到所有子树的父节点，在操作时对于所有父节点的子节点加上相同的数，在q次操作完成之后，所有节点的权值都是其父节点与其自身的权值之和。 代码如下 /** * struct Point { * int x; * int y; * Point(int xx, int yy) : x(xx), y(yy) {} * }; */ class Soluti...

题意 在1~n这nnn个数中选定几个数组成一个集合，使所有选出来的数都满足m个限制，求合法集合个数。 100分做法：暴力枚举 我们只需要将所有可能出现的数字集合都枚举出来，一一判断选出的数能否满足限制并计算个数即可。 代码如下  * struct Point { * int x; * int y; * Point(int xx, int yy) : x(xx), y(yy) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int 集合大小 * @param...

##题意 给定一棵有nnn个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。 若某节点只有一个子结点，则此处将其看作左儿子结点 ##0分做法：枚举 将所有可能出现的中序序列枚举，并根据中序遍历和前序遍历计算后序遍历，若后序遍历与所给相等说明得到所需中序遍历，由于所有不同的序列有n!种，故该方法不可行 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int 二叉树节点数量 * @param pre intvector 前序序列 * @param suf intvector...

给定一颗节点编号为1~n的，且以1为根的树，给出n组询问，每次询问给定一个数对(x,y)，求\sum_{i为x到根路径上的点(包括x和根)}^{}{(y+2i)xor(y+i)}∑i为x到根路径上的点(包括x和根)​ (y+2i)xor(y+i).对于这n组询问的答案，不需要依次输出n个数，你只需要输出他们的和对998244353的取模即可。树的信息以及询问不会直接给出，输入数据只包含随机种子，具体生成方式请仔细阅读备注内容。

题意 在一个的矩阵中每个元素的数值都为0或1，放置一个长宽分别为与的十字，求十字覆盖元素和的最大值。下文中代表玩家数量（）。##18分做法：暴力对于每一个点，暴力计算在这个点爆炸能炸死的人，代码如下 class Solution { public: //bool isLegal(Point a,int i,int j,int xl,int xr){return a.x==i||a.y==j&&a.x>=xl&&a.x<=xr;} int BoomKill(int n, int m, vector<Point>& Player) {...