QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#601548 | #8244. Digit Translation | andahe | WA | 1ms | 5896kb | C++17 | 1.7kb | 2024-09-30 06:28:27 | 2024-09-30 06:28:28 |
Judging History
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;
}
详细
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'