tire树，经常被用来做字符串插入，和字符串查找，省时省空间

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 1E5+10;
int a[N][26];
int idx,p,u;
char str[N];
int cnt[N];

void insert(char *str)
{
    p=0;
    for(int i=0;str[i];i++)
    {
        u=str[i]-'a';
        if(!a[p][u]) a[p][u]= ++idx;
        p=a[p][u];
    }
    cnt[p]++;
}

int query(char *str)
{
    p=0;
    for(int i=0;str[i];i++)
    {
        u=str[i]-'a';
        if(!a[p][u]) return 0;
        p=a[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    cin>>n;
    char op[2];
    for(int i=0;i<n;i++)
    {
        scanf("%s%s",op,str);
        if(*op=='I') insert(str);
        else printf("%d\n",query(str));
    }
   return 0;
}

#include <iostream>
using namespace std;
const int N=110;
int t,n;
int g[N][N];
char c;
int ex,ey,sx,sy;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool dfs(int x,int y)
{
    g[x][y]=1;
    if(x==ex&&y==ey) return true;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>n-1||b<0||b>n-1) continue;
        if(g[a][b]) continue;
        g[a][b]=1;
        if(dfs(a,b)) return true;

    }
    return false;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int  i=0;i<n;i++)
            for(int j=0;j<n;j++)
                g[i][j]=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                char c;
                cin>>c;
                if(c=='#')
                    g[i][j]=1;
                else g[i][j]=0;
            }
        cin>>sx>>sy>>ex>>ey;
        if(g[sx][sy]||g[ex][ey])
        {
            cout<<"NO"<<endl;
            continue;
        }
        if(dfs(sx,sy))
            cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

[USACO10OCT]Lake Counting S

题面翻译

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个 $N\times M(1\leq N\leq 100, 1\leq M\leq 100)$ 的网格图表示。每个网格中有水（W） 或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入第 $1$ 行：两个空格隔开的整数：$N$ 和 $M$。

第 $2$ 行到第 $N+1$ 行：每行 $M$ 个字符，每个字符是 W 或 .，它们表示网格图中的一排。字符之间没有空格。

输出一行，表示水坑的数量。

题目描述

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.

输入格式

Line 1: Two space-separated integers: N and M * Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.

输出格式

Line 1: The number of ponds in Farmer John’s field.

样例 #1

样例输入 #1

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

样例输出 #1

3

提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 110;

int n, m;
char g[N][N];
bool st[N][N]; //存状态：淹没淹过
int res = 0;

int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

void dfs(int x, int y){
    for(int i = 0; i < 8; i++){
        int a = x + dx[i], b = y + dy[i];

        if(a < 0 || a >= n || b < 0 || b >= m) continue;
        if(g[a][b] != 'W') continue;
        if(st[a][b]) continue;

        st[a][b] = true;
        dfs(a, b);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%s", g[i]);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j< m; j++){
            if(g[i][j] == 'W' && !st[i][j]){
                dfs(i, j);
                res++;
            } 
        }
    }
    printf("%d\n", res);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

struct Range
{
    int l,r;
    bool operator< (const Range&W)const
    {
        return l < W.l;
    }
}range[N];    //重载小于号，使其以左端点进行排序

int main()
{
    int n,d;
    cin >> n>>d;
    for(int i = 0;i < n;i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(y > d) 
        {
            cout<<-1;
            return 0;
        }
        double dt = sqrt(d*d - y*y);        //勾股定理求x的长
        range[i] = {x-dt, x + dt};      //线段范围
    }

    sort(range,range + n);  //左端点排序

    int res = 1;
    int maxr = range[0].r;      //初始化为第一条线段的右端点
    for(int i = 1;i < n;i ++)   //从第二条线段开始遍历
    {
        if(range[i].l <= maxr) maxr = max(maxr,range[i].r); //如果当前线段左端点比上一个右端点小，说明能合并
        else        // 当前线段左端点比右端点大，不能合并，更新
        {
            res ++;
            maxr = range[i].r;
        }
    }

    cout << res << endl;

    return 0;
}

有人知道哪里出问题了吗

f[i][j]:考虑前i种糖果，且总和除以k的余数是j的方案

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;

int n,k;
int w[N];
int f[N][N];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>w[i];
    //f[0][1]...[k-1]，余数不可能大于1，所以这些方案都不合法
    memset(f,-0x3f,sizeof f);
    //当一种糖果都不考虑，且余数为0的糖果总量为0
    f[0][0] = 0;
    //这里必须这么写：因为j代表的是个余数
    //j-w[i]是非常必要的，很有可能是负数，必须要转换成正数
    //不是普通背包里转换成当前背包容量是j，减去第i个包的重量
    //原理不太一致
    // (x+k)%k---转换成正数
    //(j-w[i])%k 这是那个x，一步都不能省略的！！
    for(int i=1;i<=n;i++)
        for(int j=0;j<k;j++)
        {
            f[i][j]=max(f[i-1][j],f[i-1][((j-w[i])%k+k)%k]+w[i]);
        }
    //从n种糖果考虑，且除以k的余数是0的最大糖果数量
    cout<<f[n][0]<<endl;
    return 0;

}

