自动搬运

查看原文

来自洛谷，原作者为

	a1a2a3a4a5 蒟蒻可骂，私信互关，互关者备故事来

搬运于2025-08-24 22:49:41，当前版本为作者最后更新于2023-08-19 19:47:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

没有思维难度的暴力

1. 题意

操作1

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

操作2

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

• 当 $k$ 相等的两个直线，他们平行或重合。

• 当 $k$ 和 $b$ 都相等的两个直线，他们重合，也就是有很多很多的公共点。

• 在同一个平面内，两条不平行不重合的直线恰好有一个交点。

• 如果 $b$ 相等，那么当 x==0 时，y==b 所以当两个直线的 $b$ 相等时，必定有一个交点。

所以这里我们只需要把与当前 $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;
}