Skip to content

2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest

Contents

Contest Info

Practice Link

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

Solutions

A. Automatic Door

UnSolved.

题意:

思路:

B. Berland Army

UnSolved.

题意:

思路:

C. Downloading B++

UpSolved by Dup4.

题意:

要下载一个软件,默认的下载速度是 t_0 s/byte, 可以花费 p_1 元,买加速包,能够以 t_1 s/byte 下载 a_1 byte,或者花费 p_2 元,能够以 t_2 s/byte 下载 a_2 byte,问在 T 时间内下载完,最少需要花多少钱。

思路:

枚举一个加速包的用量,二分另一个加速包的用量。

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 ll INF = 1e18;

ll f, T, t0, a1, t1, p1, a2, p2, t2;

inline ll ceil(ll x, ll y) {
    return (x + y - 1) / y;
}

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

struct E {
    ll a, t, p;
    bool operator<(const E &other) const {
        if (t != other.t)
            return t < other.t;
        return p < other.p;
    }
} e[3];

ll calc(ll remind, ll x, E e) {
    ll _remind = remind - e.a * x;
    if (_remind < 0)
        _remind = 0;
    ll useT = e.t * (remind - _remind);
    return useT + _remind * t0;
}

ll gao() {
    if (t0 * f <= T)
        return 0;
    ll res = INF;
    int n = ceil(f, e[1].a);
    for (int i = 0; i <= n; ++i) {
        ll now = e[1].p * i;
        ll remind = f - e[1].a * i;
        if (remind < 0)
            remind = 0;
        ll useT = e[1].t * (f - remind);
        if (useT > T)
            break;
        ll _T = T - useT;
        //	dbg(i, remind, f - remind, useT, now, _T);
        if (remind * e[0].t <= _T) {
            chmin(res, now);
            //	dbg(i, remind, remind * e[0].t, now);
        } else {
            if (remind * e[2].t > _T)
                continue;
            int _n = ceil(remind, e[2].a);
            int l = 0, r = _n, tar = _n;
            while (r - l >= 0) {
                int mid = (l + r) >> 1;
                //	dbg(mid, calc(remind, mid, e[2]));
                if (calc(remind, mid, e[2]) <= _T) {
                    tar = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            //	dbg(i, tar, _n);
            chmin(res, now + e[2].p * tar);
        }
    }
    if (res >= INF)
        return -1;
    return res;
}

int main() {
    scanf("%lld%lld%lld", &f, &T, &t0);
    scanf("%lld%lld%lld", &a1, &t1, &p1);
    scanf("%lld%lld%lld", &a2, &t2, &p2);
    e[0] = {1, t0, 0};
    e[1] = {a1, t1, p1};
    e[2] = {a2, t2, p2};
    sort(e + 1, e + 3);
    printf("%lld\n", gao());
    return 0;
}

D. Packmen Strike Back

Solved By Hsueh-. 4:29(+)

题意:

一个 1 \cdot n 的图,给上面的每个 P 规定一个方向,一旦方向确定就不能更改,问吃到最大的 * 的最下时间。

思路:

  • P 的个数大于等于 2 的时候可以吃到所有的 *
  • 那么二分答案去 check。
  • f_i 表示前 iP 能覆盖的最大的 1 - f_i
  • 对于 iP 有三种转移,分别是向左,向右或者 i - 1 向左 i 向右,dp 去 check。
Code
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

#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...);
}

int n;
char s[N];
int a[N];
int f[N];
int P[N], tot;

bool ok(int l, int r) {
    if (l > r)
        return 1;
    else
        return a[r] - a[l - 1] == 0;
}

bool check(int x) {
    memset(f, 0, sizeof f);
    for (int i = 1; i <= tot; ++i) {
        // left
        if (ok(f[i - 1] + 1, P[i] - x - 1))
            f[i] = max(f[i], P[i]);
        // right
        if (ok(f[i - 1] + 1, P[i] - 1))
            f[i] = max(f[i], P[i] + x);
        // left right
        if (i >= 2 && ok(f[i - 2] + 1, P[i] - x - 1))
            f[i] = max(f[i], P[i - 1] + x);
    }
    // dbg(f[1], f[2]);
    return ok(f[tot] + 1, n);
}

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + (s[i] == '*');
    }
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'P') {
            P[++tot] = i;
        }
    }
    if (tot == 1) {
        int cnt1 = 0, cnt2 = 0, pos = P[1], l = 0, r = 0;
        for (int i = pos - 1; i >= 1; --i) {
            if (s[i] == '*') {
                ++cnt1;
                l = i;
            }
        }
        for (int i = pos + 1; i <= n; ++i) {
            if (s[i] == '*') {
                ++cnt2;
                r = i;
            }
        }
        int res1 = 0, res2 = 0;
        if (cnt1 > cnt2) {
            res1 = cnt1, res2 = pos - l;
        } else if (cnt2 > cnt1) {
            res1 = cnt2, res2 = r - pos;
        } else {
            res1 = cnt1, res2 = min(pos - l, r - pos);
        }
        printf("%d %d\n", res1, res2);
    } else {
        printf("%d ", a[n]);
        // check(4);
        int l = 0, r = n, res = -1;
        while (r - l >= 0) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid - 1;
                res = mid;
            } else {
                l = mid + 1;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

E. Field of Wonders

Solved By Hsueh-. 1:39(+)

题意:

长度为 n 的字符串,其中有几个位置是不确定的,但是答案只有 m 种,问一定可以成为 * 的字符有几个。

思路:

模拟。

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

using namespace std;

const int N = 1e3 + 10;

int n, m;
string s;
string str[N];
int vis[N], cnt[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> s;
    for (auto it : s) {
        vis[it]++;
    }
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> str[i];
    }
    int res = 0;
    for (int i = 'a'; i <= 'z'; ++i) {
        char c = i;
        if (vis[i])
            continue;
        bool F = true;
        for (int j = 1; j <= m; ++j) {
            memset(cnt, 0, sizeof cnt);
            bool FF = true;
            for (int k = 0; k < n; ++k) {
                if (s[k] == '*' && vis[str[j][k]]) {
                    FF = false;
                    break;
                }
                if (s[k] == '*') {
                    cnt[str[j][k]]++;
                } else if (s[k] != str[j][k]) {
                    FF = false;
                    break;
                }
            }
            if (FF && !cnt[c]) {
                F = false;
                break;
            }
        }
        res += F;
    }
    cout << res << "\n";
    return 0;
}

