2018 ACM-ICPC, Syrian Collegiate Programming Contest

Contents

Contest Info
Solutions

Contest Info

Solved	A	B	C	D	E	F	G	H	I	J	K	L
10/12	O	O	O	O	-	O	O	O	O	O	O	-

O 在比赛中通过
Ø 赛后通过
! 尝试了但是失败了
- 没有尝试

Solutions

A. Hello SCPC 2018!

Solved By Hsueh-. 0:04(+)

题意：

判断十二个数字是否满足；
前4个递增
后面8个严格大于前4个

思路：

模拟。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N];

int main() {
    freopen("hello.in", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        for (int i = 0; i < 12; ++i) {
            scanf("%d", a + i);
        }
        sort(a + 4, a + 12);
        bool F = true;
        for (int i = 1; i < 12; ++i) {
            if (a[i] < a[i - 1]) {
                F = false;
                break;
            }
        }
        puts(F ? "yes" : "no");
    }
    return 0;
}

B. Binary Hamming

Solved By Dup4. 0:10(+)

题意：

给出两个 01 串，可以打乱字母排列顺序，使得两个 01 串的汉明码距离最大。

思路：

尽可能贪心放 01 使得同一位不同即可。

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("hamming.in", "r", stdin);
    int _T;
    cin >> _T;
    string s, t;
    while (_T--) {
        int n;
        cin >> n;
        cin >> s >> t;
        int a[2] = {0, 0}, b[2] = {0, 0};
        for (auto &c : s) ++a[c - '0'];
        for (auto &c : t) ++b[c - '0'];
        cout << min(a[0], b[1]) + min(a[1], b[0]) << "\n";
    }
    return 0;
}

C. Portals

Solved By Dup4. 1:00(+)

题意：有一个 $1 \cdot n$ 的迷宫，. 表示空地，# 表示障碍物，o 表示传送门(即含有 o 的格子都可以互相到达), s 表示起点，e 表示终点。现在可以将 # 边成 .，问最少的次数使得 s 不能到达 e。

思路：

需要最多的次数是 $2$ ，并且可以发现肯定是将离 s 或者 e 最近的 . 更改掉，分类讨论一下然后判连通即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}
#define SZ(x) (int(x.size()))

const int N = 2e5 + 10;
int n, st, ed;
char s[N];

struct UFS {
    int fa[N], rk[N];
    void init(int n) {
        memset(fa, 0, sizeof(fa[0]) * (n + 5));
        memset(rk, 0, sizeof(rk[0]) * (n + 5));
    }
    int find(int x) {
        return fa[x] == 0 ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (rk[fx] > rk[fy])
                swap(fx, fy);
            fa[fx] = fy;
            if (rk[fx] == rk[fy])
                ++rk[fy];
            return true;
        }
        return false;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
} ufs;

bool ok() {
    ufs.init(n);
    vector<int> vec;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'o')
            vec.push_back(i);
    }
    for (int i = 2; i <= n; ++i)
        if (s[i] == '.' || s[i] == 'o' || s[i] == 's' || s[i] == 'e') {
            if (s[i - 1] == '.' || s[i - 1] == 'o' || s[i - 1] == 's' || s[i - 1] == 'e')
                ufs.merge(i - 1, i);
        }
    for (int i = 1; i < SZ(vec); ++i) ufs.merge(vec[i - 1], vec[i]);
    return !ufs.same(st, ed);
}

int gao1(int st) {
    for (int i = st - 1; i >= 1; --i) {
        if (s[i] == '.') {
            s[i] = '#';
            if (ok())
                return 1;
            s[i] = '.';
            break;
        }
    }
    for (int i = st + 1; i <= n; ++i) {
        if (s[i] == '.') {
            s[i] = '#';
            if (ok())
                return 1;
            s[i] = '.';
            break;
        }
    }
    return 0;
}

