D
赛时并没有意识到枚举范围在三次根号n里,加上自己手写的二分sqrt挂了(丢人),一直没过去,后面把sqrt部分改好也就过了。
所以本题只需要枚举,然后,稍微分i是p还是q一下就行。
然后看了看jls和dls的提交sqrt的实现,偷了偷了。
// jls
LL Sqrt(LL n) {
LL v = sqrt(n);
while ((v + 1) * (v + 1) <= n) v++;
while (v * v > n) v--;
return v;
}
// dls
LL t = sqrt(n)+0.1;
F
字符串双哈希判一下就行。
赛时想到类似kmp的快速判断字符串相等,并没有实现。
然后,顺便就偷了dls双哈希的板子(自己稍微改了变量名什么的)
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<int,int> hashv;
const LL mod1=1000000007;
const LL mod2=1000000009;
hashv operator + (hashv a,hashv b) {
int c1=a.fi+b.fi,c2=a.se+b.se;
if (c1>=mod1) c1-=mod1;
if (c2>=mod2) c2-=mod2;
return mkp(c1,c2);
}
hashv operator - (hashv a,hashv b) {
int c1=a.fi-b.fi,c2=a.se-b.se;
if (c1<0) c1+=mod1;
if (c2<0) c2+=mod2;
return mkp(c1,c2);
}
hashv operator * (hashv a,hashv b) {
return mkp(1ll*a.fi*b.fi%mod1,1ll*a.se*b.se%mod2);
}
const int N = 2e6+10;
int n;
char s[N];
hashv pw[N], Hx[N], rHx[N], base=mkp(13331,23333);
int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout << fixed; // << setprecision(20); // double
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
scanf("%d", &n);
n *= 2;
scanf("%s", s+1);
pw[0]=mkp(1,1);
for (int i=1;i<=n;i++)
pw[i]=pw[i-1]*base, Hx[i] = Hx[i-1]*base+mkp(s[i],s[i]);
for(int i = n; i >= 1; i --)
rHx[i] = rHx[i+1]*base+mkp(s[i], s[i]);
for(int i = 0; i <= n/2; i ++) {
hashv hx1 = Hx[i]*pw[n/2-i]+(Hx[n]-Hx[n/2+i]*pw[n/2-i]);
hashv hx2 = rHx[i+1]-rHx[n/2+i+1]*pw[n/2];
if(hx1 == hx2) {
for(int j = n/2+i; j > i; j --)
printf("%c", s[j]);
puts("");
printf("%d\n", i);
return 0;
}
}
puts("-1");
return 0;
}
Comments | NOTHING
该文章已经关闭评论