USACO 12月 2021-2022 December Contest Silver 题解

目录

Problem 1. Closest cow wins

Problem 2. Connecting Two Barns

Problem 3. Convoluted Intervals

---

Problem 1. Closest cow wins

Farmer John owns a long farm along the highway that can be considered somewhat like a one-dimensional number line. Along the farm, there are KK grassy patches (1≤K≤2⋅1051≤K≤2⋅105); the ii-th patch is located at position pipi and has an associated tastiness value titi (0≤ti≤1090≤ti≤109). Farmer John's nemesis, Farmer Nhoj, has already situated his MM cows (1≤M≤2⋅1051≤M≤2⋅105) at locations f1…fMf1…fM. All K+MK+M of these locations are distinct integers in the range [0,109][0,109].

Farmer John needs to pick NN (1≤N≤2⋅1051≤N≤2⋅105) locations (not necessarily integers) for his cows to be located. These must be distinct from those already occupied by the cows of Farmer Nhoj, but it is possible for Farmer John to place his cows at the same locations as grassy patches.

Whichever farmer owns a cow closest to a grassy patch can claim ownership of that patch. If there are two cows from rival farmers equally close to the patch, then Farmer Nhoj claims the patch.

Given the locations of Farmer Nhoj's cows and the locations and tastiness values of the grassy patches, determine the maximum total tastiness Farmer John's cows can claim if optimally positioned.

拥有最靠近某个草地的奶牛的农夫拥有这一草地。如果来自两方农夫的两头奶牛距这一草地相等，则 Farmer Nhoj 拥有该草地。给定 Farmer Nhoj 的奶牛的位置以及草地的位置和美味值，求 Farmer John 的奶牛以最优方式放置时可以达到的最大总美味值。

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains K, M, and N.

第一行输入K，M，和N

The next KK lines each contain two space-separated integers pipi and titi.

后面K行输入pi和ti

The next MM lines each contain a single integer fifi.

后面M行输入fi

OUTPUT FORMAT (print output to the terminal / stdout):

An integer denoting the maximum total tastiness. Note that the answer to this problem can be too large to fit into a 32-bit integer, so you probably want to use 64-bit integers (e.g., "long long"s in C or C++).

SAMPLE INPUT:

6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11

SAMPLE OUTPUT:

36

If Farmer John places cows at positions 11.511.5 and 88 then he can claim a total tastiness of 10+12+14=3610+12+14=36.

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int K, M, N;
	cin >> K >> M >> N;
	vector<pair<int, int>> patches(K + M); // patches and Nhoj's cows
	for (int i = 0; i < K; ++i)
		cin >> patches[i].first >> patches[i].second;
	for (int i = K; i < K + M; ++i) {
		cin >> patches[i].first;
		patches[i].second = -1;
	}
	sort(begin(patches), end(patches));
	vector<uint64_t> increases;
	int last_i = -1;
	uint64_t sum_range = 0;
	for (int i = 0; i < (int)patches.size(); ++i) {
		if (patches[i].second == -1) {
			if (last_i == -1) { // try placing to left of Nhoj's leftmost cow
				increases.push_back(sum_range);
			} else {
				uint64_t cur_ans_1 = 0;	  
				uint64_t best_ans_1 = 0; 
				for (int j = last_i + 1, r = last_i; j < i; ++j) { 
					while (r + 1 < i &&
						   (patches[r + 1].first - patches[j].first) * 2 <
							   patches[i].first - patches[last_i].first) {
						cur_ans_1 += patches[++r].second;
					} 
					best_ans_1 = max(best_ans_1, cur_ans_1);
					cur_ans_1 -= patches[j].second;
				}
				assert(2 * best_ans_1 >= sum_range); 
				increases.push_back(best_ans_1); 
				increases.push_back(sum_range - best_ans_1);
			}
			last_i = i;
			sum_range = 0;
		} else {
			sum_range += patches[i].second;
		}
	} 
	increases.push_back(sum_range); 
	sort(rbegin(increases), rend(increases));
	increases.resize(N);
	uint64_t ans = 0;
	for (auto val : increases)
		ans += val;
	cout << ans << "\n";
}

Problem 2. Connecting Two Barns

Farmer John's farm consists of a set of NN fields (1≤N≤105)(1≤N≤105), conveniently numbered 1…N1…N. Between these fields are MM bi-directed paths (0≤M≤105)(0≤M≤105), each connecting a pair of fields.

The farm contains two barns, one in field 1 and the other in field NN. Farmer John would like to ensure that there is a way to walk between the two barns along some series of paths. He is willing to build up to two new paths to accomplish this goal. Due to the way the fields are situated, the cost of building a new path between fields ii and jj is (i−j)2(i−j)2.

Please help Farmer John determine the minimum cost needed such that barns 11 and NN become reachable from each-other.

农场有两个牛棚，一个在田地 1 中，另一个在田地 NN 中。Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。 他愿意建造至多两条新道路来实现这一目标。由于田地的位置因素，在田地 ii 和 jj 之间建造新道路的花费是 (i−j)2(i−j)2。

请帮助 Farmer John 求出使得牛棚 11 和 NN 可以相互到达所需要的最小花费。

INPUT FORMAT (input arrives from the terminal / stdin):

Each input test case contains TT sub-cases (1≤T≤201≤T≤20), all of which must be solved correctly to solve the input case.

The first line of input contains TT, after which TT sub-test cases follow.

Each sub-test case starts with two integers, NN and MM. Next, MM lines follow, each one containing two integers ii and jj, indicating a path between two different fields ii and jj. It is guaranteed that there is at most one path between any two fields, and that the sum of N+MN+M over all sub-test cases is at most 5⋅1055⋅105.

