Skip to content

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

Contents

Contest Info

Practice Link

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

Solutions

A. Toda 2

Solved By Hsueh-. 0:39(+)

题意：

每次选 2-5 个人减一分，问所有人同分时候的最大分数。

思路：

模拟题，显然每次只用 2-3 人，那么：

  • 如果只有一个最大的就和次大的一起减一分。
  • 如果是偶数则选择两个减一分。
  • 如果是奇数则选择三个减一分。
Code 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e2 + 10, M = 1e4 + 10;

struct E {
    int id, v;
    E() {}

    E(int id, int v) : id(id), v(v) {}

    bool operator<(const E &other) const {
        return v < other.v;
    }
} a[N];

int n;
int f[M][N];
priority_queue<E> q;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i].v);
        a[i].id = i;
        q.push(a[i]);
    }
    for (int cas = 1;; ++cas) {
        vector<E> vec;
        vec.push_back(q.top());
        q.pop();
        while (!q.empty()) {
            if (q.top().v == vec[0].v) {
                vec.push_back(q.top());
                q.pop();
            } else {
                break;
            }
        }
        if (vec.size() == n) {
            printf("%d\n", vec[0].v);
            printf("%d\n", cas - 1);
            for (int i = 1; i < cas; ++i) {
                for (int j = 1; j <= n; ++j) {
                    printf("%d", f[i][j]);
                }
                puts("");
            }
            break;
        }
        if (vec.size() == 1) {
            E tmp = q.top();
            q.pop();
            tmp.v = max(tmp.v - 1, 0);
            f[cas][tmp.id] = 1;
            q.push(tmp);
            vec[0].v = max(vec[0].v - 1, 0);
            f[cas][vec[0].id] = 1;
            q.push(vec[0]);
        } else if (vec.size() % 2 == 0) {
            vec[0].v = max(vec[0].v - 1, 0);
            vec[1].v = max(vec[1].v - 1, 0);
            f[cas][vec[0].id] = 1;
            f[cas][vec[1].id] = 1;
            for (auto it : vec) {
                q.push(it);
            }
        } else {
            vec[0].v = max(vec[0].v - 1, 0);
            vec[1].v = max(vec[1].v - 1, 0);
            vec[2].v = max(vec[2].v - 1, 0);
            f[cas][vec[0].id] = 1;
            f[cas][vec[1].id] = 1;
            f[cas][vec[2].id] = 1;
            for (auto it : vec) {
                q.push(it);
            }
        }
    }
    return 0;
}

B. Minimum and Maximum

Solved By Hsueh-. 1:05(+)

题意：

  • 给定数组长度，每次可以询问 a_i, a_j 的大小关系。
  • 在只能询问 \frac{3n}{2}-2 次的情况下得出的最大值下标和最小值下标。

思路：

  • 先询问相邻的两个，大的放在 Big 里，小的放在 Small 里面，那么这时候询问了 \frac{n}{2} 次，每个数组只有 \frac{n}{2} 个元素。
  • 接下来最大值去 Big 里面找，最小值去 Small 里找，分别需要 \frac{n}{2}-1 次，就可以了。
Code 
#include <bits/stdc++.h>

using namespace std;

int n;

int ask(int x, int y) {
    if (x == y)
        return 0;
    printf("? %d %d\n", x + 1, y + 1);
    fflush(stdout);
    char op[10];
    scanf("%s", op);
    if (op[0] == '<')
        return -1;
    else if (op[1] == '=')
        return 0;
    else
        return 1;
}

int main() {
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%d", &n);
        vector<int> big, small;
        for (int i = 0; i < n / 2; ++i) {
            if (ask(2 * i, 2 * i + 1) < 0) {
                big.push_back(2 * i + 1);
                small.push_back(2 * i);
            } else {
                small.push_back(2 * i + 1);
                big.push_back(2 * i);
            }
        }
        if (n & 1) {
            big.push_back(n - 1);
            small.push_back(n - 1);
        }
        int Min = small[0], Max = big[0];
        for (int i = 1, len = small.size(); i < len; ++i) {
            if (ask(Min, small[i]) > 0) {
                Min = small[i];
            }
        }
        for (int i = 1, len = big.size(); i < len; ++i) {
            if (ask(Max, big[i]) < 0) {
                Max = big[i];
            }
        }
        printf("! %d %d\n", Min + 1, Max + 1);
        fflush(stdout);
    }
    return 0;
}

