这题数据还是有点水啊，，四重循环过了。看到有大佬做了优化不过暂时没研究。关键步骤是想到我们按列划分子状态，每处理一个子三角后可以在它右边“贴上”一列技能点，贴上的边不能长于原三角右侧边长度+1，我们用dp[i][j][k]表示从左至右的第i列选了j个技能，总使用技能点数k情况下的最大收益，就可以写出状态转移式dp[i][j][k]=max(dp[i-1][j-1i-1][j(j+1)/2m])，复杂度n^3m。 #include<bits/stdc++.h> using namespace std; const int maxn=51; const int maxm=1301; ...

https://ac.nowcoder.com/acm/problem/19798 水题。推推公式发现，最终的答案等于求和（数列a的所有区间和w(区间长度)）。对于每一个区间长度k，共有n-k+1个区间和它对应。并且这些区间的区间和总和呈现出一种累加的、三角形式的关系，例如样例中k=2时区间和总和=a1+2a2+a3。且区间长度k和n-k对应的区间和总和是一样的。这个总和可以用前缀和递推O（1）地求出，所以整体复杂度On。 #include<bits/stdc++.h> using namespace std; #define ll long long const int ma...

https://ac.nowcoder.com/acm/problem/20265 补充数据范围：k<=15, c<=5我们尝试着模拟给砖块着色的过程，已经处理完[1,l]区间时，l+1位置可以安放除了color[l]之外任何一种颜色的砖块。这是一个很显然的状态转移的过程，接下来思考如何表示一个状态。如果朴素的表示，记录每种颜色剩了多少，那么是5^15的状态数，过大。这里我们要发现，剩余砖块数量相等的两种颜色，其实是“等价”的。于是我们可以把状态表示为：剩余砖块数量为i的颜色有多少种，这样的状态复杂度是15^5的，可行。具体来讲，设dp[a][b][c][d][e][last]表...

https://ac.nowcoder.com/acm/problem/14393 最初看到题目说父节点序号一定小还以为要搞什么大动作用树剖……结果想多了。在树上相距小于1的店就是自己、父亲、孩子们。为了O（1）计算每次这些点的权值和，我们记录三个数组（看代码,,cnt123），分别表示x被选中次数，x的孩子们被选中的次数和，x的孙子们被选中的次数和。这样val[x]=cnt1[x]+cnt1[fa[x]]+cnt2[x]，val[fa[x]]方法同上，val[sons]=cnt1[x]*sons.size+cnt2[x]+cnt3[x] #include<bits/stdc++.h&...

给一块矩形蛋糕，要求切成等面积的n个矩形，且长宽比的最大值最小。首先题目中的切n-1刀是很自然的，不需要去管，因为每一刀只能把一块切成两块，所以任何分割情况都是合法的。接下来看到n最大是10，那就很可能是指数级或阶乘级的算法，自然想到dfs。怎么搜呢？我们枚举每一刀的位置即可，对于当前矩形假如要把它切成k块，下一刀的取法只有2*(k-1)种方案，取最小的一种即可 #include<bits/stdc++.h> using namespace std; double dfs(double x,double y,double k){ if(k==1){ ret...

https://ac.nowcoder.com/acm/problem/20252 字符串最长50，求压缩后的最短长度。 这题的关键在于M。如果只有R，那么就是基础的区间dp，每次可以压缩时令dp(l,r) = min(dp(l,r), dp(l,mid)+1)，三重循环搞定。多出了规定“M”改变了什么呢？首先是每组压缩前要多一个字母，其次，如果[l, mid]中有M，那么它是不可以和[mid+1,r]合并的，这是因为题设中，末尾的R会优先匹配距离它近的M，而不是l之前的M。 所以我们每处dp要记录两个值，令dp[l][r][0]表示[l, r]中不出现M的情况下，最短的压缩长度；dp[l]...

