QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#114640#6635. Strange KeyboardxaphoenixAC ✓948ms219156kbC++143.1kb2023-06-22 18:07:582023-06-22 18:07:59

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-22 18:07:59]
  • 评测
  • 测评结果:AC
  • 用时:948ms
  • 内存:219156kb
  • [2023-06-22 18:07:58]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define LC k<<1
#define RC k<<1|1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = (n) - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef pair<double, double> PDD;
typedef pair<ull, ull> PUU;
typedef pair<LL, LL> PLL;

const int N = 1100000;
const int M = 1100000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = 1e18;
const double eps = 1e-9;

mt19937_64 Rand((unsigned long long)new char);
#define rand Rand

int T, n, m, k, pp[N], len[N], cp[N];
string s[N], t;
LL f[N], dis[N];
vector<PIL> g[N];
vector<int> tmp;
int ch[M][26], pos, rt;
LL val[M];
int newnode() {
	pos++;
	memset(ch[pos], 0, sizeof(ch[pos]));
	val[pos] = INF;
	return pos;
}
LL dp[N];
priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL,int>>> q;
void dijkstra(int st) {
	rep(i, 0, k) dis[i] = INF, pp[i] = 0;
	dis[st] = 0;
	q.push(mp(0, st));
	while (!q.empty()) {
		int now = q.top().se; q.pop();
		if (pp[now]) continue;
		pp[now] = 1;
		for (auto p: g[now]) {
			int y = p.fi;
			LL w = p.se;
			if (dis[now] + w < dis[y]) dis[y] = dis[now] + w, q.push(mp(dis[y], y));
		}
	}
}
int main() {
	IO;
	cin >> T;
	while (T--) {
		cin >> n >> k;
		rep(i, 0, k) f[i] = INF, pp[i] = cp[i] = 0, g[i].clear();
		tmp.clear();
		repn(i, 1, n) {
			cin >> s[i];
			len[i] = s[i].size();
			f[len[i] % k] = min(f[len[i] % k], (LL)len[i]);
			if (!cp[len[i] % k]) cp[len[i] % k] = 1, tmp.pb(len[i] % k);
		}
		cin >> t;
		m = t.size();
		rep(i, 0, k) {
			for (auto j: tmp) {
				int w = f[j] / k + 1, tgt = (i + j) % k;
				if (i > tgt) w++;
				g[tgt].pb(mp(i, w));
			}
		}
		dijkstra(0);
		/*
		rep(i, 0, k) dis[i] = INF, pp[i] = 0;
		dis[0] = 0;
		while (1) {
			LL mn = INF;
			int pos = -1;
			rep(i, 0, k) if (!pp[i] && dis[i] < mn) mn = dis[i], pos = i;
			if (pos == -1) break;
			pp[pos] = 1;
			for (auto p: g[pos]) {
				int y = p.fi;
				LL w = p.se;
				dis[y] = min(dis[y], dis[pos] + w);
			}
		}
		*/
		pos = 0;
		rt = newnode();
		repn(i, 1, n) {
			int cur = rt;
			rep(j, 0, len[i]) {
				int p = s[i][j] - 'a';
				if (ch[cur][p]) cur = ch[cur][p];
				else cur = ch[cur][p] = newnode();
				int left = len[i] - j - 1;
				val[cur] = min(val[cur], dis[left % k] + left / k + 1);
			}
		}
		repn(i, 1, m) dp[i] = INF;
		dp[0] = 0;
		rep(i, 0, m) {
			int cur = rt;
			repn(j, i + 1, m) {
				int p = t[j - 1] - 'a';
				cur = ch[cur][p];
				if (cur == 0) break;
				dp[j] = min(dp[j], dp[i] + val[cur]);
			}
		}
		if (dp[m] == INF) cout << "-1\n";
		else cout << dp[m] << "\n";
	}	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 12ms
memory: 79212kb

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: 124ms
memory: 219156kb

input:

1
1413 4867
yumnkkghwtqnhpmmsbfwypcwudihegsvtdaykueuqozagpgdnhbwzoqrqswyctzonwmjdjmmpyzbyihhpyznmqltcuckqmcybbdafoexqztxhzlfjowznisnxtgoiqjztogldyegajmegalqgawrzotuntocmsagvkzdnwhmaewuxiuhvintpzwyrkgapnmegpveyuuorrfvrfakjyetfaoqtvwghlslsvmahrkvzkwpaviufknrpuapicqdnn
yumnkkghwtqnhpmmsbfwypcwudihegsvt...

output:

10

result:

ok 1 number(s): "10"

Test #3:

score: 0
Accepted
time: 317ms
memory: 115684kb

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: 948ms
memory: 99332kb

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: 53ms
memory: 107340kb

input:

1
7 4864
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205

result:

ok 1 number(s): "205"

Test #6:

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

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: 146ms
memory: 101368kb

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: 22ms
memory: 186632kb

input:

1
1 5000
abaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5023990000

result:

ok 1 number(s): "5023990000"

Test #9:

score: 0
Accepted
time: 28ms
memory: 106212kb

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: 26ms
memory: 108164kb

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