C. Bulmart

Solved By Hsueh- & Dup4. 3:09(+3)

题意：

  • 有 n 个城市，m 条无向边，有 w 个商店，第 i 个商店座落在第 i 个城市，拥有 k_i 件商品，商品的单价为 p_i.
  • 现在有 q 次询问，每次询问给出 g_j, r_j, a_j，表示某人在 g_j 那个城市，需要买入至少 r_j 件物品，总花费不超过 a_j，问最少的时间。
  • 这里的购买可以让其他城市邮寄过来，时间是花费最长的那个包裹，边权为 1。

思路：

  • 先预处理出每个点到其他任意一点的最小距离。
  • 然后将每个商店按照单价排序，对于每次询问，二分 t，然后贪心去符合要求的商店购买。
  • 时间复杂度 O(nm + nw \log n)。

其实堆优化可撤销贪心也是可以的，赛后过了(

Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SZ(x) (int((x).size()))
const int N = 2e5 + 10;
int n;
ll r, l[N], t[N];

int main() {
    scanf("%d%lld", &n, &r);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", l + i);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", t + i);
        if (l[i] > t[i]) {
            puts("-1");
            return 0;
        }
    }
    vector<ll> vec;
    int limit = 1e5;
    ll res = 0, pre = 0, T = 0;
    for (int i = 1; i <= n; ++i) {
        if (pre >= l[i]) {
            pre -= l[i];
            T += l[i];
            continue;
        }
        l[i] -= pre;
        t[i] -= pre;
        T += pre;
        pre = 0;
        ll need = l[i] * 2 - t[i];
        if (need <= 0) {
            T += l[i] * 2;
        } else {
            ll cnt = need / r;
            ll mod = need % r;
            res += cnt;
            res += (mod > 0);
            for (ll j = 1, k = T; j <= cnt && SZ(vec) < limit; ++j, k += r) {
                vec.push_back(k);
            }
            T += r * cnt;
            l[i] -= r * cnt;
            l[i] -= mod;
            T += l[i] * 2;
            if (mod) {
                vec.push_back(T);
                pre = r - mod;
            }
            T += mod;
        }
    }
    printf("%lld\n", res);
    if (res <= limit) {
        for (int i = 0; i < SZ(vec); ++i) {
            printf("%lld%c", vec[i], " \n"[i == SZ(vec) - 1]);
        }
    } else {
        puts("");
    }
    return 0;
}

D. Running Over The Bridges

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

题意：

  • 有 n 座桥, 第 i 座桥的长度为 l_i，在第 i 座桥上最多的停留时间为 t_i，现在有一个人要从第 1 座桥按顺序经过这 n 座桥，它的速度是 2s 走一个单位长度，但是有一种药水，每次喝下后持续 r 个时间单位，使得它能够 1s 走一个单位长度，问这个人最少要喝多少次药水，使得能走完这 n 座桥，在满足上述限制的情况下，如果喝的次数小于等于 10^5, 那么要输出喝药水的时刻。

思路：

贪心，对于每座桥，考虑对于这座桥最少要喝几次，然后最后一次喝药水，尽量靠后，把药水的收益留给下一座桥。

Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SZ(x) (int((x).size()))
const int N = 2e5 + 10;
int n;
ll r, l[N], t[N];