F. Lost in Transliteration

Solved By Hsueh-. 0:32(+)

题意:

  • u 可以变成 oo
  • h 可以变成 kh
  • 问有几种字符串?

思路:

  • u 变成 oo
  • 遇到 h 删去前面的 k
  • 然后去重统计个数。
Code
#include <bits/stdc++.h>

using namespace std;

int n;
string s;
map<string, int> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        string t = "";
        for (int j = 0, len = s.size(); j < len; ++j) {
            if (s[j] == 'u')
                t += "oo";
            else {
                if (s[j] == 'h') {
                    while (!t.empty() && t[t.size() - 1] == 'k') {
                        t.pop_back();
                    }
                }
                t += s[j];
            }
        }
        if (!mp.count(t)) {
            mp[t]++;
            ++res;
        }
    }
    cout << res << "\n";
    return 0;
}

G. Orientation of Edges

Solved By Hsueh-. 2:38(+)

题意:

一张混合图,有一些有向边和无向边,给定一个起点,分别给无向边定向使得 S 到达的点最多最小,独立回答最大最小值。

思路:

  • 最大值,贪心的拓展到没到达的点。
  • 最小值,贪心的不拓展到其他点。
Code
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;

struct Edge {
    int to, id, val;

    Edge() {}

    Edge(int to, int id, int val) : to(to), id(id), val(val) {}
};

int n, m, s, tot;
vector<vector<Edge>> G, und;
int res[N], vis[N];

