2021-2022 ACM-ICPC Latin American Regional Programming Contest

2021-2022 ACM-ICPC Latin American Regional Programming Contest

J. Joining Pairs

思路:

本题显然答案为$N$的情况为两条线段的顶点都出现在矩形边框上且连接会相交。其余为$Y$。

如何判断连接会相交？我们可以把二维的矩形转化为一维来写

inline int go(int x, int y){
    if(y == 0) return x;
    if(x == n) return n + y;
    if(y == m) return m +  2 * n - x;  
    if(x == 0) return (n + m) * 2 - y;
    return -1;
}
1
2
3
4
5
6
7

如果转化为一维 的两条线段没有交点或者一条线段把另一条包含在内就不会相交，其余情况能相交。我们可以先把所有点在边框上的线段进行升序排序，然后进行遍历：我们把前一条线段称为seg1，当前线段称为seg2，如果seg2的左端点比 seg1的左端点小那么就是完全包含的情况，不会相交，否则如果seg2的左端点比seg1的右端点小就是有交点，我们可以用栈模拟一下即可（可以自己画图理解）。

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> PII;

vector<PII>q;

int n, m, t;

inline int go(int x, int y){
    if(y == 0) return x;
    if(x == n) return n + y;
    if(y == m) return m +  2 * n - x;  
    if(x == 0) return (n + m) * 2 - y;
    return -1;
}

int main(){
    scanf("%d %d %d",&n, &m, &t);
    while(t -- ){
        int a, b, u, v;
        scanf("%d %d %d %d",&a, &b, &u, &v);
        int l = go(a, b), r = go(u, v);
        if(l > r) swap(l, r);
        if(l > -1 && r > -1){
            q.push_back({r, l});
        }
    }
    sort(q.begin(), q.end());
    stack<PII>stk;
    for(auto [y, x] : q){
        while(!stk.empty() && x < stk.top().first) stk.pop();
        if(!stk.empty() && x < stk.top().second){
            puts("N");
            return 0;
        }
        stk.push({x, y});
    }
    puts("Y");
    return 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

M. Most Ordered Way

题目给的$0.85s$把时间复杂度卡死在$O(n^2)$, $O(n^{2}logn)$过不去。

思路（没有官方题解，看别人代码悟的）

循环n​次，每次找到第i次应该写哪门作业，题目要求字典序尽可能最小，那么，我们每次循环，从下标小的往下标大的地方找，每次计算完成作业时间和作业截止时间中间的时间的差值，然后取个前缀最小值，如果能找到某门作业的需要做的时间小于等于前缀最小值且下标的字典序更小就更新一下，遍历n次即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int n;

int main(){
	scanf("%d",&n);
	vector<array<int,3>>a(n);
	for(int i = 0; i < n; i ++ ){
		int t, d;
		scanf("%d %d",&t, &d);
		a[i] = {d, t, i};
	}
	sort(a.begin(), a.end());
	LL sum = 0;
	for(int i = 0; i < n; i ++ ){
		if(sum + a[i][1] > a[i][0]){
			printf("*\n");
			return 0;
		}
		sum += a[i][1];
	}
	LL now = 0;
	while(!a.empty()){//O(n^2)
		int j = -1, maxn = 1e9 + 1;
		LL s2 = now;
		for(int i = 0; i < a.size(); i ++ ){
			if(maxn >= a[i][1] && (j == -1 || a[i][2] < a[j][2])){
				j = i;
			}
			s2 += a[i][1];
			maxn = min(maxn * 1ll, a[i][0] - s2);
		}
		now += a[j][1];
		printf("%d ", a[j][2] + 1);
		if(a.size() == 1) printf("\n");
		a.erase(a.begin() + j);
	}
}
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