测试题目选的很好不是太难，也不是太简单

大盗阿福(动态规划)

动态规划：f数组表示前i个的最大值,转移方程 $f[i] = max(f[i-1], f[i-2] + w[i])$

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

using namespace std;

const int N = 100010;

int f[N], w[N];

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);

        f[1] = w[1];    //初始化，当只有一个商店时f[1] = w[i]
        for(int i = 2; i <= n; i ++)     
        {
            f[i] = max(f[i-1], f[i-2] + w[i]);
        }
        cout << f[n] << endl;
    }
    return 0;
}

六度分离(floyd)

floyd多源最短路:题目所说是任意两个不相邻的点之间最多间隔7个点，我们可以吧题目转化下，求这个点点与其他所有点之间的最小值，如果这两个点之间有关系则把这两点距离置为1，否则置为0x3f3f3f3f.然后求一遍最短路。另外注意到这题n的范围很小，所以就往那些耗时大的算法上想，比如dfs,bfs,递归等等，一般题目出题者设置的标准复杂度都是尽可能的大，然而不超时。

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

using namespace std;

const int N = 1100;

int g[N][N], n, m;

bool floyd()
{
    for(int k = 0; k < n; k ++)
    {
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < n; j ++)
            {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            if(g[i][j] > 7) return false;
        }
    }
    return true;
}

int main()
{
    int x, y;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        //从0~n-1 每两个不认识的人之间最大距离为7       
        memset(g, 0x3f, sizeof g);
        while(m --)
        {
            scanf("%d%d", &x, &y);
            g[x][y] = g[y][x] = 1;
        }

        for(int i = 0; i < n; i ++) g[i][i] = 0;
        if(floyd()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

滑动窗口(单调队列)

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

using namespace std;

const int N = 1e6 + 10;

int n, k, s[N];
int q[N], hh, tt;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) scanf("%d", &s[i]);

    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++)
    {
        if(hh <= tt && q[hh] < i-k+1) hh ++;
        while(hh <= tt && s[q[tt]] > s[i]) tt --;
        q[++ tt] = i;
        if(i >= k) printf("%d ", s[q[hh]]);
    }
    printf("\n");

    hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++)
    {
        if(hh <= tt && q[hh] < i-k+1) hh ++;
        while(hh <= tt && s[q[tt]] < s[i]) tt --;
        q[++ tt] = i;
        if(i >= k) printf("%d ", s[q[hh]]);
    }
    return 0;
}

$red and black$

这个题是bfs或者dfs的常规题目，第一先把图存下来，bfs一般用pair和队列.同时要注意是否对dist数组进行初始化，有的是-1，有的是0x3f3f3f3f,总之都是为了方便做题，初始化其他数也行。然后通过初始点想四周扩展，注意不要将重复的点加入队列。因此需要一个判重数组。其他就没啥了

 #include <iostream> //flood fill 算法 bfs()写法
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#define x first
#define y second

using namespace std;

const int N = 22;

typedef pair<int, int> PII;

int n, m, res;
char g[N][N];
bool st[N][N];

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

int bfs(int sx, int sy)
{
    queue<PII> q, res;//res 存放答案，q用来遍历g;sx sy 表示黑色瓷砖坐标
    q.push({sx, sy});
    res.push({sx, sy});

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++)
        {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if(st[xx][yy] == false && g[xx][yy] == '.' && 
             xx >= 0 && xx < n && yy >= 0 && yy < m)
             {
                 q.push({xx, yy});
                 res.push({xx, yy});
                 st[xx][yy] = true;
             }
        }
    }
    return res.size();
}

int main()
{
    while(scanf("%d%d", &m, &n) != EOF)
    {
        if(m == 0 && n == 0) break;
        memset(st, 0, sizeof st);
        for(int i = 0; i < n; i ++)
        {
            scanf("%s", g[i]);
        }
        int sx, sy;
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < m; j ++)
            {
                if(g[i][j] == '@')
                    sx = i, sy = j;
            }
        }
        int res = bfs(sx, sy);
        cout << res << endl;
    }
    return  0;
}

迷宫三

这个题也是bfs或dfs的应用

 #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 20;

int n, m;
char g[N][N];
int dist[N][N];

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

int bfs(int sx, int sy)
{
    memset(dist, -1, sizeof dist);
    queue<PII> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int distance = dist[t.x][t.y];

        for(int i = 0; i < 4; i ++)
        {
            int xx = t.x + dx[i], yy = t.y + dy[i];
            if(g[xx][yy] == '.' && xx >= 0 && xx < n && yy >= 0 &&
                yy < m && dist[xx][yy] == -1)
                {
                    dist[xx][yy] = distance + 1;
                    q.push({xx, yy});
                }
        }
    }
    bool success = false;
    int res = 2e9;
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(i == 0 || j == 0 || i == n-1 || j == m-1)
            {
                if(g[i][j] == '.' && dist[i][j] != -1){
                    res = min(res, dist[i][j]);
                    success = true;
                }
            }
        }
    }
    if(success) return res;
    else return -1;

}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        scanf("%s", g[i]);
    }
    int sx, sy;
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(g[i][j] == '@')
                sx = i, sy = j;
        }
    }
    int res = bfs(sx, sy);
    cout << res << endl;

    return 0;
}