Skip to content

2019-2020 ACM-ICPC Latin American Regional Programming Contest

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J K L M
9/13 - - Ø O O - O Ø O - O O O
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

A. Algorithm Teaching

UnSolved.

题意：

思路：

B. Build the Perfect House

UnSolved.

题意：

思路：

C. Cut Inequality Down

UpSolved by Dup4.

题意：

有一个序列 a_i，长度为 n，和两个参数 L, U，现在每次询问给出 B, E, X，要求作如下操作：

  • 令 i 从 B 遍历到 E。
  • 然后令 \displaystyle X = max(L, min(R, X + a_i))。
  • 输出最后的 X。

思路：

  • 考虑对于每一次查询，可以 O(\log n) 的时间找到下一个变化的点，那么从下一个变化的点开始往下走，那么容易发现从下一个变化的点开始走的初始值要么是 L，要么是 U，那么我们可以将每个 a_i 拆成两个点，一个是起始值为 L，从第 i 个点开始往下走，一个是起始值为 U，从第 i 个点开始往下走，发现会形成树形结构。
  • 那么我们每次从初始值找到第一个变化的点之后直接在树上倍增即可。
Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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...);
}
#define fi first
#define se second
#define SZ(x) (int(x.size()))
const int N = 1e5 + 10, M = 20;
const ll INFLL = 1e18;
int n, L, R, q, a[N];
// 0 L 1 R
ll S[N];

vector<vector<int>> G;

struct RMQ {
    ll Max[N][M];
    ll Min[N][M];
    int mm[N];
    void init(int n, ll *b) {
        mm[0] = -1;
        for (int i = 1; i <= n; ++i) {
            mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
            Max[i][0] = b[i];
            Min[i][0] = b[i];
        }
        for (int j = 1; j <= mm[n]; ++j) {
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
                Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    ll queryMax(int x, int y) {
        int k = mm[y - x + 1];
        return max(Max[x][k], Max[y - (1 << k) + 1][k]);
    }
    ll queryMin(int x, int y) {
        int k = mm[y - x + 1];
        return min(Min[x][k], Min[y - (1 << k) + 1][k]);
    }
    int queryL(int x, ll ini) {
        int l = x, r = n, res = n;
        while (r - l >= 0) {
            int mid = (l + r) >> 1;
            if (ini + queryMin(x, mid) - S[x - 1] <= L) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res + 1;
    }
    int queryR(int x, ll ini) {
        int l = x, r = n, res = n;
        while (r - l >= 0) {
            int mid = (l + r) >> 1;
            if (ini + queryMax(x, mid) - S[x - 1] >= R) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res + 1;
    }
} rmq;

void addEdge(int ini, int id) {
    int nl = rmq.queryL(id / 2, ini);
    int nr = rmq.queryR(id / 2, ini);
    if (nl < nr) {
        // dbg(nl * 2, id);
        G[nl * 2].push_back(id);
    } else {
        // dbg(nr * 2 + 1, id);
        G[nr * 2 + 1].push_back(id);
    }
}

int fa[M][N * 2 + 10];

void dfs(int u) {
    for (int i = 1; i < M; ++i) fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (auto &v : G[u]) {
        fa[0][v] = u;
        dfs(v);
    }
}

ll get(int u, int E) {
    // dbg(u, E);
    for (int i = M - 1; i >= 0; --i) {
        if (fa[i][u] / 2 <= E)
            u = fa[i][u];
    }
    // dbg(u, E);
    ll ans = u % 2 ? R : L;
    ans += S[E] - S[u / 2 - 1];
    if (ans > R)
        ans = R;
    if (ans < L)
        ans = L;
    return ans;
}

int main() {
    scanf("%d%d%d", &n, &L, &R);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), S[i] = S[i - 1] + a[i];
    rmq.init(n, S);
    G.clear();
    G.resize(n * 2 + 20);
    for (int i = 1; i <= n; ++i) {
        addEdge(L, 2 * i);
        addEdge(R, 2 * i + 1);
    }
    fa[0][2 * (n + 1)] = 2 * (n + 1);
    fa[0][2 * (n + 1) + 1] = 2 * (n + 1) + 1;
    dfs(2 * (n + 1));
    dfs(2 * (n + 1) + 1);
    scanf("%d", &q);
    for (int i = 1, B, E, X; i <= q; ++i) {
        scanf("%d%d%d", &B, &E, &X);
        int nl = rmq.queryL(B, X);
        int nr = rmq.queryR(B, X);
        if (min(nl, nr) - 1 >= E) {
            ll ans = S[E] - S[B - 1] + X;
            if (ans > R)
                ans = R;
            if (ans < L)
                ans = L;
            printf("%lld\n", ans);
        } else {
            int id;
            if (nl < nr)
                id = nl * 2;
            else
                id = nr * 2 + 1;
            printf("%lld\n", get(id, E));
        }
    }
    return 0;
}

D. Dazzling stars

Solved By Hsueh-. 3:47(+1)

题意：

  • 有 n 个星星，每个星星有坐标和亮度，问是否存在一个方向，使得这个方向过来亮度从高到低递减。

思路：

处理出每对从亮的到暗的方向向量范围，看有没有交集。

Code 
#include <bits/stdc++.h>

using namespace std;

using db = double;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}

const db PI = acos(-1.0), eps = 1e-8;
const int N = 2e3 + 10;

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

struct Point {
    int x, y;

    Point() {}
    Point(int x, int y) : x(x), y(y) {}
    Point operator-(const Point &other) const {
        return {x - other.x, y - other.y};
    }
    Point rot() {
        return {-y, x};
    }
} a[N];

struct node {
    Point p;
    int val, id;
    db arc;

    bool operator<(const node &other) const {
        if (sgn(arc - other.arc) == 0)
            return val > other.val;
        else
            return arc < other.arc;
    }
};

int n, tot;
vector<node> vec;
int b[N];
int add[N * N];
int l[N * N], r[N * N];

bool ok() {
    if (vec.empty())
        return true;
    for (auto &it : vec) {
        it.arc = atan2(it.p.y, it.p.x);
    }
    sort(vec.begin(), vec.end());
    for (int i = 0, len = vec.size(); i < len; ++i) {
        if (vec[i].val == 1)
            l[vec[i].id] = i;
        else
            r[vec[i].id] = i;
    }
    for (int i = 0; i < tot; ++i) {
        if (l[i] < r[i]) {
            add[l[i]]++;
            add[r[i] + 1]--;
        } else {
            add[l[i]]++;
            add[0]++;
            add[r[i] + 1]--;
        }
    }
    int cnt = 0;
    for (int i = 0; i < 2 * tot; ++i) {
        cnt += add[i];
        if (cnt == tot)
            return true;
    }
    return false;
}

void push(Point a, Point b) {
    vec.push_back({(a - b).rot(), -1, tot});
    vec.push_back({(b - a).rot(), 1, tot});
    tot++;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d %d", &a[i].x, &a[i].y, &b[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (b[i] == b[j])
                continue;
            if (b[i] > b[j]) {
                push(a[i], a[j]);
            } else {
                push(a[j], a[i]);
            }
        }
    }
    if (ok())
        puts("Y");
    else
        puts("N");
    return 0;
}