void gao1() {
    int cnt = 1;
    memset(vis, 0, sizeof vis);
    memset(res, 0, sizeof res);
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto it : G[u]) {
            int v = it.to;
            if (!vis[v]) {
                ++cnt;
                vis[v] = true;
                q.push(v);
            }
        }
        for (auto it : und[u]) {
            int v = it.to, id = it.id, val = it.val;
            if (!vis[v] && !res[id]) {
                res[id] = val;
                ++cnt;
                vis[v] = true;
                q.push(v);
            }
        }
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= tot; ++i) {
        if (res[i] == 1)
            putchar('+');
        else
            putchar('-');
    }
    puts("");
}

void gao2() {
    int cnt = 1;
    memset(vis, 0, sizeof vis);
    memset(res, 0, sizeof res);
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto it : G[u]) {
            int v = it.to;
            if (!vis[v]) {
                ++cnt;
                vis[v] = true;
                q.push(v);
            }
        }
        for (auto it : und[u]) {
            int v = it.to, id = it.id, val = it.val;
            if (!res[id]) {
                res[id] = -val;
            }
        }
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= tot; ++i) {
        if (res[i] == 1)
            putchar('+');
        else
            putchar('-');
    }
    puts("");
}

int main() {
    scanf("%d %d %d", &n, &m, &s);
    G.clear();
    G.resize(n + 1);
    und.clear();
    und.resize(n + 1);
    for (int i = 1, op, u, v; i <= m; ++i) {
        scanf("%d %d %d", &op, &u, &v);
        if (op == 1) {
            G[u].push_back(Edge(v, 1, 1));
        } else {
            und[u].push_back(Edge(v, ++tot, 1));
            und[v].push_back(Edge(u, tot, -1));
        }
    }
    gao1();
    gao2();
    return 0;
}

H. Palindromic Cu

Solved By Dup4. 2:01(+1)

题意:

给出一个字符串 S,可以将其中的字符重新排列,问能够分成若干个等长的回文串,求分得的最小数量和方案。

思路:

  • 考虑串的个数 kn 的因子,然后暴力枚举。
  • 如何判断是否合法?

a = \mbox{出现奇数次字符个数}, len = \frac{n}{k}

  • 如果 a = 0,那么输出原串。
  • 否则需要满足 k \geq a(len - 1) 是偶数,并且 (k - a) 也是偶数。
Code
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int(x.size()))
#define mkp make_pair
const int N = 4e5 + 10;
int n;
char s[N];
int cnt[320];

