ACM-ICPC North America Qualifier Contest 2016

Posted on | In

今天与ConanYu、Sprinkle一起在计蒜客打了这一场Replay。

Solutions

A. A New Alphabet(01:32, -6)

Solution of A

简单模拟，不过中间把`看成了’，WA了好多好多发，ACM不需要视力系列= =

Code of A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
const char str[][10] = {
    "@",
    "8",
    "(",
    "|)",
    "3",
    "#",
    "6",
    "[-]",
    "|",
    "_|",
    "|<",
    "1",
    "[]\\/[]",
    "[]\\[]",
    "0",
    "|D",
    "(,)",
    "|Z",
    "$",
    "\'][\'",
    "|_|",
    "\\/",
    "\\/\\/",
    "}{",
    "`/",
    "2"
};
int main() {
    string source, dest;
    getline(cin, source);
    const int n = source.size();
    for(int i = 0; i < n; i++)
    {
        if(!isalpha(source[i])) {
            dest += source[i];
        } else {
            if(source[i] >= 'A' && source[i] <= 'Z') {
                source[i] += 32;
            }
            dest += str[source[i] - 'a'];
        }
    }
    cout << dest << endl;
}

B. Arcade!(unsolve)

C. Big Truck(02:09)

Solution of C

简单的双关键最短路。

Code of C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define endl '\n'
#define all(a) a.begin(), a.end()

typedef long long ll;

void solve();
int32_t main() {
#ifdef Semon0x29a
    assert(freopen("Testing.txt", "r", stdin));
#endif
    solve();
}

template <typename T> inline bool chkmin(T &a, T b) { return (a > b) ? (a = b, true) : false; }
template <typename T> inline bool chkmax(T &a, T b) { return (a < b) ? (a = b, true) : false; }

const int maxn = 105;
const int INF = 0x3f3f3f3f;

struct Node {
    int u, dis, score;
    Node(int a = 0, int b = 0, int c = 0) : u(a), dis(b), score(c) {}
    bool operator< (const Node& b) const {
        if (dis == b.dis) return score < b.score;
        return dis > b.dis;
    }
};

struct edge {
    int v, w;
    edge(int a = 0, int b = 0) : v(a), w(b) {}
};

int n, m;
vector<edge> G[maxn];
int w[105], dis[105], score[105], vis[105];

void init() {
    for (int i = 0; i < maxn; i++) {
        G[i].clear();
    }
    memset(vis, 0, sizeof vis);
    memset(dis, 0x3f, sizeof dis);
    memset(score, 0, sizeof score);
}

void addedge(int u, int v, int w) {
    G[u].emplace_back(v, w);
    G[v].emplace_back(u, w);
}

bool Dijkstra() {
    priority_queue<Node> Q;
    Q.emplace(1, 0, w[1]), dis[1] = 0, score[1] = w[1];
    while (!Q.empty()) {
        int u = Q.top().u; Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        if (u == n) return true;
        for (const edge& e : G[u]) {
            if (vis[e.v]) continue;
            if (chkmin(dis[e.v], dis[u] + e.w)) {
                score[e.v] = score[u] + w[e.v];
                Q.emplace(e.v, dis[e.v], score[e.v]);
            }
            else if (dis[e.v] == dis[u] + e.w && chkmax(score[e.v], score[u] + w[e.v])) {
                Q.emplace(e.v, dis[e.v], score[e.v]);
            }
        }
    }
    return false;
}

void solve() {
    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    scanf("%d", &m);
    while (m--) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w);
    }
    if (Dijkstra()) printf("%d %d\n", dis[n], score[n]);
    else printf("impossible\n");
}

D. Brackets(unsolve, -4)

E. Dots and Boxes(unsolve)

F. Free Desserts(unsolve)

G. Inverse Factorial(00:31, -2)

Solution of G

斯特林公式求阶乘位数，据说斯特林公式在小数据时精确度不够，所以对于位数小于等于13的直接在1~15的阶乘表中找，大于13的用二分+斯特林公式找。

