2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest
Contents
Contest Info
| 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.
题意:
要下载一个软件,默认的下载速度是 
思路:
枚举一个加速包的用量,二分另一个加速包的用量。
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(+)
题意:
一个 P 规定一个方向,一旦方向确定就不能更改,问吃到最大的 * 的最下时间。
思路:
- 当 P的个数大于等于的时候可以吃到所有的 *。
- 那么二分答案去 check。
- 表示前 - 个 - 能覆盖的最大的 - 。 
- 对于 个 有三种转移,分别是向左,向右或者 向左 向右, 去 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(+)
题意:
长度为 * 的字符有几个。
思路:
模拟。
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)
题意:
给出一个字符串 
思路:
- 考虑串的个数 是 的因子,然后暴力枚举。 
- 如何判断是否合法?
令 
- 如果 ,那么输出原串。 
- 否则需要满足 , 是偶数,并且 也是偶数。 
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)
题意:
- 给出 个物品,第 个物品的权值为 ,现在考虑将它们分组,每组物品个数不少于 个,一组物品的代价为其物品的极差,考虑如何分组使得最大极差最小。 
- 输出这个最小的最大极差。
思路:
先二分 
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)
题意:
有 
求最多能拆几座城市。
思路:
- 使劲儿贪心。
- 一座城市如果它要被拆,那么拆的越晚,答案肯定不会更差。
- 那么预处理出每座城市最晚什么时候被拆。
- 然后将城市按 从小到大排序,一一决策,假设当前这座城市能够被拆,那么一定拆。 
怎么样能被拆?
- 假设这座城市最晚被拆的时间为 ,那么前 个月份还剩下的钱要大于等于 ,然后我们考虑花哪个月份的钱,肯定是小于 ,并且离 越近的那个月份,这个可以用线段树维护一下,然后暴力去扣钱,一个每个月份只会被扣光一次。 
- 时间复杂度 。 
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(+)
题意:
思路:
正着推一遍,倒着推一遍即可。
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;
}
Created: March 27, 2022