寒假训练——第二周（DFS）

A - Oil Deposits

思路：

$D FS 四周八个格子即可$
$y 总：一般两重循环特判中心位置$

代码如下：


#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 110, M = 1010, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;

int n, m;
char s[N][N];
bool st[N][N];

void dfs(int sx, int sy)
{
    st[sx][sy] = true;
    
    //cout << " --- " << sx << " " << sy << endl;
    
    for (int i = sx - 1; i <= sx + 1; i ++ )
        for (int j = sy - 1; j <= sy + 1; j ++ )
        {
            if(i < 0 || i >= n || j < 0 || j >= m) continue;
            if(i == sx && j == sy) continue;
            if(s[i][j] == '*' || st[i][j]) continue;
            
            dfs(i, j);
        }
}

void solve()
{
    //cin >> n >> m;
    
    memset(st, 0, sizeof st);
    
    for (int i = 0; i < n; i ++ )
        scanf("%s", s[i]);
    
    int res = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if(!st[i][j] && s[i][j] == '@')
            {
                res ++;
                dfs(i, j);
            }
    
    printf("%d\n", res);
    
    return;
}

signed main()
{
    //fast;
    int T = 1; 
    //cin >> T;
    while(scanf("%d%d", &n, &m), n || m)
        solve();
    
    return 0;
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

B - 单词接龙

思路：

预处理每个字符串的最大后缀
从任何满足龙头的单词 $D FS$ ，记录全局最大值

代码如下：

//#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 30, M = 1010, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;

int n, m;
int ans = 0;
string word[N];
int used[N];
int g[N][N];
char start;

void dfs(string dragon, int last)
{
    ans = max(ans, (int)dragon.size());
    
    if(ans == 26) cout << dragon << endl;
    
    used[last] ++;
    
    for (int i = 0; i < n; i ++ )
        if(g[last][i] && used[i] < 2)
            dfs(dragon + word[i].substr(g[last][i]), i);
    
    used[last] --;
}

void solve()
{
    cin >> n;
    
    for (int i = 0; i < n; i ++ )
        cin >> word[i];
    
    cin >> start;
    
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
        {
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k ++ )
            {
                if(a.substr(a.size() - k) == b.substr(0, k))
                {
                    g[i][j] = k;
                    break;
                }
            }
        }
        
    for (int i = 0; i < n; i ++ )
        if(word[i][0] == start)
            dfs(word[i], i);
        
    cout << ans << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

C - 生日快乐

思路：

题目只说面积相等，没说形状相等，我们只需按照剩余的块数将剩余的蛋糕等分即可
如何等分？将分别按照长宽除以剩余块数，如此，刀数与剩余面积时确定的
$D FS$ 如何切（即、 $D FS$ 分为哪两个部分)，直到剩余块数为 1，结束

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 30, M = 1010, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;

int n;
double x, y;

double dfs(double x, double y, int k)
{
    if(k == 1) return max(x, y) / min(x, y);
    
    double xx = x / k, yy = y / k;
    double res1, res2, res = 1e9;
    for (double i = 1; i <= k / 2; i += 1.0 )
    {
        res1 = max(dfs(xx * i, y, i), dfs(x - xx * i, y, k - i));
        res2 = max(dfs(x, yy * i, i), dfs(x, y - yy * i, k - i));
        res = min({res, res1, res2});
    }
    
    return res;
}

void solve()
{
    cin >> x >> y >> n;
    
    printf("%.6f\n", dfs(x, y, n));
    
    return;
}

signed main()
{
    //fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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
52
53
54

D - 奇怪的电梯

思路：

记录上下两种 $t y p e$
按照类型 $D FS$ 即可

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 210, M = 1010, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;

int n;
int A, B;
int change[N];
int ans = INF;
bool st[N];

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

void dfs(int u, int cnt)
{
    if(cnt > ans) return;
    if(u == B) ans = min(ans, cnt);
    
    for (int i = 0; i < 2; i ++ )
    {
        int x = u + type[i] * change[u];
        if(x <= 0 || x > n) continue;
        if(st[x]) continue;
        
        st[x] = true;
        dfs(x, cnt + 1);
        st[x] = false;
    }
    
    return;
}

void solve()
{
    cin >> n >> A >> B;
    
    for (int i = 1; i <= n; i ++ )
        cin >> change[i];
    
    dfs(A, 0);
    
    if(ans != INF) cout << ans << endl;
    else cout << -1 << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

E - 全排列问题

思路：

简单 $D FS$

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 15, M = 1010, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;

int n;
int path[N];
bool st[N];

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

void dfs(int u)
{
    if(u == n)
    {
        for (int i = 0; i < u; i ++ )
            printf("%5d", path[i]);
        puts("");
    }
    
    for (int i = 1; i <= n; i ++ )
    {
        if(!st[i])
        {
            st[i] = true;
            path[u] = i;
            dfs(u + 1);
            st[i] = false;
            path[u] = 0;
        }
    }
    
    return;
}

void solve()
{
    cin >> n;
    
    dfs(0);
    
    return;
}

signed main()
{
    //fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65

F - 滑雪

思路：

记忆化搜索板子题

代码如下：



#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 110, M = 1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

int n, m;
int g[N][N];
int f[N][N];
int ans = -INF;

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

int dfs(int x, int y)
{
    int &v = f[x][y];
    
    if(v != -1) return v;
    
    v = 1;
    
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 1 || a > n || b < 1 || b > m) continue;
        if(g[a][b] < g[x][y])
            v = max(v, dfs(a, b) + 1);
    }
    
    return v;
}

void solve()
{
    cin >> n >> m;
    
    memset(f, -1, sizeof f);
    
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> g[i][j];
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res = max(res, dfs(i, j));
    
    cout << res << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

相关阅读:
C/C++---------------LeetCode第LCR. 024.反转链表
阿里云通义千问大模型正式开放；玩10次ChatGPT就要消耗1升水
centos7 安装mariadb
你以为你了解TCP协议？这些你可能不知道的细节才是关键！
JS操作字符串面试题系列（2）-每天做5题
VAE, the principle and the code
ICV：2025年中国汽车磁传感器芯片市场规模将超过30亿元
Spring AOP
Win10远程连接服务器失败，报错：出现了内部错误
Python 潮流周刊#54：ChatTTS 强大的文本生成语音模型

原文地址：https://blog.csdn.net/m0_61409183/article/details/126444762

寒假训练——第二周（DFS）

目录

A - Oil Deposits

B - 单词接龙

C - 生日快乐

D - 奇怪的电梯

E - 全排列问题

F - 滑雪