QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111915#5440. P-P-PalindromewhyTL 3ms5276kbC++172.8kb2023-06-09 09:59:312023-06-09 09:59:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-09 09:59:35]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:5276kb
  • [2023-06-09 09:59:31]
  • 提交

answer

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef double db;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
const int N=1e6+86;

struct PAM
{
	int siz,tot,lst;
	int ch[N][26],len[N],fail[N],num[N];
	char s[N];
    struct edge{int to,nxt;}e[N];
    int head[N],_tot;
    void add(int u,int v){e[++_tot]={v,head[u]},head[u]=_tot;}
	
	int node(int l)
	{
		len[++siz]=l;
		memset(ch[siz],0,sizeof(ch[siz]));
		fail[siz]=num[siz]=0;
		return siz;
	}
	void clear()
	{
		siz=-1;
		lst=_tot=0;
		s[tot=0]='$';
		node(0);
		node(-1);
		fail[0]=1;
	}
	int getfail(int x)
	{
		while(s[tot-len[x]-1]!=s[tot]) x=fail[x];
		return x;
	}
	int insert(char c)
	{
		s[++tot]=c;
		int now=getfail(lst);
		if(!ch[now][c-'a'])
		{
			int x=node(len[now]+2);
			fail[x]=ch[getfail(fail[now])][c-'a'];
			ch[now][c-'a']=x;
		}
		lst=ch[now][c-'a'];
        num[lst]++;
		return num[ch[now][c-'a']];
	}
    void dfs(int u)
    {
        for(int i=head[u];i;i=e[i].nxt)
            dfs(e[i].to);
        num[fail[u]]+=num[u];
    }
    void calc()
    {
        for(int i=0;i<=siz;i++)
            if(i!=1) add(fail[i],i);
        dfs(1);
    }
}pre,suf;
ll ans;
int n;
char s[N];
void dfs(int x1,int x2)
{
    if(x1>1&&x2>1)
    {
        map<int,int> mp;
        int t1=pre.fail[x1],t2=suf.fail[x2],cnt=0;
        while(t1>1)
        {
            mp[pre.len[t1]]+=pre.num[t1];
            t1=pre.fail[t1];
        }
        while(t2>1)
        {
            if(mp.count(pre.len[x1]-suf.len[t2])) cnt+=(pre.len[x1]-suf.len[t2]<=suf.len[t2])?(pre.len[x1]-suf.len[t2]<suf.len[t2])?4:2:0;
            t2=suf.fail[t2];
        }//printf("%d\n",cnt);
        ans+=cnt+1;
    }
    for(int i=0;i<26;i++)
        if(pre.ch[x1][i]) dfs(pre.ch[x1][i],suf.ch[x2][i]);//printf("%d %d %d %c\n",x1,pre.ch[x1][i],pre.num[pre.ch[x1][i]],i+'a'),
}

template<typename T>
inline void read(T &x)
{
	T k=1;char ch=getchar();x=0;
	while(ch<'0'||ch>'9'){if(ch=='-') k=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x*=k;
}

int main()
{
    read(n);
    pre.clear();
    suf.clear();
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        pre.lst=suf.lst=0;
        pre.tot=suf.tot=0;
        int len=strlen(s+1);
        for(int j=1;j<=len;j++)
            suf.insert(s[j]);
        for(int j=len;j>=1;j--)
            "%d\n",pre.insert(s[j]);
    }
    pre.calc();
    suf.calc();
    dfs(0,0);
    dfs(1,1);
    printf("%lld\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5276kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 2ms
memory: 5168kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 3ms
memory: 5244kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 2ms
memory: 5168kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: -100
Time Limit Exceeded

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:


result: