数学考试 这个题明显直接暴力枚举是不太行的，更优解是进行dp 设为之间所有的最大值 那么我们只要遍历一遍当左区间取到的时候，另一个区间的最大值就是 利用前缀和从右往左维护 maxn为从右往左维护时记录的最大值 code #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 200000 + 7; ll sum[MAXN] , a[MAXN]; int main(void){ int T; cin>>T; while(T--){ int n , k; cin&...

1,第几天  标题：第几天2000年的1月1日，是那一年的第1天。那么，2000年的5月4日，是那一年的第几天？注意：需要提交的是一个整数，不要填写任何多余内容。  2000%400==0所以 2,明码  标题：明码汉字的字形存在于字库中，即便在今天，16点阵的字库也仍然使用广泛。16点阵的字库把每个汉字看成是16x16个像素信息。并把这些信息记录在字节中。 一个字节可以存储8位信息，用32个字节就可以存一个汉字的字形了。把每个字节转为2进制表示，1表示墨迹，0表示底色。每行2个字节，一共16行，布局是： 第1字节，第2字节 第3字节，第4字节 .... 第31字节, 第32字节这道题目是给你...

1.15.125GB 【问题描述】在计算机存储中，15.125GB是多少MB？【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。 15488.000000 #include<bits/stdc++.h> using namespace std; int main(void){ printf("%lf\n",15.125*1024); system("pause"); return 0; }2.约数个数 【问题描述】1200000有多少个约数（只计算正约数）...

原文链接链接有效的将的区间dp优化成 题目 1898: [蓝桥杯][算法提高VIP]合并石子  在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。  code #include<bits/stdc++.h> using namespace std; const int MAXN = 1005; const int INF = 1 << 30; int sum[MAXN],n; int Minval(){ int dp[MAXN][MAXN],s[MAXN][MA...

hdu1166裸的线段树问题，就是一个简单的单点操作和求和操作 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAXN = 5e5 + 7; ll pre[MAXN], tree[MAXN * 4], ans[MAXN]; string Ins[] = {"Add", "Sub", "Query", "End"}; void Buildtree(ll p, ll l, ll r) //建树 { i...