int main() {
    scanf("%d%lld", &n, &r);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", l + i);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", t + i);
        if (l[i] > t[i]) {
            puts("-1");
            return 0;
        }
    }
    vector<ll> vec;
    int limit = 1e5;
    ll res = 0, pre = 0, T = 0;
    for (int i = 1; i <= n; ++i) {
        if (pre >= l[i]) {
            pre -= l[i];
            T += l[i];
            continue;
        }
        l[i] -= pre;
        t[i] -= pre;
        T += pre;
        pre = 0;
        ll need = l[i] * 2 - t[i];
        if (need <= 0) {
            T += l[i] * 2;
        } else {
            ll cnt = need / r;
            ll mod = need % r;
            res += cnt;
            res += (mod > 0);
            for (ll j = 1, k = T; j <= cnt && SZ(vec) < limit; ++j, k += r) {
                vec.push_back(k);
            }
            T += r * cnt;
            l[i] -= r * cnt;
            l[i] -= mod;
            T += l[i] * 2;
            if (mod) {
                vec.push_back(T);
                pre = r - mod;
            }
            T += mod;
        }
    }
    printf("%lld\n", res);
    if (res <= limit) {
        for (int i = 0; i < SZ(vec); ++i) {
            printf("%lld%c", vec[i], " \n"[i == SZ(vec) - 1]);
        }
    } else {
        puts("");
    }
    return 0;
}

E. Award Ceremony

Solved By Hsueh- & ltslts. 3:50(+)

题意：

  • 每个人有一个起始的分数 a_i 以及一个等待揭晓的分数 d_i。
  • 假设揭开某人后，他的排名变化 t。
  • 安排一个揭开分数的顺序使得 \sum t 最大。

思路：

显然对每两个人的排名先后顺序变化研究，然后求 sum 即可。

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

using namespace std;

const int N = 1e2 + 10;

struct E {
    int id, a, d;

    bool operator<(const E &other) const {
        if (a != other.a) {
            return a > other.a;
        } else {
            return id < other.id;
        }
    }
} a[N];

int n;

int f(int x, int y) {
    E startX = a[x], startY = a[y];
    E endX = a[x], endY = a[y];
    endX.a += endX.d;
    endY.a += endY.d;
    if (startX < startY && endY < endX)
        return 1;
    if (startY < startX && endX < endY)
        return 1;

    if (startX < startY && endY < startX && endX < endY)
        return 2;
    if (startX < startY && startY < endX && endX < endY)
        return 2;

    if (startY < startX && startX < endY && endY < endX)
        return 2;
    if (startY < startX && endX < startY && endY < endX)
        return 2;
    return 0;
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input", "r", stdin);
#endif
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &a[i].a, &a[i].d);
        a[i].id = i;
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            res += f(i, j);
        }
    }
    printf("%d\n", res);
    return 0;
}

F. Ber Patio

UnSolved.

题意：

思路：

G. Car Repair Shop

Solved By Dup4. 0:54(+)

题意：

  • 有一个修车店，每一时刻只能修一辆车。
  • 现在有 n 辆车，每辆车有 s_i, d_i，表示顾客希望从 s_i 时刻开始修，d_i 表示这辆车需要修 d_i 时间。

现在对于每辆车：

  • 如果 [s_i, s_i + d_i - 1] 这个时间段没被占用，那么这辆车就被安排在这个时间段修。
  • 否则，找一个最小的正整数 x，满足 [x, x + d_i - 1] 这个时间段没有汽车修，这个时候 x \leq s_i 是被允许的。

思路：

  • 用个容器维护一个二元组，然后问题就相当于判断线段是否相交。
  • 对于第二种操作，容易发现贪心的选 x，可取的值并不多。
Code 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pLL = pair<ll, ll>;
#define fi first
#define se second
const int N = 210;
int n;
ll s[N], d[N];

vector<pLL> vec;

bool cross(pLL x, pLL y) {
    if ((x.fi <= y.fi && x.se >= y.fi) || (x.fi <= y.se && x.se >= y.se) || (y.fi <= x.fi && y.se >= x.fi) ||
            (y.fi <= x.se && y.fi >= x.se))
        return true;
    return false;
}

bool ok(ll l, ll r) {
    for (auto &it : vec) {
        if (cross(pLL(l, r), it)) {
            return false;
        }
    }
    return true;
}

