ACM-ICPC 2018 沈阳赛区网络预赛

Contents

A. Gudako and Ritsuka
B. Call of Accepted
C. Convex Hull
D. Made In Heaven
E. The cake is a lie
F. Fantastic Graph
G. Spare Tire
H. Hamming Weight
I. Lattice's basics in digital electronics
J. Ka Chang
K. Supreme Number

A. Gudako and Ritsuka

留坑。

B. Call of Accepted

题意：

定义了一种新的运算符 $x \; d \; y$ 然后给出中缀表达式，求值。

思路：

先中缀转后缀，然后考虑如何最大如何最小，按题意模拟即可。

Code

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

#define ll long long

char s[110];
ll suffix[110];
int vis[110];

unordered_map<char, int> mp;

inline void Init() {
    mp.clear();
    mp['('] = 0;
    mp['+'] = 1;
    mp['-'] = 1;
    mp['*'] = 2;
    mp['d'] = 3;
}

stack<char> symbol;
stack<ll> Min, Max;

inline void Run() {
    Init();
    while (scanf("%s", s) != EOF) {
        while (!symbol.empty()) symbol.pop();
        while (!Min.empty()) Min.pop();
        while (!Max.empty()) Max.pop();
        memset(vis, 0, sizeof vis);
        int cnt = 0;
        for (int i = 0, len = strlen(s); i < len; ++i) {
            if (isdigit(s[i])) {
                ll tmp = 0;
                int flag = 1;
                if (i == 1 && s[0] == '-')
                    symbol.pop(), flag = -1;
                else if (i > 1 && s[i - 1] == '-' && s[i - 2] == '(')
                    symbol.pop(), flag = -1;
                for (; i < len && isdigit(s[i]); ++i) {
                    tmp = tmp * 10 + s[i] - '0';
                }
                suffix[++cnt] = tmp * flag;
                --i;
            } else {
                if (symbol.empty())
                    symbol.emplace(s[i]);
                else if (s[i] == '(')
                    symbol.emplace(s[i]);
                else if (s[i] == ')') {
                    while (1) {
                        int top = symbol.top();
                        symbol.pop();
                        if (top == '(')
                            break;
                        suffix[++cnt] = top;
                        vis[cnt] = 1;
                    }
                } else {
                    while (!symbol.empty() && mp[symbol.top()] >= mp[s[i]]) {
                        suffix[++cnt] = symbol.top();
                        symbol.pop();
                        vis[cnt] = 1;
                    }
                    symbol.emplace(s[i]);
                }
            }
        }
        while (!symbol.empty()) {
            suffix[++cnt] = symbol.top();
            symbol.pop();
            vis[cnt] = 1;
        }
        for (int i = 1; i <= cnt; ++i) {
            if (!vis[i]) {
                Min.emplace(suffix[i]);
                Max.emplace(suffix[i]);
            } else {
                ll top1 = Min.top();
                Min.pop();
                ll top2 = Min.top();
                Min.pop();
                ll top3 = Max.top();
                Max.pop();
                ll top4 = Max.top();
                Max.pop();
                if (suffix[i] == '+') {
                    Min.emplace(top1 + top2);
                    Max.emplace(top3 + top4);
                } else if (suffix[i] == '-') {
                    Min.emplace(top2 - top3);
                    Max.emplace(top4 - top1);
                } else if (suffix[i] == '*') {
                    ll ansmin = top2 * top1;
                    ansmin = min(ansmin, top2 * top3);
                    ansmin = min(ansmin, top4 * top1);
                    ansmin = min(ansmin, top4 * top3);
                    ll ansmax = top2 * top1;
                    ansmax = max(ansmax, top2 * top3);
                    ansmax = max(ansmax, top4 * top1);
                    ansmax = max(ansmax, top4 * top3);
                    Min.emplace(ansmin);
                    Max.emplace(ansmax);
                } else {
                    Min.emplace(top2);
                    Max.emplace(top3 * top4);
                }
            }
        }
        printf("%lld %lld\n", Min.top(), Max.top());
    }
}

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

    Run();
    return 0;
}

