比赛第三题

重点先放在前面：建议加强数据

---

恶搞算法

首先很容易想到的正常$O(n^2)$做法，按题意模拟即可。

#include <iostream>
using namespace std;
int k1[200005],cnt,cnt_i;//cnt当前线的条数
int k2[100005],b2[100005];
const int ch = 100000;

bool vis[100005];

int main(){
	int n,x,k,b;
	cin >> n;
	for (int i = 1; i <= n; i++){
		scanf("%d%d%d",&x,&k,&b);
		if (x == 1){
			k2[++cnt_i] = k;
			b2[cnt_i] = b;
			++cnt;
			k1[k+ch]++;
		}else if (x == 2){
			cout << cnt - k1[k+ch] << "\n";
		}else {
			for (int j = 1; j <= cnt_i; j++){
				if(!vis[j]&&(k2[j]!=k||(k2[j]==k&&b2[j]==b))){
					cnt --;
					k1[k2[j]+ch]--;
					vis[j] = 1;
				}
			}
		}
	}
}

只有40分……然而我太菜了，想不到正解……
于是我愤怒地盯着删除操作的那个循环。

欸，把相交的线删了，不就只剩与它k相同的直线了吗？直接把循环替换成cnt = k1[k+ch];，27分！其实已经超出预期了。

但是——当我们加个卡时把它俩结合在一起……

			if ((clock()-strat) > 0.4*CLOCKS_PER_SEC)
				cnt = k1[k+ch];
			else {
				for (int j = 1; j <= cnt_i; j++){
					if(!vis[j]&&(k2[j]!=k||(k2[j]==k&&b2[j]==b))){
						cnt --;
						k1[k2[j]+ch]--;
						vis[j] = 1;
					}
				}
			}

就会发生奇妙的化学反应……

这说明了数据可能有一点水……

---

说句闲话

你有一个苹果，我有一个苹果，交换后还是一个苹果；我有一个垃圾算法，我还有一个垃圾算法，交换后就不只是一个垃圾算法了。（bushi