int gao2(int st) {
    int i, j;
    for (i = st - 1; i >= 1; --i) {
        if (s[i] == '.') {
            break;
        }
    }
    for (j = st + 1; j <= n; ++j) {
        if (s[j] == '.') {
            break;
        }
    }
    // dbg(st, i, j);
    if (i >= 1 && j <= n) {
        s[i] = '#';
        s[j] = '#';
        if (ok())
            return 1;
        s[i] = '.';
        s[j] = '.';
    }
    return 0;
}

int gao() {
    if (ok())
        return 0;
    if (gao1(st))
        return 1;
    if (gao1(ed))
        return 1;
    if (gao2(st))
        return 2;
    if (gao2(ed))
        return 2;
    return -1;
}

int main() {
    freopen("portals.in", "r", stdin);
    int _T;
    cin >> _T;
    while (_T--) {
        scanf("%d%s", &n, s + 1);
        for (int i = 1; i <= n; ++i) {
            if (s[i] == 's')
                st = i;
            else if (s[i] == 'e')
                ed = i;
        }
        printf("%d\n", gao());
    }
    return 0;
}

D. Carnival Slots

Solved By Heush-. 1:44(+)

题意：

一张 $n \cdot m$ 的的图，你可以任意修改 \,/ 使得每列掉下来的权值数量和最大。

思路： - 记忆化搜索。

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 5e2 + 10;

int n, m;
char G[N][N];
int f[N][N], num[N], val[N];

int gao(int x, int y) {
    if (x == n + 1) {
        return val[y];
    }
    if (f[x][y] != -1)
        return f[x][y];
    int& res = f[x][y];
    res = gao(x + 1, y);
    if (G[x][y] != '.' && y - 1 >= 1)
        res = max(res, gao(x + 1, y - 1));
    if (G[x][y] != '.' && y + 1 <= m)
        res = max(res, gao(x + 1, y + 1));
    return res;
}

int main() {
    freopen("balls.in", "r", stdin);

    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                f[i][j] = -1;
            }
        }
        for (int i = 1; i <= m; ++i) {
            scanf("%d", num + i);
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%s", G[i] + 1);
        }
        for (int i = 1; i <= m; ++i) {
            scanf("%d", val + i);
        }
        ll res = 0;
        for (int i = 1; i <= m; ++i) {
            res += 1ll * gao(1, i) * num[i];
        }
        printf("%lld\n", res);
    }
    return 0;
}

E. 2Nodes

UnSolved.

题意：

有一棵树，每个点有颜色(白、红、蓝)，每秒钟，对于每个白色节点，如果它相邻的节点中存在非白色的，那么就将当前节点染色成那个节点的颜色，如果有多个，那么选取标号最小的那个点的颜色作为当前点的染色。
现在最多能将 $2$ 个点变成白色，问如何变使得最终红色点最多？

思路：

F. Pretests

Solved By Dup4. 2:45(+2)

题意：

对于一个题目，有 $t$ 组数据，有 $n$ 份待评测的程序，每份程序如果挂在了第 $k$ 个点，那么它需要的测试时间为 $k$ ，如果通过所有数据，那么测试的时间为 $t$ ，现在给出每份程序对于每个点的通过情况，可以重新安排测试点的顺序，使得总的测试时间最小。输出字典序最小的方案。

思路：

$f[S]$ 表示前 $i$ 个测试点的集合为 $S$ ，需要的最少测试时间，然后枚举一个 $j$ 进行转移， $j$ 要包含在 $S$ 中。
然后发现额外的贡献是测试程序的通过测试点的集合是 $S$ 的超集，然后这部分贡献可以用高维前缀和预处理。
总时间复杂度 $O(n \cdot 2^n)$ ，对于字典序，直接记录一个 string 即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 10, INF = 0x3f3f3f3f;
int t, n, cnt[N], f[N];
char s[110];
vector<int> g[N];

inline void chmin(int &x, int y) {
    if (x > y)
        x = y;
}

