题意：给你两个整数n和k。求你用 1~ n构造一个存在 1~n 长度的连续子列都能加起来之和取模n等于k，如果不能，输出-1. 思路：我们可以知道长度为n时的子列只有一个，和为n * (n+1)/2 ,所以当(n * (n+1)/2)%m=k时才有解。当n为偶数时，1+（n-1）=n、2+（n-2)=n、......所以二二之和可以为n除n和n/2外，要有解k=n/2,所以为奇数长度时用n/2和二二之和为n的数凑成，为偶数就再奇数基础加上n.所以可以构造成{1，n-1，2, n-2....，n/2,n};当n为奇数时，1+（n-1）=n、2+（n-2)=n、......所以二二之和可以为n除n...

题意：给你一个n*m的矩阵，求矩阵的子矩阵最大压强为多少，压力F为子矩阵所有元素之和，受力面积为子矩阵最后一行的元素之和？ 思路：由于我们只要求最大压力，所以我们根据公式求每一列的子列的最大压力即可。 代码： #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #define inf 1000000007 #define eps 0.00000001 using namespace std; typedef long long ll; type...

题意：给你一个柱状图，有n根柱子，给予你每根的宽度和高度，求柱状图的最大矩形面积？ 思路：单调栈，维护一个单调递增的栈，维护高度和左边界。当h[i]>栈顶元素的高度时入栈，左边界不变。当h[i]<栈顶元素的高度时，栈顶元素出栈，并计算以该栈顶元素高度为一条边的矩形最大面积（既（右边界-左边界） * 高度）。直到栈为空或h[i]>栈顶元素的高度时停止。将其入栈。如果栈为空，左边界不变，否则更新左边界。当h[i]=栈顶元素的高度时,开始下一个元素。 代码： #include <iostream> #include <cstdio> #include &lt...

