dfs(暴力枚举) $O(n^2)$

这题的方案数相当于是求组合数问题
但是带行列限制 不然可以直接输出组合数了
试图利用这个优化 但是看起来挺失败的 699ms

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 10;

int n, k;
//存储可以放棋子的地方的坐标
PII g[N * N];
//z是g的数组长度
int z, cnt;
bool st[N * N], cols[N], rows[N];

void dfs(int u, int h)
{
    if(u == k)
    {
       cnt++;
       return;
    }

    //h是这个状态的最高位 因为是排列数所以比他低的用不上
    for(int i = h; i<z; i++)
    {
        if(st[i] || cols[g[i].first] || rows[g[i].second])
        {
           continue; 
        }
        //显而易见的判断、选择和回溯了
        st[i] = cols[g[i].first] = rows[g[i].second] = true; 
        dfs(u + 1, i);
        st[i] = cols[g[i].first] = rows[g[i].second] = false;
    }
}

int main()
{
    while(scanf("%d %d", &n, &k), n != -1 && k != -1)
    {
        z = cnt = 0;
        for(int i = 0; i<n; i++)
        {
            getchar();
            for(int j = 0; j<n; j++)
            {
                char t = getchar();
                //只需要棋盘区域的坐标 空白区域用不上
                if(t == '#')
                {
                    g[z++] = {i, j};
                }
            }
        }

        dfs(0, 0);
        printf("%d\n", cnt);
    }
}

 // 要求每一层最右边的节点，直接宽搜，输出每一层最右边的节点即可
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        // 定义一个队列，用于宽度搜索
        queue<TreeNode*> que;
        vector<int> res;
        if(root) que.push(root);
        while(que.size()){
            // 同一层的节点连续被放进去，记录当前层的长度
            // 以保证本次遍历都是当前层的，并且输出最后一个元素
            int len = que.size();
            for(int i = 0; i < len; ++i){
                auto tmp = que.front();
                que.pop();
                // 把下一层的节点从左到右放到队列中
                if(tmp->left) que.push(tmp->left);
                if(tmp->right) que.push(tmp->right);
                // 输出最右边的元素
                if(i == len - 1) res.push_back(tmp->val);
            }
        }
        return res;
    }
};

[USACO11OPEN]Corn Maze S

题面翻译

奶牛们去一个 $N\times M$ 玉米迷宫，$2 \leq N \leq 300,2 \leq M \leq300$。

迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。

如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。

玉米迷宫除了唯一的一个出口都被玉米包围。

迷宫中的每个元素都由以下项目中的一项组成：

1. 玉米，# 表示，这些格子是不可以通过的。
2. 草地，. 表示，可以简单的通过。
3. 传送装置，每一对大写字母 $\tt{A}$ 到 $\tt{Z}$ 表示。
4. 出口，= 表示。
5. 起点， @ 表示

奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 $1$ 个单位时间。从装置的一个结点到另一个结点不花时间。

题目描述

This past fall, Farmer John took the cows to visit a corn maze. But this wasn’t just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both directions: a cow can slide from the slide’s start to the end instantly, or from the end to the start. If a cow steps on a space that hosts either end of a slide, she must use the slide.

The outside of the corn maze is entirely corn except for a single exit.

The maze can be represented by an N x M (2 <= N <= 300; 2 <= M <= 300) grid. Each grid element contains one of these items:

* Corn (corn grid elements are impassable)

* Grass (easy to pass through!)

* A slide endpoint (which will transport a cow to the other endpoint)

* The exit

A cow can only move from one space to the next if they are adjacent and neither contains corn. Each grassy space has four potential neighbors to which a cow can travel. It takes 1 unit of time to move from a grassy space to an adjacent space; it takes 0 units of time to move from one slide endpoint to the other.