int main() {
    freopen("tests.in", "r", stdin);
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d%d", &t, &n);
        for (int i = 0; i < (1 << t); ++i) cnt[i] = 0, f[i] = INF, g[i].clear();
        f[0] = 0;
        int more = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%s", s);
            int res = 0;
            for (int j = 0; j < t; ++j) {
                if (s[j] == '1') {
                    res |= 1 << j;
                }
            }
            if (res == (1 << t) - 1)
                more += t - 1;
            else
                ++cnt[res];
        }
        for (int j = 0; j < t; ++j) {
            for (int i = 0; i < 1 << t; ++i) {
                if (!(i >> j & 1))
                    cnt[i] += cnt[i ^ (1 << j)];
            }
        }
        for (int i = 1; i < 1 << t; ++i) {
            for (int j = 0; j < t; ++j) {
                if ((i >> j) & 1) {
                    int nx = i ^ (1 << j);
                    g[nx].push_back(j);
                    if (f[nx] < f[i] || (f[nx] == f[i] && g[nx] < g[i])) {
                        f[i] = f[nx];
                        g[i] = g[nx];
                    }
                    g[nx].pop_back();
                }
            }
            f[i] += cnt[i];
        }
        printf("%d\n", f[(1 << t) - 1] + n + more);
        for (int i = 0; i < t; ++i) printf("%d%c", g[(1 << t) - 1][i] + 1, " \n"[i == t - 1]);
    }
    return 0;
}

G. Is Topo Logical?

Solved By Dup4. 3:22(+1)

题意：

给出一个 $n$ 和两个入度数组 $a, b$ ，要求构造一个 $n$ 个点的有向图，满足刚开始时第 $i$ 个点的入度为 $a_i$ ，跑完拓扑排序后第 $i$ 个点的度数为 $b_i$ 。

思路：

基于 $b$ 数组中是否为 $0$ 将点分成两部分，为 $0$ 的那部分组成一条链，不为 $0$ 的那部分组成一个环。
然后根据入度连边即可，根据 $a_i, b_i$ 讨论一下入度的来源。

Code

#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int(x.size()))
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

const int N = 2e5 + 10;
int n, a[N], b[N], need[N];
vector<vector<int>> G;

bool gao() {
    G.clear();
    G.resize(n + 1);
    vector<int> A, B;
    for (int i = 1; i <= n; ++i) {
        need[i] = a[i] - b[i];
        if (!b[i])
            A.push_back(i);
        else
            B.push_back(i);
    }
    if (SZ(B) == 1)
        return 0;
    for (int i = 0; i < SZ(B); ++i) {
        if (!i)
            G[B.back()].push_back(B[i]);
        else
            G[B[i - 1]].push_back(B[i]);
        --b[B[i]];
    }
    for (int i = 0; i < SZ(B); ++i) {
        for (int j = 0; b[B[i]] && j < SZ(B); ++j)
            if (i != j) {
                if (i == 0 && j == SZ(B) - 1)
                    continue;
                if (i != 0 && j == i - 1)
                    continue;
                --b[B[i]];
                G[B[j]].push_back(B[i]);
            }
        if (b[B[i]])
            return 0;
        for (int j = 0; need[B[i]] && j < SZ(A); ++j) {
            --need[B[i]];
            G[A[j]].push_back(B[i]);
        }
        if (need[B[i]])
            return 0;
    }
    sort(A.begin(), A.end(), [&](int x, int y) {
        return a[x] < a[y];
    });
    for (int i = 0; i < SZ(A); ++i) {
        if (a[A[i]] > i)
            return 0;
        for (int j = 0; a[A[i]] && j < i; ++j) {
            --a[A[i]];
            G[A[j]].push_back(A[i]);
        }
    }
    int sze = 0;
    for (int i = 1; i <= n; ++i) sze += SZ(G[i]);
    printf("%d\n", sze);
    for (int i = 1; i <= n; ++i) {
        for (auto& it : G[i]) {
            printf("%d %d\n", i, it);
        }
    }
    return 1;
}

