Educational Codeforces Round 3

这个Education的不算Rating的，难得处女战。。。还是写个前五题的题解，纪念一下~~

题A

题意：给你n个u盘，每个的存储容量ai，然后让你存一个容量为m的东西，问你要多少个u盘。

题解：这个如果看成背包问题的话，就是价值为1的容量为ai的背包，然而价值都是一样的，那么就可以直接排序贪心取较大的即可。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 const int maxn = 1e3 + 10;
 6 int val[maxn];
 7 
 8 int main() {
 9  // freopen("case.in", "r", stdin);
10   int n, m;
11   cin >> n >> m;
12   for (int i = 0; i < n; i++) cin >> val[i];
13   sort(val, val + n);
14   int sum = 0, ans = 0;
15   for (int i = n - 1; i >= 0; i--) {
16     sum += val[i]; ans++;
17     if (sum >= m) break;
18   }
19   cout << ans << endl;
20 }

既然可以当成背包做，就有了一下版本。。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 const int maxn = 1e5 + 100;
 6 int dp[maxn], val[maxn];
 7 
 8 int main() {
 9   //freopen("case.in", "r", stdin);
10   int n, m;
11   cin >> n >> m;
12   int sum = 0;
13   for (int i = 1; i <= n; i++)  {
14     cin >> val[i];
15     sum += val[i];
16   }
17   for (int i = 1; i <= sum; i++)  dp[i] = maxn;
18   for (int i = 1; i <= n; i++) {
19     for (int j = sum; j >= val[i]; j--) {
20       dp[j] = min(dp[j], dp[j - val[i]] + 1);
21     }
22   }
23   int ans = maxn;
24   for (int i = m; i <= sum; i++)  ans = min(ans, dp[i]);
25   cout << ans << endl;
26 }

题B

题意：给你n本书，有m种种类，问你取两种不同种类有多少种方案。

题解：虽然n很大，但是m很小，所以枚举书的种类即可。。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 ll num[110];
 7 
 8 int main() {
 9   //freopen("case.in", "r", stdin);
10   int n, m;
11   cin >> n >> m;
12   for (int i = 1; i <= n; i++) {
13     int v; cin >> v;
14     num[v]++;
15   }
16   ll ans = 0;
17   for (int i = 1; i <= m; i++)
18     for (int j = 1; j <= m; j++)
19       if (i != j) ans += num[i] * num[j];
20   cout << (ans / 2) << endl;
21 }

题C

题意：给你n个服务器，每个服务器可以做的任务数mi，然后可以用一秒钟的时间将一个任务从一个服务器，传到另外一个服务器，问你最少需要多少时间使得所有服务器的最大值-最小值最小。

题解：这道题应该也是贪心吧，先我们给出最后的服务器应该有的结果，然后排序之后与最后的结果一一做差，最后除以2就是要花费的最短时间了，理解一下其中贪心为何成立。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 const int maxn = 1e5 + 100;
 6 int val[maxn], newv[maxn];
 7 
 8 int main() {
 9   //freopen("case.in", "r", stdin);
10   int n, sum = 0;
11   cin >> n;
12   for (int i = 1; i <= n; i++) {
13     cin >> val[i];
14     sum += val[i];
15   }
16   sort(val + 1, val + 1 + n);
17   int x = n - sum % n;
18   for (int i = 1; i <= x; i++)  newv[i] = sum / n;
19   for (int i = x + 1; i <= n; i++)  newv[i] = sum / n + 1;
20   int ans = 0;
21   for (int i = 1; i <= n; i++)  ans += abs(newv[i] - val[i]);
22   cout << (ans / 2) << endl;
23 }

题D

题意：有m个货物，需要购买k个，然后要兑换相应的货币进行购买。兑换规则如下：给出每一天的英镑和美元的单价，也就是假设现在手上的是软妹币，然后5就代表5个软妹币换成一个美元，共n天。然后你可以选择任意一天进行兑换任意数量的货币，然后进行购买，现在问你最少需要多少天可以买到k个货物。

