举报
我要举报 xiexinzhe 抄题解！
他不仅抄了 5 道紫题，还抄了 2 道黑题！！！应当棕名！！！你们可以看，比如他做的第一道紫题：优秀的拆分，和题解的几乎一样，只是改了变量名。
例如：他的代码（他是我团队的人，我能看他代码）
#include<bits/stdc++.h>
using namespace std;
inline int gi() {
register int data=0,w=1;
register char ch=0;
while (!isdigit(ch) && ch != '-')
ch = getchar();
if (ch== '-')
w = -1,ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int pigupigu_youdayouyuan=3e4+5;
char a[pigupigu_youdayouyuan];
int N,lg[pigupigu_youdayouyuan],f[pigupigu_youdayouyuan],g[pigupigu_youdayouyuan];
struct SuffixArray
{
int sa[pigupigu_youdayouyuan], rnk[pigupigu_youdayouyuan], lcp[pigupigu_youdayouyuan];
void buildSA()
{
#define cmp(i, j, k) (y[i] == y[j] && y[i + k] == y[j + k])
static int x[pigupigu_youdayouyuan], y[pigupigu_youdayouyuan], bln[pigupigu_youdayouyuan];
memset(sa, 0, sizeof(sa));
memset(rnk, 0, sizeof(rnk));
memset(lcp, 0, sizeof(lcp));
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
memset(bln, 0, sizeof(bln));
int M = 122;
for (int i = 1; i <= N; i++)
bln[x[i] = a[i]]++;
for (int i = 1; i <= M; i++)
bln[i] += bln[i - 1];
for (int i = N; i >= 1; i--)
sa[bln[x[i]]--] = i;
for (int k = 1; k <= N; k <<= 1)
{
int p = 0;
for (int i = 0; i <= M; i++) y[i] = 0;
for (int i = N - k + 1; i <= N; i++) y[++p] = i;
for (int i = 1; i <= N; i++) if (sa[i] > k) y[++p] = sa[i] - k;
for (int i = 0; i <= M; i++) bln[i] = 0;
for (int i = 1; i <= N; i++) bln[x[y[i]]]++;
for (int i = 1; i <= M; i++) bln[i] += bln[i - 1];
for (int i = N; i >= 1; i--) sa[bln[x[y[i]]]--] = y[i];
swap(x, y); x[sa[1]] = p = 1;
for (int i = 2; i <= N; i++) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
if (p >= N) break;
M = p;
}
for (int i = 1; i <= N; i++)
rnk[sa[i]] = i;
for (int i = 1, j = 0; i <= N; i++)
{
if (j)
j--;
while (a[i + j] == a[sa[rnk[i] - 1] + j])
++j;
lcp[rnk[i]] = j;
}
}
int st[16][pigupigu_youdayouyuan];
void buildST() {
memset(st, 63, sizeof(st));
for (int i = 1; i <= N; i++) st[0][i] = lcp[i];
for (int i = 1; i <= 15; i++)
for (int j = 1; j <= N; j++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r) {
int _l = l, _r = r;
l = min(rnk[_l], rnk[_r]) + 1, r = max(rnk[_l], rnk[_r]);
int t = lg[r - l + 1];
return min(st[t][l],st[t][r-(1<<t)+1]);
}
}A,B;
void Sol()
{
scanf("%s", a + 1);
N=strlen(a+1);
A.buildSA(),A.buildST();
reverse(&a[1], &a[N + 1]);
B.buildSA(), B.buildST();
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
for(int Len=1;Len<=N/2;Len++)
{
for(int i=Len,j=i+Len;j<=N;i+=Len,j+=Len)
{
int Lcp=min(A.query(i,j),Len),Lcs=min(B.query(N-i+2,N-j+2),Len-1);
int t=Lcp+Lcs-Len+1;
if(Lcp+Lcs>=Len)
{
g[i-Lcs]++;
g[i-Lcs+t]--;
f[j+Lcp-t]++;
f[j+Lcp]--;
}
}
}
for(int i=1;i<=N;i++)
{
f[i]+=f[i-1],g[i]+=g[i-1];
}
long long ans=0;
for(int i=1;i<N;i++)
{
ans+=1ll*f[i]*g[i+1];
}
printf("%lld\n",ans);
}
int main()
{
int i,T;
#ifndef ONLINE_JUDGE
#endif
for(i=2;i<=30000;i++)
{
lg[i]=lg[i>>1]+1;
}
scanf("%d",&T);
while (T--)
{
Sol();
}
return 0;
}
题解代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
inline int gi() {
register int data = 0, w = 1;
register char ch = 0;
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') w = -1, ch = getchar();
while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();
return w * data;
}
const int MAX_N = 3e4 + 5;
char a[MAX_N];
int N, lg[MAX_N], f[MAX_N], g[MAX_N];
struct SuffixArray {
int sa[MAX_N], rnk[MAX_N], lcp[MAX_N];
void buildSA() {
#define cmp(i, j, k) (y[i] == y[j] && y[i + k] == y[j + k])
static int x[MAX_N], y[MAX_N], bln[MAX_N];
memset(sa, 0, sizeof(sa));
memset(rnk, 0, sizeof(rnk));
memset(lcp, 0, sizeof(lcp));
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
memset(bln, 0, sizeof(bln));
int M = 122;
for (int i = 1; i <= N; i++) bln[x[i] = a[i]]++;
for (int i = 1; i <= M; i++) bln[i] += bln[i - 1];
for (int i = N; i >= 1; i--) sa[bln[x[i]]--] = i;
for (int k = 1; k <= N; k <<= 1) {
int p = 0;
for (int i = 0; i <= M; i++) y[i] = 0;
for (int i = N - k + 1; i <= N; i++) y[++p] = i;
for (int i = 1; i <= N; i++) if (sa[i] > k) y[++p] = sa[i] - k;
for (int i = 0; i <= M; i++) bln[i] = 0;
for (int i = 1; i <= N; i++) bln[x[y[i]]]++;
for (int i = 1; i <= M; i++) bln[i] += bln[i - 1];
for (int i = N; i >= 1; i--) sa[bln[x[y[i]]]--] = y[i];
swap(x, y); x[sa[1]] = p = 1;
for (int i = 2; i <= N; i++) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
if (p >= N) break;
M = p;
}
for (int i = 1; i <= N; i++) rnk[sa[i]] = i;
for (int i = 1, j = 0; i <= N; i++) {
if (j) j--;
while (a[i + j] == a[sa[rnk[i] - 1] + j]) ++j;
lcp[rnk[i]] = j;
}
}
int st[16][MAX_N];
void buildST() {
memset(st, 63, sizeof(st));
for (int i = 1; i <= N; i++) st[0][i] = lcp[i];
for (int i = 1; i <= 15; i++)
for (int j = 1; j <= N; j++)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r) {
int _l = l, _r = r;
l = min(rnk[_l], rnk[_r]) + 1, r = max(rnk[_l], rnk[_r]);
int t = lg[r - l + 1];
return min(st[t][l], st[t][r - (1 << t) + 1]);
}
} A, B;
void Sol() {
scanf("%s", a + 1); N = strlen(a + 1);
A.buildSA(), A.buildST();
reverse(&a[1], &a[N + 1]);
B.buildSA(), B.buildST();
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
for (int Len = 1; Len <= N / 2; Len++) {
for (int i = Len, j = i + Len; j <= N; i += Len, j += Len) {
int Lcp = min(A.query(i, j), Len), Lcs = min(B.query(N - i + 2, N - j + 2), Len - 1);
int t = Lcp + Lcs - Len + 1;
if (Lcp + Lcs >= Len) {
g[i - Lcs]++, g[i - Lcs + t]--;
f[j + Lcp - t]++, f[j + Lcp]--;
}
}
}
for (int i = 1; i <= N; i++) f[i] += f[i - 1], g[i] += g[i - 1];
long long ans = 0;
for (int i = 1; i < N; i++) ans += 1ll * f[i] * g[i + 1];
printf("%lld\n", ans);
}
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
for (int i = 2; i <= 30000; i++) lg[i] = lg[i >> 1] + 1;
int T; scanf("%d", &T);
while (T--) Sol();
return 0;
}
你看是不是差不多？
我要求他被棕名！！！
加载中...