牛客春招刷题训练营 - 2025.3.31 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 挑7

简要题意

数 上有 因子 或数位 的数的个数。

Solution

枚举判断即可，时间复杂度为 。

Code

void R()
{
	int n,cnt=0;
	cin>>n;
	for (int i=1;i<=n;i++)
		if (i%7==0)
			cnt++;
		else
		{
			int t=i;
			while (t)
			{
				if (t%10==7)
				{
					cnt++;
					break;
				}
				t/=10;
			}
		}
	cout<<cnt;
	return;
}

Medium 仰望水面的歪

简要题意

给定三维坐标系、定点 ，找一个方向向量（最简整数比格式）使得原点沿该方向发射的射线经过 平面反射后过点 。

Solution

根据初中知识可以知道，对点 关于 的对成点 ， 和答案只差一个系数。

因为给的都是整点，所以我们直接消去 就好，时间复杂度为 。

Code

void R()
{
	int n,h;
	cin>>n>>h;
	for (int i=0;i<n;i++)
	{
		i64 x,y,z;
		cin>>x>>y>>z;
		z=2*h-z;
		i64 t=gcd(x,gcd(y,z));
		x/=t,y/=t,z/=t;
		cout<<x<<' '<<y<<' '<<z<<'\n';
	}
	return;
}

Hard 1or0

简要题意

对 串定义 。

有 次询问，每次给定 ，求 。

Solution

当且仅当 是一个全 串。

所以题意可以转化为数区间全 子串数。

今天天气太冷了，不想动脑，直接上线段树：

线段树节点维护：当前区间答案、当前区间全 前后缀长度。

合并答案就是左右儿子答案加上左后缀乘右前缀。

合并前后缀要特殊考虑一下区间全 的情况。

时间复杂度为 。

Code

template <class Info>
struct SGT
{
	int n;
	vector<Info> info;

	SGT():n(0) {}
	SGT(int n_,Info v_=Info()) { init(n_,v_); }

	template <class T>
	SGT(vector<T> init_) { init(init_); }

	void init(int n_,Info v_=Info()) { init(vector(n_,v_)); }

	template <class T>
	void init(vector<T> init_)
	{
		n=init_.size();
		info.assign(4<<__lg(n),Info());
		function<void(int,int,int)> build=[&](int p,int l,int r)
		{
			if (r-l==1)
			{
				info[p]=init_[l];
				return;
			}
			int m=(l+r)>>1;
			build(p<<1,l,m);
			build(p<<1|1,m,r);
			pushup(p);
		};
		build(1,0,n);
	}

	void pushup(int p) { info[p]=info[p<<1]+info[p<<1|1]; }

	Info rangeQuery(int p,int l,int r,int x,int y)
	{
		if (l>=y||r<=x) return Info();
		if (l>=x&&r<=y) return info[p];
		int m=(l+r)>>1;
		return rangeQuery(p<<1,l,m,x,y)+rangeQuery(p<<1|1,m,r,x,y);
	}

	//O(log n)区间查询[l,r)
	Info rangeQuery(int l,int r) { return rangeQuery(1,0,n,l,r); }
};

struct Info
{
	i64 x=0,l=0,r=0,len=0;
	bool emp=1;
};

Info operator + (Info a,Info b)
{
	if (a.emp) return b;
	if (b.emp) return a;
	Info res;
	res.x=a.x+b.x+a.r*b.l;
	res.len=a.len+b.len;
	if (a.l==a.len)
		res.l=a.len+b.l;
	else res.l=a.l;
	if (b.r==b.len)
		res.r=b.len+a.r;
	else res.r=b.r;
	res.emp=0;
	return res;
}

void R()
{
	int n,q;
	string s;
	cin>>n>>s>>q;
	vector<Info> a(n);
	for (int i=0;i<n;i++)
	{
		bool t=s[i]=='0';
		a[i]={t,t,t,1,0};
	}
	SGT<Info> sgt(a);

	for (int i=0;i<q;i++)
	{
		int l,r;
		cin>>l>>r;
		i64 len=r-l+1;
		cout<<len*(len+1)/2-sgt.rangeQuery(l-1,r).x<<'\n';
	}
	return;
}