题解：这里的情况有点乱，理清一下，就是现在有n天的兑换时间，我们要选择一天兑换足够的英镑和美元，然后购买需要最少钱的m个货物中的k个货物，因为可能靠前的兑换规则兑换的少，但是时间够早，也有可能要到最后一天才可以兑换最多的货币，但是时间慢。对于这种情况一般是要枚举，但是数据量都很大，怎么枚举比较合适呢？这是这道题的难题。答案就是枚举天数，我们枚举这一天，然后看着一天是否满足，如果满足就挪到前面去，如果不满足就往后枚举，由于满足单调性，所以我们就采用二分来进行枚举。复杂度为O(nlogn)。

 1 /*zhen hao*/
 2 #include 
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 const int maxn = 2e5 + 10;
 7 const int inf = 1e8;
 8 int n, m, k, s;
 9 int a[maxn], b[maxn], t[maxn], v[maxn];
10 vectorint, int> > > item;
11 
12 bool check(int day) {
13   item.clear();
14   int mina = inf, minb = inf;
15   int posa, posb;
16   for (int i = 1; i <= day; i++) {
17     if (mina > a[i]) mina = a[i], posa = i;
18     if (minb > b[i]) minb = b[i], posb = i;
19   }
20   for (int i = 1; i <= m; i++) {
21     if (t[i] == 1) item.push_back(make_pair(1ll * v[i] * mina, make_pair(i, posa)));
22     else item.push_back(make_pair(1ll * v[i] * minb, make_pair(i, posb)));
23   }
24   sort(item.begin(), item.end());
25   ll sum = 0;
26   for (int i = 0; i < k; i++) sum += item[i].first;
27   return s >= sum;
28 }
29 
30 int main() {
31   //freopen("case.in", "r", stdin);
32   cin >> n >> m >> k >> s;
33   for (int i = 1; i <= n; i++)  scanf("%d", a + i);
34   for (int i = 1; i <= n; i++)  scanf("%d", b + i);
35   for (int i = 1; i <= m; i++)  scanf("%d%d", t + i, v + i);
36   int l = 0, r = n + 1;
37   while (l + 1 < r) {
38     int m = (l + r) / 2;
39     if (check(m)) r = m;
40     else l = m;
41   }
42   if (l == n) { puts("-1"); return 0; }
43   printf("%d\n", r);
44   check(r);
45   for (int i = 0; i < k; i++) printf("%d %d\n", item[i].second.first, item[i].second.second);
46   return 0;
47 }

注意上面二分的写法，这是我从cf的代码中看到的一种比较新颖的方式，我们需要的是最前面的满足条件的最前面的天数，具体做法是先让l和r都后退一步，然后如果有一种情况满足就赋值给r，然后当r前面的那个不满足的时候我们找到的r就是满足情况的最小的方式，也就是l+1，如果还满足会赋值给r，所以最后找到的r就是满足答案的最小值。最后还有一个细节就是check（r）之后方便输出答案。

题E

题意：给你一个图，有m条边，如果让你一定要选这条边的最小生成树的权值是多少。输出m个数作为答案。

