NFLS-DAY 6

Posted on By 张, 高畅 NFLS-DAY 6无评论

T0

准确的说，昨天(DAY 6)是放假
但是blog如果不连续会不会被当成少写一篇而被惩罚呢？(bushi

T1

有辆公交车，它可以承载35人，包括一个司机。车子最后一排有4个座位，其他10排都有3个座位。每个上车的人，都会先往左边坐（司机所在的那侧）。现在告诉你，有多少人在车上，绘制车内情况。

又是可爱的签到题，但是有点不可爱。
注意一些细节，以及是从车后到车前去填满，不过题目描述确实有那么一点点敷衍。

#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
    scanf("%d", &n);
    printf("+------------------------+\n");
    for (int i = 1; i <= 4; i++) {
        printf("|");
        for (int j = 1; j <= 11; j++) {
            int x;
            if (j == 1)
                x = i;
            else
                x = 4 + 3 * (j - 2) + (i == 4 ? 3 : i);
            if (i == 3 && j > 1)
                printf("..");
            else {
                if (x <= n)
                    printf("O.");
                else
                    printf("#.");
            }
        }
        if (i != 3)
            printf("|");
        else
            printf(".");
        if (i == 1)
            printf("D");
        else
            printf(".");
        printf("|");
        if (i == 1 || i == 4)
            printf(")");
        puts("");
    }
    printf("+------------------------+\n");
    return 0;
}

T2

猜数字游戏啦！给你如下四种提示：
（1）这个数严格大于x吗？
（2）这个数严格小于x吗？
（3）这个数大于等于x吗？
（4）这个数小于等于x吗？
每个提示，都会给出相应的答案，yes或者no。
如果有多个数满足条件，输出最小的。如果不存在这样的数，输出“Impossible”。

