个人题目思路库

AK后上岸

2026-06-01 21:55:28

发布于：浙江

13阅读

0回复

0点赞

原题（部分可开）

方法1：

#include<bits/stdc++.h>
using namespace std;
int n,t;
string s;
long long ans;
struct aaa
{
	int x;
	int v;
}a[200005];
int main()
{
	cin>>n>>t;
	cin>>s;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i].x;
		if (s[i-1]-'0') a[i].v=1;
		else a[i].v=-1;
	}
	int T=t;
	while(T--)
	{
		for (int i=1;i<=n;i++) a[i].x+=a[i].v;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				if (i!=j&&(a[i].x==a[j].x||a[i].x>a[j].x)&&a[i].x-a[i].v<a[j].x-a[j].v) ans++;
	}
	cout<<ans;
	return 0;
	//方法1:模拟
	//time：O(t*n*n)
}

~~华丽超时~~

方法2：

#include<bits/stdc++.h>
using namespace std;
int n,t;
string s;
long long ans;
struct aaa
{
	int x;
	int v;
}a[200005];
int main()
{
	cin>>n>>t;
	cin>>s;
	for (int i=1;i<=n;i++)
	{
		cin>>a[i].x;
		if (s[i-1]-'0') a[i].v=1;
		else a[i].v=-1;
	}
	int T=t;
	for (int i=1;i<=n;i++) a[i].x+=t*a[i].v;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (i!=j&&(a[i].x==a[j].x||a[i].x>a[j].x)&&a[i].x-a[i].v*t<a[j].x-a[j].v*t) ans++;
	cout<<ans;
	return 0;
	//方法2:优化模拟 
	//time：O(n*n)
}

~~略有提升，但依旧超时~~

方法3：

#include<bits/stdc++.h>
using namespace std;
int n,t;
string s;
long long ans;
struct aaa
{
	int x;
	int v;
};
aaa l[200005];
aaa r[200005];
int e,sr,sl;
int main()
{
	cin>>n>>t;
	cin>>s;
	for (int i=1;i<=n;i++)
	{
		cin>>e;
		if (s[i-1]-'0')
		{
			sr++;
			r[sr].x=e;
			r[sr].v=1;
		}
		else
		{
			sl++;
			l[sl].x=e;
			l[sl].v=-1;
		}
	}
	int T=t;
	for (int i=1;i<=sl;i++) l[i].x+=t*l[i].v;
	for (int i=1;i<=sr;i++) r[i].x+=t*r[i].v;
	for (int i=1;i<=sl;i++)
	{
		for (int j=1;j<=sr;j++)
			if ((l[i].x==r[j].x||l[i].x<r[j].x)&&l[i].x-l[i].v*t>r[j].x-r[j].v*t) ans++;
	}
	cout<<ans;
	return 0;
	//方法3:优化思路，加入贪心算法
	//贪心:速度一致，只有正负异向才有可能相遇 
	//time：O(n*n)不到，此处为最坏 
}

~~改进较小，但快了一点~~

方法4：

#include<bits/stdc++.h>
using namespace std;
int n,t;
string s;
long long ans;
struct aaa
{
	long long x;
	int v;
};
aaa l[200005];
int e,sr,sl;
long long a[200005];
int main()
{
	cin>>n>>t;
	cin>>s;
	for (int i=1;i<=n;i++)
	{
		cin>>e;
		if (s[i-1]-'0')
		{
			sr++;
			a[sr]=e;
		}
		else
		{
			sl++;
			l[sl].x=e;
			l[sl].v=-1;
		}
	}
	sort(a+1,a+sr+1);
	for(int i=1;i<=sl;++i)
    {
        int l1=l[i].x;
        int l2=l1-2*t;
        int L=lower_bound(a+1,a+sr+1,l2)-a;
        int R=lower_bound(a+1,a+sr+1,l1)-a-1;
        if(R>=L) ans+=R-L+1;
    }
	cout<<ans;
	return 0;
	//方法4:强化思路，加入二分算法
	//二分:将左行点排序，查找相遇右行点区间收尾，利用区间求数个数公式，求出相遇点个数 
	//time：O(nlogn)
}