发表算法7 分钟读完 (大约1092个字)

D2T1：贪心、二分、并查集

一些技巧

常见的贪心技巧

货币使用问题：
尽可能少用，那么我们就先拿面值最大的，依次往下走，最后拿光了即可。

区间调度问题：
工作时间不能重叠，在可选工作中，每次都选取结束时间最早的作为选择，可以使工作量最大。

阅读更多
发表算法 / 动态规划10 分钟读完 (大约1483个字)

搜索与状压 DP

DFS

搜索和DP不分家，几乎所有的DP都能用搜索解决（虽然复杂度可能较劣）。不过，如果实在想不出正解，DFS不失为骗分的好手段。

主要的搜索算法有：

  1. DFS/BFS爆搜
  2. 双向BFS
  3. 启发式搜索（又称A*）
  4. 迭代加深搜索
  5. IDA*（迭代加深+启发式）
  6. 记忆化搜索
  7. 剪枝

重要程度：1,7,6 > 4,3 > 5,2。

阅读更多
发表算法 / 动态规划3 分钟读完 (大约411个字)

高级动态规划：区间、树形

区间 DP

P1880 [NOI1995]石子合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 220;

int ans, dp[N][N], n, a[N], s[N];

int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", a+i);
        s[i] = s[i-1] + a[i];
    }
    for(int i=1; i<=n; ++i) {
        s[i+n] = s[i+n-1] + a[i];
    }
    memset(dp, 0x3f, sizeof dp);
    for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    ans = 0x3f3f3f3f;
    for(int i=1; i<=n; ++i) {
        //printf("%d ", dp[i][i+n-1]);
        ans = min(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    
    memset(dp, 0, sizeof dp);
    for(int i=1; i<=2*n; ++i) dp[i][i] = 0;
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
            }
        }
    }
    ans = 0;
    for(int i=1; i<=n; ++i) {
        ans = max(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    return 0;
}

P1063 能量项链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int N = 220;

int n, h[N], t[N], dp[N][N];
int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &h[i]);
        h[i+n] = h[i];
    }
    for(int i=1; i<2*n; ++i) t[i] = h[i+1];
    
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=2*n; ++i, ++j) {
            for(int k=i; k<j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + h[i] * t[k] * t[j]);
            }
        }
    }
    int ans = 0;
    for(int i=1; i<=n; ++i) {
        ans = max(ans, dp[i][i+n-1]);
    }
    printf("%d\n", ans);
    return 0;
}


P3146 [USACO16OPEN]248 G

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

int n, dp[300][300], ans = 0;
int main() {
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &dp[i][i]);
    }
    
    for(int l=2; l<=n; ++l) {
        for(int i=1, j=l; j<=n; ++i, ++j){
            for(int k=i; k<j; ++k) {
                if(dp[i][k] == dp[k+1][j]) 
                    dp[i][j] = max(dp[i][j], dp[i][k]+1);
            }
            ans = max(ans, dp[i][j]);
        }
    } printf("%d\n", ans);
    return 0;
}

树形 DP

树形DP三大问题：树的最大独立集 树的重心 树的最长路径

阅读更多
Butterfly：添加全局吸底 Aplayer 播放器
发表Hexo6 分钟读完 (大约874个字)

Butterfly：添加全局吸底 Aplayer 播放器

以下步骤在 Butterfly主题上可以正常生效。如果你使用的是其他主题，可以根据情况自行适配。

配置播放器

解决与 hexo-tag-aplayer 的兼容问题

如果你没有安装过 hexo-tag-aplayer 插件，请直接跳过该步骤。

如果你安装过 hexo-tag-aplayer，请在 Hexo 的配置文件中修改以下设置：

阅读更多
C++ STL：SET & MULTISET
发表算法7 分钟读完 (大约982个字)

C++ STL：SET & MULTISET

定义