void gao(int k) {
    cout << k << "\n";
    vector<string> pre(k, ""), mid(k, "");
    vector<char> DB;
    if ((n / k) % 2) {
        vector<char> single;
        for (int i = 1; i < 255; ++i) {
            if (cnt[i] & 1) {
                single.push_back(char(i));
                --cnt[i];
            }
        }
        for (int i = 1; i < 255; ++i) {
            while (cnt[i] > 0 && SZ(single) + 2 <= k) {
                cnt[i] -= 2;
                single.push_back(char(i));
                single.push_back(char(i));
            }
        }
        for (int i = 0; i < k; ++i) {
            mid[i] += single.back();
            single.pop_back();
        }
    }
    for (int i = 1; i < 255; ++i) {
        assert(cnt[i] % 2 == 0);
        while (cnt[i] >= 2) {
            cnt[i] -= 2;
            DB.push_back(char(i));
        }
    }
    for (int i = 0; i < k; ++i) {
        while (SZ(pre[i]) * 2 + SZ(mid[i]) + 2 <= n / k) {
            pre[i] += char(DB.back());
            DB.pop_back();
        }
    }
    for (int i = 0; i < k; ++i) {
        assert(SZ(pre[i]) + SZ(mid[i]) + SZ(pre[i]) == n / k);
        if (SZ(pre[i]))
            cout << pre[i];
        if (SZ(mid[i]))
            cout << mid[i];
        if (SZ(pre[i])) {
            reverse(pre[i].begin(), pre[i].end());
            cout << pre[i];
        }
        cout << " \n"[i == k - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(cnt, 0, sizeof cnt);
    cin >> n >> (s + 1);
    for (int i = 1; i <= n; ++i) {
        assert(int(s[i]) <= 255);
        ++cnt[int(s[i])];
    }
    int a = 0;
    for (int i = 1; i < 255; ++i)
        if (cnt[i] & 1)
            ++a;
    for (int i = 1; i <= n; ++i)
        if (n % i == 0) {
            if (i == n) {
                gao(i);
                break;
            }
            if (a == 0 && (n / i) % 2 == 0) {
                gao(i);
                break;
            }
            if (a > 0 && i >= a && (i - a) % 2 == 0 && ((n / i) - 1) % 2 == 0) {
                gao(i);
                break;
            }
        }
    return 0;
}

I. Photo Processing

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

题意:

  • 给出 n 个物品,第 i 个物品的权值为 a_i,现在考虑将它们分组,每组物品个数不少于 k 个,一组物品的代价为其物品的极差,考虑如何分组使得最大极差最小。
  • 输出这个最小的最大极差。

思路:

先二分 x,转为判定性问题,然后 f[i] 表示前 i 个物品是否能够被分成若干组,并且每组的极差小于 x,然后转移即可,转移部分相当于查询区间和,以及单点修改,但是注意到更新的点和查询的区间点有单调性,直接动态处理前缀和即可。

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 = 3e5 + 10;
int n, K, a[N], f[N], S[N];

int ok(int x) {
    // dbg(x);
    memset(f, 0, sizeof f);
    S[0] = 0;
    int l = 1;
    for (int i = 1; i <= n; ++i) {
        while (a[i] - a[l] > x) ++l;
        int r = i - K + 1;
        //	dbg(i, l, r);
        if ((l <= r && (l - 1 <= 0 || S[r - 1] - S[l - 2] > 0)))
            f[i] = 1;
        S[i] = S[i - 1] + f[i];
    }
    return f[n];
}

int main() {
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    sort(a + 1, a + 1 + n);
    int l = 0, r = a[n] - a[1], res = r;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (ok(mid)) {
            r = mid - 1;
            res = mid;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", res);
    return 0;
}

J. Renovation

Solved By Dup4. 4:47(+1)

题意:

n 个月份,有 m 个城市要拆,每个城市有两个属性 b_i, p_i,每个月份会获得 a_i 元钱,一个城市能在第 i 个月份被拆除当且仅当 b_i \geq a_i,并且:

p_i \geq \sum\limits_{i = 1}^n - \sum [j \in \mbox{已经被拆除城市}] \cdot p_j

求最多能拆几座城市。

思路:

  • 使劲儿贪心。
  • 一座城市如果它要被拆,那么拆的越晚,答案肯定不会更差。
  • 那么预处理出每座城市最晚什么时候被拆。
  • 然后将城市按 p_i 从小到大排序,一一决策,假设当前这座城市能够被拆,那么一定拆。

怎么样能被拆?

  • 假设这座城市最晚被拆的时间为 j,那么前 j 个月份还剩下的钱要大于等于 p_i,然后我们考虑花哪个月份的钱,肯定是小于 j,并且离 j 越近的那个月份,这个可以用线段树维护一下,然后暴力去扣钱,一个每个月份只会被扣光一次。
  • 时间复杂度 O(n \log n)
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pII = pair<int, int>;
#define fi first
#define se second
#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 = 1e5 + 10;
int n, m, a[N];

struct E {
    int b, p, id;
    bool operator<(const E& other) const {
        if (p != other.p)
            return p < other.p;
        return b < other.b;
    }
} e[N];

struct SEG {
    struct node {
        ll val;
        int pos;
        node() {
            val = 0, pos = -1;
        }
        node operator+(const node& other) const {
            node res = node();
            res.val = val + other.val;
            res.pos = max(pos, other.pos);
            return res;
        }
    } t[N << 2];
    void build(int id, int l, int r) {
        t[id] = node();
        if (l == r) {
            t[id].val = a[l];
            if (t[id].val == 0)
                t[id].pos = -1;
            else
                t[id].pos = l;
            //	dbg(id, l, r, t[id].pos, t[id].val);
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    void update(int id, int l, int r, int pos, int v) {
        if (l == r) {
            t[id].val += v;
            if (t[id].val == 0)
                t[id].pos = -1;
            else
                t[id].pos = l;
            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];
    }
    ll query(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr)
            return t[id].val;
        int mid = (l + r) >> 1;
        ll res = 0;
        if (ql <= mid)
            res += query(id << 1, l, mid, ql, qr);
        if (qr > mid)
            res += query(id << 1 | 1, mid + 1, r, ql, qr);
        return res;
    }
    int queryPos(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr)
            return t[id].pos;
        int mid = (l + r) >> 1;
        int pos = -1;
        if (ql <= mid)
            pos = max(pos, queryPos(id << 1, l, mid, ql, qr));
        if (qr > mid)
            pos = max(pos, queryPos(id << 1 | 1, mid + 1, r, ql, qr));
        return pos;
    }
} seg;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= m; ++i) scanf("%d", &e[i].b);
    for (int i = 1; i <= m; ++i) scanf("%d", &e[i].p);
    vector<pII> vec;
    for (int i = 1; i <= n; ++i) {
        while (SZ(vec) && a[i] >= vec.back().fi) vec.pop_back();
        vec.push_back(pII(a[i], i));
    }
    reverse(vec.begin(), vec.end());
    for (int i = 1; i <= m; ++i) {
        auto pos = lower_bound(vec.begin(), vec.end(), pII(e[i].b, -1));
        if (pos == vec.end())
            e[i].id = -1;
        else
            e[i].id = pos->se;
        //	dbg(i, e[i].id);
    }
    sort(e + 1, e + 1 + m);
    int res = 0;
    seg.build(1, 1, n);
    for (int i = 1; i <= m; ++i)
        if (e[i].id != -1) {
            int id = e[i].id;
            if (seg.query(1, 1, n, 1, id) >= e[i].p) {
                ++res;
                int need = e[i].p;
                while (need > 0) {
                    int pos = seg.queryPos(1, 1, n, 1, id);
                    if (a[pos] >= need) {
                        a[pos] -= need;
                        seg.update(1, 1, n, pos, -need);
                        need = 0;
                    } else {
                        need -= a[pos];
                        seg.update(1, 1, n, pos, -a[pos]);
                        a[pos] = 0;
                    }
                }
            }
        }
    printf("%d\n", res);
    return 0;
}

K. Road Widening

Solved By Hsueh-. 1:05(+)

题意:

n 条路,每条路分为两种,可以将第二种变成第一种,使得满足 |s_i-s_{i-1}| \leq 1,问做大的变化长度。

思路:

正着推一遍,倒着推一遍即可。

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

using namespace std;

using ll = long long;

const int N = 2e5 + 10;

int n;
ll a[N], b[N], f[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld %lld", a + i, b + i);
        f[i] = a[i] + b[i];
    }
    for (int i = 2; i <= n; ++i) {
        f[i] = min(f[i - 1] + 1, f[i]);
    }
    for (int i = n - 1; i >= 1; --i) {
        f[i] = min(f[i + 1] + 1, f[i]);
    }
    for (int i = 1; i <= n; ++i) {
        if (f[i] < a[i]) {
            puts("-1");
            return 0;
        }
    }
    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        res += f[i] - a[i];
    }
    printf("%lld\n", res);
    for (int i = 1; i <= n; ++i) {
        printf("%lld%c", f[i], " \n"[i == n]);
    }
    return 0;
}

L. Berland.Taxi

UnSolved.

题意:

思路:

M. Quadcopter Competition

Solved By Dup4. 0:17(+)

题意:

在二维平面上给出一个起点和一个 flag,然后要求从起点出发绕一圈回来,使得 flag 严格被包含于这个圈子。

思路:

分共线和不共线讨论,其实也可以归并成一条。

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

int x[2], y[2];

int dis(int x, int y, int x1, int y1) {
    return abs(x - x1) + abs(y - y1);
}

int main() {
    scanf("%d%d%d%d", x, y, x + 1, y + 1);
    int Dis = dis(x[0], y[0], x[1], y[1]);
    if (x[0] == x[1] || y[0] == y[1])
        printf("%d\n", Dis * 2 + 6);
    else
        printf("%d\n", Dis * 2 + 4);
    return 0;
}

Last update: March 27, 2022
Created: March 27, 2022
Back to top