C. Convex Hull

留坑。

D. Made In Heaven

题意：

找第 $k$ 短路。

思路：

A* 算法。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;

#define N 1005
#define M 50005

int n, m, k;
ll T;
bool vis[N];
int d[N];

struct node {
    int v;
    int cost;
    node() {}
    node(int v, ll cost) : v(v), cost(cost) {}
    inline bool operator<(const node &b) const {
        return cost + d[v] > b.cost + d[b.v];
    }
} edge[M], revedge[M];

struct Edge {
    int v, cost;
    inline Edge() {}
    inline Edge(int v, int cost) : v(v), cost(cost) {}
};

vector<Edge> E[N], revE[N];

inline void Dijstra(int st) {
    memset(vis, false, sizeof vis);
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
    }
    priority_queue<node> q;
    d[st] = 0;
    q.push(node(st, 0));
    while (!q.empty()) {
        node tmp = q.top();
        q.pop();
        int u = tmp.v;
        if (vis[u])
            continue;
        vis[u] = true;
        int len = E[u].size();
        for (int i = 0; i < len; ++i) {
            int v = E[u][i].v;
            int cost = E[u][i].cost;
            if (!vis[v] && d[v] > d[u] + cost) {
                d[v] = d[u] + cost;
                q.push(node(v, d[v]));
            }
        }
    }
}

inline int A_star(int st, int ed) {
    priority_queue<node> q;
    q.push(node(st, 0));
    --k;
    while (!q.empty()) {
        node tmp = q.top();
        q.pop();
        int u = tmp.v;
        if (u == ed) {
            if (k)
                --k;
            else
                return tmp.cost;
        }
        int len = revE[u].size();
        for (int i = 0; i < len; ++i) {
            int v = revE[u][i].v;
            int cost = revE[u][i].cost;
            q.push(node(v, tmp.cost + cost));
        }
    }
    return -1;
}

inline void addedge(int u, int v, int w) {
    revE[u].push_back(Edge(v, w));
    E[v].push_back(Edge(u, w));
}

int st, ed;

inline void RUN() {
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 0; i <= n; ++i) {
            E[i].clear();
            revE[i].clear();
        }
        scanf("%d %d %d %lld", &st, &ed, &k, &T);
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            addedge(u, v, w);
        }
        Dijstra(ed);
        if (d[st] == INF) {
            puts("Whitesnake!");
            continue;
        }
        int ans = A_star(st, ed);
        if (ans == -1) {
            puts("Whitesnake!");
            continue;
        }
        puts(ans <= T ? "yareyaredawa" : "Whitesnake!");
    }
}

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

    RUN();

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

E. The cake is a lie

留坑。

F. Fantastic Graph

题意：

给出一张二分图，若干条边，选择一些边进去，使得所有点的度数在 $[L,R]$ 之间。

思路：

XDL 说爆搜，加上优秀的剪枝（8ms）。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 10;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;

struct node {
    int l, r;
    inline node() {}
    inline node(int l, int r) : l(l), r(r) {}
} arr[maxn];

bool flag = false;
int n, m, k;
int sum;
int res_L;
int res_R;
int L, R;
int du_left[maxn];
int du_right[maxn];

inline void Init() {
    memset(du_left, 0, sizeof du_left);
    memset(du_right, 0, sizeof du_right);
}

inline void DFS(int idx, int cnt) {
    if (sum == n + m) {
        flag = true;
        return;
    }
    if (idx > k)
        return;
    if (k - idx + 1 + cnt < res_L)
        return;
    if (cnt >= res_R)
        return;
    if (flag)
        return;
    // do
    if (du_left[arr[idx].l] < R && du_right[arr[idx].r] < R) {
        du_left[arr[idx].l]++;
        du_right[arr[idx].r]++;
        if (du_left[arr[idx].l] == L)
            sum++;
        if (du_right[arr[idx].r] == L)
            sum++;
        DFS(idx + 1, cnt + 1);
        if (flag)
            return;
        if (du_left[arr[idx].l] == L)
            sum--;
        if (du_right[arr[idx].r] == L)
            sum--;
        du_left[arr[idx].l]--;
        du_right[arr[idx].r]--;
    }
    // not do
    DFS(idx + 1, cnt);
    if (flag)
        return;
}

