QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#111929#5440. P-P-PalindromewhyWA 1ms1560kbC++173.1kb2023-06-09 10:26:232023-06-09 10:26:26

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 10:26:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:1560kb
  • [2023-06-09 10:26:23]
  • 提交

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]=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;
	}
	void 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];
        // while(t1>1)
        // {
        //     mp[pre.len[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",(((pre.len[x1]/pre.len[x1]-pre.len[t1])&1)?0:-2)+pre.len[x1]/(pre.len[x1]-pre.len[t1])/2*4);
        if(pre.len[t1]==suf.len[t2]&&t1>1&&t2>1)
            ans+=((pre.len[x1]/(pre.len[x1]-pre.len[t1])&1)?0:-2)+pre.len[x1]/(pre.len[x1]-pre.len[t1])/2*4;
        ans++;
    }
    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--)
            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: 1ms
memory: 1560kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 1ms
memory: 1536kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 1ms
memory: 1560kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 1552kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1342

result:

wrong answer 1st numbers differ - expected: '1282', found: '1342'