6/12
2016 Multi-University Training Contest 7
期望 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\n", 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\n", cas, m != -1 ? "Yes" : "No");
if (m != -1) {
printf ("%d\n", m);
for (int i=0; i<m; ++i) {
printf ("%d %d\n", 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:\n", ++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\n", 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\n", 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;
}
}
}