OUTPUT FORMAT (print output to the terminal / stdout):

Output TT lines. The iith line should contain a single integer giving the minimum cost for the iith sub-test case.

SAMPLE INPUT:

2
5 2
1 2
4 5
5 3
1 2
2 3
4 5

SAMPLE OUTPUT:

2
1

In the first sub-test case, it is optimal to connect fields 2 and 3 with a path, and fields 3 and 4 with a path.

In the second sub-test case, it is optimal to connect fields 3 and 4 with a path. No second path is needed.

SCORING:

• Test case 2 satisfies N≤20N≤20.
• Test cases 3-5 satisfy N≤103N≤103.
• Test cases 6-10 satisfy no additional constraints.

#include <bits/stdc++.h>

using namespace std;

void dfs(const vector<vector<int>>& edges, vector<int>& component, const int currv, const int id) {
  for(int child: edges[currv]) {
    if(component[child] != id) {
      component[child] = id;
      dfs(edges, component, child, id);
    }
  }
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> edges(n);
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  vector<int> component(n);
  iota(component.begin(), component.end(), 0);
  for(int i = 0; i < n; i++) {
    if(component[i] == i) {
      dfs(edges, component, i, i);
    }
  }
  if(component[0] == component[n-1]) {
    cout << "0\n";
    return;
  }
  vector<vector<int>> componentToVertices(n);
  for(int i = 0; i < n; i++) {
    componentToVertices[component[i]].push_back(i);
  }
  long long ans = 1e18;
  vector<long long> srccost(n, 1e9);
  vector<long long> dstcost(n, 1e9);
  for(int i: componentToVertices[component[0]]) {
    for(int j = 0; j < n; j++) {
      srccost[component[j]] = min(srccost[component[j]], (long long)abs(i - j));
    }
  }
  for(int i: componentToVertices[component[n-1]]) {
    for(int j = 0; j < n; j++) {
      dstcost[component[j]] = min(dstcost[component[j]], (long long)abs(i - j));
    }
  }
  for(int i = 0; i < n; i++) ans = min(ans, srccost[i]*srccost[i] + dstcost[i]*dstcost[i]);
  cout << ans << "\n";
}

int main() { 
  int t;
  cin >> t;
  for(int i = 0; i < t; i++) {
    solve();
  }
  return 0;
}

Problem 3. Convoluted Intervals

The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of NN intervals (1≤N≤2⋅1051≤N≤2⋅105), where the iith interval starts at position aiai on the number line and ends at position bi≥aibi≥ai. Both aiai and bibi are integers in the range 0…M0…M, where 1≤M≤50001≤M≤5000.

To play the game, Bessie chooses some interval (say, the iith interval) and her cousin Elsie chooses some interval (say, the jjth interval, possibly the same as Bessie's interval). Given some value kk, they win if ai+aj≤k≤bi+bjai+aj≤k≤bi+bj.

For every value of kk in the range 0…2M0…2M, please count the number of ordered pairs (i,j)(i,j) for which Bessie and Elsie can win the game.

奶牛们正在努力尝试发明有趣的新游戏来玩。他们目前的工作之一与一组 N 个区间（1≤N≤2⋅1051≤N≤2⋅105）有关，其中第 ii 个区间从数轴上的 ai 位置开始，并在位置 bi≥aibi≥ai 结束。aiai 和 bibi 均为 0…M 范围内的整数，其中 1≤M≤50001≤M≤5000。对范围 0…2M0…2M 内的每个值 kk，请计算使得 Bessie 和 Elsie 可以赢得游戏的有序对 (i,j)(i,j) 的数量。

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN and MM. Each of the next NN lines describes an interval in terms of integers aiai and bibi.

第一行输入N和M

后面每N行是ai和bi的区间值

OUTPUT FORMAT (print output to the terminal / stdout):

Please print 2M+12M+1 lines as output, one for each value of kk in the range 0…2M0…2M.

SAMPLE INPUT:

2 5
1 3
2 5

SAMPLE OUTPUT:

0
0
1
3
4
4
4
3
3
1
1

In this example, for just k=3k=3, there are three ordered pairs that will allow Bessie and Elie to win: (1,1)(1,1), (1,2),(1,2), and (2,1)(2,1).

SCORING:

• Test cases 1-2 satisfy N≤100,M≤100N≤100,M≤100.
• Test cases 3-5 satisfy N≤5000N≤5000.
• Test cases 6-20 satisfy no additional constraints.

Note that output values might be too large to fit into a 32-bit integer, so you may want to use 64-bit integers (e.g., "long long" ints in C or C++).

需要longlong！！！！

#include <bits/stdc++.h>
using namespace std;

int main() { 
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> ivals(N);
	for (auto &ival : ivals)
		cin >> ival.first >> ival.second;
	vector<int64_t> win_start(2 * M + 1), win_end(2 * M + 1);
	{
		vector<int64_t> a_freq(M + 1);
		for (int i = 0; i < N; ++i)
			++a_freq.at(ivals.at(i).first);
		for (int i = 0; i <= M; ++i)
			for (int j = 0; j <= M; ++j)
				win_start.at(i + j) += a_freq.at(i) * a_freq.at(j);
	}
	{
		vector<int64_t> b_freq(M + 1);
		for (int i = 0; i < N; ++i)
			++b_freq.at(ivals.at(i).second);
		for (int i = 0; i <= M; ++i)
			for (int j = 0; j <= M; ++j)
				win_end.at(i + j) += b_freq.at(i) * b_freq.at(j);
	}
	int64_t win_count = 0;
	for (int i = 0; i <= 2 * M; ++i) {
		win_count += win_start.at(i);
		cout << win_count << "\n";
		win_count -= win_end.at(i);
	}
}