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



前言

嫑问我为什么70+天没更新这个系列，搞美赛没时间弄 + 回家没效率 _(:з)∠)_
题目按照通过人数降序排列（基本上）
只有部分 QAQ

K - Supreme Number

Link
https://nanti.jisuanke.com/t/A1999
Description
给定数N，求最大的不超过N的满足所有其各位子序列组成的数均为1或质数
Solution: 打表
能满足这一条件的数应该是不多的，打表完发现的确是不多，直接交表！

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;

int arr[20] = {1,2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317};
char str[N];

int main() {
    int t, csn = 1;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", str);

        int num;
        if(strlen(str) >= 4) {
            num = 317;
        } else {
            sscanf(str, "%d", &num);
        }

        int pos = upper_bound(arr, arr + 20, num) - arr - 1;
        printf("Case #%d: %d\n", csn++, arr[pos]);
    }
}


D - Made In Heaven

Link
https://nanti.jisuanke.com/t/A1992
Description
K短路问题
Solution: A*算法解决k短路问题
比赛时才知道还有模板题系列 QAQ
就是k短路模板题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000 + 15;

int d[N];

struct Node {
    int u, w;

    bool operator < (const Node& b) const {
        if(d[u] + w != d[b.u] + b.w) {
            return d[u] + w > d[b.u] + b.w;
        }
        return w > b.w;
    }
};

struct edge{
    int v, w, nxt;
};

struct Graph {
    edge e[N];
    int head[N], tot;

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

    inline void addEdge(int u, int v, int w) {
        e[tot] = edge{v, w, head[u]};
        head[u] = tot++;
    }
};

Graph g, ginv;
bool inque[N];
int cnt[N];

void solveD(int des) {
    memset(d, 0x3f, sizeof(d));
    memset(inque, false, sizeof(inque));
    queue<int> que;

    d[des] = 0;
    que.push(des);
    inque[des] = true;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        inque[u] = false;

        for(int i = ginv.head[u]; ~i; i = ginv.e[i].nxt) {
            int v = ginv.e[i].v;
            if(d[v] > d[u] + ginv.e[i].w) {
                d[v] = d[u] + ginv.e[i].w;
                if(inque[v] == false) {
                    que.push(v);
                    inque[v] = true;
                }
            }
        }
    }
}

bool solve(int src, int des, int k, int lim) {
    memset(cnt, 0, sizeof(cnt));
    priority_queue<Node> que;
    que.push(Node{src, 0});

    while(!que.empty()) {
        int u = que.top().u;
        int w = que.top().w;
        que.pop();

        cnt[u]++;
        if(cnt[u] == k && u == des) {
            return true;
        }
        if(cnt[u] > k) {
            continue;
        }

        for(int i = g.head[u]; ~i; i = g.e[i].nxt) {
            int v = g.e[i].v;
            if(w + g.e[i].w <= lim) {
                que.push(Node{v, w + g.e[i].w});
            }
        }
    }
    return false;
}

int main() {
    int n, m, src, des, k, lim;
    while(~scanf("%d%d%d%d%d%d", &n, &m, &src, &des, &k, &lim)) {
        g.init();
        ginv.init();
        while(m--) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g.addEdge(u, v, w);
            ginv.addEdge(v, u, w);
        }

        solveD(des);

        puts(solve(src, des, k, lim) ? "yareyaredawa" : "Whitesnake!");

    }
}


I - Lattice’s basics in digital electronics

Link
https://nanti.jisuanke.com/t/A1997
Description
（不想描述系列）
Solution: 模拟
按照题意模拟即可，蒟蒻用了AC自动机
（PS：隐隐约约记得队友打了400+行代码 QwQ）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15;

int  nxt[N][2];
int  fail[N];
char tag[N];
int  tot;

int  que[N];
int  head, tail;
vector<pair<string, char> > vec_in;

inline void newNode(int& x) {
    x = tot++;
    memset(nxt[x], -1, sizeof(nxt[x]));
    fail[x] = 0;
    tag[x] = 0;
}

inline void init() {
    head = tail = 0;
    tot = 1;
    memset(nxt[0], -1, sizeof(nxt[0]));
    fail[0] = tag[0] = 0;
}