int main() {
    freopen("topo.in", "r", stdin);
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        for (int i = 1; i <= n; ++i) scanf("%d", b + i);
        if (!gao())
            printf("-1\n");
    }
    return 0;
}

H. Bugged System

Solved By Hsueh-. 1:29(+4)

题意：

一个地铁站，有 $n$ 个站，但是存在一个 bug，如果一个人从 $a$ 站进站 $b$ 站出来则不用钱，人们可以交换地铁卡。
问 $n$ 个人分别从 $s_i$ 进站， $d_i$ 出站，是否存在一个方案使得大家不花钱。
如果存在则输出最小行动距离和。

思路：

很显然如果存在则是一个环，那么每个站的进站数量等于出站数量，距离就是每个人的行动距离

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e6 + 10;

int n, m;
ll a[N];
int vis[N];

int main() {
    freopen("bugged.in", "r", stdin);

    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            vis[i] = 0;
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", a + i);
        }
        ll res = 0;
        for (int i = 1, s, d; i <= m; ++i) {
            scanf("%d %d", &s, &d);
            vis[s]++;
            vis[d]--;
            res += abs(a[s] - a[d]);
        }
        for (int i = 1; i <= n; ++i) {
            if (vis[i]) {
                res = -1;
                break;
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}

I. Rise of the Robots

Solved By Hsueh-. 2:34(+3)

题意：

一个半径为 $R$ 的图，一个半径为 $r$ 机器人，经过 $n$ 次操作，每次操作都从 $(x,y)$ 到 $(x+dx_i, y+dy_i)$ ，问是否存在一个起点，使得机器人没有出整个圆。

思路：

猜测可以求出一个圆表示机器人的路径，那么求一个最小覆盖圆即可。

Code

#include <bits/stdc++.h>

using namespace std;

using db = double;

const int N = 1e5 + 10;
const db eps = 1e-10;

mt19937 rnd(time(0));

int sgn(db x) {
    if (fabs(x) < eps)
        return 0;
    return x > 0 ? 1 : -1;
}

struct Point {
    db x, y;
    Point(db x = 0, db y = 0) : x(x), y(y) {}
    Point operator+(const Point& b) const {
        return Point(x + b.x, y + b.y);
    }
    Point operator-(const Point& b) const {
        return Point(x - b.x, y - b.y);
    }
    Point operator*(const db& b) const {
        return Point(x * b, y * b);
    }
    Point operator/(const db& b) const {
        return Point(x / b, y / b);
    }
    db operator^(const Point& b) const {
        return x * b.y - y * b.x;
    }
    db operator*(const Point& b) const {
        return x * b.x + y * b.y;
    }
    db len() {
        return hypot(x, y);
    }
    db len2() {
        return x * x + y * y;
    }
    db dis(Point b) {
        return hypot(x - b.x, y - b.y);
    }
    Point rotright() {
        return Point(y, -x);
    }
} p[N];

struct Circle {
    Point p;
    db r;
    Circle() {}
    Circle(Point p, db r) : p(p), r(r) {}
    Circle(db x, db y, db r) : p(Point(x, y)), r(r) {}
    Circle(Point a, Point b, Point c, int opt = 0) {
        if (opt == 0) {
            Point p0 = (a + b) / 2;
            Point v0 = (b - a).rotright();
            Point p1 = (a + c) / 2;
            Point v1 = (c - a).rotright();
            db t = ((p1 - p0) ^ v1) / (v0 ^ v1);
            p = p0 + v0 * t;
            r = p.dis(a);
        }
    }
};

int n, R, r;

Point solve() {
    shuffle(p + 1, p + 1 + n, rnd);
    Circle cir(0, 0, 0);
    for (int i = 1; i <= n; ++i) {
        if (sgn((cir.p - p[i]).len2() - cir.r) > 0) {
            cir.p = p[i];
            cir.r = 0;
            for (int j = 1; j < i; ++j) {
                if (sgn((cir.p - p[j]).len2() - cir.r) > 0) {
                    cir.p = (p[i] + p[j]) / 2;
                    cir.r = (p[j] - cir.p).len2();
                    for (int k = 1; k < j; ++k) {
                        if (sgn((cir.p - p[k]).len2() - cir.r) > 0) {
                            cir = Circle(p[i], p[j], p[k]);
                            cir.r = (p[k] - cir.p).len2();
                        }
                    }
                }
            }
        }
    }
    cir.p.x *= -1;
    cir.p.y *= -1;
    if (sgn(cir.p.x) == 0)
        cir.p.x = 0;
    if (sgn(cir.p.y) == 0)
        cir.p.y = 0;
    return cir.p;
}

int main() {
    freopen("robots.in", "r", stdin);

    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d %d %d", &n, &R, &r);
        db x = 0, y = 0;
        for (int i = 1, dx, dy; i <= n; ++i) {
            scanf("%d %d", &dx, &dy);
            x += dx, y += dy;
            p[i] = Point(x, y);
        }
        ++n;
        p[n] = Point(0, 0);
        Point res = solve();
        printf("%.9f %.9f\n", res.x, res.y);
    }
    return 0;
}

