2016 Multi-University Training Contest 7

6/12

期望 B Balls and Boxes（BH）

题意：

　　n个球放到m个盒子里，xi表示第i个盒子里的球的数量，求V的期望值。

思路：

　　官方题解：

代码：

#include <bits/stdc++.h>

typedef long long ll;

ll GCD(ll a, ll b) {
    return b ? GCD (b, a % b) : a;
}

int main() {
    ll n, m;
    while (scanf ("%I64d%I64d", &n, &m) == 2 && n + m) {
        ll x = n * (m - 1);
        ll y = m  * m;
        ll gcd = GCD (x, y);
        printf ("%I64d/%I64d
", x / gcd, y / gcd);
    }
    return 0;
}

图论 E Elegant Construction（BH）

题意：

　　构造一张图，使得第i个点恰好能走到a[i]个点。

思路：

　　显然从a[i]=0的点开始，a[i]大的点一定会连向少的点，类似拓扑排序的做法。时间复杂度O(n^2)。

代码：

#include <bits/stdc++.h>

const int N = 1e3 + 5;
int n;

struct Edge {
    int u, v;
};
std::vector<Edge> edges;

struct Node {
    int v, id;
    bool operator < (const Node &rhs) const {
        return v < rhs.v;
    }
}a[N];

bool vis[N];

int solve() {
    std::sort (a+1, a+1+n);
    edges.clear ();
    memset (vis, false, sizeof (vis));
    for (int i=1; i<=n; ++i) {
        if (a[i].v != 0) return -1;
        vis[a[i].id] = true;
        for (int j=1; j<=n; ++j) {
            if (vis[a[j].id]) continue;
            if (a[j].v == 0) continue;
            edges.push_back ({a[j].id, a[i].id});
            a[j].v--;
        }
    }
    return (int) edges.size ();
}

int main() {
    int T;
    scanf ("%d", &T);
    for (int cas=1; cas<=T; ++cas) {
        scanf ("%d", &n);
        for (int i=1; i<=n; ++i) {
            scanf ("%d", &a[i].v);
            a[i].id = i;
        }
        int m = solve ();
        printf ("Case #%d: %s
", cas, m != -1 ? "Yes" : "No");
        if (m != -1) {
            printf ("%d
", m);
            for (int i=0; i<m; ++i) {
                printf ("%d %d
", edges[i].u, edges[i].v);
            }
        }
    }
    return 0;
}

优先队列+优化 J Joint Stacks（BH）

题意：

　　两个栈，A和B，三种操作：入栈，出栈，以及A，B按照入栈时间合并，输出每次出栈的数字。

思路：

　　可以用优先队列来模拟栈操作，合并的话就是按照时间排序后合并，时间复杂度应该是O(nlogn)（应该还要大），结果超时了。后来试过用并查集乱搞可是写搓了，一度想弃疗。。。后来再回到原来的做法，加了一个优化（队列小的合并到大的），就AC了！（也就是想到了并查集按秩合并的思想）

　　当然巧妙的做法还是官方的三个栈。

代码：

优先队列

#include <bits/stdc++.h>

const int N = 1e5 + 5;
int n;

struct Node {
    int x, t;
    bool operator < (const Node &rhs) const {
        return t < rhs.t;
    }
};
std::priority_queue<Node> pque[2];

int real[2];

void merge(int id1, int id2) {
    if (pque[id2].size () > pque[id1].size ()) {
        std::swap (id1, id2);
        std::swap (real[0], real[1]);
    }
    while (!pque[id2].empty ()) {
        pque[id1].push (pque[id2].top ());
        pque[id2].pop ();
    }
}

int main() {
    int cas = 0;
    while (scanf ("%d", &n) == 1 && n) {
        printf ("Case #%d:
", ++cas);
        char op[10], C[2], D[2];
        for (int i=0; i<2; ++i) {
            while (!pque[i].empty ()) pque[i].pop ();
        }
        real[0] = 0; real[1] = 1;
        for (int i=1; i<=n; ++i) {
            scanf ("%s", op);
            if (op[0] == 'p') {
                scanf ("%s", C);
                int id = C[0] - 'A';
                id = real[id];
                if (op[1] == 'u') {
                    int x;
                    scanf ("%d", &x);
                    pque[id].push ({x, i});
                } else {
                    printf ("%d
", pque[id].top ().x);
                    pque[id].pop ();
                }
            } else {
                scanf ("%s%s", C, D);
                int id1 = C[0] - 'A';
                int id2 = D[0] - 'A';
                merge (real[id1], real[id2]);
            }
        }
    }
    return 0;
}

O(n)

void work()
{
	top[0] = top[1] = top[2] = 0;
	for (int i = 0; i < n; ++i) {
		char op[10], s[5];
		scanf("%s%s", op, s);
		int a = s[0] - 'A';
		if (op[1] == 'u') {
			scanf("%d", &x[i]);
			sta[a][top[a]++] = i;
		} else if (op[1] == 'o') {
			if (!top[a]) a = 2;
			printf("%d
", x[sta[a][--top[a]]]);
		} else {
			scanf("%s", s);
			top[2] = merge(sta[0], sta[0] + top[0],
			               sta[1], sta[1] + top[1],
			               sta[2] + top[2]) - sta[2];
			top[0] = top[1] = 0;
		}
	}
}