CCF-CSP19＜2020-06＞-第1/2题

202006-1 线性分类器

题目：202006-1

题目分析：

给定n个点，并标记为AB两类，问给定直线是否能将其分为两个点集。

简单数学知识，点在直线上满足ax+by+c=0，点在直线割平面所得的上下其值会正负相反。

AC代码：

// -*- coding:utf-8 -*-

// File    :   202006-1.cpp
// Time    :   2024/03/26
// Author  :   wolf

#include <iostream>
#include <vector>
const int N = 1e8 + 10;
using namespace std;
vector<pair<int, int>> A, B;
#define ll long long

// 判断该点在直线的哪一侧
int func(ll t0, ll t1, ll t2, ll x, ll y)
{
    return (t0 + t1 * x + t2 * y) > 0 ? 1 : -1;
}

int main()
{
    int n, m;
    cin >> n >> m;
    // 读入n个点，使用两个vector进行存储
    for (int i = 0; i < n; i++)
    {
        ll x, y;
        char type;
        cin >> x >> y >> type;
        if (type == 'A')
            A.push_back(make_pair(x, y));
        else if (type == 'B')
            B.push_back(make_pair(x, y));
    }
    while (m--)
    {
        ll t0, t1, t2;
        cin >> t0 >> t1 >> t2;
        bool ans = true; // 标记，假设是满足的
        int A_std, B_std;
        // 设定A标准 B标准，就是在A集合和B集合各自随便抓一个点，代表它们集合中的点应该在直线哪边
        // 当且仅当A集合内的点都和A标准相等，B集合内的点都和B标准相等，再A标准不等于B标准，才满足题意
        A_std = func(t0, t1, t2, A[0].first, A[0].second);
        for (unsigned int i = 0; i < A.size(); i++)
        {
            if (func(t0, t1, t2, A[i].first, A[i].second) != A_std)
            {
                ans = false;
                break;
            }
        }
        B_std = func(t0, t1, t2, B[0].first, B[0].second);
        for (unsigned int i = 0; i < B.size(); i++)
        {
            if (func(t0, t1, t2, B[i].first, B[i].second) != B_std)
            {
                ans = false;
                break;
            }
        }
        if (A_std != B_std && ans == true)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

202006-2 稀疏矩阵（100）

题目：202006-2

题目分析：

如题，给定两个向量，但是是稀疏的。稀疏就是该向量大多数位置都是0，只有少数有值。

最简单的想法就是用数组模拟这两个向量，然后for循环模拟相加，但这样显然超时间，考虑负数的话要达到10^12，应该是0分。

再进一步，想到两重循环遍历这两个向量，index相等时相乘，30分，在10^5时就会超时，只能过前三个点，因此30分。

要完成10^9的数据规模，应该是O(n)，即只能遍历一次。那么就遍历一个向量A，对于这个向量A的每一个，用while使得B不超过A的当前index但尽可能增大，这样大概就是2O(n)的复杂度，因此能100分。

AC代码：

// -*- coding:utf-8 -*-

// File    :   202006-2.cpp
// Time    :   2024/03/25
// Author  :   wolf

#include <algorithm>
#include <iostream>
#include <vector>
#define ll long long

using namespace std;
vector<pair<int, int>> v1, v2;
bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first;
}

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    for (int i = 0; i < a; i++)
    {
        int index, value;
        cin >> index >> value;
        v1.push_back(make_pair(index, value));
    }
    for (int i = 0; i < b; i++)
    {
        int index, value;
        cin >> index >> value;
        v2.push_back(make_pair(index, value));
    }
    ll ans = 0;
    // 30分答案
    // for (unsigned int i = 0; i < v1.size(); i++)
    // {
    //     for (unsigned int j = 0; j < v2.size(); j++)
    //     {
    //         if (v1[i].first == v2[j].first)
    //             ans += v1[i].second * v2[j].second;
    //     }
    // }

    // 100分答案
    sort(v1.begin(), v1.end(), cmp);
    sort(v2.begin(), v2.end(), cmp);
    unsigned int v2i = 0;
    for (unsigned int v1i = 0; v1i < v1.size(); v1i++)
    {
        while (v2[v2i].first < v1[v1i].first && v2i < v2.size())
            v2i++;
        if (v1[v1i].first == v2[v2i].first)
            ans += v1[v1i].second * v2[v2i].second;
    }
    cout << ans << endl;
    return 0;
}