J. Clarifications

Solved By Dup4 & Hsueh-. 4:19(+)

题意：

在一场时长为 $m$ 的比赛中，有 $n$ 个问题，有 $k$ 个种类的问题，有两个回答的人 A 和 B，A 能在任何时刻回答任何问题，B 只能回答在这之前 A 回答过的问题中相同种类的问题。
每个问题有两个参数 $t_i, p_i$ ，分别表示询问的时刻和种类。现在问基于上述限制条件，回答完所有问题最少需要多少时间。

思路：

考虑已经被 A 回答过的种类是没有区别的，并且优先级最低。
然后考虑还没有回答过的，但是已经在队列中了，我们根据他们在队列中出现的次数进行优先级排序，对于 A 来说，每次取优先级最高的出来回答掉，然后释放出一些问题，可以让 B 也一起帮忙回答。
但是如果有两个问题的出现次数相同，我们可以将下一秒会出现的问题也纳入考量之中。
维护优先级的操作可以用线段树维护。

Code

#include <bits/stdc++.h>
using namespace std;
using pII = pair<int, int>;
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
const int N = 1e5 + 10, INF = 1e9;
int n, m, K, sta[N];

struct SEG {
    struct node {
        int val, pos;
        node(int val = 0, int pos = 0) : val(val), pos(pos) {}
        node operator+(const node &other) const {
            node res = node();
            if (val > other.val) {
                res = (*this);
            } else {
                res = other;
            }
            return res;
        }
    } t[N << 2];
    void build(int id, int l, int r) {
        t[id] = node();
        if (l == r) {
            t[id].pos = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void update(int id, int l, int r, int pos, int v) {
        //		dbg(id, l, r, pos, v);
        if (l == r) {
            t[id].val += v;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(id << 1, l, mid, pos, v);
        else
            update(id << 1 | 1, mid + 1, r, pos, v);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
} seg;

int main() {
    freopen("clar.in", "r", stdin);
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d%d%d", &m, &n, &K);
        vector<vector<int>> vec(m + 5);
        for (int i = 1, t, p; i <= n; ++i) {
            scanf("%d%d", &t, &p);
            vec[t].push_back(p);
        }
        // 0 没出现过 1 在seg中 2 被回答过一次
        for (int i = 1; i <= K; ++i) sta[i] = 0;
        seg.build(1, 1, K);
        int cnt = 0;
        int t = 1;
        int remind = n;
        while (remind) {
            if (t <= m)
                for (auto &it : vec[t]) {
                    if (sta[it] == 0) {
                        ++sta[it];
                        seg.update(1, 1, K, it, 1);
                    } else if (sta[it] == 1) {
                        seg.update(1, 1, K, it, 1);
                    } else if (sta[it] == 2) {
                        ++cnt;
                    }
                }
            if (t + 1 <= m)
                for (auto &it : vec[t + 1]) {
                    if (sta[it] == 1) {
                        seg.update(1, 1, K, it, 1);
                    }
                }
            if (cnt)
                --cnt, --remind;
            int val = seg.t[1].val, pos = seg.t[1].pos;
            if (sta[pos] != 1)
                pos = 0;
            if (pos) {
                cnt += val - 1;
                sta[pos] = 2;
                --remind;
                seg.update(1, 1, K, pos, -INF);
            } else if (cnt) {
                --cnt;
                --remind;
            }
            if (t + 1 <= m)
                for (auto &it : vec[t + 1]) {
                    if (it == pos) {
                        --cnt;
                    } else if (sta[it] == 1) {
                        seg.update(1, 1, K, it, -1);
                    }
                }
            ++t;
        }
        printf("%d\n", t - 1);
    }
    return 0;
}

K. Tourists' Tour

Solved By Dup4 & Hsueh-. 1:11(+1)

题意：

有 $n$ 座山峰，每座山峰的高度为 $h_i$ ，对于第 $i$ 座山峰，如果它左边有比他高的山峰，那么它会找一座离它最近的并且比它高的然后在这之间建立一座桥(即连一条边)。
对于右边亦是如此，现在要对这些边进行染色，使得任意两条相邻的边不同色，注意边是无向边。

思路：

强制让高的山峰连向低的山峰，变成 DAG，然后暴力染色即可。

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];
vector<vector<int> > G;
int col[N], in[N], vis[N][6];

int gao() {
    int rt = 0;
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 0) {
            rt = i;
            break;
        }
    }
    int Max = 0;
    queue<int> q;
    q.push(rt);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 1; i <= 5; ++i) {
            if (vis[u][i])
                continue;
            col[u] = i;
            Max = max(Max, i);
            for (auto v : G[u]) {
                vis[v][i] = 1;
                in[v]--;
                if (in[v] == 0) {
                    q.push(v);
                }
            }
            break;
        }
    }
    return Max;
}

