求助ABC284F
  • 板块学术版
  • 楼主Hell0_W0rld
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/1/9 16:48
  • 上次更新2023/10/24 05:01:02
查看原帖
求助ABC284F
555345
Hell0_W0rld楼主2023/1/9 16:48

RT,错了 07_killer 的几个测试点,求 HACK

代码可视化:

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define rep(i,l,r) for(register ll i=(l);i<=(r);++i)
#define Rep(i,l,r) for(register ll i=(r);i>=(l);--i)
#define repD(i,u,E) for(register ll i=hd[u];i;i=E[i].nxt)
#define all(x) x.begin(),x.end()
using namespace std;
void upd_s(ll&x,ll v){x=min(x,v);}
void upd_b(ll&x,ll v){x=max(x,v);}
const ll N=3e6+9;
ll n;
ull p[N]={1};//p[i]: BASE^i
ull h[N][2];//哈希
const ll BASE=1321;
ull pre(ll r,ll k){return h[r][k];}
ull suf(ll l,ll k){return h[n][k]-h[n-l][k]*p[l];}
int main(){
	string t;
	cin>>n>>t;
	string a=t.substr(0,n);
	string b=t.substr(n);
	reverse(a.begin(),a.end());
	for(ll i=1;i<=n;i++)p[i]=p[i-1]*BASE;
	for(ll i=1;i<=n;i++)h[i][0]=h[i-1][0]*BASE+a[i-1];
	for(ll i=1;i<=n;i++)h[i][1]=h[i-1][1]*BASE+b[i-1];//前缀哈希 0-a 1-b
	rep(x,0,n){
		ll y=n-x;
		if(suf(x,0)==pre(x,1) && pre(y,0)==suf(y,1)){
			cout<<t.substr(0,x)<<t.substr(n+x)<<endl<<x<<endl;
			return 0;
		}
	} 
	cout<<-1<<endl;
	return 0;
}

验证码ab99

2023/1/9 16:48
加载中...