blowhail

题解

/ 注册

全部文章 / 题解（共43篇）

选择客栈

枚举右边的客栈，每次都先找距离当前客栈最近的蛮族最低消费小于p的客栈 (可以用一个数组来记录最近的小于p的客栈，如果第i个咖啡小于p，那么vis[i]=i,否则 vis[i]=vis[i-1]然后再计算最近的客栈左边的颜色和当前客栈相同的颜色的数量，加上即可 (颜色数量可以用一个二维数...

2020-09-07

0 756

南园满地堆轻絮

题意看了好久才明白(:з」∠)给一个序列a[],要求一个不会递减的数组b[]，并且b要满足|a[i]-b[i]|尽量小用二分找a与b的差值如果差值是x如果a[i]>=b[i-1],那b[i]=max(b[i-1],a[i]-x)如果a[i]<b[i-1]-x,那差值x就不成立其他情况就...

2020-09-06

0 623

XOR-pyramid

推导一下f的式子所以用dp[l][r]来表示区间l,r的答案就可以得到 dp[l][r]=dp[l][r-1] dp[l+1][r] #include <cstdio> #include <iostream> #include <algorithm> #incl...

2020-08-29

0 657

华华和月月种树

用dfs序来存这个树，然后来进行加权值和查询操作因为要添加节点，所以先提前把节点都算上，再在最后把多加的值给减去 #include <cstdio> #include <iostream> #include <algorithm> #include <cst...

2020-08-29

0 701

装货箱

n最大21个，直接dfs用一个数组来保存装箱的货物dfs的时候判断当前货物能不能放到箱子里在dfs前先从大到小排序一下，因为先放大的肯定是最优的方案 #include <cstdio> #include <iostream> #include <algorithm>...

2020-08-20

0 694

[SCOI2009]生日礼物

尺取法用一个数组来记录颜色，先固定左边，右移右边的范围，如果满足条件，再把左边的范围缩小，来找出最小的区间 #include <cstdio> #include <iostream> #include <algorithm> #include <cstrin...

2020-08-18

0 631

地斗主

推出前几项为1,5,11,36 ，直接用oeis找出规律(:з」∠)a(n) = a(n-1) + 5*a(n-2) + a(n-3) - a(n-4)因此，可以用矩阵快速幂来算[a(5),a(4),a(3),a(2)] = [a(4),a(3),a(2),a(1)] * #include &l...

2020-08-16

1 855

排座椅

因为行和列有不同的划分，所以要分别处理行和列每次输入两个人的坐标后，判断是在行还是列进行划分，在这一行(列)进行计数最后按照计数的大小排序一下即可因为输出要按照从小到大，所以再对序号进行一次排序 #include <cstdio> #include <iostream> #i...

2020-08-13

0 515

追债之旅

在最短路上进行一些改变将原本的dis[n] 改为dis[n][i] (i为天数然后用dijkstra，在计算的时候把天数算上去 #include <cstdio> #include <iostream> #include <algorithm> #include...

2020-08-12

0 727

蓝魔法师

做树形dp，dp[i][j]表示根为i的节点，连通块为j时的方案数在处理的时候有两种情况断开当前节点和儿子节点，那么直接将儿子节点的所有方案乘上当前节点的方案就行了如果不断开，那就需要合并，假设当前节点有p个连通块，儿子节点有q个那么dp[u][p+q]+=dp[u][p]*dp[v][q] #in...

2020-08-11

0 599