https://ac.nowcoder.com/acm/contest/3007

题解 https://ac.nowcoder.com/discuss/367149?type=101&order=0&pos=1&page=1

A. 配对

 

题意：A，B两个集合，要使每个元素两两配对，且每对求和，使第K大的和最大。

贪心

只用前K大的数配对，变成使最小的和最大，可以贪心地倒序配对，取每次地最小值，最小值一定最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++h>
using namespace std;
const int N = 100050;
int a[N], b[N], n, k, ans = 2e8;
int main(){
    int i, j;
    scanf("%d%d", &n, &k);
    for(i = 1; i <= n; i++)scanf("%d", &a[i]);
    for(i = 1; i <= n; i++)scanf("%d", &b[i]);
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    for(i = n; i > n - k; i --)
        ans = min(ans, a[i] + b[n - k + n + 1 - i]);
    printf("%d\n", ans);
    return 0;
}

 

E. 立方数

 

题意：对于给定的正整数 NN，求最大的正整数 AA，使得存在正整数 BB，满足 A3B=NA^3B=N，输入包含 TT 组数据，1≤T≤10,0001≤T≤10,000；1≤N≤10181≤N≤10^{18}。

神仙优化题

显然是要对 NN 质因数分解，对每个质因数验证是否三次方仍为因数，因此可以只枚举 N1/3N^{1/3} 以内的质因数，但是数据很大，只有优化到 N1/4N^{1/4} 才行，所以考虑只枚举 N1/4N^{1/4} 以内的质因数，枚举完还剩下的质因数一定大于 N1/4N^{1/4} ，那么最多只会还有一个因数，满足它的三次方仍为因数，因为如果有两个，每个因数最小为 N1/4N^{1/4} ，乘积最小为 N6/4N^{6/4} 。

并且最后剩下的那个数如果存在因数满足它的三次方仍为因数，那么剩下的那个数一定是完全立方数，而那个因数就是它唯一的因数。它的因数最小为 N1/4N^{1/4} ，立方最小为 N3/4N^{3/4} ，如果还有一个不同的因数，那个数一定大于 N1/4N^{1/4} ，那么乘积就大于 NN。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 31700;
int T;
ll x, pri[N], pr_tr[N], pr_qu[N];
bool vis[N];
int main() {
	scanf("%d", &T);
	for (int i = 2; i < N; i++) {
		if (vis[i])continue;
		pri[++pri[0]] = 1ll * i;
		pr_tr[pri[0]] = 1ll * i*i*i;
		pr_qu[pri[0]] = 1ll * i*pr_tr[pri[0]];
		for (int j = i * i; j < N; j += i)vis[j] = 1;
	}
	while (T--) {
		scanf("%lld", &x);
		ll ans = 1;
		for (int i = 1; pr_qu[i] <= x; i++) {
			if (x%pri[i] != 0)continue;
			while (x%pr_tr[i] == 0) {
				ans *= pri[i];
				x /= pr_tr[i];
			}
			while (x%pri[i] == 0)x /= pri[i];
		}
		ll L = 1, R = 1000000;
		while (L < R) {
			ll mid = L + R >> 1;
			if (mid*mid*mid >= x)R = mid;
			else L = mid + 1;
		}
		if (L*L*L == x)ans *= L;
		printf("%lld\n", ans);
	}
	return 0;
}

 

I. 云

 

题意：平面上有两类矩形，A类都在第三象限，B类都在第一象限，都不与坐标轴相交。A类向右移动，B类向下移动，速度都相同。问有几对A和B矩形相交。

神仙思维题

扫描线

两种矩形都运动不好处理，所以考虑相对运动，B不动，A向右上动，由运动合成可知A的路径为 y=xy=x 方向，原先的两个矩形相遇等价于A向 y=xy=x 方向移动能碰到B，又等价于它们在 y=−xy=-x 上的投影线段相交。

