QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123612#6635. Strange KeyboardwnmrmrAC ✓315ms288352kbC++202.6kb2023-07-13 00:07:402023-07-13 00:07:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-13 00:07:43]
  • 评测
  • 测评结果:AC
  • 用时:315ms
  • 内存:288352kb
  • [2023-07-13 00:07:40]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

#define int long long

using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 2e6 + 5;
const int MOD = 1e9+7; //998244353;
const ll INF = ll(4e18) + 5;

const int M = 2e6+100;

int tree[M][26];
int best[M];
int li = 1;

int custo[MAXN];


void add(string s){
	int at = 0;
	int foi = s.size();
	for(auto c : s){
		int id = c-'a';
		foi--;
		if(tree[at][id] == 0){
			tree[at][id] = li;
			best[li] = INF;
			assert(best[li] > 0);
			li++;
		}
		at = tree[at][id];
		best[at] = min(best[at],custo[foi]);
	}

}

void solve(){
	int n,k;
	cin >> n >> k;
	for(int i = 0; i < li; i++){
		for(int j = 0; j < 26; j++) tree[i][j] = 0;
		best[i] = INF;
	}
	li=1;
	vector<string> st(n);
	for(int i = 0; i < n; i++) cin >> st[i];
	vector<int> tam(n);
	int sum = 0;
	set<int> s;
	for(int i = 0; i < n; i++){
		tam[i] = st[i].size();
		sum += tam[i];
		s.insert(tam[i]);
	}
	sum += k;
	for(int i = 0; i <= sum; i++) custo[i] = INF;
	vector<vector<int>> g(sum+1);
	vector<int> dif(s.begin(),s.end());
	for(int i = k; i <= sum; i++){
		g[i-k].pb(i);
	}
	for(int i = 1; i < k; i++){
		for(auto e : dif){
			int go = i+e;
			g[go].pb(i);
		}
	}
	queue<int> q;
	q.push(0);
	custo[0] = 0;
	while(!q.empty()){
		int u = q.front(); q.pop();
		assert(u <= sum);
		assert(u == 0 || custo[u] > 0);
		for(auto v : g[u]) if(custo[v] == INF){
			custo[v] = custo[u]+1;
			q.push(v);
		}
	}
	for(int i = 0; i < n; i++) add(st[i]);
	string t;
	cin >> t;
	int m  = t.size();
	vector<int> dp(m+1,INF);
	dp[0] = 0;
	for(int i = 0; i < m; i++){
		if(dp[i] == INF) continue;
		int eu = 0;
		for(int j = i; j < m; j++){
			int id = t[j]-'a';
			if(tree[eu][id] == 0) break;
			eu = tree[eu][id];
			dp[j+1] = min(dp[j+1],dp[i]+best[eu]+1);
		}
	}
	cout << (dp[m] == INF ? -1 : dp[m]) << '\n';
}

