QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404939 | #3010. Subsequences in Substrings | Lspeed# | AC ✓ | 30ms | 14152kb | C++14 | 1.8kb | 2024-05-05 01:35:44 | 2024-05-05 01:35:45 |
Judging History
answer
#include<bits/stdc++.h>
#define x first
#define y second
#define eb emplace_back
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define sz(x) (int)(x).size()
#define make_unique(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())
using namespace std;
typedef long long i64;
//typedef __int128 i128;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef tuple<int,int,int> iii;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
int readInt() { int a; scanf("%d",&a); return a; }
i64 readLong() { i64 a; scanf("%lld",&a); return a; }
char readChar() { char a; scanf(" %c",&a); return a; }
double readDouble() { double a; scanf(" %lf",&a); return a; }
void readString(char *s) { scanf(" %s",s); }
const int mod = 998244353;
int add(int a, int b) { return ((a+=b)>=mod) ? a-mod:a; }
int mul(int a, int b) { return a*1ll*b%mod; }
int pw(int a, int b) {
int ans = 1, res = a;
for(int i = 1; i <= b; i*=2, res=mul(res,res)) {
if(i&b) {
ans = mul(ans, res);
}
}
return ans;
}
const int N = 100005;
char S[N], T[N];
int dp[N][26];
int main() {
readString(S+1);
readString(T+1);
int n = strlen(S+1);
int m = strlen(T+1);
int inf = (1<<30);
FOR(i,0,25) dp[n+1][i] = inf;
ROF(i,n,1) {
FOR(j,0,25) dp[i][j] = dp[i+1][j];
dp[i][S[i]-'a'] = i;
}
i64 ans = 0;
FOR(i,1,n) {
int cur = i-1;
FOR(j,1,m) {
cur = dp[cur+1][T[j]-'a'];
if(cur == inf) break;
}
if(cur != inf) ans += (n-cur+1);
}
printf("%lld\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 13960kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
5000050000
result:
ok answer is '5000050000'
Test #2:
score: 0
Accepted
time: 30ms
memory: 14100kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
4990154851
result:
ok answer is '4990154851'
Test #3:
score: 0
Accepted
time: 4ms
memory: 13960kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok answer is '99999'
Test #4:
score: 0
Accepted
time: 0ms
memory: 14092kb
input:
zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok answer is '99999'
Test #5:
score: 0
Accepted
time: 4ms
memory: 13964kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
25000000
result:
ok answer is '25000000'
Test #6:
score: 0
Accepted
time: 4ms
memory: 14152kb
input:
abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd...
output:
4999600009
result:
ok answer is '4999600009'
Test #7:
score: 0
Accepted
time: 13ms
memory: 10876kb
input:
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...
output:
2141234561
result:
ok answer is '2141234561'
Test #8:
score: 0
Accepted
time: 28ms
memory: 14028kb
input:
wihvaaqgcpykasskatdribceiwzsmjjuuqjononjknibpawvqtqeumefxkhoafyndgpipsfjxjhbqbfyqsjudqbuimewxmleojthsptiasfdgjtebxiawijflvdxvzohzedotgapzauzimqcjsgrziissrndyglcfftnnlpaoyxkzejlobssdkcbxpipvyebemirndverdgdvvgkdcejuousanpxxkhdtwwmblqmwcyalthjmuynwmxaponazdazeazztkeoxdhhesxdqelnywvqdlcmstmfullktqtvmlsu...
output:
4742431461
result:
ok answer is '4742431461'
Test #9:
score: 0
Accepted
time: 28ms
memory: 13964kb
input:
amplpsqzijrsvjngzzeidkopdzrakreyesiklovfcymebhprmsbrghdljejpizhnzbtsnjfczwlqyytmzjejfxetvjgzzjtsqbpownodtmvakxtqwwklkwuukuqhnwjxakmqgwulsfxzyyhvzsngeclgqmmxonaizvajzgmehgzucqoydxjxuaoctjmarsubzhjkudquwlkefsyutcwhywbvyhbrpccsoswijledgxonogqiwewskgdaxuibtbhjblycupocgvxoyhoeulnzsbyvvwluswwxfrebjuylmeov...
output:
4744748626
result:
ok answer is '4744748626'
Test #10:
score: 0
Accepted
time: 28ms
memory: 14092kb
input:
byqhmrogmrkrkxlopxzyrphkqoflakhnkpjdvojgpwfxndlvuxhjjdsuwudjjpgldwbcuqgffvsgdcykrrqxilxuclgoecxabivddsgyesxorzdgnydiiuhfoestiuyckxovcmuporhstqntgkxfdqrqdhremdaqgmyiuhbcvtfaunwpgkhqapzpfnpqhxxllmptxoueguozeluzxksmzaqnhvjikgvwkjkztqrkpplizyoshavxpnfwbynwquhzushxwckftjvveazomjbyibhynxphhicasishegoxitjo...
output:
4741244687
result:
ok answer is '4741244687'
Test #11:
score: 0
Accepted
time: 4ms
memory: 14024kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
3887366754
result:
ok answer is '3887366754'
Test #12:
score: 0
Accepted
time: 3ms
memory: 14052kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
aaacccabababacccccbbccaaaaabcacabaaccabccabcacbbccabbbacccabaaaacabbcbaccbabbccaccbcaabcacbaccabcaabcccaaabcabcabccbabcccabbaaccbaccacbcabacccbabacacbabaccaaababababaacbacbaacabbcbcbccccaaaacabcabbbcb caabc
output:
17714
result:
ok answer is '17714'
Test #14:
score: 0
Accepted
time: 1ms
memory: 8016kb
input:
acbdccaaacdbdbccccdddaddbdcbbdbbbadaacbbaddcdbcacaadcddcbdabdbdacadaadbbccaaacbdccabbbaabcbdcbabcdcadaacbdbbddbcccbdbcabacaadddbcaadbcacbdbccccacdddaaacccdddacbbabccbbcacbbbabdcbaddcbddadbbdcdcbcdcabdbdbdacdbabacdbdbcdcdbdcadbbcbbaacddccccdddbbcabcdddccbbdcbcdbdbdcddbdcbcbbbbdccccbbdabdcbbbdabcbbcbc...
output:
1923795
result:
ok answer is '1923795'
Test #15:
score: 0
Accepted
time: 4ms
memory: 4736kb
input:
dcdcaabcbbacccbaacacdeacaaadcdecaeeceecabeecadbdabbcabbadcaaedbcdeabddccdbbcaadabecdcabdebaeacdbccaebadaacdbdedccdcccbcbbeedbaeeabdecccabcbbaaacbcaeeadedeebbdeeebeacdcaddeabddaeedbbdaeeddeaedaeaaeacdceabceaeaceeecacdecdcadceceacdacccdeacdceededaeaadcdcdebbeaacaccccbbcbebddadaaecbabdaedcaabdacccbbdae...
output:
45098892
result:
ok answer is '45098892'
Test #16:
score: 0
Accepted
time: 8ms
memory: 7268kb
input:
haggcbhhacdahgcacdhcgehgcfcecffgecaaeggadfgbgdeedffafhecccgegbagcbahebhaaaaaahbgccffagbggdbcedgbhfaacefcdheabeefghdfdfabcbhhbaeefdbgaaahcfdhfeacgfbehbdhfdehaagfgfgehcdbadecbchgbadaadeaaabgafccaceadhdadhhhadfbddhddfceebbfgcgehdchhbgcfhedafgaebhgbfgdhcdbdbeebcahgfdfefhbcbhdddaadacbhgeahfhcddecfedaeebb...
output:
292904504
result:
ok answer is '292904504'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
aabb ab
output:
4
result:
ok answer is '4'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
aabb ba
output:
0
result:
ok answer is '0'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
abcdabcd ac
output:
14
result:
ok answer is '14'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
abcdefghijklmnopqrstuvwxyz z
output:
26
result:
ok answer is '26'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
abcdefghijklmnopqrstuvwxyz za
output:
0
result:
ok answer is '0'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
a a
output:
1
result:
ok answer is '1'
Test #23:
score: 0
Accepted
time: 1ms
memory: 5840kb
input:
abcdefg abcdefg
output:
1
result:
ok answer is '1'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
pp p
output:
3
result:
ok answer is '3'