E. Eggfruit Cake

Solved By Dup4. 0:14(+)

题意：

给出一个字符串环，里面只有 E 和 P 两种字符，现在问有多少区间，满足这个区间长度小于等于 S，并且里面至少有一个 E。

思路：

复制一遍，拓展成 2n，然后扫一遍即可。

Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int n, S;
char s[N];

int main() {
    scanf("%s%d", s + 1, &S);
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) s[i + n] = s[i];
    int pre = 0;
    for (int i = 1; i <= n; ++i)
        if (s[i] == 'E')
            pre = i;
    ll res = 0;
    for (int i = n + 1; i <= n * 2; ++i) {
        if (s[i] == 'E')
            pre = i;
        int last = i - S;
        res += max(0, pre - last);
    }
    printf("%lld\n", res);
    return 0;
}

F. Fabricating Sculptures

UpSolved by Dup4.

题意：

堆箱子，最底层有 S 个，一共有 B 个箱子，一层一层往上堆，每一层必须连续，且个数不超过之前那一层，并且当前层的箱子必须都要上一层的箱子之上。

思路：

f[i][j] 表示用了 i 个箱子，最上层有 j 个，那么转移有：

f[i][j] = \sum\limits_{k = j}^S f[i - k][k] \cdot (k - j + 1)

然后维护 f[i][j] \cdot j 以及 f[i][j] 的后缀和即可。

Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#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 mod = 1e9 + 7;
const int N = 5e3 + 10;
int n, S, B;
ll f[N][N], g[N][N], h[N][N];

// f[i][j] 用了i个 最上面一层有j 个的方案数

