blowhail

分类

题解(43)

/ 注册

全部文章（共43篇）

区间权值

把式子拆分之后可以发现，它是在区间长度为1-n的范围内求各种前缀和，可以用一些例子分析一下怎么计算如果n为6（对号代表要加上这些a[i]）可以发现，随着范围增加，会多出一部分的值，可以用 sum[n-i+1]-sum[i-1]来算这些多出的值（sum[i]代表前缀和）再继续往后的时候，会倒过来，4和...

2020-07-24

0 677

着色方案

对于每种油漆，如果它能涂的数量相同，那对结果贡献就是相同的，所以，用dp[a][b][c][d][e][las],a,b,c,d,e表示还能涂1,2,3,4,5个木块，las表示上一次涂的是哪一种剩余量的油漆。假如上一次涂的是剩余量为2的油漆如果当前 a 还有剩余，那么最终结果应该加上: ( a ...

2020-07-23

0 494

BOWL 碗的叠放

因为碗的数量很少，直接全排列求所有叠放情况就行了，然后考虑两个碗之间的关系。一共有四种情况1，如果上面的碗的底比下面的碗口大，那就直接堆上去2，如果上面的碗的碗口小于了下面的碗的底，那就放到下面的碗里面了3，上面的碗斜率小于下面的碗，再看有没有放到碗底4，下面的碗斜率小于上面的碗，看碗有没有完全放进...

2020-07-22

0 576

点权和

每次询问一个点，会让当前节点和父亲节点和儿子节点+1，而父亲节点和儿子节点受到影响之后，也会让祖父节点和孙子节点受到影响，所以我们用三个数组受到影响的次数来进行计算。定义a,b,c分别表示当前节点+1的次数，儿子节点+1的次数，孙子节点+1的次数。而父亲节点和祖父节点我们可以用fa[]来表示。每次询...

2020-07-21

0 550

生日快乐

每次切蛋糕只有两种情况，横着切和竖着切，并且最大只有10个人，所以直接dfs。如果切x，那么只能在x均分成n份的地方切，也就是x/n的倍数，模拟每种情况即可。 #include <cstdio> #include <iostream> #include <algorit...

2020-07-20

0 506

压缩

如果没有M的话，是一个正常的区间dp，我们可以列出来它的转移方程① dp[l][r]=min( dp[l][r] , dp[l][j] + dp[j+1][r] );如果当前区间（l，r）前半段和后半段相同，那就将它压缩一半然后加上一个R：② dp[l][r]=min( dp[l][r] , dp[...

2020-07-18

0 464

kingdom

题意看了好久才明白什么意思(:з」∠)一开始以为只有最底部的节点需要传递信息，但其实是每个官员都要传递信息。比如这个图，红色是国王，蓝色的三个是非重儿子的节点（还有其他节点没画），传递信息的时候，蓝1传给国王花费1，蓝2是蓝1的重儿子，传给蓝1不花费，蓝1再传给国王再花费1，蓝3传给蓝1花费1，再...

2020-07-17

0 664

矩阵取数游戏

思路：因为是在每行的首尾取数，所以每行都互不相关，因此分别对每行进行处理就行了。每次取首尾一个数，就可以转化为在区间（l，r）中取max( dp[l][r-1]+a[r],dp[l+1][r]+a[l])。注：数据会爆long long ，可以用int128 #include <cstdi...

2020-07-16

0 943

Color

题意：给一个二分图染色，有公共点的边不能同色，求最小的颜色方案。思路：因为有公共点的边不能染同种颜色，所以，连的边最多的点就是要染的颜色数量了。方案的求法，可以先从度最大的点开始，求出最大匹配，然后染色，之后再找下一个度最大的求最大匹配，染色。 #include <cstdio>...

2020-07-15

0 704

最短路

思路：因为边的数量最多比点多100个，所以先把多余的那些边去掉，用lca计算最短路，然后再把多余的边加上，再对这些多余的边进行bfs。去掉和加上多余边的方法：在存图的时候，利用并查集判断一下，如果这两个点有同一个父亲节点，那就证明这个边是多余的，就先把它给存起来而不加到图里。 #include &...

2020-07-13

0 680