signed main(){

	ios::sync_with_stdio(false); cin.tie(NULL);
	for(int i = 0; i < MAXN; i++) custo[i] = INF;
	int t = 1;
	cin >> t;

	while(t--){
		solve();
	}

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 22516kb

input:

2
2 3
defgh
abc
abcde
1 1
a
b

output:

3
-1

result:

ok 2 number(s): "3 -1"

Test #2:

score: 0
Accepted
time: 72ms
memory: 152148kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 160ms
memory: 47708kb

input:

10
446 4905
afigcjhcgagabbiccehjcjajigghgbjjadccicghggijjdfeciaccgheedjdhgfjdfdbgidbbdjaiehhceeehchhabhaideggjbjajgfgicfdggahhbjgdebccbgbiedhehaebdccdfdffaacjcfbgjeegbahhbgcdjigijajheidchbddicehhhjbeiaajgedhdcjiefdgdbjjfaegheeidieheecaicciaajbabiidcecefgiicccdidegeica
afigcjhcgagabbiccehjcjajigghgbj...

output:

3
2
2
11
6
5
1
1
1
1

result:

ok 10 numbers

Test #4:

score: 0
Accepted
time: 315ms
memory: 33432kb

input:

100
140 4879
baabaababbababbaabababaaababbbabbbbbbabbababbbabbbbabbbbbbaabbbbbbbbabaabbbaabaabbbaabbabaabaabbbabbbababbbaabbabaaaaabbaaabbbabb
baa
baabaababbababbaabababaaababbbabbbbbbabbab
baabaababbababbaabababaaabab
baabaababbababbaabababaaababbbabbb
baabaababbababbaabababaaababbbabbbbbbabbababbb...

output:

1
1
1
1
3
1
1
1
1
1
1
3
2
1
1
1
2
1
1
2
1
1
1
1
1
1
1
1
1
4
3
2
1
2
1
1
1
1
1
2
1
1
1
3
1
1
1
2
1
1
1
2
3
1
1
1
2
1
1
1
1
1
1
1
1
3
2
3
1
3
1
1
2
1
2
3
2
1
1
1
3
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
2
1
4
1

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 122ms
memory: 134916kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 99ms
memory: 100024kb

input:

10
7 4923
baaabbabbbabbbbbabaabaabababbabbaaaabbaaabbbbabbaaababaaaaabaaabbabbbabbaaaabbaabbbaabbaaababaaababbabaababbaababbabaaabaabbaaabaaaababbabbabaabaabaabaabbbbaabaabbbaababbabbabaaaabbbaabbbaaaabaaaaababbaabaaaaababbbbaaaabbbaababbaabbabaabaaaaababaababaabaaaaabababababbabbbabababaaabaababbaa...

output:

4287
228
3671
549
129
372
475
534
336
288

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 138ms
memory: 40704kb

input:

100
7 4807
abbababaababbaabbabbaabaababbaaababaabaaabbaaaabababbbaabbaaabababbaabaabbaaaaabbbbaabbbaaabbbbabaabbbaaaaabbbaabbaaaabbaaababbaaabbbbabaabbababababbbabaaabaaaabbbbabbabbbbbaabaaabaababbabaaabbaabbabbabaaababbbabbabbbaababaabaaaabaaabbbbabbaabaababbbabbbbaaaabbabbbaabbaabbbbb
aaaaababaaab...

output:

45
32
11
4
2475
132
50
330
20
6
99
25
126
6
4
14
74
108
208
11
5
67
166
2822
178
1307
548
92
386
493
279
2415
255
262
567
215
46
113
31
651
17
4
8
21
12
100
69
152
15
55
521
146
11
13
181
-1
442
1839
2
5
31
26
122
696
280
77
1
839
11
273
7
178
421
228
6
6
82
116
1
-1
293
519
5
160
15
126
13
31
619
4...

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 109ms
memory: 288352kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5023990000

result:

ok 1 number(s): "5023990000"

Test #9:

score: 0
Accepted
time: 95ms
memory: 131928kb

input:

1
100000 4817
acdcaaccca
cdbbbbabba
bcbccbcdbd
cdabaddaad
ddbdbabcac
dadadbbcba
aabcbbcabc
cdcadbbbda
dabacdbabd
dcbadbdabd
cdcbacbada
cadbbadbac
dbadbccdcd
babaddcdca
aaaddacccc
dabdcdadbb
abbbadbdaa
bcdbbacdaa
bcbcbddadb
bddaccbaba
baddadaaac
adbadbdaaa
cacbbbcdbc
abccdcacdb
abaacddbbc
acbbbcbcdc
...

output:

618356

result:

ok 1 number(s): "618356"

Test #10:

score: 0
Accepted
time: 73ms
memory: 96124kb

input:

10
3901 4952
srsofqyvrt
tazndzviuq
jcomfoxkiw
huzfqiecss
hhdtqpaohy
qcrokphbtf
xzkxssibix
hokmdpzydu
jreaeulsjt
vmxdsazajq
jawyofqbck
cwmzupygdm
rgsahqyxqt
kckgorfgvi
kcawvezmyb
mpcyhdifgn
xiwtmwttmp
mzknfqoifl
vbpvvdnqpy
anpdgjnbew
scekjovqpr
lzhfocjvld
oswjfhjdby
pmdbjddkpv
yjbnjcdtmc
gmpjgtpksa
r...

output:

904
208656
4560
30873
28272
5377
1326
93956
93720
282610

result:

ok 10 numbers