P9571

HasNoName · 2023-08-20 11:13:13 · 个人记录

题目

首先，需要知道 k 相同时两条线平行， b 也相同时两条线重合。

用暴力枚举每一项

#include<iostream>
using namespace std;
struct yxkb// 存储每一项的值和是否被计算过
{
    int k,b;
    bool t;
}s,a[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin.tie(0);
    int T,k=0,q;
    cin>>T;
    while(T--)
    {
        cin>>q>>s.k>>s.b;
        if(q==1)
            a[++k]=s;
        if(q==2)
        {
            int sum=0;
            for(int i=1;i<=k;i++)
            {
                if(a[i].k!=s.k&&!a[i].t)sum++;// 不平行且没被计算过
            }
            cout<<sum<<endl;
        }
        if(q==3)
        {
            for(int i=1;i<=k;i++)
            {
                if(a[i].k!=s.k||a[i].b==s.b)// 不平行或重合
                {
                    a[i].t=1;
                }
            }
        }
    }
    return 0;
}

但这样只能在 n > 5000 的情况下就会 TLE ，所以想到了 map

用一个 map 套 map 存储每一个 k 的 b 的数量，把总量用 sum 存起来

#include<iostream>
#include<map>
#define N 100001
using namespace std;
map<int,map<int,int> >a;
map<int,int>c;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin.tie(0);
    int n,q,k,b,sum=0;
    cin>>n;
    for(int T=1;T<=n;T++)
    {
        cin>>q>>k>>b;
        if(q==1)
        {
            a[k][b]++;
            a[k][N]++;//这一行的数量
            sum++;
        }
        if(q==2)
        {
            cout<<sum-a[k][N]<<'\n';
        }
        if(q==3)
        {
            c=a[k];//存储平行的
            a.clear();//删除所有直线
            a[k]=c;//保存平行的
            a[k][N]=a[k][N]-a[k][b];//减去重合的
            sum=a[k][N];//刷新线的数量
            a[k][b]=0;
        }
    }
    return 0;
}

但最后一个点超时了，所以只得了 75 分

后来用了 multiset （可重复的 set ） 因为 multiset 可重复，而 set 不能重复，所以用 set 存储出现过的 k 值，再到 multeset 里进行计算

#include<iostream>
#include<map>
#include<set>
#define N 150005
using namespace std;
set<int>c;
multiset<int>a[500005];
set<int>::iterator it;//定义 set 迭代器 
int f[500005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin.tie(0);
    int n,q,k,b,sum=0,s;
    cin>>n;
    for(int T=1;T<=n;T++)
    {
        cin>>q>>k>>b;
        k+=N;
        if(q==1)
        {
            a[k].insert(b);//这个 k 里存在 b
            c.insert(k);//有这个 k
            sum++;
        }
        if(q==2)
        {
            cout<<sum-a[k].size()<<'\n';//用总数减去平行和重合的个数得到与 y=kx+b 相交的个数
        }
        if(q==3)
        {
            int u=0;
            for(it=c.begin();it!=c.end();it++)//从 s 最小的 k 开始到 s 最大的 k  
            {
                s=(*it);//这一项的 k
                if(s==k)
                {
                    sum-=a[s].count(b);//sum 减去完全重合个数 
                    a[s].erase(b);//完全重合的删去
                    continue;
                }
                sum-=a[s].size();//sum 减去不平行个数 
                a[s].clear();//清空这个 k 
                f[++u]=s;//因为在循环里修改 c 会出错，所以要先存起来
            }
            for(int i=1;i<=u;i++)c.erase(f[i]);//擦去这个 k
        }
    }
    return 0;
}