[已解决]c语言题目求解题思路

kkk聪

求解题思路即可

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-5-31 21:07:58

#include <stdio.h>

int bloom(int f, int m) {
    // f: 花, m: 月份
    switch (f)
    {
    case 1:
        return m >= 1 && m <= 3;
    case 2:
        return m >= 3 && m <= 4;
    case 3:
        return m >= 4 && m <= 5;
    case 4:
        return m >= 9 && m <= 10;
    }
    return 0;
}

void foo(int* a, int* b) {
    int t;
    if ((*a) > (*b)) {
        t = (*a);
        (*a) = (*b);
        (*b) = t;
    }
}

int main(void) {
    int n, p, q, m, x, u, v;
    scanf("%d", &n);
    int P[n + 1];
    P[0] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &P[i]);
    }
    scanf("%d%d", &p, &q);
    foo(&p, &q); // 确保 p < q
    scanf("%d", &m);
    int res[m];
    for (int test = 0, sum, max; test < m; ++test) {
        sum = 0;
        max = 0;
        scanf("%d%d%d", &x, &u, &v);
        foo(&u, &v);
        // 状况1
        for (int i = u; i != v; ++i) {
            if (i > n) i = 1;
            if (i == v) {
                sum += bloom(P[i], x);
                break;
            }
            sum += bloom(P[i], x);
        }
        max = max > sum ? max : sum;
        sum = 0;
        // 状况2
        for (int i = u; ; --i) {
            if (i < 1) i = n;
            if (i == v) {
                sum += bloom(P[i], x);
                break;
            }
            sum += bloom(P[i], x);
        }
        max = max > sum ? max : sum;
        sum = 0;
        // 状况3
        if (u != p && v != q) {
            for (int i = u, move = 1; i != v; i += move) {
                if (i > n) i = 1;
                if (i < 1) i = n;
                if (i == v) {
                    sum += bloom(P[i], x);
                    break;
                }
                sum += bloom(P[i], x);
                if (i == p) {
                    i = q;
                    sum += bloom(P[i], x);
                    move = -move;
                }
                else if (i == q) {
                    i = p;
                    sum += bloom(P[i], x);
                    move = -move;
                }
            }
            max = max > sum ? max : sum;
            sum = 0;
            // 状况4
            for (int i = u, move = -1; i != v; i += move) {
                if (i > n) i = 1;
                if (i < 1) i = n;
                if (i == v) {
                    sum += bloom(P[i], x);
                    break;
                }
                sum += bloom(P[i], x);
                if (i == p) {
                    i = q;
                    sum += bloom(P[i], x);
                    move = -move;
                }
                else if (i == q) {
                    i = p;
                    sum += bloom(P[i], x);
                    move = -move;
                }
            }
            max = max > sum ? max : sum;
            sum = 0;
        }
        res[test] = max;
    }
    for (int i = 0; i < m; ++i) {
        res[i] ? printf("%d\n", res[i]) : printf("So Sad\n");
    }
    return 0;
}

10
1 1 2 4 3 2 4 4 3 3
3 9
5
1 1 5
1 3 9
3 5 10
7 1 10
10 2 9
2
2
4
So Sad
3

跳转到最佳答案楼层

jhq999

8型环状双向链表，然后递归枚举去吧
struct POINT
{
        int isflower;
        int ispssed;
        POINT* prev;
        POINT* next;
        POINT* bridge；
}；

kkk聪