inline void build() {
    for(auto ele : vec_in) {
        int p = 0;
        for(auto ch : ele.first) {
            int idx = ch - '0';
            if(nxt[p][idx] == -1) {
                newNode(nxt[p][idx]);
            }
            p = nxt[p][idx];
        }

        tag[p] = ele.second;
    }
}

void setFail() {
    for(int idx = 0; idx < 2; idx++) {
        if(~nxt[0][idx]) {
            que[head++] = nxt[0][idx];
        } else {
            nxt[0][idx] = 0;
        }
    }
    while(tail != head) {
        int p = que[tail++];
        for(int idx = 0; idx < 2; idx++) {
            if(~nxt[p][idx]) {
                fail[nxt[p][idx]] = nxt[fail[p]][idx];
                que[head++] = nxt[p][idx];
            } else {
                nxt[p][idx] = nxt[fail[p]][idx];
            }
        }
    }
}

string solve(string& s) {
    string ans;

    int p = 0;
    for(char ch : s) {
        int idx = ch - '0';
        p = nxt[p][idx];
        if(tag[p]) {
            ans.push_back(tag[p]);
            p = 0;
        }
    }
    return ans;
}

void solveHexToOk(string& str_hex, string& str_ok, int len) {
    const char* mp[] = {
        "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
        "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"
    };

    str_ok.clear();

    string tmp;
    for(char ch : str_hex) {
        int val = 0;
        if('0' <= ch && ch <= '9') {
            val = ch - '0';
        } else if ('A' <= ch && ch <= 'Z'){
            val = ch - 'A' + 10;
        } else {
            val = ch - 'a' + 10;
        }

        for(int i = 0; mp[val][i]; i++) {
            tmp.push_back(mp[val][i]);
        }
    }

    for(int i = 0; i + len < (int)tmp.size(); i += len + 1) {
        int cnt = 0;
        for(int j = 0; j < len; j++) {
            if(tmp[i + j] == '1') {
                cnt++;
            }
        }

        if((cnt & 1) ^ (tmp[i + len] == '1')) {
            for(int j = 0; j < len; j++) {
                str_ok.push_back(tmp[i + j]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while(t--) {
        init();
        vec_in.clear();

        int len, m;
        cin >> len >> m;

        while(m--) {
            int num;
            string s;
            cin >> num >> s;
            vec_in.emplace_back(make_pair(s, (char)num));
        }

        build();
        setFail();

        string str_hex, str_ok;
        cin >> str_hex;
        solveHexToOk(str_hex, str_ok, 8);

        string ans = solve(str_ok);
        for(int i = 0; i < (int)str_ok.size() && i < len; i++) {
            cout << ans[i];
        }
        cout << endl;
    }
    return 0;
}


G - Spare Tire

Link
https://nanti.jisuanke.com/t/A1995
Description
给定

\[\begin{aligned} a_n & = 0 & n = 0 \\ & = 2 & n = 1\\ & = \frac{3a_{n-1}-a_{n-2}}{2} + n + 1 & n > 1 \end{aligned}\]

再给定n, m (1 <= n, m <= 1e8)，求所有满足b[i]使得 1 <= b[i] <= n 且 b[i]与m互质，求

\[\begin{aligned} ans = \sum\limits_i a_{b_i} \end{aligned}\]

Solution: Mobius反演
正解是容斥原理，但是蒟蒻不会，所以蒟蒻用自己的方法推 QAQ

\[\begin{aligned} ans &= \sum\limits_{i=1}^{n} [(i, m)=1] a_i \\ &= \sum\limits_{i=1}^{n} \sum\limits_{d|(i, m)} \mu(d) a_i \\ &= \sum\limits_{i=1}^{n} \sum\limits_{d|(i, m)} \mu(d) \ast i(i+1) \\ &= \sum\limits_{d|m} \sum\limits_{k=1}^{n/d} \mu(d) \ast kd(kd + 1) \\ &= \sum\limits_{d|m} d\mu(d) \sum\limits_{k=1}^{n/d}k + \sum\limits_{d|m} d^2\mu(d) \sum\limits_{k=1}^{n/d}k^2 \\ \end{aligned}\]

因此分解质因数后枚举无平方数因子，再通过和公式与平方和公式便可得到结果
然后会发现这和用容斥原理解决的代码其实是一样的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 256 + 15;
const int MOD = 1e9 + 7;
const ll inv6 = 166666668;
const ll inv2 = 500000004;

vector<int> prime_fac;

inline void depositNum(int x) {
    prime_fac.clear();
    for(int i = 2, n = sqrt(x); i <= n; i++) {
        if(x % i == 0) {
            prime_fac.emplace_back(i);
            while(x % i == 0) {
                x /= i;
            }
        }
    }
    if(x != 1) {
        prime_fac.emplace_back(x);
    }
}

inline ll solve(int n, int m) {
    ll ret = 0;
    for(int bit = 0, sz = 1 << prime_fac.size(); bit < sz; bit++) {
        int cnt = 0;
        ll x = 1;
        for(int j = 0; j < prime_fac.size(); j++) {
            if(bit >> j & 1) {
                x = x * prime_fac[j];
                cnt ^= 1;
            }
        }

        ll div = n / x;
        if(cnt == 0) {
            ll t1 = x * x % MOD * div % MOD * (div + 1) % MOD * (2 * div + 1) % MOD * inv6 % MOD;
            ll t2 = x * div % MOD * (div + 1) % MOD * inv2 % MOD;
            ret = (ret + t1 + t2) % MOD;
        } else {
            ll t1 = x * x % MOD * div % MOD * (div + 1) % MOD * (2 * div + 1) % MOD * inv6 % MOD;
            ll t2 = x * div % MOD * (div + 1) % MOD * inv2 % MOD;
            ret = ((ret - t1 - t2) % MOD + MOD) % MOD;
        }
    }
    return ret;
}

int main() {
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        depositNum(m);
        printf("%lld\n", solve(n, m));
    }
}


F - Fantastic Graph

Link
https://nanti.jisuanke.com/t/A1997
Description
给定一个二分图，左边有n个顶点，m个顶点，k条边，现在问可否选出若干条边，使得每个点的度数都位于[l, r]中
Solution: 有上下界的网络流
一条边对应了两个顶点，而点的度数又与所关联的边有关，这样可以想到可以用网络流解决这一问题
建立源点汇点，从源点出发连接k条边的节点，从k个节点出发连接(n+m)个节点，最后从这(n+m)个节点连接到汇点建有上下界流量的边
再用有上下界的网络流解决即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e4 + 15;
const int M = 1e6 + 15;
const int inf = 0x3f3f3f3f;

struct edge {
    int v, val, cap, next;
    edge(int pv, int pval, int pcap, int pnext): v(pv), val(pval), cap(pcap), next(pnext) {}
    edge() {}
};

edge e[M];
int  tot, head[N], pre[N], d[N], cur[N], gap[N];

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

inline void addEdge(int u, int v, int val) {
    e[tot] = edge(v, 0, val, head[u]);
    head[u] = tot++;
    e[tot] = edge(u, val, val, head[v]);
    head[v] = tot++;
}

int ISAP(int src, int des, int n) {
    memcpy(cur, head, sizeof(head));
    memset(gap, 0, sizeof(gap));
    memset(d, 0, sizeof(d));
    int u = pre[src] = src;
    int sum = 0;
    gap[0] = n;
    while(d[src] < n) {
        if(u == des) {
            int v, aug = inf;
            for(u = pre[des], v = des; v != src; v = u, u = pre[u])     aug = min(aug, e[cur[u]].cap - e[cur[u]].val);
            for(u = pre[des], v = des; v != src; v = u, u = pre[u]) {
                e[cur[u]].val += aug;
                e[cur[u]^1].val -= aug;
            }
            sum += aug;
            continue;
        }

        bool flag = false;
        for(int& i = cur[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if(d[u] == d[v] + 1 && e[i].cap - e[i].val) {
                pre[v] = u;
                u = v;
                flag = true;
                break;
            }
        }

        if(!flag) {
            int mind = n;
            for(int i = head[u]; ~i; i = e[i].next) {
                int v = e[i].v;
                if(e[i].cap - e[i].val && d[v] < mind) {
                    mind = d[v];
                    cur[u] = i;
                }
            }

            if((--gap[d[u]]) == 0)    break;
            d[u] = mind + 1;
            gap[d[u]]++;
            u = pre[u];
        }
    }
    return sum;
}

int main() {
    int csn = 1;
    int lnum, rnum, m, lim_lower, lim_upper;
    while(~scanf("%d%d%d%d%d", &lnum, &rnum, &m, &lim_lower, &lim_upper)) {
        init();
        int s = 0, t = 1 + m + (lnum + rnum);
        int ss = t + 2, tt = t + 1;

        // build graph ----
        addEdge(t, s, inf);
        for(int i = 1; i <= m; i++) {
            addEdge(s, i, 2);
        }

        for(int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            u += m;
            v += m + lnum;
            addEdge(i, u, 1);
            addEdge(i, v, 1);
        }

        for(int u = m + 1; u <= m + lnum + rnum; u++) {
            addEdge(ss, t, lim_lower);
            addEdge(u, tt, lim_lower);
            addEdge(u, t, lim_upper - lim_lower);
        }
        // ----

        int ans = ISAP(ss, tt, ss + 1);
        //printf("|||%d\n", ans);
        printf("Case %d: %s\n", csn++, ((lnum + rnum) * lim_lower <= ans) ? "Yes" : "No");
    }
}


B - Call of Accepted

Link
https://nanti.jisuanke.com/t/A1990
Description
给定表达式求最大值与最小值，其中xdy表示可以取 [x, x * y] 中的数，并且d是右结合的，且运算优先级比 +-* 高
Solution: 调度场算法
需要对调度场算法进行改造
因为d是右结合的，故遇到栈顶为d时，不能立即将其弹出，而应继续入栈
剩下部分同调度场算法
最后是解决最大值最小值的问题，因为视作区间进行运算，’+’的范围则是小+小，大+大，’-‘的范围是大-小，小-大，‘*’的范围较难确定，但可以确定必然是端点之间乘出来的，所以枚举结果sort一下即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <stack>
#include <algorithm>
const int N = 100 + 5;
using namespace std;
typedef long long ll;

struct Data{
    ll data;
    int type;
};

struct Num{
    ll l, r;
};

char s[N];
Data suffix_exp[N];
int  pp;

int getPriority(char a){
    if(a == 'd')                       return 3;
    else if(a == '*' || a == '/')      return 2;
    else if(a == '+' || a == '-')      return 1;
    else                               return 0;
}

void getSuffixExp(char s[]){
    pp = 0;
    stack<char> stk;
    for(int i = 0; s[i]; ){
        if(isdigit(s[i])){
            sscanf(s + i, "%lld", &suffix_exp[pp].data);
            suffix_exp[pp++].type = 0;
            while(isdigit(s[i]))    i++;
        }else{
            if(s[i] == ')'){
                while(stk.top() != '('){
                    suffix_exp[pp++] = Data{stk.top(), 1};
                    stk.pop();
                }
                stk.pop();
            }else{
                while(s[i] != 'd' && s[i] != '(' && !stk.empty() && getPriority(stk.top()) >= getPriority(s[i])){
                    suffix_exp[pp++] = Data{stk.top(), 1};
                    stk.pop();
                }

                stk.push(s[i]);
            }

            i++;
        }
    }
    while(!stk.empty()){
        suffix_exp[pp++] = Data{stk.top(), 1};
        stk.pop();
    }
}

void solve(ll& ansmin, ll& ansmax){
    stack<Num> stk;
    for(int i = 0; i < pp; i++){
        if(suffix_exp[i].type == 0){
            stk.push(Num{suffix_exp[i].data, suffix_exp[i].data});
        }else{
            Num t2 = stk.top();
            stk.pop();
            Num t1 = stk.top();
            stk.pop();

            if(suffix_exp[i].data == '+')                   stk.push(Num{t1.l + t2.l, t1.r + t2.r});
            else if(suffix_exp[i].data == '-')              stk.push(Num{t1.l - t2.r, t1.r - t2.l});
            else if(suffix_exp[i].data == '*'){
                ll choice[4] = {t1.l * t2.l, t1.l * t2.r, t1.r * t2.l, t1.r * t2.r};
                sort(choice, choice + 4);
                stk.push(Num{choice[0], choice[3]});
            }else if(suffix_exp[i].data == 'd'){
                stk.push(Num{t1.l, t1.r * t2.r});
            }
        }
    }

    ansmin = stk.top().l, ansmax = stk.top().r;
}

int main(){
    while(cin >> s){
        ll ansmin, ansmax;
        getSuffixExp(s);
        solve(ansmin, ansmax);

        cout << ansmin << " " << ansmax << endl;
    }
}