int main() {
    freopen("tour.in", "r", stdin);

    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            col[i] = 0;
            in[i] = 0;
            for (int j = 0; j < 6; ++j) {
                vis[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
        }
        G.clear();
        G.resize(n + 1);
        stack<int> stk;
        for (int i = 1; i <= n; ++i) {
            while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
            if (!stk.empty()) {
                int u = stk.top();
                int v = i;
                G[u].push_back(v);
                in[v]++;
            }
            stk.push(i);
        }
        while (!stk.empty()) stk.pop();
        for (int i = n; i >= 1; --i) {
            while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
            if (!stk.empty()) {
                int u = stk.top();
                int v = i;
                G[u].push_back(v);
                in[v]++;
            }
            stk.push(i);
        }
        int Max = gao();
        printf("%d\n", Max);
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", col[i], " \n"[i == n]);
        }
    }
    return 0;
}

L. Sad Meals

UnSolved.

题意：

有一个厨师做菜，假设他在第 $i$ 天之前已经会了 $x$ 道菜了。
那么他在第 $i$ 可能学新菜，即 $a_i = x + 1$ 。
也可能顺着前一天的顺序做菜，即 $a_i = a_{i - 1} + 1$ 。
如果前一天做完了已经学会的菜，那么就重新开始轮回，即做第一道菜 $a_i = 1$ 。
现在给出 $a$ 数组，但是挖空了一些位置，要求补充上这些位置，使得满足上述限制条件。

思路：

Last update: March 27, 2022
Created: March 27, 2022