jhq999 发表于 2022-5-31 08:45
8型环状双向链表，然后递归枚举去吧
struct POINT
{

刚学到指针没两节，，不会用链表，不过谢谢

wp231957

kkk聪 发表于 2022-5-31 13:16
刚学到指针没两节，，不会用链表，不过谢谢

它这可不是普通的链表，单链表就一个后驱指针
双链表还增加一个前驱指针，它这个又增加一个什么桥指针已经看不懂了

jhq999

wp231957 发表于 2022-5-31 18:00
它这可不是普通的链表，单链表就一个后驱指针
双链表还增加一个前驱指针，它这个又增加一个什么桥指针已 ...

湖里有座桥链接两点，把环状链表变成8

傻眼貓咪

jhq999 发表于 2022-5-31 19:02
湖里有座桥链接两点，把环状链表变成8

可能我理解有错，来学习学习。我的理解是题目好象没有说一定要用桥，也有不用桥能就能看到更多花的状况吧？8 字环形好象也不正确，因为 8 字环形表示 某些状况桥会用到两次（一来一回），题目声明每个点不能重复，桥必须只能走 1 次（p 和 q 点各为一次）。

正确应该只是算出 S 字形或反 S 字形 C 字形顺时针 和 C 字形逆时针 4 种状况的最大值便可。

傻眼貓咪

#include <stdio.h>

int bloom(int f, int m) {
    // f: 花, m: 月份
    switch (f)
    {
    case 1:
        return m >= 1 && m <= 3;
    case 2:
        return m >= 3 && m <= 4;
    case 3:
        return m >= 4 && m <= 5;
    case 4:
        return m >= 9 && m <= 10;
    }
    return 0;
}

void foo(int* a, int* b) {
    int t;
    if ((*a) > (*b)) {
        t = (*a);
        (*a) = (*b);
        (*b) = t;
    }
}

int main(void) {
    int n, p, q, m, x, u, v;
    scanf("%d", &n);
    int P[n + 1];
    P[0] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &P[i]);
    }
    scanf("%d%d", &p, &q);
    foo(&p, &q); // 确保 p < q
    scanf("%d", &m);
    int res[m];
    for (int test = 0, sum, max; test < m; ++test) {
        sum = 0;
        max = 0;
        scanf("%d%d%d", &x, &u, &v);
        foo(&u, &v);
        // 状况1
        for (int i = u; i != v; ++i) {
            if (i > n) i = 1;
            if (i == v) {
                sum += bloom(P[i], x);
                break;
            }
            sum += bloom(P[i], x);
        }
        max = max > sum ? max : sum;
        sum = 0;
        // 状况2
        for (int i = u; ; --i) {
            if (i < 1) i = n;
            if (i == v) {
                sum += bloom(P[i], x);
                break;
            }
            sum += bloom(P[i], x);
        }
        max = max > sum ? max : sum;
        sum = 0;
        // 状况3
        if (u != p && v != q) {
            for (int i = u, move = 1; i != v; i += move) {
                if (i > n) i = 1;
                if (i < 1) i = n;
                if (i == v) {
                    sum += bloom(P[i], x);
                    break;
                }
                sum += bloom(P[i], x);
                if (i == p) {
                    i = q;
                    sum += bloom(P[i], x);
                    move = -move;
                }
                else if (i == q) {
                    i = p;
                    sum += bloom(P[i], x);
                    move = -move;
                }
            }
            max = max > sum ? max : sum;
            sum = 0;
            // 状况4
            for (int i = u, move = -1; i != v; i += move) {
                if (i > n) i = 1;
                if (i < 1) i = n;
                if (i == v) {
                    sum += bloom(P[i], x);
                    break;
                }
                sum += bloom(P[i], x);
                if (i == p) {
                    i = q;
                    sum += bloom(P[i], x);
                    move = -move;
                }
                else if (i == q) {
                    i = p;
                    sum += bloom(P[i], x);
                    move = -move;
                }
            }
            max = max > sum ? max : sum;
            sum = 0;
        }
        res[test] = max;
    }
    for (int i = 0; i < m; ++i) {
        res[i] ? printf("%d\n", res[i]) : printf("So Sad\n");
    }
    return 0;
}

10
1 1 2 4 3 2 4 4 3 3
3 9
5
1 1 5
1 3 9
3 5 10
7 1 10
10 2 9
2
2
4
So Sad
3

jhq999

傻眼貓咪 发表于 2022-5-31 20:15
可能我理解有错，来学习学习。我的理解是题目好象没有说一定要用桥，也有不用桥能就能看到更多花的状况吧 ...

用ispass判断走过没有，最笨的枚举用到了

傻眼貓咪

jhq999 发表于 2022-5-31 21:39
用ispass判断走过没有，最笨的枚举用到了

原来这样，学习学习

jhq999

傻眼貓咪 发表于 2022-6-1 08:14
原来这样，学习学习

当时看到圈就想到环形链表，然后再看到桥，想到最笨的枚举寻路方法
还是你的简单易懂

傻眼貓咪

jhq999 发表于 2022-6-1 09:05
当时看到圈就想到环形链表，然后再看到桥，想到最笨的枚举寻路方法
还是你的简单易懂

哈哈哈，我是把图画在纸上，找出所有路线，才发现原来路线不多。