P9571 「NnOI R2-T3」Horizon Blue

· · 题解

没有思维难度的暴力

1. 题意

操作1

我们把直线的 k 和 b 存在一个 vector 里，这里的细节下面补充。

操作2

初二的应该学过函数和图像，下面是关于这些东西的一点点特性：

所以这里我们只需要把与当前 k 相同的直线数量都减去就是与当前直线恰好有一个交点的直线数量。 然后关于如何找到与当前 k 相同的直线数量，我用 map 开了一个桶存着 k 的数量。

在这里说一下：我代码中的 unordered_map 可以看成更快的 map，真的很快，有时候可以多过好几个测试点。

操作3

“至少”说明重合和有一个交点的直线都要删去，我直接用的 vector 暴力删，只因其他的都不是很会。

这里还要说到 vector 的单点删除的一个优化。我们普通删除是这样的：

a.erase(a.begin+i);

下面一种是优化：

swap(a.begin()+i,a.back())；
a.pop_back()；

这个的原理是把当前要删除的数与最后一位交换，然后删除最后面的数。

我不是很清楚他的原理，只知道有点快，上网搜了一下也找不到答案。

2. 优化

上面的直接写出来已经可以得到惊人的 54 分了！下面是一些小优化，加上就 100 分了！

通过观察，我们发现我们操作 1、2 的时间复杂度都很小，所以只要优化操作 3： 我们在删除的是 k 不相等的或者是 b 相等的，之前开了个桶存的 b 可以判断是否还有相同的 b，桶 k 可以判断是否还有不同的 k，如果没有了就 break，然后就可以直接 100 分！

3. 代码

主食很详细：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,zong;// zong 存的是总共现在有的线段的数量。 
vector<int> zk,zb;// zk 存 k[i] 的值，zb 存 b[i] 的值。 
unordered_map<int,int> tk,tb;// tk 存 k[i] 的数量，tb 存 b[i] 的数量 。 
signed main()
{
    cin>>n;
    for(int i1=1,op,k,b;i1<=n;i1++)
    {
        cin>>op>>k>>b; 
        if(op==1)
            zong++,tk[k]++,tb[b]++,
            zk.push_back(k),zb.push_back(b);
        else if(op==2) cout<<zong-tk[k]<<'\n';
        //总共的线段减去平行和重合的线段，就是恰好有一个交点的线段。 
        else if(op==3)
        {
            if(tk[k]==zong&&tb[b]<=0) continue;//优化 
            for(vector<int>::iterator k1=zk.end()-1,b1=zb.end()-1;k1>=zk.begin();k1--,b1--)
                //迭代器，相当于遍历，主要是快。 
                if(*k1!=k||*b1==b)
                {
                    zong--,tk[*k1]--,tb[*b1]--;
                    // 把操作 1 那反过来。（毫无思维难度） 
                    swap(*k1,zk.back()),zk.pop_back(),
                    swap(*b1,zb.back()),zb.pop_back();
                    if(tk[k]==zong&&tb[b]<=0) continue;//优化 
                }
        }
    }
    return 0;
}