blowhail

分类

题解(43)

/ 注册

全部文章（共43篇）

矩阵消除游戏

用二进制模拟行的选择，然后从大到小选列比如1010就是第2和4行被选中这样枚举，如果这一行被选，就加上这一行的值没有选中的就计算列的和，从大到小再选列即可 #include <cstdio> #include <iostream> #include <algorithm...

2020-08-11

0 684

购物

用dp来做，dp[i][j]表示第i天买j个糖果的最小值转移方程就可以写成dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)(j-k)) k的值从i-1到(i-1)m #include <cstdio> #include <...

2020-08-09

0 549

小A的最短路

先不看线缆，会发现，直接用lca求最短路就行了加上线缆，就多加一个判断即可比如询问x到y，线缆是j到k在dis(x,y)，dis(x,j)+dis(k,y)，dis(x,k)+dis(j,y)这三个中取最小 #include <cstdio> #include <iostream&...

2020-08-07

0 689

兔子的区间密码

要让异或后的值尽量大，那就应该让两个数的对于位置的值尽量不一样从l，r的最高位开始看，如果相同，那异或之后就是0了，因此直接不考虑继续往后面的位置看，当他们不一样的时候，一定是l当前位为0，r当前为1假如当前是第i位，那么l一定小于2^i,并且之后的每一位，都可以在异或后得到1所以，直接把l，r异或...

2020-08-04

0 605

Xor Path

因为要求所有路径的异或和，而异或又有个特殊性质a xor a =0因此只需要求每个点在最短路径上的出现次数可以通过计算与点相连的边的经过次数来计算点的次数 #include <cstdio> #include <iostream> #include <algorithm...

2020-08-03

0 613

Max Power

如果要学一个技能，需要把它整个倒三角的技能都学会所以，可以从右上角开始计算dp[i][j][k]表示第i列，第j行，学了k个技能转移方程就是：dp[i][j][k]=max(dp[i][j][k],dp[i+1][p][k-j]+a[j][i])p的值为从j-1到n-i+1 #include <...

2020-07-31

0 587

涂色PAINT

区间dp用dp[i][j]表示区间i~j的最小涂色次数如果i和j的颜色一样，就可以转化为dp[i][j-1]或者dp[i+1][j]如果不一样，就枚举i和j中间的每一个，计算dp[i][k]+dp[k+1][j]的值 #include <cstdio> #include <iost...

2020-07-30

0 526

乌龟棋

和之前的着色方案差不多用dp[a][b][c][d] ，a表示1的卡片，b表示2的卡片，c表示3的卡片，d表示4的卡片然后直接搜索就行了 #include <cstdio> #include <iostream> #include <algorithm> #inc...

2020-07-29

0 528

小A的柱状图

维护一个单调递增的队列，如果一个新的柱比之前的短，那就更新最大的矩形方案。 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include &...

2020-07-28

0 490

wpy的请求

要把一个带负边权的图改为非负的，并且还要最短路的路径不变可以利用spfa的缩放因为dis[v] > dis[u]+w 所以dis[u]-dis[v]+w > 0用一个节点作为超级源节点，与每一个的距离都是0，然后spfa进行缩放 #include <cstdio> #in...

2020-07-27

0 723