题意：给你一个a数组和一个w数组，定义请你求 的值? 思路：由于n<=5 * 10^5,所以暴力肯定是不行的，所以我们可以按暴力求法列出式子看是否能优化。当n=5时，结果=f(1,1)+f(1,2)+f(1,3)+f(1,4)+f(1,5)+f(2,2)+f(2,3)+f(2,4)+f(2,5)+f(3,3)+f(3,4)+f(3,5)+f(4,4)+f(4,5)+f(5,5);f(1,1)+f(2,2)+f(3,3)+f(4,4)+f(5,5)=w1 * (a1+a2+a3+a4+a5);f(1,2)+f(2,3)+f(3,4)+f(4,5)=w2 * (a1+2(a2+a3+a4)+...

题意：给你n种染料，每种染料可以使用Ci次，同一种染料不能连续使用，求用完所有染料的方案数为多少种？ 思路：纯动态规划，我们用dp[a][b][c][d][e][last]描述一个还可以使用一次的染料为a种，还可以使用两次的染料为b种，.....,可以使用五次的染料为f种时上一次染色为使用还可以使用last次的染料。我们可以分析状态是怎么来的得出状态转化方程，例如，dp[a][b][c][d][e][1]时，如果上上次不为2，则上一次则使用的为a+1种染料的其中一种，如果上上次为2，则说明上一次(a+1)种有一种不能使用，所以为a种中的其中一种。 代码： #include <iostre...

题目：给与你n只碗，每只碗上宽下窄，告诉你上下半径和高度，请你求出n只碗叠放的高度最小为多少？ 思路：由于n<=9,所以可以直接枚举碗的顺序，求高度。我们可以对两只碗不同情况的叠加情况（从边的斜率和上下半径考虑）进行分析，维护下底高度。 代码： #include <bits/stdc++.h> #define inf 1000000007 #define eps 0.000001 using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn=100005;...

题意：将一块x*y的蛋糕切n-1刀分成n块面积相同的小蛋糕，每次切只能平行于边将一块切成二块。求N块蛋糕的长边与短边的比值的最大值最小为多少？ 思路：我们发现n<=10,而且每次切只能平行于边将一块切成二块，而且每一块面积相同，所以我们可以用dfs枚举每一种切法。平行于y边切：可以切成(i * x/n) * y和((n-i) * x/n) * y两块（0<i<n，x/n表示将x分为n份，你只能切这份额的倍数，否则会导致最终无法切成面积相等的n块）平行于x边切：可以切成(i * y/n) * x和((n-i) * y/n) * x两块 代码： #include <bits...

题意：给与一个长度不超过50的字符串，它可以按下列方式压缩：M是开始，R是重复从前一个M开始的字符串。求字符串压缩后的最短长度。 思路：区间dp:dp[i][j][0/1]:dp[i][j][0]表示从i到j这段字符串中没有有M、dp[i][j][1]表示从i到j这段字符串中可以出现M的最少字符数。当一段字符串可以被压缩时：dp[i][j][0]=min(dp[i][j][0],dp[i][i+k/2-1][0]+1);(无M才可以被压缩)字符串更新时：dp[i][j][0]=min(dp[i][j][0],dp[i][x][0]+(j-x)(后一段的字符数))(x>=i&&am...

题意： 有一棵节点数为n的树，每一个子节点向父节点传送消息时，如果以父节点为根的子树中该节点为根的子树中节点数最多，则该节点花费为父节点的花费，否则为父节点花费+1.求所有节点一层一层向根节点传送消息的花费之和尽量大时的花费为多少？ 思路：这题我们可以用dp解决，我们求的是n个节点树的最大花费，所以我们设sum[i]为节点数为i的树的最大花费，我们知道节点数最多的子树（设节点数为x）传送消息的花费为父节点的花费，相当于该子树节点向根节点传送信息花费为0，而其他子树的节点向根节点传送信息花费为1，又因为子树的花费是树的花费的一部分，所以树的最大花费为=（ sum[子树] ）+其他子树的节...

题意：给予一颗树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和（与点x树上距离<=1的所有点点权之和）.如果是第i次操作，这次操作结果为ans,则这个结果的值加上i * ans，结果模19260817。 思路：设数组f1[]记录该点本身修改的次数，数组f2[]记录该点儿子的修改次数，数组f3[]记录该点孙子的修改次数。该点v的点权= f1[v] (本身修改次数) + f1[parent[v]] (父亲修改次数) +f2[v] (儿子修改次数)该点父亲的点权=f1[parent[v]] (父亲修改次数) + f1[parent[pare...

题意：给与一个二分图，给边染色，连接同一端点的边的颜色不能相同，求最少用多少种颜色才能完成染色？ 思路：二分图最大匹配的匈牙利算法，对一条边进行染色，设一个端点最小可染的颜色为x，另一个端点最小可染的颜色为x.①x==y,该边染成x.②x<y,将该边强行染成x，最小可染颜色为y的点显然已经有了一条为x的边，所以将原先为x的边强行染为y，然后原先为x的边指向的点只好将原先为y的边再强行染成x（如果该点y颜色没有用，则该为边改为y，x颜色标识没用，条件可行），不断进行下去，直到可行为止。 代码： #include <bits/stdc++.h> #define inf 99824...

题意：给出一个n*m的矩阵，每一次取数从每一行中取一个数，每行取数的得分为每行所取数a[i][j] * ,k表示第几次取，且每次取数只能取头或者尾。求取完后的得分最大值？ 思路：我们可以发现每一行的取数只与当前行有关，所以该题相当于求n次数组中取数得分之和。我们可以区间dp解决。每一次不断增加区间长度，区间长度为1时相当于该数为最后一个取得。状态转化方程：dp[i][j]=max(dp[i+1][j]+(a[i]<<(j-i+1),dp[i][j-1]+(a[j]<<(j-i+1)));结果将每一行的dp[1][m]加起来就好。 注意：对于数据范围最好用__int12...