题解：先求出最小生成树，我们可以发现如果（u，v）要加进去的话，那么形成的环里减去最大权值的一个边就可以，这也是求最小生成树贪心的想法，求这个环内最大权值用的方法就是倍增LCA，在找最近祖先的时候维护一个类似地val[i][j]，表示i这个结点到1<的结点中的最大权值，然后在求LCA的过程中更新答案即可。

  1 /*zhen hao*/
  2 #include 
  3 using namespace std;
  4 
  5 typedef long long ll;
  6 const int maxn = 2e5 + 100;
  7 const int maxd = 25;
  8 int n, m, tot;
  9 int head[maxn], fa[maxn][maxd], val[maxn][maxd], root[maxn], dep[maxn];
 10 ll ans[maxn];
 11 
 12 struct Edge1 {
 13   int u, v, w, id;
 14   bool operator < (const Edge1& a) const {
 15     return w < a.w;
 16   }
 17 };
 18 
 19 struct Edge2 {
 20   int v, w, next;
 21 };
 22 
 23 Edge1 edge1[maxn];
 24 Edge2 edge2[maxn<<1];
 25 
 26 void init_tree() {
 27   memset(head, -1, sizeof head);
 28   tot = 0;
 29 }
 30 
 31 void add_edge(int u, int v, int w) {
 32   edge2[tot] = (Edge2){v, w, head[u]};
 33   head[u] = tot++;
 34 }
 35 
 36 int find_set(int rt) {
 37   if (rt == root[rt]) return rt;
 38   return root[rt] = find_set(root[rt]);
 39 }
 40 
 41 void bfs(int rt) {
 42   queue<int> q;
 43   q.push(rt);
 44   fa[rt][0] = rt;
 45   dep[rt] = 1;
 46   while (!q.empty()) {
 47     int u = q.front(); q.pop();
 48     for (int i = 1; i < maxd; i++)  fa[u][i] = fa[fa[u][i - 1]][i - 1];
 49     for (int i = 1; i < maxd; i++)  val[u][i] = max(val[u][i - 1], val[fa[u][i - 1]][i - 1]);
 50     for (int i = head[u]; ~i; i = edge2[i].next) {
 51       int v = edge2[i].v;
 52       if (v == fa[u][0])  continue;
 53       fa[v][0] = u;
 54       val[v][0] = edge2[i].w;
 55       dep[v] = dep[u] + 1;
 56       q.push(v);
 57     }
 58   }
 59 }
 60 
 61 int find_ans(int u, int v) {
 62   if (dep[u] > dep[v])  swap(u, v);
 63   int du = dep[u], dv = dep[v], ret = 0;
 64   for (int d = dv - du, i = 0; d; i++, d >>= 1) {
 65     if (d & 1) { ret = max(ret, val[v][i]); v = fa[v][i]; }
 66   }
 67   if (u == v) return ret;
 68   for (int i = maxd - 1; i >= 0; i--) {
 69     if (fa[u][i] == fa[v][i]) continue;
 70     ret = max(ret, val[u][i]);  u = fa[u][i];
 71     ret = max(ret, val[v][i]);  v = fa[v][i];
 72   }
 73   ret = max(ret, val[u][0]);
 74   ret = max(ret, val[v][0]);
 75   return ret;
 76 }
 77 
 78 int main() {
 79   //freopen("case.in", "r", stdin);
 80   cin >> n >> m;
 81   for (int i = 0; i < m; i++) {
 82     int u, v, w;
 83     scanf("%d%d%d", &u, &v, &w);
 84     edge1[i] = (Edge1){u, v, w, i};
 85   }
 86 
 87   init_tree();
 88   for (int i = 1; i <= n; i++)  root[i] = i;
 89 
 90   sort(edge1, edge1 + m);
 91   ll res = 0;
 92   for (int i = 0; i < m; i++) {
 93     int fu = find_set(edge1[i].u);
 94     int fv = find_set(edge1[i].v);
 95     if (fu != fv) {
 96       res += edge1[i].w;
 97       root[fv] = fu;
 98       add_edge(edge1[i].u, edge1[i].v, edge1[i].w);
 99       add_edge(edge1[i].v, edge1[i].u, edge1[i].w);
100     }
101   }
102   bfs(1);
103   for (int i = 0; i < m; i++) {
104     ans[edge1[i].id] = res - find_ans(edge1[i].u, edge1[i].v) + edge1[i].w;
105   }
106   for (int i = 0; i < m; i++) {
107     cout << ans[i] << endl;
108   }
109 }

代码写得有点丑，将就着看。。。