专栏文章

8.17测试总结

LLuck_Deepsea
算法·理论参与者 1已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mioa1c96
此快照首次捕获于
2025/12/02 15:48
3 个月前
此快照最后确认于
2025/12/02 15:48
3 个月前
查看原文

8.178.17测试总结

T638034真实社交T638034 真实社交

得分:5050

应得:100100

考点:map+pairmap+pair

错误思路:暴力得分

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

正确代码:

CPP
#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落落的去维护数组T638156 落落的去维护数组

得分:7474

应得:100100

考点:模拟

错误思路:暴力得分

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

核心代码（分类判断）：

CPP
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;
			}
		}

正确代码:

CPP
#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交叉区间T638430 交叉区间

得分:1010

应得:100100

考点:结构体+upperbound+lowerbound结构体+upper_bound+lower_bound

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

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

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

CPP
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;

正确代码:

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...