pLL get(ll d) {
    if (ok(1, 1 + d - 1))
        return pLL(1, 1 + d - 1);
    for (auto &it : vec) {
        if (ok(it.se + 1, it.se + d)) {
            return pLL(it.se + 1, it.se + d);
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld", s + i, d + i);
    }
    for (int i = 1; i <= n; ++i) {
        pLL tmp = pLL(s[i], s[i] + d[i] - 1);
        if (!ok(s[i], s[i] + d[i] - 1)) {
            tmp = get(d[i]);
        }
        vec.push_back(tmp);
        sort(vec.begin(), vec.end());
        printf("%lld %lld\n", tmp.fi, tmp.se);
    }
    return 0;
}

H. Delete Them

Solved By Dup4. 0:41(+)

题意：

有 n 个字符串，现在选出 m 个字符串，然后要构造一个模式串，使得模式串能匹配上这 m 个字符串，但是不能匹配上剩下的 n - m 个字符串，模式串中可以有 ?，但是没有 *。

思路：

  • 对于 m 个字符串，按位考虑，如果当前位相同，就放特定字符，否则放 ?。
  • 然后拿这个模式串去匹配剩下的 n - m个，如果能匹配上就无解。
Code 
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int(x.size()))
const int N = 1e2 + 10;
int n, m, vis[N];

vector<string> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    s.clear();
    s.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
    }
    vector<int> vec(m);
    for (auto &it : vec) cin >> it, vis[it] = 1;
    string t = "";
    int len = SZ(s[vec[0]]);
    for (int i = 1; i < m; ++i) {
        if (SZ(s[vec[i]]) != len) {
            cout << "No\n";
            return 0;
        }
    }
    for (int i = 0; i < len; ++i) {
        char ch = s[vec[0]][i];
        int ok = 1;
        for (int j = 1; j < m; ++j) {
            if (s[vec[j]][i] != ch) {
                ok = 0;
                break;
            }
        }
        if (ok)
            t += ch;
        else
            t += "?";
    }
    for (int i = 1; i <= n; ++i)
        if (vis[i] == 0 && SZ(s[i]) == len) {
            int ok = 1;
            for (int j = 0; j < len; ++j) {
                if (s[i][j] != t[j] && t[j] != '?') {
                    ok = 0;
                    break;
                }
            }
            if (ok) {
                cout << "No\n";
                return 0;
            }
        }
    cout << "Yes\n";
    cout << t << "\n";
    return 0;
}

I. Olympiad in Programming and Sports

Solved By Hsueh-. 2:49(+7)

题意：

  • 有 n 个学生，两个社团 A, B，第 i 个学生加入 A 社团，能给 A 社团带来 a_i 点属性值，加入 B 社团能带来 b_i 点属性，现在要挑选 p 个学生加入 A 社团，s 个学生加入 B 社团，使得带来的属性和最大。
  • 问最大属性和。

思路：

费用流。

  • 源点向每个人流流量 1，费用 0 的边。
  • 每个人向 A, B 组流流量 1，费用为 -a_i/-b_i 的边。
  • A, B 组分别向汇点流 p, s 的边。
Code 
#include <bits/stdc++.h>

using namespace std;

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

struct Min_Cost_Max_Flow {
    static const int N = 1e4 + 10;
    static const int M = 1e6 + 10;
    const int INF = 0x3f3f3f3f;
    struct E {
        int to, nxt, cap, flow, cost;
    } edge[M << 1];
    int head[N], tot;
    int pre[N], dis[N];
    int vis[N];
    int n;

    void init(int _n) {
        n = _n;
        tot = 0;
        memset(head, -1, sizeof head);
    }

    void addedge(int u, int v, int cap, int cost) {
        edge[tot] = {v, head[u], cap, 0, cost};
        head[u] = tot++;
        edge[tot] = {u, head[v], 0, 0, -cost};
        head[v] = tot++;
    }

    bool SPFA(int s, int t) {
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            dis[i] = INF;
            vis[i] = false;
            pre[i] = -1;
        }
        dis[s] = 0;
        vis[s] = true;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = false;
            for (int i = head[u]; ~i; i = edge[i].nxt) {
                int v = edge[i].to;
                if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                    dis[v] = dis[u] + edge[i].cost;
                    pre[v] = i;
                    if (!vis[v]) {
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
        }
        if (pre[t] == -1)
            return false;
        else
            return true;
    }