Code of G

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;

inline int calc(int n) {
    return floor(log10(2 * pi * n) * 0.5 + n * log10(n / e) + 1 + eps);
}

ll fac[16];
char s[1000005];

int main() {
#ifdef Semon0x29a
    assert(freopen("Testing.txt", "r", stdin));
#endif

    fac[1] = 1;
    for (int i = 2; i <= 15; i++) {
        fac[i] = fac[i - 1] * i;
    }
    while (scanf("%s", s) == 1) {
        int n = strlen(s);
        if (n <= 13) {
            ll x = atoll(s);
            for (int i = 1; i <= 15; i++) {
                if (fac[i] == x) {
                    printf("%d\n", i);
                    break;
                }
            }
        }
        else {
            int l = 16, r = 230000;
            while (l < r) {
                int mid = (l + r) >> 1;
                int x = calc(mid);
                if (x >= n) r = mid;
                else l = mid + 1;
            }
            printf("%d\n", r);
        }
    }
}

H. Nine Packs(01:55, -1)

Solution of H

每个物品的价值看作1，即可用01背包求得刚好为某一重量时的最小袋数，需要降序排序消除后效性 (好像其实不用?)。
然后在背包内扫一遍取最小即可。

Code of H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m;
int v[maxn], w[maxn];
int a[maxn], b[maxn];

int main() {
#ifdef Semon0x29a
    assert(freopen("Testing.txt", "r", stdin));
#endif

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &b[i]);
    }
    sort(a + 1, a + 1 + n, greater<int>());
    sort(b + 1, b + 1 + m, greater<int>());

    int suma = 0, sumb = 0;
    for (int i = 1; i <= n; i++) suma += a[i];
    for (int i = 1; i <= m; i++) sumb += b[i];

    memset(v, 0x3f, sizeof v);
    v[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = suma; j >= a[i]; j--) {
            v[j] = min(v[j], v[j - a[i]] + 1);
        }
    }

    memset(w, 0x3f, sizeof w);
    w[0] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = sumb; j >= b[i]; j--) {
            w[j] = min(w[j], w[j - b[i]] + 1);
        }
    }

    int res = 0x3f3f3f3f;
    for (int i = min(suma, sumb); i > 0; i--) {
        res = min(res, v[i] + w[i]);
    }
    if (res == 0x3f3f3f3f) printf("impossible\n");
    else printf("%d\n", res);
}

I. Primonimo(unsolve)

J. Quick Estimates(00:14)

Solution of J

没看题，样例看着像是直接输出位数，然后试了一发就过了= =

Code of J

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char s[105]; scanf("%s", s);
        printf("%d\n", strlen(s));
    }
}

K. Robotopia(01:12, -1)

Solution of K

显然每种Robot最多只会有10000个，所以直接暴力枚举即可。

Code of K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int l1, a1, l2, a2, lt, at;
        scanf("%d%d%d%d%d%d", &l1, &a1, &l2, &a2, &lt, &at);
        set<pair<int, int>> S;
        for (int i = 1; i <= 10000; i++) {
            if (l1 * i >= lt || a1 * i >= at) {
                break;
            }
            int ll = lt - l1 * i, aa = at - a1 * i;
            if (ll % l2 == 0 && aa % a2 == 0 && ll / l2 == aa / a2) {
                S.insert({ i, ll / l2 });
            }
        }
        for (int i = 1; i <= 10000; i++) {
            if (l2 * i >= lt || a2 * i >= at) {
                break;
            }
            int ll = lt - l2 * i, aa = at - a2 * i;
            if (ll % l1 == 0 && aa % a1 == 0 && ll / l1 == aa / a1) {
                S.insert({ ll / l1, i });
            }
        }
        if (S.size() == 1) printf("%d %d\n", S.begin()->first, S.begin()->second);
        else printf("?\n");
    }
}

L. Unusual Darts(unsolve)