方式 效果
set <数据类型名> 集合名; 先定义一个容器，容器内无任何元素
set <数据类型名> 集合名(另一个集合名); 定义一个集合并用另一个集合初始化（只能是数据类型相同的集合，不能是数组）
set <数据类型名> 集合名(另一个集合名.begin(), 另一个集合名.end()); 定义一个集合并用另一个集合初始化（只能是数据类型相同的集合，不能是数组）
set <数据类型名> 集合名[集合数量]; 定义集合数组
set <Elem> 产生一个set，以 (operator <) 为排序准则
set <Elem, cmp> 产生一个set，以cmp为排序准则
阅读更多
Hexo：将你的博客部署到 Vercel
发表Hexo12 分钟读完 (大约1821个字)

Hexo：将你的博客部署到 Vercel

写在前面

近些日子，静态网站的热度又渐渐高了起来。相比于动态网站，静态网站具有轻量、无需服务器、利于SEO、速度快等特点，非常适合个人博客。再加上Hexo、Hugo等静态博客渲染框架的日渐成熟，已能与Wordpress、Typecho等老牌动态博客框架分庭抗礼。

与此同时，很多静态托管网站也应运而生。各种托管网站看似鱼龙混杂，其实由于各种原因，在国内能用的也就那么几家；如果你像我一样，没有服务器、没有备案，还想白嫖（），那么仅有的选择就更少了。综合各种因素，目前最适合托管静态博客的服务有：

阅读更多
Hexo：为你的博客配置 PWA
数论：整除问题
发表算法 / 数论2 分钟读完 (大约361个字)

数论：整除问题

整除分块

与其说整除分块是一种算法，不如说它是一个技巧。有时我们需要计算这样的式子：

$$
\sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor
$$

根据经验，我们发现 $\lfloor\frac{n}{i}\rfloor$ 只有 $O(\sqrt n)$ 种取值。对于每种取值，$i$ 都会有一个连续的范围。假设函数 $f$ 的前缀和可以预处理后快速求出，那么我们可以枚举 $\lfloor\frac{n}{i}\rfloor$ 的所有取值，并和 $f$ 的连续一段的和相乘。具体可以见代码：

1
2
3
4
5
6
7
// s[i] 为函数 f(i) 的前缀和 
int ans = 0;
for(int i=1, j; i<=n; i=j+1) {
    j = n/(n/i);
    ans += (s[j]-s[i-1])*(n/i);
}
printf("%d\n", ans);
阅读更多
图论
发表算法13 分钟读完 (大约2024个字)

图论

图论算法一般都是揉在一起的，很难单独把算法拆开讲，所以直接上题目吧。分类是大致分的，其实有很多是交叉的。

二叉树

二叉树的遍历有三种，分别为前序遍历，中序遍历和后序遍历，并且给定其中的两种遍历能够求出另一种遍历 (必须已知中序遍历)。

阅读更多
Hexo：配置 SSH 公钥部署
发表Hexo4 分钟读完 (大约574个字)

Hexo：配置 SSH 公钥部署

配置 git 使用 ssh 密钥

git 支持 https 和 git 两种传输协议。其实两种方式都可以，但是如果使用https协议，每次pull、push都要输入密码（大部分电脑上），所以建议使用ssh密钥对认证，可实现免密且更加安全。下面将介绍Hexo如何配置 SSH 公钥部署。

示例在Windows环境下。

阅读更多
关注我

分类

标签

AI3
Aplayer1
Butterfly1
DAG1
DFS3
GitHub1
Gulp1
Hexo4
LCA1
PB_DS1
PWA1
SSH1
STL2
Vercel1
二分图2
动态规划3
匹配2
单调队列2
博客4
双指针1
图书馆4
图论4
小说7
尺取法1
平衡树1
应用程序1
排序2
数学2
数据结构1
数论3
最小割1
最短路4
树1
游记1
码风1
算法26
网络流5
记忆化搜索4
部署3
随感1
随笔1

最新文章

归档

×