小A的柱状图 区间[L,R]中矩形的高度取决于[L,R]中高度的最小值。如果下一个矩形高度比当前矩形高度小，这块矩形的高度就不可能再成为满足条件的矩形的高度。于是就可以把高度比下一块矩形大的矩形都删掉，用一个高度为下一个矩形的高度，宽度为删掉的矩形宽度和下一个矩形宽度的累加和代替。用单调栈维护，更新单调栈时更新答案。 代码： #include<bits/stdc++.h> using namespace std; typedef long long LL; const int MAX_N=1e6+5; LL st[MAX_N]; LL w[MAX_N]; int l,r; int...

生日快乐题解 题解 ： 这个题数据范围较小，可以直接尝试枚举所有切割情况。 题目中有要求，将蛋糕分成大小相等的n块，每一次切割的线一定与一条边平行。所以首先每一刀有两种切法，与长边平行和与短边平行。为了能够将蛋糕n等分，那么当前这一刀可以是过长边的一个n等分点并与短边平行，或过短边的一个n等分点与长边平行。 代码： #include<bits/stdc++.h> using namespace std; typedef long long LL; const int MAX_N=2e6+20; const int INF=0x3f3f3f3f; const LL MOD=1926...

点权和题解 题目分析： 一道以空间换时间的题目。关键在维护什么和怎么维护才能高效地得到答案。通过仔细又认真地观察，再加上一点灵感，可以发现。每个点位置处地答案可以由这个点和与它距离小于等于2点的更新次数马上得到。设有一个点，记为v，如果我们知道下面几个量，那么此时v处的答案可以在O(1)的时间马上得到： 当前结点父亲的父亲的更新次数cntff 当前结点的父亲的更新次数cntf 当前结点的更新次数cnt 当前结点所有儿子的更新次数cntc 当前结点所有孙子的更新次数cntcc 当前结点兄弟结点的更新次数cntb 当前结点的度数deg 若已知了上面几个量，那么v处此时的答案为： 为了可以在O(...

[SCOI2007]压缩 题解很显然是一个dp。。。很妙的一个dp,很难的一个dp。。。因为M，R存在造成的不同结果，需要分类讨论。记: dp[i][j][0]为区间[i,j]不加M时最短长度 dp[i][j][1]为区间[i,j]有M时最短长度 那么转移方程为：dp[i][j][0]=min(dp[i][k][0]+i-k)| i<=k<=jdp[i][j][0]=min(dp[i][j][0],dp[i][(i+j)/2][0]+1)|如果可以被压缩的话dp[i][j][1]=min(min(dp[i][k][0],dp[i][k][1])+1+min(dp[k+1][j]...

I题题解 这道题和HDU 3551是一样的。关键在拆点建图上把点v拆成d[v]个点。同时将每条边拆成2个点分别为。将相连。同时将与拆成的个点连边，将与拆成的个点连边。如题目中样例的第三组数据： 3 21 1 21 32 3 第1个点拆成1个点，编号为1。第2个点拆成1个点，编号为2。第3个点拆成2个点，编号分别为3，4第1条边拆成两个点，编号为5，6。（5，6）（5，1）（6，3）（6，4）连边。第2条边拆成两个点，编号为7，8。（7，8）（7，2）（8，3）（8，4）连边。注意这里的边是无向边。建图之后跑一般图匹配。如果是完全匹配输出“yes”，否则输出“no” 为什么这样可行？ 将每...

分析： 开始看到这个题的时候，我就想着去构造这样一棵树，可是构造失败了。这个题的数据范围是8000，其实已经提示了构造可能是不可行的，否则这个数据范围要更大才对。于是看了大佬的题解,想了好长时间才恍然大悟。 树形结构有着很好的对称性，这种对称性是指当拿掉一个结点后，这个结点所连接的几个部分仍然是树。这就意味着一个子树上的答案的求解过程很有可能和这个结点上的答案的求解过程有一定的相似性。和在遇到树形结构的问题时可以先思考一个结点上的答案是否可以由它的子树转移而来，从而将问题的规模缩小。这也是树形DP的基本思路之一。这个题有下面几个特点： 1. 一个结点的子树中，有一个特殊的“心腹”2. 树的结...

题目描述： 一颗个节点的树。给定个点集（个帮派），编号为。第i个点集代表第i个帮派占据的点的集合。定义一个节点被占领当且仅当满足下面其中一个条件： 该结点被一个帮派所占据。 该结点位于被占领的两个结点的路径上。 Q个询问，每个询问给出一个点，一个数，和个数（），代表在这个询问中选取（）这个帮派，在此次询问中只考虑这个帮派，问结点V距最近的一个被占领的结点的距离。 数据范围：1≤n,k,Q≤500000, 1≤每个帮派占据城市数之和≤500000, 1≤每个询问中考虑的帮派数之和≤500000建议好好读一下原题目，涉及的量比较多。不是很好理解。 题目分析： 麻烦的一道题。为了解决这个题，首...

分析： 这个题用到了树的以下性质：如果两个节点位于同一个节点的两个不同子树上，那么这连接两个点的最短路径一定经过这个节点。根据这个性质，很显然在树中新加入一个点时，只有两种情况 使用一种新的颜色 使用和相连的点相同的颜色 设f[i][j]表示前i个点使用j种颜色涂色的方案数于是就有了转移方程： f[i][j]=f[i-1][j]+f[i-1][j-1]*(k-(j-1))代码： #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> P; c...

题目大意： 有一个长度为n的数列，要求在这个数列中选2个不相交且长度都为k的区间，求这两个区间中数字和最大的值 算法过程 A[i]表示长度为k且以i为最后一个元素的这个区间元素值的和dp[i]表示选择的第二个区间以第i个元素结尾所求和的最大值维护一个tmp，表示在前i-k个元素中长度为k的区间和最大值那么状态转移方程为 dp[i]=tmp+A[i]代码： #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> P; const int INF=0x3f...

题目大意： 有两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。需要求出所有可能的C中长度最大的回文子串（这里的字串是指连续的），输出这个最大长度即可 算法过程 嗯，区间dp。以前没写过。学会了区间dp要按长度枚举。dp[i][j][k][l]表示A的（i，j）与B的（k，l）区间内的字符是否能合并为一个回文串状态转移： if(A[i]==A[j]&&dp[i+1][j-1][k][l]) dp[i][j][k][l]=1; if(A[i]==B[l]&&amp...

题目地址：http://codeforces.com/contest/1348/problem/D 大意：第一天有一个细胞质量为1，每一天白天细胞可以发生分裂（任意个发生分裂，前后质量守恒），晚上细胞质量增加（每个细胞质量增加1）。给定一个n，问至少要多少天，细胞总质量恰好达到为n（2≤n≤1e9）。 分析： 先考虑分裂，分裂不会对细胞的总质量带来任何影响，只是会影响晚上细胞质量增加的值。若当前细胞数量为x，那么晚上细胞可以增加的质量dm满足x≤dm≤2x。 我们可以确定的是细胞增加最快的情况是：每一天白天所有细胞都发生分裂。但是这样不能保证最后细胞总质量恰好达到n。 计算x为满足的...

题目大意： 有N个轮子，每个轮子有一个属性（转速）。轮子之间M个二元关系，每个关系有4个属性u，v，x，y。表示轮子u和v的转速比值为x：y。问：这m个关系是否相容。（即可以同时满足）。一共T组询问T ≤ 32，N ≤ 1000，M ≤ 10000且x与y的绝对值均不超过10。 分析： 设第i个轮子的转速为。若:已知且:已知，那么:为一可计算的确定的值。若此时题目中给出与的比值且这个比值与求出来的比值不相等，就可以说明不相容。为了实现这个判断，我弄了一个fr[]数组，来判断节点是否“自由”（就是说转速是不是任意的，如果是就把这个节点的转速置为1。然后和它相连的节点的转速都可以计算了），注意同一...

题目大意：题目给定两个数n和m（1<=n<=5000,0<=m<=1e9）要求构造一个数列A，A中元素 大于等于1，小于等于1e9且满足严格递增 满足ai+aj=ak的（i,j,k）恰好有m个 如果有没有这样的A输出-1。 分析：如果ai和aj确定，那么ak唯一。也可以说任意两个可以决定第三个。 首先可以猜想当A为1到n的连续自然数时这样的三元组最大。（容易用数学归纳法证明。利用下面红字得到的结论，一个一个加。em。。。） 假如前s个数已经确定为1到s的自然数按顺序的排列，当增加第s+1个数时，满足条件的（x，y，s+1）的个数就是满足as+1-...

由最大公因数的性质:且，易得到结论：对于每一个询问，我们只需在到这个区间中找到一个，使得对任意的成立。 算法1先考虑最朴素的做法：对于每一次询问，求出到这个区间中的每一个数与的最大公因数，并记录最大的那一个。时间复杂度(为最大值)，很显然，对于本题的数据规模这个复杂度是不够的。 观察这个题的特点，发现虽然和都比较大，但是和被限制在的范围内。这个条件很有可能成为解题的关键。涉及到最大公因数的问题，如果朴素的算法不能解决，那么从因子的角度去考虑无疑是一个有益的尝试。那么问题的关键就聚焦于：1.找到的一个因子，使得在到这个区间内可以找到一个,满足(即d也是的一个因子)2.最大 朝这个方向思考于是...