最近在學習ruby，因爲認識了很多日本朋友，他們那邊可能是用ruby比較多，都問我會不會ruby，早上起來就安裝了一下，很簡單，記錄下步驟

首先要安裝ruby集成環境

https://s3.jcloud.sjtu.edu.cn/899a892efef34b1b944a19981040f55b-oss01/github-release/oneclick/rubyinstaller2/releases/download/RubyInstaller-3.3.3-1/rubyinstaller-devkit-3.3.3-1-x64.exe

在這裏下載就好，下載好了一直安裝回車，就好

接下來是用gem，這是ruby的包管理工具，一般像如下使用
```sh
gem install xxx # 包名

```
很簡單

然後是換源，這個在國内真的是逃不掉

```
gem sources # ミラーソースを確認

gem sources --remove https://rubygems.org # デフォルトのソースを削除

gem sources -a https://gems.ruby-china.com # 新しいソースを追加

gem sources --add https://mirrors.tuna.tsinghua.edu.cn/rubygems/ # 別のソースを追加

gem sources -u # ソースを更新
```

這樣就可以了，接下來安裝ruby流行的web後端框架，rails
```
gem install rails
```

這個好像很流行很强大

然後還發現個寶藏框架

sinatra

真的很簡潔，第一次見比flask,fastapi還簡介的框架

```ruby
require 'sinatra'

# 定义一个根路径的 GET 请求处理程序
get '/' do
  "Hello, World!"
end

# 定义一个带有参数的路径
get '/hello/:name' do
  "Hello, #{params[:name]}!"
end

# 定义一个 POST 请求处理程序
post '/submit' do
  "You submitted: #{params[:message]}"
end
```

![image.png](/static/img/d421e891c2f276954aa0aeb5cecdf8f3.image.webp)

ruby學習

今天做https://www.acwing.com/problem/content/description/103/

直接模拟就可以，首先全部初始化高度为最高，对于每对关系，把中间的牛高度-1，可能有重复关系所以要去重


```cpp
#include <iostream>
#include <algorithm>
using namespace std;
void max_heights(int n, int p, int h, int m, int relations[][2]) {
    // 初始化每头牛的身高为 H
    int heights[n];
    fill(heights, heights + n, h);
    // 记录已经处理过的区间
    bool processed_intervals[n][n];
    fill(&processed_intervals[0][0], &processed_intervals[0][0] + n * n, false);
    for (int i = 0; i < m; ++i) {
        int a = relations[i][0];
        int b = relations[i][1];
        // 确保 a < b
        if (a > b) swap(a, b);
        // 如果这个区间还没有被处理过
        if (!processed_intervals[a - 1][b - 1]) {
            // 在 a 和 b 之间的牛的身高减去 1
            for (int j = a; j < b - 1; ++j) {
                heights[j] -= 1;
            }
            // 记录这个区间已经被处理过
            processed_intervals[a - 1][b - 1] = true;
        }
    }
    // 输出结果
    for (int i = 0; i < n; ++i) {
        cout << heights[i] << endl;
    }
}
int main() {
    int n, p, h, m;
    cin >> n >> p >> h >> m;
    int relations[m][2];
    for (int i = 0; i < m; ++i) {
        cin >> relations[i][0] >> relations[i][1];
    }
    // 计算每头牛的最大可能身高
    max_heights(n, p, h, m, relations);
    return 0;
}

```

最高的牛，模拟题

https://www.acwing.com/problem/content/131/

今天这题，dfs爆搜



- dfs爆搜，注意20剪枝
- 所有火车都进栈出栈这代表一个结果产生
- 车站不为空就能选择出栈
- 如果还有火车未进栈，则可以选择进栈