Corn-filled spaces are denoted with an octothorpe (#). Grassy spaces are denoted with a period (.). Pairs of slide endpoints are denoted with the same uppercase letter (A-Z), and no two different slides have endpoints denoted with the same letter. The exit is denoted with the equals sign (=).

Bessie got lost. She knows where she is on the grid, and marked her current grassy space with the ‘at’ symbol (@). What is the minimum time she needs to move to the exit space?

输入格式

第一行：两个用空格隔开的整数 $N$ 和 $M$。

第 $2\sim N+1$ 行：第 $i+1$ 行描述了迷宫中的第 $i$ 行的情况（共有$M$个字符，每个字符中间没有空格）。

输出格式

一个整数，表示起点到出口所需的最短时间。

样例 #1

样例输入 #1

5 6
###=##
#.W.##
#.####
#.@W##
######

样例输出 #1

3

提示

例如以下矩阵，$N=5,M=6$。

###=##
#.W.##
#.####
#.@W##
######

唯一的一个装置的结点用大写字母 $\tt{W}$ 表示。

最优方案为：先向右走到装置的结点，花费一个单位时间，再到装置的另一个结点上，花费 $0$ 个单位时间，然后再向右走一个，再向上走一个，到达出口处，总共花费了 $3$ 个单位时间。

看法

这题非常坑，只是传统BFS加个传送门，让这个题难度倍增，调了几个小时，服了
首先看坑点

传送点只是一个中介点
#   #   #   #   #   #   =   #   #
#   .   .   .   .   .   .   #   #
#   #   #   A   #   #   #   #   #
#   @   .   .   #   A   .   .   #
#   #   #   #   #   #   #   #   #

这说明存在正解路径是经过传送门走一步又回来才能到达终点
这个传送门性质特殊
这就需要考虑怎么判重，防止多次无用的进入传送门
尝试这么做：
可以发现传送门只会进一次，之后再尝试进入传送门的路径都不是最短路
那么我们不管传送前那个点，让它dist还是-1（用来判重），然后给传送后的位置设置距离后加入队列行不行呢
实际上不行，问题很隐蔽，因为可能在传送后位置还在队列没出来时候，发生了如下事情：

(注意考虑bfs队列位置对应距离可能存在相差为1的两个值)
有路径进入传送后位置，把它当作起跳点传送，这样落脚点（就是原来传送前那个dist是-1的位置）的距离被更新成正的
之后有路径进入传送前位置（这个路径更新前距离比之前的大1），然后传送后的位置距离被设置为比原来多1的结果

这样在它出来时候，它的距离不是原来和他对应的那个值，这样就产生了错误，具体来说：
1.bfs角度：不能保证bfs中一旦进入队列那么该点入度已经为0的特点
2.根据dijk最短路原理,先从队列里出来的应该是距离最小的点，而在它出来时，比它本身的值多1，这样求的最短路很可能就是错的（只要队列里还有和它本来应该等于的距离相等的位置）
正确做法：
光dist是不能判重的，还需要一个额外的判重数组，它只给传送前位置标记防止再进入，而不能都标记（因为可能进传送门又出来，要保证回得去）

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
#define speed_up ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define x first
#define y second
const int N=310;
int n,m;
char g[N][N];
ll dist[N][N];
bool gone[N][N];
pii st;
vector<pii> fly[26];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

ll bfs(){
    dist[st.x][st.y]=0;
    gone[st.x][st.y]= true;
    queue<pii> q;
    q.push(st);
    while(!q.empty()){
        auto t=q.front();
        int x=t.x,y=t.y;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<0 || nx>=n || ny<0 || ny>=m || g[nx][ny]=='#')continue;
            if(gone[nx][ny])continue;
            int xx,yy;
            gone[nx][ny]= true;
            if(isalpha(g[nx][ny])){
                int seq=g[nx][ny]-'A';
                pii a=fly[seq][0],b=fly[seq][1];
                if(make_pair(nx,ny) == a)xx=b.x,yy=b.y;
                else xx=a.x,yy=a.y;
                dist[xx][yy]=dist[x][y]+1;
                q.push({xx,yy});
            }
            else {
                q.push({nx,ny});
                dist[nx][ny]=dist[x][y]+1;
                if(g[nx][ny]=='=')return dist[nx][ny];
            }
        }
    }
}

int main(){
    cin>>n>>m;
    memset(dist,-1,sizeof dist);
    for(int i=0;i<n;i++){
        cin>>g[i];
        for(int j=0;j<m;j++){
            if(g[i][j]=='@')st={i,j};
            if(isalpha(g[i][j]))fly[g[i][j]-'A'].push_back({i,j});
        }
    }

    cout<<bfs();
    return 0;
}

总结

可能只用dist判重算是偷懒了，如果习惯做bfs加上额外的一个判重数组可能这个题就轻松水过去了，正因为执着于用dist判重才花费了好多时间，这事具有两面性，多个额外判重数组有时候未必会更坏

C++版本

思路核心是转换成了二维数组s_list中对于每个字符串s的j列元素是否相等

#include<iostream>
using namespace std;

