CVBB ACM Team

A. LCM Problem

直接看 $2l$ 是否在范围内。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		if(l*2>r)printf("%d %d\n",-1,-1);
		else printf("%d %d\n",l,l*2);
	}
	return 0;
}

B. Array Walk

明显这回退的若干次应该是同一个位置，枚举 $1$ 到 $n$ 假定这是要退回的位置，计算答案取最大。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],pre[N];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,k,z,res=0;
		scanf("%d%d%d",&n,&k,&z);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]),pre[i]=pre[i-1]+a[i];
		for(int i=1;i<n;i++)
		{
			if(k-i<0)break;
			int maxz=min(z*2,k-i),p=maxz,q=i,sum=0;
			while(p--)sum+=a[q],q=2*i+1-q;
			sum+=pre[k-maxz+1];
			res=max(res,sum);
		}
		printf("%d\n",res);
	}
	return 0;
}

C. Good String

看同一个字符或 $abababab$ 形式的子序列最长多长，删去剩余字符。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
char s[N];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s);
		int n=strlen(s),res=n;
		for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
		{
			int ni=0,nj=0;
			for(int k=0;s[k];k++)
			{
				if(ni<=nj&&s[k]==i+'0')ni++;
				else if(ni>nj&&s[k]==j+'0')nj++;
			}
			res=min(res,n-nj*2);
			if(i==j)res=min(res,n-ni-nj);
		}
		printf("%d\n",res);
	}
	return 0;
}

D. Segment Intersections

分类大讨论。总体思想是在两区间有交叠之前是花费 $1$ 受益无的阶段；有交叠后花费 $1$ 受益 $1$ ，达到完全重合后拓展同一边花费 $2$ 受益 $1$ 。

赛时除零的情况没有特判，被学弟hack了。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		ll n,k,l1,r1,l2,r2;
		scanf("%lld%lld%lld%lld%lld%lld",&n,&k,&l1,&r1,&l2,&r2);
		if(l1>l2)swap(l1,l2),swap(r1,r2);
		if(r2<r1)
		{
			k-=(r2-l2)*n;
			if(k<=0){printf("0\n");continue;}
			ll t1=r1-r2+l2-l1;
			ll used=min(k/t1+(k%t1!=0),n);
			if(used==k/t1+(k%t1!=0))printf("%lld\n",k);
			else printf("%lld\n",(k-n*t1)*2+n*t1);
		}
		else if(l2<r1)
		{
			k-=(r1-l2)*n;
			if(k<=0){printf("0\n");continue;}
			ll t1=r2-r1+l2-l1;
			if(!t1){printf("%lld\n",k*2);continue;}
			ll used=min(k/t1+(k%t1!=0),n);
			if(used==k/t1+(k%t1!=0))printf("%lld\n",k);
			else printf("%lld\n",(k-n*t1)*2+n*t1);
		}
		else
		{
			ll t1=l2-r1,t2=r2-l1,res=(1LL<<60);
			for(int i=1;i<=n;i++)
			{
				if(k-(t2*(i-1))<t2)
				{
					ll tmp=(t1+t2)*(i-1)+t1+(k-(t2*(i-1)));
					res=min(res,tmp);
				}
				if(t2*i>k)break;
				ll tmp=(t1+t2)*i+(k-t2*i)*2;
				res=min(res,tmp);
			}
			printf("%lld\n",res);
		}
	}
	return 0;
}

E. Calendar Ambiguity

$m$ 个月，每月 $d$ 天， $w$ 天一周。问 $x$ 月的第 $y$ 天和 $y$ 月的第 $x$ 天是一周里的同一天的组数。

即 $(x-1)d+y\equiv (y-1)d+x(\mod w)$ ，可以化为 $(d-1)x\equiv (d-1)y(\mod w)$ 。相当于 $x\equiv y(\mod \frac{w}{gcd(w,d-1)})$ 。

点击以显示 ⇲

点击以隐藏 ⇱

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		ll m,d,w;
		scanf("%lld%lld%lld",&m,&d,&w);
		ll k=min(m,d),mod=w/__gcd(d-1,w);
		if(d==1)puts("0");
		else
		{
			ll tmp=k/mod;
			ll res=tmp*(tmp-1)/2*mod+tmp*(k%mod);
			printf("%lld\n",res);
		}
	}
	return 0;
}

CVBB ACM Team

用户工具

站点工具

目录

A. LCM Problem

B. Array Walk

C. Good String

D. Segment Intersections

E. Calendar Ambiguity

页面工具