完全背包问题

动态规划

完全背包问题相对于01背包问题改变的就是第$i$个物品选取的数量，01背包最多就只能选一个，而完全背包只需要在体积允许的条件下选取任意个数，然后取$max$即为只从前$i$个物品中选且总体积不超过$j$的集合的最大值。
数组：$f[i][j]$
状态转移方程：$f[i][j] = max\{f[i][j], f[i - 1][j - k * v[i]] + k * w[i]\}$ $(k从0开始枚举)$

$Java$ 代码

import java.util.*;

public class Main {
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 1; i <= n; i ++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                for (int k = 0; k * v[i] <= j; k ++) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                }
            }
        }
        System.out.print(f[n][m]);
    }
}

优化时间

我们发现，上述的算法时间复杂度比较高，有3重循环，那么我们来考虑是否可以优化。

从$f[i][j]与f[i][j - v]$的关系出发，看能否推导除直接的关系，那么就可以省略$k$这一层的循环了。

$f[i][j] = max\{f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, …, f[i - 1][j - k_1v] + k_1w\}$

$f[i][j - v] = max\{f[i - 1][j - v], f[i - 1][j - 2v] + w, …, f[i - 1][j - (v + k_2v)] + k_2w\}$

由$k_1, k_2$的含义可知，$k_1v = j$, $v + k_2v = j$, 所以化简得$k_1 = k_2 + 1$。

故，$f[i][j - v] = max\{f[i - 1][j - v], f[i - 1][j - 2v] + w, …, f[i - 1][j - (v + (k_1 - 1)v)] + (k_1 - 1)w\}$

我们可以惊奇地发现，$f[i][j - v]$与$f[i][j]$除去第一项的其他部分，每一项之差为$w$，所以，

$f[i][j] = max\{f[i - 1][j], f[i][j - v] + w\}$

$Java$ 代码

import java.util.*;

public class Main {
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 1; i <= n; i ++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i ++) 
            for (int j = 1; j <= m; j ++) {
                f[i][j] = f[i - 1][j];
                if (j >= v[i]) f[i][j] = Math.max(f[i - 1][j], f[i][j - v[i]] + w[i]);
            }
        System.out.print(f[n][m]);
    }
}

进一步优化空间

这里优化空间的思路同01背包，只是枚举$j$的顺序是从小到大，01背包是从大到小（需要理解原理）。

import java.util.*;

public class Main {
    static final int N = 1010;
    static int[] v = new int[N], w = new int[N], f = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 1; i <= n; i ++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i ++) 
            for (int j = v[i]; j <= m; j ++) {
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
        System.out.print(f[m]);
    }
}

发现题库存在一个专题和股票有关，便特开此专题（多处参考彩色铅笔 题解）

acwing。1055 股票买卖2

题目描述

给定一个长度为 $N$ 的数组，数组中的第 $i$ 个数字表示一个给定股票在第 $i$ 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式

第一行包含整数 $N$，表示数组长度。

第二行包含 $N$ 个不大于 $10000$ 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

$1 \le N \le 10^5$

输入样例1：

6
7 1 5 3 6 4

输出样例1：

7

输入样例2：

5
1 2 3 4 5

输出样例2：

4

输入样例3：

5
7 6 4 3 1

输出样例3：

0

样例解释

样例1：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例2：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 0。

算法一、动态规划—>状态机模型

时间复杂度

$ O (n) $

空间复杂度

$ O (n) $

代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 110;
int f[N][2];
int n;

int main()
{
    cin >> n;
    f[0][1] = -0x3f3f3f3f;
    for (int i = 1; i <= n; ++ i)
    {
        int w;
        cin >> w;
        f[i][0] = max(f[i - 1][0], f[i - 1][1] + w);
        f[i][1] = max(f[i - 1][0] - w, f[i - 1][1]);
    }
    cout << f[n][0];
    return 0;
}

算法二： 贪心

#include <iostream>
using namespace std;
int n, ans, pre, w;

int main()
{
    cin >> n >> pre;
    for (int i = 1; i < n; i ++)
    {
        cin >> w;
        if (w - pre > 0) ans += w - pre;
        pre = w;
    }
    cout << ans;
    return 0;
}

acwing1057、买卖股票4

状态机 O(nk)

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 110;
int f[N][M][2];
int n, K;
int main()
{
    cin >> n >> K;
    if (K > n / 2) K = n / 2;
    for (int j = 0; j <= K; j ++) f[0][j][0] = f[0][j][1] = -0x3f3f3f3f;
    f[0][0][0] = 0;
    for (int i = 1; i <= n; i ++) 
    {
        int w;
        cin >> w;
        for (int j = 0; j <= K; j ++) // 已经进行了j次交易
        {
            //f[i][0][0] = f[i - 1][0][0];
            if(j) f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][1] + w);
            f[i][j][1] = max(f[i - 1][j][0] - w, f[i - 1][j][1]);
        }
    }
    int res = 0;
    for (int i = 0; i <= K; i ++) res = max(res, f[n][i][0]);
    cout << res << endl;
    return 0;
}

待更新.......