Skip to content

ACM-ICPC 2018 南京赛区网络预赛

Contents

A. An Olympian Math Problem

cout << n - 1 << endl;

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

#define ll long long

int t;
ll n;

inline void Run() {
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &n);
        printf("%lld\n", n - 1);
    }
}

int main() {
#ifdef LOCAL
    freopen("Test.in", "r", stdin);
#endif

    Run();

    return 0;
}

B. The writing on the wall

题意：

给出 n \cdot m 的矩形，找出有多少个子矩形不包含黑块。

思路：

枚举每一个当右下角的情况，那么情况总数就是黑块构成的边界里面的格子数量，优先队列优化。

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

#define ll long long
#define N 100010
#define M 110

int t, n, m, k;
int G[N][M];
int low[M];

struct node {
    ll h, num;
    inline node() {}
    inline node(ll h, ll num) : h(h), num(num) {}
    inline bool operator<(const node &r) const {
        return h < r.h;
    }
};

priority_queue<node> q;

int main() {
#ifdef LOCAL_JUDGE
    freopen("Text.txt", "r", stdin);
#endif  // LOCAL_JUDGE
    scanf("%d", &t);
    for (int kase = 1; kase <= t; ++kase) {
        printf("Case #%d: ", kase);
        memset(G, 0, sizeof G);
        memset(low, 0, sizeof low);
        while (!q.empty()) q.pop();
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1, x, y; i <= k; ++i) {
            scanf("%d%d", &x, &y);
            G[x][y] = 1;
        }
        ll ans = 0, sum = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                // if (i % 1000 == 0) cout << i << endl;
                if (G[i][j] == 1) {
                    while (!q.empty()) q.pop();
                    sum = 0;
                    low[j] = i;
                    continue;
                }
                if (j == 1) {
                    while (!q.empty()) q.pop();
                    sum = 0;
                }
                ll H = i - low[j];
                ll num = 1;
                while (!q.empty() && q.top().h > H) {
                    num += q.top().num;
                    sum -= q.top().h * q.top().num;
                    q.pop();
                }
                sum += num * H;
                ans += sum;
                q.emplace(H, num);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C. GDY

按题意模拟即可，注意细节。

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

int Move[] = {
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        10,
        11,
        12,
        13,
        1,
        2,
};

struct DT {
    int num[15], cnt;
    int score;
    inline DT() {
        score = 0;
        cnt = 0;
        memset(num, 0, sizeof num);
    }
    inline void Get() {
        for (int i = 1; i <= 13; ++i) score += num[i] * i;
    }
} arr[250];

int t, n, m;
queue<int> q;

inline void work() {
    int turn = 1, pre = -1, tot = 0, nx;
    for (int i = 0; i < 13; ++i)
        if (arr[1].num[Move[i]]) {
            pre = Move[i];
            --arr[1].num[Move[i]];
            --arr[1].cnt;
            break;
        }
    while (true) {
        turn = turn % n + 1;
        if (tot == n - 1) {
            for (int i = turn; i <= n; ++i)
                if (!q.empty()) {
                    ++arr[i].cnt;
                    ++arr[i].num[q.front()];
                    q.pop();
                }
            for (int i = 1; i < turn; ++i)
                if (!q.empty()) {
                    ++arr[i].cnt;
                    ++arr[i].num[q.front()];
                    q.pop();
                }
            for (int i = 0; i < 13; ++i)
                if (arr[turn].num[Move[i]]) {
                    --arr[turn].num[Move[i]];
                    if (--arr[turn].cnt == 0)
                        return;
                    pre = Move[i];
                    tot = 0;
                    break;
                }
        } else if (pre == 2)
            tot++;
        else {
            if (pre == 13)
                nx = 1;
            else
                nx = pre + 1;
            if (arr[turn].num[nx]) {
                --arr[turn].num[nx];
                if (--arr[turn].cnt == 0)
                    return;
                pre = nx;
                tot = 0;
            } else {
                if (arr[turn].num[2]) {
                    --arr[turn].num[2];
                    if (--arr[turn].cnt == 0)
                        return;
                    pre = 2;
                    tot = 0;
                } else
                    tot++;
            }
        }
    }
}

inline void Run() {
    scanf("%d", &t);
    for (int kase = 1; kase <= t; ++kase) {
        while (!q.empty()) q.pop();
        printf("Case #%d:\n", kase);
        scanf("%d%d", &n, &m);
        for (int i = 1, u; i <= m; ++i) {
            scanf("%d", &u);
            q.emplace(u);
        }
        for (int i = 1; i <= n; ++i) {
            arr[i] = DT();
            for (int j = 1; j <= 5; ++j) {
                if (!q.empty()) {
                    arr[i].num[q.front()]++;
                    q.pop();
                    ++arr[i].cnt;
                }
            }
        }
        work();
        for (int i = 1; i <= n; ++i) {
            arr[i].Get();
            if (arr[i].score == 0)
                puts("Winner");
            else
                printf("%d\n", arr[i].score);
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("Test.in", "r", stdin);
#endif

    Run();
    return 0;
}

D. Jerome's House

留坑。

E. AC Challenge

题意：

有 n 道题目，每次提交得到分数 t \cdot a_i + b_i 有一些题目的提交必须要某些题目提交之后才能提交，求最后获得的最大分数。

思路：

记忆化搜索，二进制标记状态。

或者 状压 DP。

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

using namespace std;

typedef long long ll;

ll dp[1 << 20];

int n;

struct node {
    ll ai, bi;
    int state;
    inline node() {}
    inline node(ll ai, ll bi, int state) : ai(ai), bi(bi), state(state) {}
} arr[30];

inline ll DFS(int t, int S) {
    if (t > n)
        return 0;
    if (dp[S] != -1)
        return dp[S];
    ll res = 0;
    for (int i = 0; i < n; ++i) {
        int tmp = 1 << i;
        if ((tmp & S) == 0) {
            if ((S & arr[i].state) != arr[i].state)
                continue;
            res = max(res, t * arr[i].ai + arr[i].bi + DFS(t + 1, (S | tmp)));
        }
    }
    dp[S] = res;
    return res;
}

inline void RUN() {
    while (~scanf("%d", &n)) {
        memset(dp, -1, sizeof dp);
        for (int i = 0; i < n; ++i) {
            int m;
            int S = 0;
            scanf("%lld %lld %d", &arr[i].ai, &arr[i].bi, &m);
            while (m--) {
                int tmp = 0;
                scanf("%d", &tmp);
                S += (1 << (tmp - 1));
            }
            arr[i].state = S;
        }
        ll ans = DFS(1, 0);
        printf("%lld\n", ans);
    }
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("Text.txt", "r", stdin);
#endif  // LOCAL_JUDGE

    RUN();

#ifdef LOCAL_JUDGE
    fclose(stdin);
#endif  // LOCAL_JUDGE

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

#define N (1 << 21)
#define ll long long

struct node {
    ll a, b;
    int sta;
    inline void scan() {
        int tot, k;
        sta = 0;
        scanf("%lld%lld%d", &a, &b, &tot);
        while (tot--) {
            scanf("%d", &k);
            sta |= (1 << (k - 1));
        }
    }
} arr[25];

int n;
ll dp[N];

inline ll Count(int x) {
    int res = 0;
    while (x) {
        ++res;
        x &= (x - 1);
    }
    return res;
}

inline void Run() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) arr[i].scan();
        memset(dp, -1, sizeof dp);
        ll ans = 0;
        dp[0] = 0;
        for (int i = 0; i < (1 << n); ++i) {
            if (dp[i] == -1)
                continue;
            for (int j = 1; j <= n; ++j) {
                if (!(i & (1 << (j - 1))) && (i & (arr[j].sta)) == arr[j].sta) {
                    int tmp = i | (1 << (j - 1));
                    ll t = Count(tmp);
                    dp[tmp] = max(dp[tmp], dp[i] + arr[j].a * t + arr[j].b);
                    ans = max(ans, dp[tmp]);
                }
            }
        }
        printf("%lld\n", ans);
    }
}

int main() {
#ifdef LOCAL
    freopen("Test.in", "r", stdin);
#endif

    Run();
    return 0;
}

F. An Easy Problem On The Trees

留坑。

G. Lpl and Energy-saving Lamps

题意：

有 n 个房间，每次按顺序换灯泡，一个房间要不所有灯泡都换，要不一个都不换，每个月有固定的新灯泡数，没还完留到下个月，询问第几个月能够换掉几个房间以及剩下的房间数。

思路：

线段树维护一个最小值，预处理答案。

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

#define N 100010
#define INF 0x3f3f3f3f
#define ll long long

typedef pair<int, int> pii;

int n, m, q, sum;
int arr[N];
pii ans[N];

struct node {
    int l, r, cnt;
    int Min, sum;
    inline node() {}
    inline node(int _l, int _r) {
        l = _l, r = _r;
        Min = sum = 0;
    }
} tree[N << 2];

inline void pushup(int id) {
    tree[id].Min = min(tree[id << 1].Min, tree[id << 1 | 1].Min);
    tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum;
    tree[id].cnt = tree[id << 1].cnt + tree[id << 1 | 1].cnt;
}

inline void build(int id, int l, int r) {
    tree[id] = node(l, r);
    if (l == r) {
        tree[id].Min = tree[id].sum = arr[l];
        tree[id].cnt = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}

int anssum, remind;

inline void query(int id) {
    if (tree[id].Min <= remind && tree[id].sum <= remind) {
        anssum += tree[id].cnt;
        sum -= tree[id].sum;
        remind -= tree[id].sum;
        tree[id].Min = INF;
        tree[id].sum = 0;
        tree[id].cnt = 0;
        return;
    }
    if (tree[id << 1].Min <= remind)
        query(id << 1);
    if (tree[id << 1 | 1].Min <= remind)
        query(id << 1 | 1);
    pushup(id);
}

inline void out(int x) {
    if (x / 10)
        out(x / 10);
    putchar(x % 10 + '0');
}

inline void Run() {
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(ans, 0, sizeof ans);
        sum = 0;
        for (int i = 1; i <= n; ++i) scanf("%d", arr + i), sum += arr[i];
        build(1, 1, n);
        remind = m;
        for (int i = 1; i <= 100000; ++i, remind += m) {
            if (sum == 0) {
                ans[i] = ans[i - 1];
                continue;
            }
            anssum = 0;
            query(1);
            ans[i].first = ans[i - 1].first + anssum;
            ans[i].second = remind;
        }
        scanf("%d", &q);
        for (int i = 1, x; i <= q; ++i) {
            scanf("%d", &x);
            out(ans[x].first);
            putchar(' ');
            out(ans[x].second);
            putchar('\n');
        }
    }
}

int main() {
#ifdef LOCAL
    freopen("Test.in", "r", stdin);
#endif

    Run();
    return 0;
}

H. Set

留坑。

I. Skr

留坑。

J. Sum

题意：

定义

F[n] = \mbox{有多少个}n = ab 有多少个

a 和 b 都不能是平方数的倍数，1 除外。

求：

\sum_{i = 1} ^ {i = n} F[n]

思路：

  • 枚举每个素数，对于拥有不同质因子的数，权值乘 2。
  • 对于拥有两个相同的质因子的数，权值除以 2。
  • 对于拥有三个或者三个以上质因子的数，权值为 0，最后求和。
  • （卡常）
Code 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 2e7 + 5;

int n;
int tot;
int isprime[maxn];
int prime[maxn];
int a[maxn];
int ans[maxn];

inline void Init_prime() {
    tot = 1;
    prime[1] = 1;
    a[1] = 1;
    ans[1] = 1;
    for (register int i = 2; i < maxn; ++i) {
        a[i] = 1;
        if (!isprime[i]) {
            prime[tot++] = i;
        }
        for (register int j = 1; j < tot && i * prime[j] < maxn; ++j) {
            isprime[i * prime[j]] = 1;
            if (!(i % prime[j])) {
                break;
            }
        }
    }
    for (register int i = 1; i < tot; ++i) {
        for (register int j = 1; j * prime[i] < maxn; ++j) {
            a[j * prime[i]] <<= 1;
        }
        if (prime[i] > maxn / prime[i])
            continue;
        for (register int j = 1; j * prime[i] * prime[i] < maxn; ++j) {
            if (j % prime[i] == 0) {
                a[j * prime[i] * prime[i]] = 0;
            }
            a[j * prime[i] * prime[i]] >>= 1;
        }
    }
    for (register int i = 1; i < maxn; ++i) {
        ans[i] = ans[i - 1] + a[i];
    }
}

int main() {
    Init_prime();
    int t;
    // cout << tot << endl;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
    return 0;
}

K. The Great Nim Game

留坑。

L. Magical Girl Haze

题意：

有 n 个城市，m 条边，可以令 k 条路权值为 0，求 1 \rightarrow n 的最短路。

思路：

对于每个城市，枚举到这个城市，免费 0-k 次的权值，跑一个（立体的？）最短路。

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

#define N 100010
#define ll long long
#define INFLL 0x3f3f3f3f3f3f3f3f

struct Edge {
    int to, nx;
    ll w;
    inline Edge() {}
    inline Edge(int to, int nx, ll w) : to(to), nx(nx), w(w) {}
} edge[N << 1];

int head[N], pos;

inline void Init() {
    memset(head, -1, sizeof head);
    pos = 0;
}

inline void addedge(int u, int v, ll w) {
    edge[++pos] = Edge(v, head[u], w);
    head[u] = pos;
}

struct node {
    int to, p;
    ll w;
    inline node() {}
    inline node(int to, int p, ll w) : to(to), p(p), w(w) {}
    inline bool operator<(const node &r) const {
        return w > r.w;
    }
};

ll dist[N][20];
bool used[N][20];
int t, n, m, k;

inline void Dijkstra() {
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= k; ++j) dist[i][j] = INFLL, used[i][j] = false;
    priority_queue<node> q;
    q.emplace(1, 0, 0);
    dist[1][0] = 0;
    while (!q.empty()) {
        int u = q.top().to;
        int p = q.top().p;
        ll w = q.top().w;
        // cout << w << endl;
        q.pop();
        if (used[u][p])
            continue;
        used[u][p] = true;
        dist[u][p] = w;
        for (int i = head[u]; ~i; i = edge[i].nx) {
            int v = edge[i].to;
            ll c = edge[i].w;
            if (dist[u][p] + c < dist[v][p]) {
                dist[v][p] = dist[u][p] + c;
                q.emplace(v, p, dist[v][p]);
            }
            if (p + 1 <= k && dist[u][p] < dist[v][p + 1]) {
                dist[v][p + 1] = dist[u][p];
                q.emplace(v, p + 1, dist[v][p + 1]);
            }
        }
    }
}

inline void Run() {
    scanf("%d", &t);
    while (t--) {
        Init();
        scanf("%d%d%d", &n, &m, &k);
        int u, v;
        ll w;
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%lld", &u, &v, &w);
            addedge(u, v, w);
        }
        Dijkstra();
        ll ans = dist[n][k];
        printf("%lld\n", ans);
    }
}
int main() {
#ifdef LOCAL
    freopen("Test.in", "r", stdin);
#endif

    Run();

    return 0;
}
Last update: March 31, 2022
Created: March 31, 2022
Back to top