如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。

M_sea 的博客

歩み続けて 辿り着く先へと

洛谷2144 [FJOI2007]轮状病毒

Luogu分析打表找规律：n=1 ans=1 n=2 ans=5 n=3 ans=16 n=4 算不出那就分析前三项，发现：$1=1\times 1,5=3\times 3-4,16=4\times 4,...$看样子是平方数，不过好像有变化——偶数项要减4。然后要平方的数是可以递推的，$f[1]=1,f[2]=3,f[i]=f[i-2]+f[i-1](2)$。到此递推式已经明显了，不过有一...

  • M_sea
  • 2017 年 09 月 03 日
  • 暂无评论

    • 洛谷1228 地毯填补问题

    Luogu分析很裸的分治题，建议将样例输出画出来。把公主视作一个已填的格子，将棋盘四分，在原棋盘中间放一块地毯（分出的四块中哪一块有障碍哪一块就不填）。然后递归（左下->左上->右下->右上）处理四块小棋盘。注意边界：当小棋盘为1*1时直接返回即可。代码#include <algorithm> #include <iostream> #include...

  • M_sea
  • 2017 年 09 月 01 日
  • 1 条评论

    • 洛谷1901 发射站

    Luogu分析先处理左边：维护一个栈顶向栈底递增的单调栈，每次进栈则处理下面的元素；再处理右边：反过来即可。那么为什么可以这样呢？对于每一个发射站，它只能影响到最左边的比它高的元素。对于进栈时pop出去的元素，它们肯定不会比新进栈的元素高，所以可以直接舍去。每次进栈时把能量加上，就解决了此题。代码#include <algorithm> #include <iostream...

  • M_sea
  • 2017 年 08 月 29 日
  • 暂无评论

    • 洛谷2342 叠积木

    Luogu分析带权并查集裸题？代码#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; int root[30010]; //父节点（下面的一摞积木） ...

  • M_sea
  • 2017 年 08 月 29 日
  • 暂无评论

    • 洛谷1220 关路灯

    Luogu分析设$f[i][j][0]$表示$i$到$j$的路灯、最后关$i$最小用电量，$f[i][j][1]$表示$i$到$j$的路灯、最后关$j$最小用电量。那么答案为 $min(f[1][n][1],f[1][n][n])$用前缀和数组sum来记录电量，则可以在O(1)时间内算出区间电量和。容易转移：$f[i][j][0]=min((a[i+1]-a[i])*(sum[n]-sum[...

  • M_sea
  • 2017 年 08 月 29 日
  • 暂无评论

    • 洛谷2822 组合数问题

    Luogu算法注意到组合数的递推公式：$c[i][j]=c[i-1][j]+c[i-1][j-1]$所以我们可以先把$c$打出来，记得$mod\ k$。然后判断这个数是否能被k整除，是的话就统计。然后离线做就行了。代码#include <cstdio> #include <iostream> #include <cstring> using namespa...

  • M_sea
  • 2017 年 08 月 29 日
  • 暂无评论

    • 洛谷1040 加分二叉树

    Luogu算法这是一道区间DP的题目。设$f[i][j]$表示第i个节点到第j个节点的最大加分，则有：$f[i][j]=max (f[i][root-1]*f[root+1][j]+v[root]) $其中$root$是枚举的树根，$v[i]$表示第i个节点的权值。可以写记搜。代码#include <algorithm> #include <iostream> #in...

  • M_sea
  • 2017 年 08 月 29 日
  • 暂无评论

    • 洛谷1064 金明的预算方案

    Luogu分析这是一道经典的依赖背包问题，我们可以对应到分组背包来解决。把主件与其附件集看成一个组，那么这个组会有5种选择：只选主件选主件和附件1选主件和附件2选主件和两个附件都不选对于一些没有两个附件的主件，我们可以手动添加一个附件，其花费、重要度都为0。这样就成功转化成了分组背包。代码#include <algorithm> #include <iostream>...

  • M_sea
  • 2017 年 08 月 29 日
  • 暂无评论

    • 洛谷1855 榨取kkksc03

    Luogu分析二维费用背包裸题，设$f[i][j][k]$表示对于前i个人用j时间和k金钱满足的最多愿望数。对应到背包问题，压缩一维，则$f[i][j]$表示当前阶段用i时间和j金钱满足的最多愿望数。那么第i件物品的价值是什么呢？就是1，因为问题问的是最多愿望数。代码#include <algorithm> #include <iostream> #include &...

  • M_sea
  • 2017 年 08 月 29 日
  • 暂无评论

    • 洛谷1541 乌龟棋

    Luogu分析这是一道较水的DP题。我们用$f[i][j][k][l]$表示用i张1、j张2、k张3、l张4所能达到的最大分数。自然写出状态转移方程：$f[i][j][k][l]=max(f[i-1][j][k][l],f[i][j-1][k][l],f[i][j][k-1][l],f[i][j][k][l-1])+a[1+i+2j+3k+4l]$代码#include <algorit...

  • M_sea
  • 2017 年 08 月 29 日
  • 暂无评论