https://ac.nowcoder.com/acm/problem/19810这题有个结论比较好猜……题目大意是，给定n要求构造一棵权值最大的树，如果一个点是父亲的重儿子，那么权值等于父亲，否则等于父亲权值+1，根权值=0。设i个节点的树的最大权值是dp[i]，然后当我们想构造一棵大小为n的树时，根节点是0，接下来n-1个点形成一个森林，设其中最大树大小为k，那么dp[n]的值就由这些子树的dp值构成，其中，对于除了重子树的节点，都有额外的权值1，所以dp[n]=dp[k]+sum(dp[ai])+n-1-k,其中sum(ai)=n-k-1,max(ai)<=k。所以核心算法就是，对...

https://ac.nowcoder.com/acm/problem/16645 这道题唯一需要注意的就是高精度了吧……思路很简单，首先发现可以每行单独处理，用dp[l,r]表示选择lr区间内的最大收益，有公式然后就在n2内处理一行，n3处理整个矩阵即可。值得一提的是高精度__int128不能在一般编译器上跑……并且它不支持cincout，需要自己准备io函数。 #include<bits/stdc++.h> using namespace std; const int maxn=81; __int128 dp[maxn][maxn],ans; int a[maxn][max...

题目链接 https://ac.nowcoder.com/acm/problem/14254 题目大意：给一个二分图（n<=1e3，m<=2e3），要求对它的边进行染色，相邻边（即有公共点的边）不能是同一种颜色，问最少用多少种颜色（k）能完成染色任务，并输出一组可行解（每条边的颜色为1~k间的数）。 在图论中有一个Vizing定理：二分图边着色所需最小颜色数，等于图中点的最大度数。我们设当前需要在u和v之间加一条边，设u点尚未用过的最小的颜色编号是x，v点尚未用过的最小颜色编号是y。那么如果x=y，就直接令边(u,v)的颜色是x（y）即可；如果x<y，我们依然令(u,v)的...

如题

I - A Boring Problem  题目大意  数列求和，其中每一项都是一个子段和的k次幂，例如： 给定原字符串为  “12345” 输出结果：1^k  (1+2)^k+2^k  (1+2+3)^k+(2+3)^k+3^k…… (1+2+3+4+5)^k+(2+3+4+5)^k+…+5^k                                        正常思路下，每个输出结果也需分别进行求和，即使用了快速幂，最后复杂度为 n^2log(n) 依然会超时，所以需优化。 将每个输出结果中的每一个加项用二项式定理展开，提取二项式系数，此时由n项变为了k项，复杂度可...

  出处：2016大连ICPC A 题意：有n个拳击手，其中一些人要进行m场拳击比赛。已知同场比赛的两名选手均可以分为高水平选手和低水平选手，并且有一些人的水平状况已经明确。需要根据选手之间的关系判断，这n个选手是否能分为高水平低水平两组。 解读：能分为两组，并不需要指明具体是某一组，例如样例中第二组，1345可拆为两组，2属于高水平组，则不管34是高水平还是低水平，最后都可以不产生矛盾地分为两组。 解题思路： 构建数组v[n]，存储这些选手的情况，1代表高水平，-1代表低水平； 构建数组edge[n][n]，记录选手之间有无比赛，有则为1，无则为0； 先假定可以分组，令flag...

在接触这个算法之前，一直觉得kmp巧夺天工，利用next数组的递推，实现对于模式串任一子串最大相同前后缀的找寻，继而在匹配目标串的过程中，一旦遇到失配情况，可以令 匹配起始下标 进行合理范围内最大的跳跃，从而将匹配整体复杂度从O(nm)降为O(m+n)。 a b c a b c ........ a b c a b k    可从目标串第二个 a 处开始匹配 shift-and算法与其思路基本相同，同样是找寻最大匹配长度，只不过它的实现基于更为方便快捷的位运算，算法的实现需要用到<bitset>这个头文件，点击查看其功能用法。bitset类实现了通过类似数组下标的方式访问对象...