inline void RUN() {
    int cas = 0;
    while (~scanf("%d %d %d", &n, &m, &k)) {
        printf("Case %d: ", ++cas);
        Init();
        scanf("%d %d", &L, &R);
        int cnt = 0;
        for (int i = 1; i <= k; ++i) {
            scanf("%d %d", &arr[i].l, &arr[i].r);
            du_left[arr[i].l]++;
            du_right[arr[i].r]++;
            if (du_left[arr[i].l] == L)
                cnt++;
            if (du_right[arr[i].r] == L)
                cnt++;
        }
        if (L == 0) {
            puts("Yes");
            continue;
        }
        if (cnt != n + m) {
            puts("No");
            continue;
        }
        sum = 0;
        res_L = ((n + m) * L + 1) / 2;
        res_R = ((n + m) * R) / 2;
        Init();
        flag = false;
        DFS(1, 0);
        puts(flag ? "Yes" : "No");
    }
}

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

    RUN();

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

G. Spare Tire

题意：

给定一个数列 $A$ ，两个整数 $n,m$ ，在 $1-n$ 中所有与 $m$ 互质的数记为 $b[i]$ ，求：

\sum_{i = 1}^{i = p} a_{b_i}

思路：

首先可以发现：

A[i] = i \cdot (i + 1) = i^2+i

$A$ 的前 $n$ 项和为：

\frac{n \cdot (n+1) \cdot (2n+1)}{6} + \frac{n \cdot (n+1)}{2}

因为 $n,m$ 很大有 $10^8$ ，而且一共有 $15000$ 个 case，所以筛法肯定不行。

考虑到：

2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23=223092870 \gt 10^8

所以 $m$ 的质因子的种类肯定少于 $9$ 个。

所以我们可以用容斥。在前 $n$ 项的和的基础上容斥包含 $m$ 的不同因子的项。时间复杂度最多为 $2^9$ 。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 10;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;

int tot;
bool isprime[maxn];
int prime[maxn];
ll inv[maxn];

