QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#601548#8244. Digit TranslationandaheWA 1ms5896kbC++171.7kb2024-09-30 06:28:272024-09-30 06:28:28

Judging History

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

  • [2024-09-30 06:28:28]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5896kb
  • [2024-09-30 06:28:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout<<#x<<" "<<x<<endl
const int N(1000005);
const int mod(9302023);
const int SIGMA = 26;
const int M(1000);
struct Automatic
{
	int ch[M][27], cnt, f[M], val[M];
	queue<int>q;
	void insert(string s)
	{
		int Now = 0;
		for(int i = 0; i < s.size(); ++i)
		{
			if(!ch[Now][s[i]-'a']) ch[Now][s[i]-'a'] = ++cnt;
			Now = ch[Now][s[i]-'a'];
		}
		val[Now] = s.size();
	}
	void getfail()
	{
		for(int i = 0; i < SIGMA; ++i) if(ch[0][i]) q.push(ch[0][i]);
		while(!q.empty())
		{
			int x = q.front(); q.pop();
			for(int i = 0; i < SIGMA; ++i)
				if(ch[x][i]) f[ch[x][i]] = ch[f[x]][i], q.push(ch[x][i]);
				else ch[x][i] = ch[f[x]][i];
		}
	}
}AC;
void Insert()
{
	AC.insert("one"); AC.insert("two"); AC.insert("zero");
	AC.insert("three"); AC.insert("four"); AC.insert("five");
	AC.insert("six"); AC.insert("seven"); AC.insert("eight"); AC.insert("nine");
}
char s[N];
ll f[N], g[N];
void Modify(int ff, int gg, int &a, int &b)
{
	if(ff > a) a = ff, b = gg;
	else if(ff == a) b = (b+gg)%mod;
}
void DP()
{
	int len = strlen(s+1), Now = 0;
	for(int i = 1; i <= len; ++i)
	{
		Now = AC.ch[Now][s[i]-'a'];
		int k = AC.val[Now];
		if(!k) { f[i] = f[i-1]; g[i] = g[i-1]; }
		else
		{
			int Mx = 0, Mxg = 0;
			Modify(f[i-1], g[i-1], Mx, Mxg);
			Modify(f[i-k]+k-1, g[i-k]==0?1:g[i-k], Mx, Mxg);
			f[i] = Mx, g[i] = Mxg;
			if(!g[i]) g[i]++;
		}
	}
	cout<<len-f[len]<<endl;
	cout<<g[len]<<endl;
}
int main()
{
	//freopen("1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s+1;
	Insert();
	AC.getfail();
	DP();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3888kb

input:

icecreamcone

output:

10
1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

onetwo

output:

2
1

result:

ok 2 lines

Test #3:

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

input:

twone

output:

3
2

result:

ok 2 lines

Test #4:

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

input:

a

output:

1
0

result:

wrong answer 2nd lines differ - expected: '1', found: '0'