// 对于变长数组的问题就定义一个大数组就可以
int main()
{
    int n;
    while(cin >> n, n!=0)
    {
        string srr[1000];
        string str;
        int min=9999;

        for (int i=0; i<n; i++)
        {
            cin >> str;
            // 逆序存储
            for(int j=str.size()-1; j>=0; j--)
                srr[i] += str[j];
            if (str.size()<min) min = str.size();
        }

        string temp = "", sub = "";
        int flag = 0;
        for (int j=0; j<min; j++)
        {
            for (int i=0; i<n; i++)  temp += srr[i][j];

            char c = temp[0];
            flag = 0;
            for (int i=0; i<temp.size(); i++)
            {
                if (c != temp[i]) flag=1;
            }
            // 字符相等
            if (flag == 0)
            {
                sub += c;
                temp = "";
            }
            else break;
        }
        if (sub == "") cout << endl;
        else 
        {
            for (int i = sub.size()-1; i>=0; i--) cout << sub[i];    
            cout << endl;
        }

    }
    return 0;
}

python版本

while(True):
    N = int(input())
    if N == 0:
        break
    s_list = []
    for i in range(N):
        t = input().strip()[::-1]
        s_list.append(t)

    s_list_len = [len(s) for s in s_list]

    temp = []
    sub = []
    for j in range(0, min(s_list_len)):
        for i in range(0, len(s_list)):
           temp.append(s_list[i][j])
        if len(set(temp)) == 1:
            sub.append(temp[0])
        else:
            break
        temp = []

    if len(sub) == 0:
        print()
    else:
        for c in sub[::-1]:
            print(c, end='')
        print()

算法2

(暴力枚举) $O(n^2)$

java 代码

n=Scanf_Int();
        m=Scanf_Int();
        if (m==n){
            out.println(0);
            out.close();
            System.exit(0);
        }
        m1=Math.abs(n-m);
        while (m1!=0){
            if (m1>0){
                l++;
                m1--;
                sum+=l;
            }
            if (m1>0){
                r++;
                m1--;
                sum+=r;
            }
        }
        out.println(sum);

Java代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        String[] nums = br.readLine().split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(nums[i]);
        }
        int[] res_min = new int[n - k + 1];
        int[] res_max = new int[n - k + 1];
        Deque<Integer> queue_min = new LinkedList<>();
        Deque<Integer> queue_max = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!queue_max.isEmpty() && arr[queue_max.peekLast()] <= arr[i]) {
                queue_max.pollLast();
            }
            while (!queue_min.isEmpty() && arr[queue_min.peekLast()]>= arr[i]) {
                queue_min.pollLast();
            }
            queue_max.offerLast(i);
            queue_min.offerLast(i);
        }
        res_max[0] = arr[queue_max.peekFirst()];
        res_min[0] = arr[queue_min.peekFirst()];
        for (int i = k; i < n; i++) {
            while(!queue_max.isEmpty() && arr[queue_max.peekLast()] <= arr[i]) {
                queue_max.pollLast();
            }
            queue_max.offerLast(i);
            if(queue_max.peekFirst() <= i - k) {
                queue_max.pollFirst();
            }
            res_max[i - k + 1] = arr[queue_max.peekFirst()];
        }
        for (int i = k; i < n; ++i) {
            while (!queue_min.isEmpty() && arr[queue_min.peekLast()] >= arr[i]) {
                queue_min.pollLast();
            }
            queue_min.offerLast(i);
            if(queue_min.peekFirst() <= i - k) {
                queue_min.pollFirst();
            }
            res_min[i - k + 1] = arr[queue_min.peekFirst()];
        }
        for (int num : res_min) {
            System.out.print(num + " ");
        }
        System.out.println();
        for (int num : res_max) {
            System.out.print(num + " ");
        }
    }
}

java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] nums = br.readLine().split(" ");
        int[] arr = new int[n];
        int l = 0;
        for(String num : nums){
            arr[l++] = Integer.parseInt(num);
        }
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]){
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            System.out.print(res[i] + " ");
            stack.push(arr[i]);
        }

    }
}

计算过程如下

朴素版代码

import java.util.Scanner;
import java.io.*;