int main() {
    scanf("%d%d", &S, &B);
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    memset(h, 0, sizeof h);
    f[S][S] = 1;
    for (int i = S; i >= 1; --i) {
        g[S][i] = (g[S][i + 1] + f[S][i]) % mod;
        h[S][i] = (h[S][i + 1] + f[S][i] * i % mod) % mod;
    }
    for (int i = S + 1; i <= B; ++i) {
        for (int j = 1; j <= S; ++j) {
            f[i][j] = 1ll * (1 - j + mod) % mod * (g[i - j][j] - g[i - j][S + 1] + mod) % mod;
            f[i][j] = (f[i][j] + (h[i - j][j] - h[i - j][S + 1] + mod) % mod) % mod;
            //	if (f[i][j]) dbg(i, j, f[i][j]);
        }
        for (int j = S; j >= 1; --j) {
            g[i][j] = (g[i][j + 1] + f[i][j]) % mod;
            h[i][j] = (h[i][j + 1] + f[i][j] * j % mod) % mod;
        }
    }
    ll res = 0;
    for (int i = 1; i <= S; ++i) {
        res = (res + f[B][i]) % mod;
    }
    printf("%lld\n", res);
    return 0;
}

G. Gluing Pictures

Solved By Dup4. 0:54(+)

题意：

给出一个字符串 S，有 q 次询问，每次询问给出一个字符串 T，问 T 最少能分成多少段，使得每段都是 S 的一个子串。

思路：

  • 考虑 f[i] 表示 T 中的前 i 个字符最少需要多少段，显然 f 具有单调不减性质。
  • 然后我们对 S 建 SAM，然后用 T 在 SAM 上跑匹配，如果不能往下拓展了就跳后缀，维护当前匹配的最长后缀长度，进行转移即可。
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...);
}

const int N = 2e5 + 10, ALP = 26;
int n, q, f[N];
char s[N], t[N];

struct SAM {
    struct node {
        int maxlen, cnt, fa, nx[ALP];
        void init() {
            maxlen = cnt = fa = 0;
            memset(nx, 0, sizeof nx);
        }
    } t[N << 1];
    int tot, lst;
    int newnode() {
        ++tot;
        t[tot].init();
        return tot;
    }
    void init() {
        tot = 0;
        lst = newnode();
    }
    void extend(int id) {
        int cur = newnode(), p;
        t[cur].cnt = 1;
        t[cur].maxlen = t[lst].maxlen + 1;
        for (p = lst; p && !t[p].nx[id]; p = t[p].fa) t[p].nx[id] = cur;
        if (!p) {
            t[cur].fa = 1;
        } else {
            int q = t[p].nx[id];
            if (t[q].maxlen == t[p].maxlen + 1) {
                t[cur].fa = q;
            } else {
                int clone = newnode();
                t[clone] = t[q];
                t[clone].cnt = 0;
                t[clone].maxlen = t[p].maxlen + 1;
                for (; p && t[p].nx[id] == q; p = t[p].fa) t[p].nx[id] = clone;
                t[cur].fa = t[q].fa = clone;
            }
        }
        lst = cur;
    }
    void build(char *s) {
        init();
        for (int i = 1; s[i]; ++i) {
            extend(s[i] - 'A');
        }
    }
    int solve(char *s) {
        int len = strlen(s + 1);
        memset(f, -1, sizeof(f[0]) * (len + 5));
        f[0] = 0;
        int cur = 1;
        int curlen = 0;
        for (int i = 1; i <= len; ++i) {
            while (cur && t[cur].nx[s[i] - 'A'] == 0) {
                cur = t[cur].fa;
                curlen = min(curlen, t[cur].maxlen);
            }
            if (cur == 0)
                return -1;
            cur = t[cur].nx[s[i] - 'A'];
            ++curlen;
            f[i] = f[i - curlen] + 1;
        }
        return f[len];
    }
} sam;

int main() {
    scanf("%s", s + 1);
    scanf("%d", &q);
    sam.build(s);
    while (q--) {
        scanf("%s", t + 1);
        printf("%d\n", sam.solve(t));
    }
    return 0;
}

H. Hold or Continue?

UnSolved.

题意：

思路：

I. Improve SPAM

Solved By Hsueh-. 1:00(+)

题意：

给定一个 DAG 的 SPAM，其中有 L 个邮件列表，n 个客户，邮件列表会像里面的邮件客户端的人发邮件，问从 1 开始发邮件，用户客户端会收到多少邮件，有多少用户收到邮件。

思路：

搜索水题。

Code 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)

void err() {
    cout << endl;
}

template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

const int N = 2e3 + 10;
const ll p = 1e9 + 7;

int n, l;
vector<vector<int>> G;
ll f[N];
int vis[N];

