ABC 386 C 求条
  • 板块灌水区
  • 楼主matrixPower
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/12/28 21:44
  • 上次更新2024/12/29 10:35:22
查看原帖
ABC 386 C 求条
1068500
matrixPower楼主2024/12/28 21:44

here

#include<bits/stdc++.h>
#define endl '\n'
#define lowbit(x) ((x)&-(x))
#define pii_small priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>
#define ll_small priority_queue<long long,vector<long long>,greater<long long>>
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 III;
const db eqs=1e-6;
const int inf=1e9;
void ll_cmax(ll &a,ll b){a=a>b?a:b;}
void ll_cmin(ll &a,ll b){a=a<b?a:b;}
void int_cmax(int &a,int b){a=a>b?a:b;}
void int_cmin(int &a,int b){a=a<b?a:b;}
bool db_eq(db a,db b){return fabs(a-b)<eqs;}
bool minuscule(char ch){return ch>='a' && ch<='z';}
bool number(char ch){return ch>='0' && ch<='9';}

const ll B=1e9+33,M=1e9+133,MAXN=500000+5;
int k;
string s1,s2;
ll a[MAXN],b[MAXN];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>k>>s1>>s2;
	int len1=s1.size(),len2=s2.size();
	for(int i=0;i<len1;i++)
	{
		a[i+1]=(a[i]+(1ll*s1[i]*B)%M)%M;
	}
	for(int i=0;i<len2;i++)
	{
		b[i+1]=(b[i]+(1ll*s2[i]*B)%M)%M;
	}
	if(abs(len1-len2)>=2) return cout<<"No\n",0;
	if(len1==len2)
	{
		bool flag=0;
		for(int i=0;i<len1;i++)
		{
			if(s1[i]!=s2[i])
			{
				if(flag) return cout<<"No\n",0;
				else flag=1;
			}
		} 
		return cout<<"Yes\n",0;
	}
	if(len1>len2)
	{
		for(int i=0;i<len1;i++)
		{
			ll sum11=(a[i]-a[0]+M)%M,sum12=(a[len1]-a[i+1]+M)%M;
			ll sum21=(b[i]-b[0]+M)%M,sum22=(b[len1-1]-b[i]+M)%M;
//			cout<<i<<' '<<sum11<<" "<<sum12<<" "<<sum21<<" "<<sum22<<endl;
			if(sum11==sum21 && sum12==sum22) return cout<<"Yes\n",0;
		}
		return cout<<"No\n",0;
	}
	if(len2>len1)
	{
		for(int i=0;i<len2;i++)
		{
			ll sum11=(a[i]-a[0]+M)%M,sum12=(a[len2-1]-a[i]+M)%M;
			ll sum21=(b[i]-b[0]+M)%M,sum22=(b[len2]-b[i+1]+M)%M;
			if(sum11==sum21 && sum12==sum22) return cout<<"Yes\n",0;
		}
		return cout<<"No\n",0;
	}
	return 0;
}

2024/12/28 21:44
加载中...