public class Main {
    static int N = 1010;
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int[][] f = new int[N][N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int m = sc.nextInt();
        for (int i = 1; i <= n; i ++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        // i = 0 时表示取前 0 个物品，即不取物品，所以总价值都为 0
        for (int i = 1; i <= n; i ++) {
            for (int j = 0; j <= m; j ++) {
                // 不包含 i 的方案
                f[i][j] = f[i - 1][j];
                // 包含 i 的方案，只有 vi ≤ j 时才会选择
                if (v[i] <= j) {
                    // 取两个方案中的最大值
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
        sc.close();
    }
}

优化

仔细分析状态变换过程可以发现，计算 f[i, j] 时只会用到 f[i - 1, j]，不需要存储 f[0 ~ i-2, j] 的值。

并且 f(i, j) = Math.max(f(i - 1, j), f(i - 1, j - v[i] + w[i]) 中，第二维 j 的值只与 j 与 j - v[i] 有关，而 j = j j - v[i] < j，都严格 ≤ j，因此可以将第一维 i 删去，用一维滚动数组来存储中间值。

等价转换
将运算过程删去第 i 维后得到以下代码

for (int i = 1; i <= n; i ++) {
    for (int j = 0; j <= m; j ++) {
        f[j] = f[j];
        if (j >= v[i]) {
            f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
        }
    }
}
System.out.println(f[m]);

我们可以发现 f[j] = f[j] 是恒等式，直接删除。
j >= v[i] 的判断可以放进 j 的循环中，所以再改进如下

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.println(f[m]);

问题
此时 f 数组由于节省空间更改为滚动数组，所以运算 i = 1 时需要用到 i = 0 时 f 数组的结果，运算 i = 2 时需要用到 i = 1 时 f 数组的结果。
这就要求在运算 Math.max(f[j], f[j - v[i]] + w[i]) 时，读取到的 f 数组里的数据必须全部是上一个 i 运算的结果。

但是由于 j 是递增的，而 j - v[i] 又严格小于 j，因此如果 f[j] 被修改，下一次读取的 f[j - v[i]] 的数据就是最新修改后的值。比如：
当 i = 1 时，我们使用的应是 i = 0 时 f 数组的数据，j 开始循环
j = 1：f[1] = Math.max(f[1], f[0] + w[1]) = Math.max(0, 0 + 2) = 2
j = 2：f[2] = Math.max(f[2], f[1] + w[1]) = Math.max(0, 2 + 2) = 4
…
此时由于 f[1] 先被修改，所以导致 j = 2 时使用的 f[1] 就是修改后的值，但我们本来只想读取 i = 0 时 f[1] 的值，出现矛盾。

如何解决
Math.max(f[j], f[j - v[i]] + w[i]) 是我们运算的根基，不要轻易修改。只需要保证 f[j - v[i]] 在使用时一定是原值即可。
所以将 j 递减循环，即可保证每一次读取的 f[j - v[i]] 都是更新前的值，完美解决该问题。比如：
当 i = 1 时，我们使用的应是 i = 0 时 f 数组的数据，j 开始循环
j = 5：f[5] = Math.max(f[5], f[4] + w[1]) = Math.max(0, 0 + 2) = 2
j = 4：f[4] = Math.max(f[4], f[3] + w[1]) = Math.max(0, 0 + 2) = 2
…
可以发现求 f[5] 时读取的 f[5] 和 f[4] 都是上一轮计算的结果，即使本次循环更新后，求 f[4] 时也不会用到，问题解决。 代码修改如下：

for (int i = 1; i <= n; i ++) {
    for (int j = m; j >= v[i]; j --) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}
System.out.println(f[m]);

优化版完整代码

import java.util.Scanner;
import java.io.*;

public class Main {
    static int N = 1010;
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int[] f = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int m = sc.nextInt();
        for (int i = 1; i <= n; i ++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        // i = 0 时表示取前 0 个物品，即不取物品，所以总价值都为 0
        for (int i = 1; i <= n; i ++) {
            for (int j = m; j >= v[i]; j --) {
                // 取两个方案中的最大值
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
        }
        System.out.println(f[m]);
        sc.close();
    }
}

<!DOCTYPE html>

<html>

<head>

</head>

<body>
    <h2>春江花月夜</h2>
    <h5>张若虚</h5>
    <p>
        春江潮水连海平，海上明月共潮生。<br>
        滟滟随波千万里，何处春江无月明！<br>
        江流宛转绕芳甸，月照花林皆似霰；<br>
        空里流霜不觉飞，汀上白沙看不见。<br>
        江天一色无纤尘，皎皎空中孤月轮。<br>
        江畔何人初见月？江月何年初照人？<br>
        人生代代无穷已，江月年年望相似。
    </p>

    <hr>

    <pre>
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d %d\n", a, b);
    return 0;
}
    </pre>

    <p>
        <i>春眠不觉晓，</i>
        <b>处处闻啼鸟。</b>
        <del>夜来风雨声，</del>
        <ins>花落知多少。</ins>
    </p>
</body>

</html>