二叉树的遍历主要是三种遍历，前序中序后序前序：父节点 左节点 右节点的顺序遍历中序：左节点 父节点 右节点的顺序遍历后序：左节点 右节点 父节点的顺序遍历因为遍历顺序 得到的最后的结果有以下特点假设一个前序遍历的结果是ABCDA一定是根节点，父节点一定在子节点前面假设一个中序遍历的结果是ABCDE假设C是根节点 那么AB一定在C的左子树上，DE一定在C的右子树上假设一个后序遍历的结果是ABCDD一定是根节点，父节点一定在子节点后面 就是写一个简单的递归就可以遍历 void preorder(node* root){ //求前序遍历 post数组储存前序遍历结果 if(root!=NULL){ ...

首先贴模板 long long dcp(long long x){ long long i,ans = 1; for(i = 2; i * i <= x; i++){ if(x % i == 0){ long long temp = 0; while(x % i == 0){ x /= i; temp++; } ans *= (temp+1); } } if(x > 1) ans *= 2; return ans; }举个例子，那么答案就是怎么理解呢，对于2 有0 1 2 3四种指数选择，对于3 有0 1两种指数选择 所以 就是4 * 2 = 8 个因子个数还是理解吧不了，那我们列...

题意 给出一颗树，以及树上的每条边的关系和点的权值，求在任意两个点的最短路径的走法下，点权异或和是多少。 解析 首先不能暴力，因为数据范围到了 $5e5$ 暴力妥妥的超时 那么我们考虑其他的做法，首先是异或和， ;  所以我们将题目转换为在最短路径下通过节点的奇偶次数， 首先我们先只考虑经过u而不以u为最短路终点的情况看，我们可以一次dfs统计出各个子树的大小 并且知道子树大小后假设sz[u]代表u节点包括自己在内的子树节点总数之和并且知道子树大小后假设sz[u]代表u节点包括自己在内的子树节点总数之和 那么把v全部遍历一遍dfs可以做到，在dfs过程中那么把v全部遍历一遍dfs可以做到，在d...

题意 给出一个倒三角，点亮一个技能就会消耗一个技能点并且得到相应的技能值，但是除了第一行的技能可以直接消耗一个技能点点亮以外其他的都要点亮他正上方以及右上方的技能，给出三角形的规模和技能点数，要求获得的技能值最大，画个图理解 我要点亮技能值为5的那个技能就要点亮他上方（技能值为一）和右上方（技能值为9的）两个点 解析 首先我们用$mp[i][j]$来储存每个点的技能值，因为用到了第i行的前的每一行都要用到，所以我们可以直接用前缀和表示这一列的和 我们用数组表示学习到处，花费了个技能点的最大收益 很容易就能想到枚举列数，从最右边开始枚举，然后枚举行数，表示学到当前前一列的某个技能的情况下，然后枚...

题意 现在给你一块长度为5的木板，给他涂色，一共有五种颜色，每一次涂色是可以选择涂连续的一段，即我可以涂一格，也可以涂两个连在一起的，也可以涂三格连续在一起的，现在给出目标状态，问要涂的最少次数。 解析 首先我们先分析一下样例是什么意思，样例1：AAAAA，很明显，就是选择颜色A,然后涂一次从最左边涂到最右边这就是最少的次数， 然后是样例二，RGBGR，三次是怎么涂的也不难理解，首先是是涂一次全部涂成R从最左边涂到最右边，即RRRRR，然后选择颜色G从第二个涂到第四个，即RGGGR，最后再涂中间这个，涂成B，就有了RGBGR。 我们可以选择使用区间dp，区间的左端点和右端点的颜色相同的话我们就...

题意 有一个一维的地图，地图上有很多个格子，每个格子上都标了一个值，现在有一个乌龟在起点处，位置为1，现在给你4种卡牌，分别标有1，2，3，4，使用卡牌可以让乌龟走卡牌上的数，即使用1让乌龟走一格，使用2让乌龟走两个，现在给你一些这种卡牌，保证卡牌用完能够走到终点，要求你如何使用能让乌龟所有停留的点上的值加起来最大。 解析 这个题目很简单，看懂了题目之后就是一个简单的dp，直接暴力的递推，然后维护格子的最大值就好了， 设一个dp数组为，分别表示每一种卡牌使用了多少个，然后递推到最后，即所有卡牌都用完， 也就是走到最后的情况就是最大的值了，直接暴力向后推就可以了，将当前的格子值加上向后分别走1，...

高飞大佬与他的硬币 Problem Description 高飞学长在结束了一天的敲代码之后，想要出门去买一点东西，现在高飞学长有着1，2，5，10四种面值的硬币， 高飞学长在想要带着最少的硬币数量去购买东西，并且商店老板不会找零， 因此高飞学长会事先拜托他的室友咕咕咕学长事先调查好他需要的物品的价格总和 假设高飞学长拥有的每种硬币数量无限，现在请你输出高飞学长最少需要的硬币数量 Input 输入一个整数，表示商品的价值总和n(0<=n<=1e6) Output 输出一个整数，表示最少使用的硬币数量 Sample Input  12  Sample Output  2  标程 #i...

题意 现在有一个柱状图，告诉你每一个，柱子的宽度和高度，然后问你这个图里最大的矩形面积，这里的矩形可以是这样的 也可以是这样的这样就很好理解了。就是找其中出现了的最大的矩形。 解析 这个题目用到了单调栈这个数据结构，简单描述一下就是栈里面的元素呈单调递增或者单调递减，并不难理解，如果是递增的，那么栈顶元素即是最大的，这个题目为什么用这个，举个例子 像这样的一个柱状图，我们肯定要穷举每一个可能组成的矩形然后来比较大小，我们可以从最左边开始，第一列 第二列 到了第三列就要比较这两个了  第四列也是这样 那么到了第五列呢，第五列比前面的更矮，我们在记录前面的最大值之后，在第五列（如果后面还有）就用不...

题意 题意就是给出一个数列和一个权值数列，然后让你按照题目中给的那个式子进行运算，认真理解一下（其实是偷看了隔壁大佬的博客，大佬博客：传送门）帮n列出来就能看到规律 解析 给出$f(l,r)=\sum_{i=l}^{r}{a_{i}}*w_{r-l+1}$， 求解 当的时候答案为 当的时候答案为由此递推就完事了 代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int N = 3e5 + 7; const ll MOD=1e...