inline void Init_prime() {
    inv[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    memset(isprime, true, sizeof isprime);
    tot = 0;
    for (int i = 2; i < maxn; ++i) {
        if (isprime[i]) {
            prime[tot++] = i;
            for (int j = (i << 1); j < maxn; j += i) {
                isprime[i] = false;
            }
        }
    }
}

vector<ll> vec;
ll n, m;
ll ans;

inline void Init(ll x) {
    vec.clear();
    for (int i = 0; i < tot && prime[i] < x; ++i) {
        if (x % prime[i] == 0) {
            vec.push_back(prime[i]);
            while (x % prime[i] == 0) {
                x /= prime[i];
            }
        }
    }
    if (x != 1)
        vec.push_back(x);
}

inline void RUN() {
    Init_prime();
    while (~scanf("%lld %lld", &n, &m)) {
        ans = n % MOD * (n + 1) % MOD * (n + 2) % MOD * inv[3] % MOD;
        if (m == 1) {
            printf("%lld\n", ans);
            continue;
        }
        Init(m);
        int len = vec.size();
        for (int i = 1; i < (1 << len); ++i) {
            int cnt = 0;
            ll t = 1;
            for (int j = 0; j < len; ++j) {
                if (i & (1 << j)) {
                    cnt++;
                    t *= vec[j];
                }
            }
            ll x = n / t;
            ll tmp = x % MOD * (x + 1) % MOD * (2 * x % MOD + 1) % MOD * inv[6] % MOD * t % MOD * (t + 1) % MOD -
                     x % MOD * (x + 1) % MOD * (x - 1) % MOD * inv[3] % MOD * t % MOD;
            tmp = (tmp + MOD) % MOD;
            if (cnt & 1) {
                ans = (ans - tmp + MOD) % MOD;
            } else {
                ans = (ans + tmp) % MOD;
            }
        }
        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
}

H. Hamming Weight

留坑。

I. Lattice's basics in digital electronics

按题意模拟即可。

Code

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

#define N 100010

int t, n, m;
string str, tmp, ttmp, ans, s;
unordered_map<string, char> mp;
unordered_map<char, string> mmp;

inline void Init() {
    mmp.clear();
    mmp['0'] = "0000";
    mmp['1'] = "0001";
    mmp['2'] = "0010";
    mmp['3'] = "0011";
    mmp['4'] = "0100";
    mmp['5'] = "0101";
    mmp['6'] = "0110";
    mmp['7'] = "0111";
    mmp['8'] = "1000";
    mmp['9'] = "1001";
    mmp['A'] = "1010";
    mmp['B'] = "1011";
    mmp['C'] = "1100";
    mmp['D'] = "1101";
    mmp['E'] = "1110";
    mmp['F'] = "1111";
    mmp['a'] = "1010";
    mmp['b'] = "1011";
    mmp['c'] = "1100";
    mmp['d'] = "1101";
    mmp['e'] = "1110";
    mmp['f'] = "1111";
}

inline bool ok(string s) {
    int cnt = 0;
    for (int i = 0; i < 8; ++i) cnt += (s[i] == '1');
    if ((s[8] == '0' && (cnt & 1)) || (s[8] == '1' && (cnt & 1) == 0))
        return true;
    return false;
}

inline void Run() {
    cin.tie(0), cout.tie(0);
    Init();
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        mp.clear();
        cin >> m >> n;
        for (int i = 1, num; i <= n; ++i) {
            cin >> num >> str;
            mp[str] = num;
        }
        cin >> s;
        tmp = "";
        str = "";
        for (int i = 0, len = s.size(); i < len; ++i) tmp += mmp[s[i]];
        for (int i = 0, len = tmp.size(); i < len;) {
            if (len - i < 9)
                break;
            ttmp = "";
            for (int cnt = 0; cnt < 9; ++cnt, ++i) ttmp += tmp[i];
            if (ok(ttmp)) {
                ttmp.erase(ttmp.end() - 1);
                str += ttmp;
                // cout << ttmp << endl;
            }
        }
        // for (auto it : mp) cout << it.first << " " << it.second << endl;
        ans.clear(), tmp.clear();
        for (int i = 0, len = str.size(); i < len && ans.size() < m; ++i) {
            tmp += str[i];
            if (mp.find(tmp) != mp.end()) {
                ans += mp[tmp];
                tmp = "";
            }
        }
        cout << ans << endl;
    }
}

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

    Run();
    return 0;
}

J. Ka Chang

题意：

两种操作：

$1 \; L \; X$ 所有深度为 $L$ 的加上 $x$ 。
$2 \; X$ 查询以 $x$ 为根的所有子节点的和。

思路：

以 $x$ 为根的子节点的和可以用 DFS 序使得所有子树的标号在一块。

然后对于更新操作，考虑两种方法操作：

暴力更新每个点
记录这个深度更新了多少，查询的时候找出这个深度中有子节点有几个，直接加上。

如果只用第二个操作更新，那么当给的树是一条链的时候，查询的复杂度达到 $O(n \log n)$ 。

只用第一个操作更新，那么更新的操作当给的树是菊花形的时候，更新的复杂度达到 $O(n \log n)$ 。

那么考虑将两种操作结合，当某个深度中元素个数大于 $sqrt(10^5)$ 的时候，用第二种操作否则用第一种

然后查询的时候，要记得都加上。

Code

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

#define N 100010
#define ll long long

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

