QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114243#6635. Strange KeyboardjeffqiWA 770ms144832kbC++232.0kb2023-06-21 17:34:492023-06-21 17:34:52

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-21 17:34:52]
  • 评测
  • 测评结果:WA
  • 用时:770ms
  • 内存:144832kb
  • [2023-06-21 17:34:49]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
using namespace std;
namespace qiqi {
	const int inf = 1e9;
	struct Trie {
		struct Node {
			vi ch; int k;
			Node() {
				ch.assign(26,-1);
				k = inf;
			}
		};
		vector<Node> a;
		Trie() {
			a.eb();
		}
		int ins(int x,int c,int k) {
			if (a[x].ch[c] == -1) {
				a[x].ch[c] = sz(a);
				a.eb();
			}
			x = a[x].ch[c];
			a[x].k = min(a[x].k,k);
			return x;
		}
	};
	void main() {
		int n,m;
		cin >> n >> m;
		vi c(m,inf); c[0] = 0;
		vector<string> s(n);
		for (int i = 0; i < n; i++) {
			cin >> s[i]; int x = sz(s[i]);
			c[x%m] = min(c[x%m],x/m+1);
		}
		vector<pii> vec;
		for (int i = 0; i < m; i++) {
			if (c[i] != inf) {
				vec.eb(i,c[i]);
			}
		}
		for (auto [d,k]:vec) {
			int g = __gcd(d,m);
			for (int i = 0; i < g; i++) {
				for (int j = 0,x = i,y = (i+d)%m; j < 2*m/g; j++,x = y,y = (y+d)%m) {
					c[y] = min(c[y],c[x]+k+(y < x));
				}
			}
		}
		Trie trie;
		for (int i = 0; i < n; i++) {
			int x = sz(s[i]),p = 0;
			for (int j = 0; j < x; j++) {
				int y = c[(m-(x-j-1)%m)%m]+(x-j-1+m-1)/m+1;
				if (y != inf) {
					p = trie.ins(p,s[i][j]-'a',y);
				}
			}
		}
		string t; cin >> t;
		n = sz(t);
		vi f(n+1,inf); f[0] = 0;
		for (int i = 0; i < n; i++) {
			if (f[i] != inf) {
				int p = 0;
				for (int j = i; j < n; j++) {
					p = trie.a[p].ch[t[j]-'a'];
					if (p == -1) {
						break;
					}
					f[j+1] = min(f[j+1],f[i]+trie.a[p].k);
				}
			}
		}
		if (f[n] == inf) {
			cout << "-1\n";
			return;
		}
		cout << f[n] << '\n';
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T; cin >> T;
	while (T--) qiqi::main();
	return 0;
}

详细

Test #1:

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

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: 87ms
memory: 4692kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 252ms
memory: 3672kb

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: 770ms
memory: 3512kb

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: 67ms
memory: 50976kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

score: 0
Accepted
time: 90ms
memory: 38192kb

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: 149ms
memory: 7744kb

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: -100
Wrong Answer
time: 45ms
memory: 144832kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

-1

result:

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