8.17测试总结

Luck_Deepsea · 2025-08-17 21:32:27 · 算法·理论

8.17测试总结

T638034 真实社交

得分:50

应得:100

考点:map+pair

错误思路:暴力得分

正确思路:使用map<pair<int,int>,int>mp;进行操作

正确代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,q;
map<pair<int,int>,int>mp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    while(q--)
    {
        int op;
        cin>>op;
        int a,b;
        cin>>a>>b;
        if(op==1)
        {
            mp[{a,b}]=1;
        }
        else if(op==2)
        {
            if(mp.count({a,b}))
            {
                mp.erase({a,b});
            }
        }
        else if(op==3)
        {
            if(mp.count({a,b})&&mp.count({b,a}))
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }
    }
    return 0;
}

T638156 落落的去维护数组

得分:74

应得:100

考点:模拟

错误思路:暴力得分

正确思路:使用多个计数器经行模拟

核心代码（分类判断）：

if(op==1)
        {
            lasttime=i;
            cin>>lastval;
        }
        else if(op==2)
        {
            int x,k;
            cin>>x>>k;
            if(0==lasttime)
            {
                a[x]+=k;
            }
            else if(t[x]>lasttime)
            {
                a[x]+=k;
            }
            else
            {
                a[x]=k;
            }
            t[x]=i;

        }
        else if(op==3)
        {
            int x;
            cin>>x;
            if(lasttime==0)
            {
                cout<<a[x]<<endl;
            }
            else if(t[x]>lasttime)
            {
                cout<<lastval+a[x]<<endl; 
            }
            else
            {
                cout<<lastval<<endl;
            }
        }

正确代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,q,lasttime,lastval;
int a[200005],t[200005];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            lasttime=i;
            cin>>lastval;
        }
        else if(op==2)
        {
            int x,k;
            cin>>x>>k;
            if(0==lasttime)
            {
                a[x]+=k;
            }
            else if(t[x]>lasttime)
            {
                a[x]+=k;
            }
            else
            {
                a[x]=k;
            }
            t[x]=i;

        }
        else if(op==3)
        {
            int x;
            cin>>x;
            if(lasttime==0)
            {
                cout<<a[x]<<endl;
            }
            else if(t[x]>lasttime)
            {
                cout<<lastval+a[x]<<endl; 
            }
            else
            {
                cout<<lastval<<endl;
            }
        }
    }
    return 0;
}

T638430 交叉区间

得分:10

应得:100

考点:结构体+upper_bound+lower_bound

错误思路:输出10（骗分），暴力写错了只能骗分QAQ

正确思路:用结构体储存，用两个数组再储存,sort排序，使用upper_bound+lower_bound进行运算，输出

核心代码（使用upper_bound+lower_bound进行运算）：

int L=a[i].l,R=a[i].r;
        int x=upper_bound(b+1,b+1+n,R)-b;
        int num1=n-x+1;
        x=lower_bound(c+1,c+n+1,L)-c;
        int num2=x-1;
        ans=ans+num1+num2;

正确代码:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=5e5+5;
struct node{
    int l,r;
}a[N];
int n,ans,b[N],c[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].l>>a[i].r;
        b[i]=a[i].l;
        c[i]=a[i].r;
    }
    sort(b+1,b+1+n);
    sort(c+1,c+1+n);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int L=a[i].l,R=a[i].r;
        int x=upper_bound(b+1,b+1+n,R)-b;
        int num1=n-x+1;
        x=lower_bound(c+1,c+n+1,L)-c;
        int num2=x-1;
        ans=ans+num1+num2;
    }
    ans/=2;
    int x=n*(n-1)/2;
    cout<<x-ans;
    return 0;
}