由于一个在第三，一个在第一象限，所以A，B的投影点的x坐标一定不同，原先平面上的点只要映射x坐标即可。投影点的x坐标为 (x1−y1)/2(x_1-y_1)/2，除2也不用了。

线段相交可以用扫描线处理。

按照左端点排序，排序时一定坐标相同的把左端点放前面，遇到右端点就-1，左端点就+1，每次只要遇到左端点，还剩下的值就是还没有闭合的线段，一定与当前线段相交，直接加入答案。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
int n, m, t;
struct X
{
	int x, lr, type;
	bool operator<(const X& b) { return x == b.x ? lr > b.lr:x < b.x; }
}a[N];
int cnt[2];
int main() {
	scanf("%d%d", &n, &m);
	int x1, y1, x2, y2;
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		a[t++] = X{ x1 - y1,1,1 };
		a[t++] = X{ x2 - y2,-1,1 };
	}
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		a[t++] = X{ x1 - y1,1,0 };
		a[t++] = X{ x2 - y2,-1,0 };
	}
	sort(a, a + t);
	ll ans = 0;
	for (int i = 0; i < t; i++) {
		cnt[a[i].type] += a[i].lr;
		if (a[i].lr == 1)ans += cnt[a[i].type ^ 1];
	}
	printf("%lld\n", ans);
	return 0;
}

 

I. 导航系统

 

题意：矩阵 dij 表示树上点i和点j的最短距离，问是否存在这样的树，若存在则输出所有边权。

假设存在，则从这个矩阵上可以找到所有边，特征就是直接相连的两条边一定满足不存在k，使得 d[i][j]=d[i][k]+d[k][j]d[i][j]=d[i][k]+d[k][j]，所以直接 n3n^3 枚举i，j，k，判断即可。

但是本题有个坑，存在边权为0，（虽然不知道这城市怎么建的），会导致重复加边，比如：1-2-3-4，12边权为0，23边权为2，34边权为0，则会把13，14，24都误当成边加进去。所以要把距离为0的城市放在一个并查集里维护，并且一个并查集只有根连出去边，其他的点只和根相连，所以总边数一定=根连出的边数+非根的点数。

题解里说把矩阵所有元素都作为边连图，原树一定是图的Kruskal生成树，求完生成树再判断。复杂度相同，也是一种新的方法。

假设Kruskal按照边权排序后先枚举到边 (u,v) ，则 (u,v) 一定是原树上的边，否则一定存在 (u,k),(k,v)，且 (u,k),(k,v) 一定小于 (u,v)。而则以此类推，Kruskal枚举到的所有边都加入生成树，且都是原树上的边，直到联通，那么Kruskal生成树就等于原树。这里就不用额外处理0了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
int p[maxn], rk[maxn];
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void uni(int x, int y) {
	x = find(x), y = find(y);
	if (x == y)return;
	if (rk[x] < rk[y])p[x] = y;
	else {
		p[y] = x;
		if (rk[x] == rk[y])rk[x]++;
	}
}
int d[510][510];
vector<int>es;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)p[i] = i;
	for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {
		scanf("%d", &d[i][j]);
		if (!d[i][j])uni(i, j);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (d[i][j] != d[j][i]) { puts("No"); return 0; }
			if (p[i] != i || p[j] != j)continue;
			bool flg = 1;
			for (int k = 1; k <= n; k++) {
				if (d[i][k] == 0 || d[j][k] == 0)continue;
				if (d[i][j] > d[i][k] + d[k][j]) {
					puts("No"); return 0;
				}
				else if (d[i][j] == d[i][k] + d[k][j]) {
					flg = 0; break;
				}
			}
			if (flg)es.push_back(d[i][j]);
		}
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++)if (p[i] != i)cnt++;
	if ((int)es.size() + cnt != n - 1)puts("No");
	else {
		puts("Yes");
		sort(es.begin(), es.end());
		for (int i = 0; i < cnt; i++)puts("0");
		for (int i : es)printf("%d\n", i);
	}
	return 0;
}