2025多校冲刺省选模拟赛3

\(T1\) A. 等差 \(100pts/100pts\)

• 考虑哈希，每 \(k\) 个作为一组与上一组统一计算。

  • 取 \(Base>\) 值域时用高精度来存储并判断的正确性显然。

• 观察到可行的最小的 \(k\) 单调不降，不妨直接枚举答案。

• 暴力实现时间复杂度为 \(O(n^{2})\) ，精细实现记录极长匹配结尾后时间复杂度为 \(O(n \log n)\) 。

  点击查看代码

  const ll mod=1000003579,base=998244353;
  ll a[2000010],pos[2000010];
  ll hsh[2000010],jc[2000010];
  ll ask_hash(ll l,ll r)
  {
  	return (hsh[r]-(__int128_t)hsh[l-1]*jc[r-l+1]%mod+mod)%mod;
  }
  int main()
  {
  #define Isaac
  #ifdef Isaac
  	freopen("arithmetic.in","r",stdin);
  	freopen("arithmetic.out","w",stdout);
  #endif
  	ll n,i,j,k,ans,flag;
  	ll last;
  	scanf("%lld",&n);
  	jc[0]=1;
  	for(i=1;i<=n;i++)
  	{
  		jc[i]=jc[i-1]*base%mod;
  		pos[i]=2*i;
  	}
  	for(i=1,k=1;i<=n;i++)
  	{
  		scanf("%lld",&a[i]);
  		hsh[i]=(hsh[i-1]*base%mod+a[i])%mod;
  		ans=0;
  		for(;2*k+1<=i;k++)
  		{
  			last=(ask_hash(k+1,2*k)-ask_hash(1,k)+mod)%mod;
  			flag=1;
  			for(j=pos[k];j+k<=i&&flag==1;j+=k)
  			{
  				flag&=((ask_hash(j+1,j+k)-ask_hash(j-k+1,j)+mod)%mod==last);
  				pos[k]=(((ask_hash(j+1,j+k)-ask_hash(j-k+1,j)+mod)%mod==last)?j:pos[k]);
  			}
  			if(j!=i&&flag==1)
  			{
  				flag&=((ask_hash(j+1,i)-ask_hash(j-k+1,i-k)+mod)%mod==(ask_hash(1+k,k+i-j)-ask_hash(1,i-j)+mod)%mod);
  			}
  			if(flag==1)
  			{
  				ans=1;
  				break;
  			}
  		}
  		printf("%lld",ans);
  	}
  	return 0;
  }
  

\(T2\) B. 叉积 \(0pts/0pts\)

• 等价于最大化 \(\sum\limits_{i=l}^{r}x'y_{i}-yx_{i}'\) 。

• 部分分

  • \(48pts\) ：暴力。
  点击查看代码

  pair<ll,ll>a[100010];
  int main()
  {
  #define Isaac
  #ifdef Isaac
  	freopen("cross.in","r",stdin);
  	freopen("cross.out","w",stdout);
  #endif
  	ll n,m,x,y,ans=0,minn,sum,i,j;
  	scanf("%lld%lld",&n,&m);
  	for(i=1;i<=n;i++)
  	{
  		scanf("%lld%lld",&a[i].first,&a[i].second);
  	}
  	for(j=1;j<=m;j++)
  	{
  		scanf("%lld%lld",&x,&y);
  		ans=sum=minn=0;
  		for(i=1;i<=n;i++)
  		{
  			sum+=x*a[i].second-y*a[i].first;
  			ans=max(ans,sum-minn);
  			minn=min(minn,sum);
  		}
  		printf("%lld\n",ans);
  	}
  	return 0;
  }
  

• 正解

  

\(T3\) C. 序列变换 \(29pts/9pts\)

• 部分分

  • \(29pts/9pts\) ：爆搜。
  点击查看代码

  const ll p=998244353;
  int a[50],b[50],ans=0;
  bitset<210>s;
  void dfs(int n)
  {
  	int flag=1;
  	for(int i=1;i<=n;i++)
  	{
  		flag&=(a[i]==b[i]);
  	}
  	if(flag==1)
  	{
  		ans=(ans+1)%p;
  		return;
  	}
  	for(int i=1;i<=n;i++)
  	{
  		for(int j=i+1;j<=n;j++)
  		{
  			if(a[i]+1<=b[i]&&a[j]+1<=b[j])
  			{
  				s[a[i]]=s[a[j]]=0;
  				if(s[a[i]+1]==0&&s[a[j+1]]==0)
  				{
  					a[i]++;
  					a[j]++;
  					s[a[i]]=s[a[j]]=1;
  					dfs(n);
  					s[a[i]]=s[a[j]]=0;
  					a[i]--;
  					a[j]--;
  				}
  				s[a[i]]=s[a[j]]=1;
  			}
  		}
  	}
  }
  int main()
  {
  #define Isaac
  #ifdef Isaac
  	freopen("transform.in","r",stdin);
  	freopen("transform.out","w",stdout);
  #endif
  	int n,i;
  	cin>>n;
  	for(i=1;i<=n;i++)
  	{
  		cin>>a[i];
  		s[a[i]]=1;
  	}
  	for(i=1;i<=n;i++)
  	{
  		cin>>b[i];
  	}
  	dfs(n);
  	cout<<ans<<endl;
  	return 0;
  }
  
  

• 正解

  

  

总结

• 因不会叉积基本概念，打完 \(T1,T3\) 后直接去学向量了。

后记

• 因是 \(IOI\) 赛制，学校 \(OJ\) 可以下载第一个非 \(AC\) 测试点。