    int gao(int s, int t, int &cost) {
        int flow = 0;
        cost = 0;
        while (SPFA(s, t)) {
            int Min = INF;
            for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) {
                if (Min > edge[i].cap - edge[i].flow) {
                    Min = edge[i].cap - edge[i].flow;
                }
            }
            for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]) {
                edge[i].flow += Min;
                edge[i ^ 1].flow -= Min;
                cost += edge[i].cost * Min;
            }
            flow += Min;
        }
        return flow;
    }
} MSMF;

const int N = 3e3 + 10;

int n, s, p;
int a[N], b[N];

int main() {
#ifdef LOCAL_JUDGE
    freopen("input", "r", stdin);
#endif
    scanf("%d %d %d", &n, &p, &s);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", b + i);
    }
    int A = n + 1, B = n + 2, S = n + 3, T = n + 4;
    MSMF.init(T + 10);
    for (int i = 1; i <= n; ++i) {
        MSMF.addedge(S, i, 1, 0);
        MSMF.addedge(i, A, 1, -a[i]);
        MSMF.addedge(i, B, 1, -b[i]);
    }
    MSMF.addedge(A, T, p, 0);
    MSMF.addedge(B, T, s, 0);
    int cost = 0;
    int flow = MSMF.gao(S, T, cost);
    assert(flow == p + s);
    vector<int> vec_A, vec_B;
    for (int u = 1; u <= n; ++u) {
        for (int i = MSMF.head[u]; ~i; i = MSMF.edge[i].nxt) {
            if (MSMF.edge[i].cap == MSMF.edge[i].flow && MSMF.edge[i].to == A) {
                vec_A.push_back(u);
                break;
            }
            if (MSMF.edge[i].cap == MSMF.edge[i].flow && MSMF.edge[i].to == B) {
                vec_B.push_back(u);
                break;
            }
        }
    }
    //    assert(vec_A.size() == p && vec_B.size() == s);
    printf("%d\n", -cost);
    for (int i = 0, len = vec_A.size(); i < len; ++i) {
        printf("%d%c", vec_A[i], " \n"[i == len - 1]);
    }
    for (int i = 0, len = vec_B.size(); i < len; ++i) {
        printf("%d%c", vec_B[i], " \n"[i == len - 1]);
    }
    return 0;
}

J. Bottles

Solved By Dup4. 1:25(+1)

题意：

  • 给出 n 个瓶子，每个瓶子里面有 a_i 升水，每个瓶子的容量是 b_i，保证 a_i \leq b_i, 现在可以将一个瓶子的水倒入另一个瓶子的水，倒入 1 升水需要一个单位时间。
  • 现在要将所有水存放在 k 个瓶子中，使得 k 最少，其次保证所用时间 T 最少。

思路：

  • 显然，题目要求找 k 个瓶子，使得这 k 个瓶子的容量和大于等于所有水的体积，并且满足剩下 n - k 个瓶子里装的水最少，即转移的水最少，那么就是选中的 k 个瓶子里装的水越多。
  • f[i][j] 表示用了 i 个瓶子，体积为 j 时所拥有的水体积的最大值，然后背包即可。
Code 
#include <bits/stdc++.h>
using namespace std;
using pII = pair<int, int>;
#define fi first
#define se second

#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 = 110;
int n, f[N][N * N];
pII a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i].fi);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i].se);
    sort(a + 1, a + 1 + n, [&](pII x, pII y) {
        return x.se > y.se;
    });
    int all = 0, vol = 0, K = -1;
    for (int i = 1; i <= n; ++i) {
        all += a[i].fi;
    }
    for (int i = 1; i <= n; ++i) {
        vol += a[i].se;
        if (K == -1 && vol >= all) {
            K = i;
        }
    }
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = K; j >= 1; --j) {
            for (int k = vol - a[i].se; k >= 0; --k) {
                //	dbg(i, j, k);
                f[j][k + a[i].se] = max(f[j][k + a[i].se], f[j - 1][k] + a[i].fi);
            }
        }
    }
    int Max = 0;
    for (int i = all; i <= vol; ++i) {
        Max = max(Max, f[K][i]);
    }
    printf("%d %d\n", K, all - Max);
    return 0;
}

K. Roads Orientation Problem

UnSolved.

题意：

思路：

L. Expression Queries

UnSolved.

题意：

思路：

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