ll gao(int u) {
    if (vis[u])
        return f[u];
    vis[u] = 1;
    if (u > l)
        f[u] = 1;
    for (auto v : G[u]) {
        f[u] = (f[u] + gao(v)) % p;
    }
    return f[u];
}

int main() {
    scanf("%d %d", &n, &l);
    G.clear();
    G.resize(n + 1);
    for (int i = 1, m; i <= l; ++i) {
        scanf("%d", &m);
        for (int j = 1, x; j <= m; ++j) {
            scanf("%d", &x);
            G[i].push_back(x);
        }
    }
    ll res1 = gao(1), res2 = 0;
    for (int i = l + 1; i <= n; ++i) {
        res2 += vis[i];
    }
    printf("%lld %lld\n", res1, res2);
    return 0;
}

J. Jumping Grasshoper

UnSolved.

题意：

思路：

K. Know your Aliens

Solved By Dup4. 1:23(+)

题意：

  • 给出一个长度为 n 的字符串 S，字符串中只有 H 和 A 两种字符。
  • 现在要构造一个多项式 P，对于第 i 个字符：
  • 如果是 H，那么要满足 P(2i) > 0。
  • 如果是 A，那么要满足 P(2i) < 0。

这个多项式要满足系数和根均为整数，最高项系数只能为 1 和 -1，并且在所有可行答案中最高项要尽可能小。

思路：

  • 考虑将多项式写成 \prod (a_i - x) 的形式，那么如果 P(2i) < 0，即有奇数个小于 0 的数相乘，否则是偶数个。
  • 那么考虑字符串中每个 H 和 A 的变换的地方，假设第 i 和第 i + 1 个字符不同，那么我们在多项式中插入 (i \cdot 2 + 1 - x)，即可符合题意。
Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SZ(x) (int((x).size()))
const int N = 1e4 + 10;
char s[N];
int n;

vector<ll> vec;

void gao(ll x) {
    ll t = vec.back();
    for (int i = SZ(vec) - 2; i >= 0; --i) {
        vec[i + 1] = vec[i + 1] * x - vec[i];
    }
    vec[0] *= x;
    vec.push_back(-t);
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    if (s[1] == 'H')
        vec.push_back(1);
    else
        vec.push_back(-1);
    for (int i = 2; i <= n; ++i) {
        if (s[i] != s[i - 1]) {
            //	cout << (i - 1) * 2 + 1 << endl;
            gao((i - 1) * 2 + 1);
        }
    }
    reverse(vec.begin(), vec.end());
    printf("%d\n", SZ(vec) - 1);
    for (int i = 0; i < SZ(vec); ++i) printf("%lld%c", vec[i], " \n"[i == SZ(vec) - 1]);
    return 0;
}

L. Leverage MDT

Solved By Hsueh-. 1:42(+)

题意：

  • 给出一个 01 二维矩阵，每次可以将某一行的状态翻转，问任意翻转后，能否找一个最大的正方形，使得正方形内全是 0，问最大的正方形面积是多少。

思路：

  • 题意等价于找一个最大的正方形，使得正方形内每一行元素一致。
  • 先对每一行处理出当前点往后有多少个连续相同的元素，然后二分正方形边长 x，然后用同样的思想对于每一列按行枚举进行 check 即可。
Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n, m;
char s[N][N];
int suf[N][N];

bool check(int x) {
    for (int j = 1; j <= m; ++j) {
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (suf[i][j] >= x)
                ++cnt;
            else
                cnt = 0;
            if (cnt >= x)
                return true;
        }
    }
    return false;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s[i] + 1);
        suf[i][m] = 1;
        for (int j = m - 1; j >= 1; --j) {
            if (s[i][j] == s[i][j + 1])
                suf[i][j] = suf[i][j + 1] + 1;
            else
                suf[i][j] = 1;
        }
    }
    int l = 1, r = 1000, res = -1;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            l = mid + 1;
            res = mid;
        } else {
            r = mid - 1;
        }
    }
    printf("%d\n", res * res);
    return 0;
}

M. Mountain Ranges

Solved By Hsueh-. 0:08(+)

题意：

问最长的增量不超过 x 的序列。

思路：

签到。

Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n, x;
int a[N], b[N];

int main() {
    scanf("%d %d", &n, &x);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        b[i] = a[i] - a[i - 1];
    }
    int res = 1, cnt = 1;
    for (int i = 2; i <= n; ++i) {
        if (b[i] <= x) {
            ++cnt;
        } else {
            cnt = 1;
        }
        res = max(res, cnt);
        // cout << i << " " << cnt << endl;
    }
    printf("%d\n", res);
    return 0;
}
Last update: March 27, 2022
Created: March 27, 2022
Back to top