CSP 202006-1 202006-2 题解

# 202006-1 线性分类器

在坐标系中，我们可以考虑使用同一横坐标x值对应的y值来判断在直线的上方一侧还是在下方一侧。
当然，如果不在坐标系中也可以统计点和直线的位置关系，这个属于计算几何的内容，感兴趣的同学可以点击这个网址自己查阅相关内容，这里就不赘述了。
还有一点需要注意的是，本题计算过程中，两整数的相乘可能导致数据范围超过int范围，需要用 long long 来保存中间值。

#include <iostream>
using namespace std;
const int N = 1010;
typedef long long LL;

int n, m, x[N], y[N];
char str[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) scanf("%d%d%s", &x[i], &y[i], &str[i]);
    while (m -- )
    {
        int a, b, c, A = 0, B = 0; // A和B用来计数属于A区域或B区域的每个点是否满足
        cin >> a >> b >> c;
        for (int i = 1; i <= n; i ++ ) // 这里只讨论A上B下的情况，另一种是对称的，如果是A下B上，统计结果应该是0
        {
            if (str[i] == 'A' && a + (LL)b * x[i] + (LL)c * y[i] > 0) A ++ ;
            if (str[i] == 'B' && a + (LL)b * x[i] + (LL)c * y[i] < 0) B ++ ;
        }
        if (A + B == n || !(A + B)) puts("Yes"); // 如果能完美分割，计数之和要么为n，要么为0
        else puts("No");
    }
    return 0;
}

202006-2 稀疏向量

双指针算法 类似于数据结构课上的归并排序
对于两个向量u和v，分别用指针i和j指向向量第一个非零位置，如果位置的下标相同，则值相乘累积到答案中；否则每次将下标较小的那个指针在对应的向量上向后（即下标增大的方向）移动一位，直到其中一个指针计算到对应向量的末尾。

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

typedef long long LL;
const int N = 5e5 + 10;

struct vtr {
	int index;
	int value;
} u[N], v[N];
int n, a, b;
LL ans = 0;

int main() {
	scanf("%d %d %d", &n, &a, &b);

	for (int i = 1; i <= a; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		u[i].index = x;
		u[i].value = y;
	}

	for (int i = 1; i <= b; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		v[i].index = x;
		v[i].value = y;
	}

	int i = 1, j = 1;
	for (i = 1, j = 1; i <= a && j <= b; ) {
		if (u[i].index == v[j].index) {
			ans += (LL)u[i].value * v[j].value;
			i++, j++;
		} else if (u[i].index < v[j].index) {
			i++;
		} else {
			j++;
		}
	}

	printf("%lld\n", ans);

	return 0;
}