这题不知道对边界判定的是不是很严，如果很严，确实是一道有点细节的题。
对于’N’的情况，只要将其转换为本式子的“反义”。(eg:" ">=")
然后记录一下符号，对于边界进行判断就可以了。

#include <bits/stdc++.h>
using namespace std;
int n, l = -2e9, lop = -1, r = 2e9, rop = -1;
unordered_map<string, int> mp;
int main() {
    cin >> n;
    mp[">"] = 0;
    mp["<"] = 1;
    mp["<="] = 2;
    mp[">="] = 3;
    while (n--) {
        string sign, answer;
        int x;
        cin >> sign >> x >> answer;
        int t = mp[sign];
        if (answer == "N")
            t = (((t - 2) % 4) + 4) % 4;
        if (!t || t == 3) {
            if (l < x || (!t && l == x)) {
                l = x;
                lop = t;
            }
        } else {
            if (x < r || (t == 1 && x == r)) {
                r = x;
                rop = t;
            }
        }
    }
    int x = l, y = r;
    if (!lop)
        x++;
    if (rop == 1)
        y--;
    if (x <= y) {
        if (l == -2e9)
            printf("-2000000000");
        else
            printf("%d\n", x);
    } else
        printf("Impossible\n");
    return 0;
}

T3

学完Fibonacci序列，YY觉得数字太单调了，她打算用S[n]=S[n-2]+S[n-1]的递推式去操作字符串。如果S[0]=AC,S[1]=ACB,则S[2]=ACACB。现在YY有两个字符串s[0]和s[1]，她想知道，s[n]中包含多少个”AC”串。

首先提前声明，我没有改动题面。
此题就是一个递推，但显然只记录本串中含有的"AC"的个数显然不行。（eg:s[0]="AA",S[1]="CC",S[2]="AACC"）
因此我们再记录收尾，在做递推时检查收尾是否能够拼接成为"AC"，然后计入答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 50;
struct node {
    char first, last;
    int cnt;
} s[N];
int n;
string s0, s1;
int main() {
    cin >> s0 >> s1 >> n;
    for (int i = 0; i < s0.size() - 1; i++) {
        if (s0[i] == 'A' && s0[i + 1] == 'C')
            s[0].cnt++;
    }
    for (int i = 0; i < s1.size() - 1; i++) {
        if (s1[i] == 'A' && s1[i + 1] == 'C')
            s[1].cnt++;
    }
    s[0].first = s0[0];
    s[0].last = s0[s0.size() - 1];
    s[1].first = s1[0];
    s[1].last = s1[s1.size() - 1];
    for (int i = 2; i <= n; i++) {
        s[i].cnt = s[i - 2].cnt + s[i - 1].cnt + ((s[i - 2].last == 'A' && s[i - 1].first == 'C') ? 1 : 0);
        s[i].first = s[i - 2].first;
        s[i].last = s[i - 1].last;
    }
    printf("%d", s[n].cnt);
    return 0;
}

T4

小王考入了大学,开学前需要去医院体检.
体检一共有N个项目,每个项目检查处都排起了队伍,并且人越来越多.
他一眼就发现,对于第i个项目,如果立即去排队,需要ai秒才能完成;
如果先做其他检查,在t秒后再来,那么要再多等上bi*t秒.
请你帮他规划,如何安排N个项目的顺序,才能尽早完成所有检查.

首先看到这题肯定是DP，然后发现自己不会写需要记录每个项目的使用情况，真的要写的话，空间直接爆掉。
因此考虑这题不是DP，而是和DP在某些题目长得很像的贪心。
考虑对于任意两项i,j。
不考虑前面的几项，若先i再j比先j再i所用时间短，则说明，i排序后在j前面。
推导sort所用的cmp函数，有:
a[i]+(a[i])×b[j]+a[j] < a[j]+(a[j])×b[i]+a[i]
因此:
a[i]×b[j] < a[j]×b[i]

T5

推箱子应该算是一个家喻户晓的游戏了，这次你的任务就是用电脑算出如何移动人物，完成推箱子。
为了使问题简化，数据中只有3个箱子和3个洞。
注：人一次只能推动一个箱子，箱子推到洞上后不会消失，还可以被推出去，只有当三个箱子同时在洞中时，游戏结束

看起来NFLS的出题人非常喜欢让我们写搜索，而且还是很复杂的DFS/BFS
并且这一题用来记录状态的st数组也开得有点超出想象力，你敢相信开8维数组？
注：似乎只能使用这种方式，map会导致最后两个点超时。
实在是佩服出题人。

#include <bits/stdc++.h>
using namespace std;
const int N = 9;
const int dx[4] = { 0, -1, 0, 1 };
const int dy[4] = { -1, 0, 1, 0 };
int n, m, st[N][N][N][N][N][N][N][N];
typedef pair<int, int> PII;
typedef pair<pair<PII, PII>, pair<PII, PII> > state;
#define x first
#define y second
char Map[N][N];
int check(PII box1, PII box2, PII box3) {
    if (Map[box1.x][box1.y] == '@' && Map[box2.x][box2.y] == '@' && Map[box3.x][box3.y] == '@')
        return 1;
    else
        return 0;
}
int bfs(PII p, PII box1, PII box2, PII box3) {
    queue<state> q;
    st[p.x][p.y][box1.x][box1.y][box2.x][box2.y][box3.x][box3.y] = 1;
    q.push({ { p, box1 }, { box2, box3 } });
    while (q.size()) {
        state u = q.front();
        q.pop();
        PII p = u.x.x, box1 = u.x.y, box2 = u.y.x, box3 = u.y.y;
        if (check(box1, box2, box3))
            return st[p.x][p.y][box1.x][box1.y][box2.x][box2.y][box3.x][box3.y] - 1;
        for (int i = 0; i < 4; i++) {
            int nx = p.x + dx[i], ny = p.y + dy[i];
            if (1 <= nx && nx <= n && 1 <= ny && ny <= m && Map[nx][ny] != '#') {
                if (nx == box1.x && ny == box1.y) {
                    int mx = nx + dx[i], my = ny + dy[i];
                    if (1 <= mx && mx <= n && 1 <= my && my <= m &&
                        !((mx == box1.x && my == box1.y) || (mx == box2.x && my == box2.y) ||
                          (mx == box3.x && my == box3.y)) &&
                        Map[mx][my] != '#') {
                        state ne = { { { nx, ny }, { mx, my } }, { box2, box3 } };
                        if (!st[nx][ny][mx][my][box2.x][box2.y][box3.x][box3.y]) {
                            st[nx][ny][mx][my][box2.x][box2.y][box3.x][box3.y] =
                                st[p.x][p.y][box1.x][box1.y][box2.x][box2.y][box3.x][box3.y] + 1;
                            q.push(ne);
                        }
                    }
                } else if (nx == box2.x && ny == box2.y) {
                    int mx = nx + dx[i], my = ny + dy[i];
                    if (1 <= mx && mx <= n && 1 <= my && my <= m &&
                        !((mx == box1.x && my == box1.y) || (mx == box2.x && my == box2.y) ||
                          (mx == box3.x && my == box3.y)) &&
                        Map[mx][my] != '#') {
                        state ne = { { { nx, ny }, box1 }, { { mx, my }, box3 } };
                        if (!st[nx][ny][box1.x][box1.y][mx][my][box3.x][box3.y]) {
                            st[nx][ny][box1.x][box1.y][mx][my][box3.x][box3.y] =
                                st[p.x][p.y][box1.x][box1.y][box2.x][box2.y][box3.x][box3.y] + 1;
                            q.push(ne);
                        }
                    }
                } else if (nx == box3.x && ny == box3.y) {
                    int mx = nx + dx[i], my = ny + dy[i];
                    if (1 <= mx && mx <= n && 1 <= my && my <= m &&
                        !((mx == box1.x && my == box1.y) || (mx == box2.x && my == box2.y) ||
                          (mx == box3.x && my == box3.y)) &&
                        Map[mx][my] != '#') {
                        state ne = { { { nx, ny }, box1 }, { box2, { mx, my } } };
                        if (!st[nx][ny][box1.x][box1.y][box2.x][box2.y][mx][my]) {
                            st[nx][ny][box1.x][box1.y][box2.x][box2.y][mx][my] =
                                st[p.x][p.y][box1.x][box1.y][box2.x][box2.y][box3.x][box3.y] + 1;
                            q.push(ne);
                        }
                    }
                } else {
                    state ne = { { { nx, ny }, box1 }, { box2, box3 } };
                    if (!st[nx][ny][box1.x][box1.y][box2.x][box2.y][box3.x][box3.y]) {
                        st[nx][ny][box1.x][box1.y][box2.x][box2.y][box3.x][box3.y] =
                            st[p.x][p.y][box1.x][box1.y][box2.x][box2.y][box3.x][box3.y] + 1;
                        q.push(ne);
                    }
                }
            }
        }
    }
    return -1;
}
int main() {
    PII p;
    vector<PII> box;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", Map[i] + 1);
        for (int j = 1; j <= m; j++) {
            if (Map[i][j] == 'X')
                p = { i, j };
            if (Map[i][j] == '*')
                box.push_back({ i, j });
        }
    }
    printf("%d", bfs(p, box[0], box[1], box[2]));
    return 0;
}