int n, q, Maxdeep;
int head[N], pos;
int ord[N], son[N], deep[N], fa[N], cnt;
vector<int> dep[N], Lar;
ll sum[N];

inline void Init() {
    memset(head, -1, sizeof head);
    pos = 0;
    cnt = 0;
    Maxdeep = 0;
    Lar.clear();
    for (int i = 0; i <= 1; ++i) dep[i].clear();
    fa[1] = 1;
    deep[1] = 0;
}

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

inline void DFS(int u, int pre) {
    ord[u] = ++cnt;
    dep[deep[u]].emplace_back(cnt);
    Maxdeep = max(Maxdeep, deep[u]);
    for (int it = head[u]; ~it; it = edge[it].nx) {
        int v = edge[it].to;
        if (v == pre)
            continue;
        deep[v] = deep[u] + 1;
        DFS(v, u);
    }
    son[u] = cnt;
}

struct node {
    int l, r;
    ll sum;
    inline node() {}
    inline node(int l, int r, ll sum) : l(l), r(r), sum(sum) {}
} tree[N << 2];

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

inline void build(int id, int l, int r) {
    tree[id] = node(l, r, 0);
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

inline void update(int id, int pos, ll val) {
    if (tree[id].l == tree[id].r) {
        tree[id].sum += val;
        return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (pos <= mid)
        update(id << 1, pos, val);
    else if (pos > mid)
        update(id << 1 | 1, pos, val);
    pushup(id);
}

ll anssum;

inline void query(int id, int l, int r) {
    if (tree[id].l >= l && tree[id].r <= r) {
        anssum += tree[id].sum;
        return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
    if (l <= mid)
        query(id << 1, l, r);
    if (r > mid)
        query(id << 1 | 1, l, r);
}

inline void Run() {
    while (scanf("%d%d", &n, &q) != EOF) {
        Init();
        for (int i = 1, u, v; i < n; ++i) {
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }
        DFS(1, 1);
        build(1, 1, n);
        int limit = (int)sqrt(100000);
        for (int i = 1; i <= Maxdeep; ++i) {
            if (dep[i].size() >= limit) {
                Lar.emplace_back(i);
                sort(dep[i].begin(), dep[i].end());
            }
        }
        for (int i = 1, op, l, x; i <= q; ++i) {
            scanf("%d", &op);
            if (op == 1) {
                scanf("%d%d", &l, &x);
                if (dep[l].size() < limit) {
                    for (auto it : dep[l]) update(1, it, (ll)x);
                } else
                    sum[l] += (ll)x;
            } else {
                scanf("%d", &x);
                anssum = 0;
                query(1, ord[x], son[x]);
                ll ans = anssum;
                int l = ord[x], r = son[x];
                for (auto it : Lar) {
                    if (it < deep[x])
                        continue;
                    int k = upper_bound(dep[it].begin(), dep[it].end(), r) -
                            lower_bound(dep[it].begin(), dep[it].end(), l);
                    if (k == 0)
                        break;
                    ans += sum[it] * k;
                }
                printf("%lld\n", ans);
            }
        }
    }
}

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

    Run();
    return 0;
}

K. Supreme Number

只有几个数，爆搜出来，判断一下

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 2e6 + 10;

string s[] = {"1", "2", "3", "5", "7", "11", "13", "17", "23", "31", "37", "53", "71", "73", "113", "131", "137", "173",
        "311", "317"};

inline void RUN() {
    int t;
    cin >> t;
    for (int cas = 1; cas <= t; ++cas) {
        cout << "Case #" << cas << ": ";
        string ans;
        string str;
        cin >> str;
        for (int i = 0; i < 20; ++i) {
            if (str.length() == s[i].length()) {
                if (str >= s[i])
                    ans = s[i];
            } else if (str.length() < s[i].length()) {
                continue;
            } else
                ans = s[i];
        }
        cout << ans << endl;
    }
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("Text.txt", "r", stdin);
#endif  // LOCAL_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    RUN();

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

Last update: March 31, 2022
Created: March 31, 2022