```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int n;  // 火车数量
vector<string> result;  // 存储所有可能的出栈顺序
stack<int> station;  // 模拟车站栈
vector<int> current;  // 当前出栈的火车顺序

// 深度优先搜索函数
void dfs(int inStack) {
    // 如果已经找到20种方案，停止搜索
    if (result.size() >= 20) {
        return;
    }

    // 如果所有火车都已进栈且栈为空，表示所有火车都已出栈
    if (inStack == n && station.empty()) {
        string s;
        // 将当前出栈顺序转换为字符串
        for (int v : current) {
            s += to_string(v);
        }
        // 将结果加入结果集
        result.push_back(s);
        return;
    }

    // 如果栈不为空，进行出栈操作
    if (!station.empty()) {
        int top = station.top();  // 获取栈顶元素
        station.pop();  // 出栈
        current.push_back(top);  // 将出栈的火车加入当前出栈顺序
        dfs(inStack);  // 递归调用dfs
        current.pop_back();  // 回溯，移除最后一个出栈的火车
        station.push(top);  // 将出栈的火车重新入栈
    }

    // 如果还有火车未进栈，进行进栈操作
    if (inStack < n) {
        station.push(inStack + 1);  // 将下一列火车进栈
        dfs(inStack + 1);  // 递归调用dfs
        station.pop();  // 回溯，移除最后一个进栈的火车
    }
}

int main() {
    cin >> n;  // 读取火车数量
    dfs(0);  // 调用dfs函数开始搜索

    // 输出前20种方案
    for (int i = 0; i < result.size() && i < 20; i++) {
        cout << result[i] << endl;
    }

    return 0;
}

```
然后最近在学习ruby

```ruby
require 'set'

# 全局变量
$n = 0
$result = []
$station = []
$current = []

# 深度优先搜索
def dfs(in_stack)
  return if $result.size >= 20

  if in_stack == $n && $station.empty?
    # 所有火车都已出栈
    $result << $current.join
    return
  end

  if !$station.empty?
    # 出栈操作
    top = $station.pop
    $current << top
    dfs(in_stack)
    $current.pop
    $station.push(top)
  end

  if in_stack < $n
    # 进栈操作
    $station.push(in_stack + 1)
    dfs(in_stack + 1)
    $station.pop
  end
end

# 主函数
def main
  $n = gets.to_i
  dfs(0)

  # 按字典序排序
  $result.sort!

  # 输出前20种方案
  $result[0, 20].each { |r| puts r }
end

# 运行主函数
main
```

9.15日算法

全球变暖

# 求细胞数量

## 题目描述

一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

## 输入格式

第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 `0` 到 `9` 的字符串，代表这个 $n \times m$ 的矩阵。

## 输出格式

一行一个整数代表细胞个数。

## 样例 #1

### 样例输入 #1

```
4 10
0234500067
1034560500
2045600671
0000000089
```

### 样例输出 #1

```
4
```

## 提示

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$。



直接dfs
```cpp
#include <iostream>
using namespace std;

int n, m;
int matrix[105][105];
bool visited[105][105];

// 方向数组，用于DFS遍历上下左右四个方向
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// DFS函数
void dfs(int x, int y) {
    visited[x][y] = true;
    
    // 遍历四个方向
    for (int i = 0; i < 4; ++i) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        
        // 检查是否越界，是否是细胞数字，是否未访问过
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] != 0 && !visited[nx][ny]) {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    
    // 读取矩阵
    for (int i = 0; i < n; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < m; ++j) {
            matrix[i][j] = row[j] - '0';
        }
    }
    
    int cell_count = 0;
    
    // 遍历矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] != 0 && !visited[i][j]) {
                // 发现一个新的细胞
                dfs(i, j);
                cell_count++;
            }
        }
    }
    
    // 输出细胞总数
    cout << cell_count << endl;
    
    return 0;
}
```


大佬题解
```cpp

#include <bits/stdc++.h>
using namespace std;
template <typename _Tp>
inline void read(_Tp &x){
    int w=1;char c=0;x=0;
    while (c^'-'&&(c<'0'||c>'9'))c=getchar();
    if (c=='-')w=-1,c=getchar();
    while (c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=w;
}
inline void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}//输入输出优化，请自动忽略
int n,m,ans,dx[]={-1,0,1,0},dy[]={0,-1,0,1},a[105][105];//a即地图，dx和dy方向增量数组就不用我讲了吧
void dfs(int x,int y){
	if (x>n||y>m||x<0||y<0)return;
	a[x][y]=0;//标记为没有
	for (int i=0;i<4;i++)if (a[x+dx[i]][y+dy[i]])dfs(x+dx[i],y+dy[i]);//如果有才搜
}//搜索
int main(){
	read(n),read(m);
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)scanf("%1d",&a[i][j]);//只读1位
	for (int i=0;i<n;i++)
	for (int j=0;j<m;j++)if (a[i][j])ans++,dfs(i,j);//找
	write(ans);//输出
	return 0;
}
```