T6

现在有两个字符串A和B，它们都是由小写字母组成。你现在有一把神奇的字符串刷子，每次可以刷一个区间，刷完之后，这个区间的字母都变成一个你想要的字母。现在你的任务是通过字符刷子，把字符串A变成字符串B。最少需要刷多少次呢？

首先还是%一下CQR与CZY，这两位在赛场上就打出的DALAO。
果然，悲伤的DP，悲伤的我。
首先先提供一个假做法(45pts):每一次使整个排列与左端点相同，然后分段进行次过程。
然后考虑正解DP。
考虑f[l][r][color]表示在[l,r]的区间，将其染成color所需的步数。
然后就可以愉快的进行记忆化搜索了。

#include &lt;bits/stdc++.h&gt;
using namespace std;
const int N = 105;
char A[N], B[N];
int a[N], b[N], f[N][N][30];
int dfs(int l, int r, int color) {
    if (l &gt; r)
        return 0;
    if (l == r) {
        if (!color)
            return a[l] != b[l];
        else
            return b[l] != color;
    }
    int &amp;u = f[l][r][color];
    if (~u)
        return u;
    u = 1e9;
    if (!color) {
        if (a[l] == b[l])
            u = dfs(l + 1, r, color);
        else {
            for (int i = l; i &lt;= r; i++) {
                if (b[i] == b[l])
                    u = min(u, dfs(l, i, b[l]) + dfs(i + 1, r, color) + 1);
            }
        }
    } else {
        if (color == b[l])
            u = dfs(l + 1, r, color);
        else {
            for (int i = l; i &lt;= r; i++) {
                if (b[i] == b[l])
                    u = min(u, dfs(l, i, b[l]) + dfs(i + 1, r, color) + 1);
            }
        }
    }
    return u;
}
int main() {
    memset(f, -1, sizeof f);
    scanf(&quot;%s%s&quot;, A + 1, B + 1);
    for (int i = 1; i &lt;= strlen(A + 1); i++) {
        a[i] = A[i] - 'a' + 1;
        b[i] = B[i] - 'a' + 1;
    }
    printf(&quot;%d&quot;, dfs(1, strlen(A + 1), 0));
    return 0;
}
训练日志

发表回复