列表

详情

NC17442. E、Charmander

描述

Charmander has a magical string s whose length is n.

At each second, every character in string s expands simultaneously, where character i will become the string Si. That means if the string contains 3 characters c1, c2 and c3, in next second the string will become .

But at any moment, each character that appears in string s can only be one of the m characters numbered from 1 to m.

Given a target string t, Charmander wants to know in which second it first appears as a substring of string s, or if it never appears?

输入描述

The input starts with one line containing exactly one integer T, which is the number of test cases.

For each test case, the first line contains three integers n, m and k, indicating the length of string s in second 0, the size of character set and the length of string t.

Then followed by one line, consisting of n integers, indicating the string s in second 0.

Then followed by m lines, each consists of ki, Si[1], , Si[ki], representing the string Si.

Then followed by one line, consisting of k integers, indicating the string t.

- 1 ≤ T ≤ 10.
- 1 ≤ n,m,k ≤ 1000.
- .
- 1 ≤ s[i], Si[j], t[i] ≤ m.
- ki ≥ 2.

输出描述

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and string t first appears in second y.

If string t never appears, y is supposed to be -1.

示例1

输入: 

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

输出: 

Case #1: 1
Case #2: 2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 2499ms, 内存消耗: 23192K, 提交时间: 2018-08-04 20:40:13 

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int M = 1005;

int w , n , m;
vector<int> trans[N];
int s[M] , f[M] , t[M];
int nxt[12][N][M];

int par[N][N] , solo[N];

void work() {
    scanf("%d%d%d" , &w , &n , &m);
    for (int i = 0 ; i < w ; ++ i) {
        scanf("%d" , &t[i]);
        -- t[i];
    }
    for (int i = 0 ; i < n ; ++ i) {
        int k , x;
        scanf("%d" , &k);
        trans[i].clear();
        for (int j = 0 ; j < k ; ++ j) {
            scanf("%d" , &x);
            trans[i].push_back(-- x);
        }
    }
    for (int i = 0 ; i < m ; ++ i) {
        scanf("%d" , &s[i]);
        -- s[i];
    }
    for (int i = 1 ; i < m ; ++ i) {
        int j = f[i];
        while (j && s[i] != s[j]) {
            j = f[j];
        }
        f[i + 1] = (s[i] == s[j]) ? j + 1 : 0;
    }
    for (int i = 0 ; i < n ; ++ i) {
        nxt[1][i][m] = m;
        for (int j = 0 ; j < m ; ++ j) {
            int k = j;
            while (k && s[k] != i) {
                k = f[k];
            }
            if (s[k] == i) ++ k;
            nxt[1][i][j] = k;
        }
    }
    for (int k = 2 ; k <= 11 ; ++ k) {
        for (int i = 0 ; i < n ; ++ i) {
            nxt[k][i][m] = m;
            for (int j = 0 ; j < m ; ++ j) {
                int x = j;
                for (auto &y : trans[i]) {
                    x = nxt[k - 1][y][x];
                }
                nxt[k][i][j] = x;
            }
        }
    }
    int res = 1 << 30;
    for (int k = 1 ; k <= 11 ; ++ k) {
        int x = 0;
        for (int i = 0 ; i < w ; ++ i) {
            x = nxt[k][t[i]][x];
        }
        if (x == m) {
            res = min(res , k);
        }
    }

    memset(par , -1 , sizeof(par));
    memset(solo , -1 , sizeof(solo));
    queue<int> Q;
    for (int i = 0 ; i < w ; ++ i) {
        int x = t[i];
        if (!~solo[x]) {
            Q.push(~x) , solo[x] = 1;
        }
        if (i + 1 < w) {
            int y = t[i + 1];
            if (!~par[x][y]) {
                Q.push(x);
                Q.push(y);
                par[x][y] = 1;
            }
        }
    }
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        if (x < 0) {
            x = ~x; int z = -1;
            for (auto &y : trans[x]) {
                if (!~solo[y]) {
                    solo[y] = solo[x] + 1;
                    Q.push(~y);
                }
                if (~z) {
                    if (!~par[z][y]) {
                        par[z][y] = solo[x] + 1;
                        Q.push(z);
                        Q.push(y);
                    }
                }
                z = y;
            }
        } else {
            int y = Q.front(); Q.pop();
            int nx = trans[x].back();
            int ny = trans[y][0];
            if (!~par[nx][ny]) {
                par[nx][ny] = par[x][y] + 1;
                Q.push(nx);
                Q.push(ny);
            }
        }
    }
    for (int i = 0 ; i < n ; ++ i) {
        for (int j = 0 ; j < n ; ++ j) {
            if (!~par[i][j]) continue;
            for (int k = 1 ; k <= 11 ; ++ k) {
                int x = nxt[k][i][0];
                x = nxt[k][j][x];
                if (x == m) {
                    res = min(res , par[i][j] + k - 1);
                }
            }
        }
    }

    if (res == 1 << 30)
        puts("-1");
    else {
        printf("%d\n" , res - 1);
    }
}

int main() {
    int T;
    scanf("%d" , &T);
    while (T --) {
        static int ca = 0;
        printf("Case #%d: " , ++ ca);
        work();
    }
}

C++(g++ 7.5.0) 解法, 执行用时: 294ms, 内存消耗: 33908K, 提交时间: 2022-11-29 14:13:43 

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define rep(i,start,end) for(int i=start;i<end;i++)
#define pii pair<int,int>
int snext[11][1111][1111];
int s[1111], t[1111], s2[1111][1111], ssize[1111];
int per[1111];
int pos[1111][1111];
queue<pii> q;
void addtoq(int k1,int k2,int x1,int x2)
{
    if (!pos[x1][x2])
        pos[x1][x2] = pos[k1][k2] + 1,
        q.emplace(x1, x2);
}
int main(void)
{
    int t2, k2 = 1;
    scanf("%d", &t2);
    while (t2--)
    {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        rep(i, 0, n)
            scanf("%d", &s[i]);
        s[n] = 0;
        rep(i, 1, m + 1)
        {
            scanf("%d", &ssize[i]);
            rep(j, 0, ssize[i])
                scanf("%d", &s2[i][j]);
            s2[i][ssize[i]] = 0;
        }
        rep(i, 0, k)
            scanf("%d", &t[i]);
        per[0] = 0, per[1] = 0;
        rep(i, 1, k)
        {
            int j = per[i];
            while (j && t[i] != t[j])
                j = per[j];
            per[i + 1] = t[i] == t[j] ? j + 1 : 0;
        }
        memset(snext[0], 0, sizeof(snext[0]));
        rep(j, 1, m + 1)
        {
            snext[0][j][k] = k;
            rep(i, 0, k)
            {
                int x = i;
                if (t[i] == j)
                    x++;
                else {
                    x = per[x];
                    x = snext[0][j][x];
                }
                snext[0][j][i] = x;
            }
        }
        int res = 1e9 + 7;
        int now = 0;
        rep(i, 0, n)
        {
            now = snext[0][s[i]][now];
            if (now == k)
                res = 0;
        }
        rep(i, 1, 11)
        {
            rep(j, 1, m + 1)
            {
                snext[i][j][k] = k;
                rep(x, 0, k)
                {
                    int a = x;
                    rep(s, 0, ssize[j])
                        a = snext[i - 1][s2[j][s]][a];
                    snext[i][j][x] = a;
                }
            }
        }
        memset(pos, 0, sizeof(pos));
        rep(j, 0, n)
            if (!pos[s[j]][s[j + 1]])
                pos[s[j]][s[j + 1]] = 1, q.emplace(s[j], s[j + 1]);
        while (!q.empty())
        {
            pii x = q.front();
            q.pop();
            int k1 = x.first, k2 = x.second;
            rep(i, 0, ssize[k1] - 1)
                addtoq(k1, k2, s2[k1][i], s2[k1][i + 1]);
            addtoq(k1, k2, s2[k1][ssize[k1] - 1], s2[k2][0]);
            rep(i, 0, ssize[k2])
                addtoq(k1,k2,s2[k2][i], s2[k2][i + 1]);
        }
        rep(i, 1, m + 1)
            rep(k2, 0, m + 1)
        {
            if (!pos[i][k2])
                continue;
            rep(x, 0, 11)
            {
                int x2 = snext[x][i][0];
                if (k2)
                    x2 = snext[x][k2][x2];
                if (x2 == k)
                    res = min(res, pos[i][k2] + x - 1);
            }
        }
        int s1, s2;
        printf("Case #%d: ", k2++);
        if (res == 1e9 + 7)
            printf("-1\n");
        else printf("%d\n", res);
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 305ms, 内存消耗: 33880K, 提交时间: 2018-08-25 23:10:27 

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define rep(i,start,end) for(int i=start;i<end;i++)
#define pii pair<int,int>
int snext[11][1111][1111];
int s[1111], t[1111], s2[1111][1111], ssize[1111];
int per[1111];
int pos[1111][1111];
queue<pii> q;
void addtoq(int k1,int k2,int x1,int x2)
{
	if (!pos[x1][x2])
		pos[x1][x2] = pos[k1][k2] + 1,
		q.emplace(x1, x2);
}
int main(void)
{
	int t2, k2 = 1;
	scanf("%d", &t2);
	while (t2--)
	{
		int n, m, k;
		scanf("%d%d%d", &n, &m, &k);
		rep(i, 0, n)
			scanf("%d", &s[i]);
		s[n] = 0;
		rep(i, 1, m + 1)
		{
			scanf("%d", &ssize[i]);
			rep(j, 0, ssize[i])
				scanf("%d", &s2[i][j]);
			s2[i][ssize[i]] = 0;
		}
		rep(i, 0, k)
			scanf("%d", &t[i]);
		per[0] = 0, per[1] = 0;
		rep(i, 1, k)
		{
			int j = per[i];
			while (j && t[i] != t[j])
				j = per[j];
			per[i + 1] = t[i] == t[j] ? j + 1 : 0;
		}
		memset(snext[0], 0, sizeof(snext[0]));
		rep(j, 1, m + 1)
		{
			snext[0][j][k] = k;
			rep(i, 0, k)
			{
				int x = i;
				if (t[i] == j)
					x++;
				else {
					x = per[x];
					x = snext[0][j][x];
				}
				snext[0][j][i] = x;
			}
		}
		int res = 1e9 + 7;
		int now = 0;
		rep(i, 0, n)
		{
			now = snext[0][s[i]][now];
			if (now == k)
				res = 0;
		}
		rep(i, 1, 11)
		{
			rep(j, 1, m + 1)
			{
				snext[i][j][k] = k;
				rep(x, 0, k)
				{
					int a = x;
					rep(s, 0, ssize[j])
						a = snext[i - 1][s2[j][s]][a];
					snext[i][j][x] = a;
				}
			}
		}
		memset(pos, 0, sizeof(pos));
		rep(j, 0, n)
			if (!pos[s[j]][s[j + 1]])
				pos[s[j]][s[j + 1]] = 1, q.emplace(s[j], s[j + 1]);
		while (!q.empty())
		{
			pii x = q.front();
			q.pop();
			int k1 = x.first, k2 = x.second;
			rep(i, 0, ssize[k1] - 1)
				addtoq(k1, k2, s2[k1][i], s2[k1][i + 1]);
			addtoq(k1, k2, s2[k1][ssize[k1] - 1], s2[k2][0]);
			rep(i, 0, ssize[k2])
				addtoq(k1,k2,s2[k2][i], s2[k2][i + 1]);
		}
		rep(i, 1, m + 1)
			rep(k2, 0, m + 1)
		{
			if (!pos[i][k2])
				continue;
			rep(x, 0, 11)
			{
				int x2 = snext[x][i][0];
				if (k2)
					x2 = snext[x][k2][x2];
				if (x2 == k)
					res = min(res, pos[i][k2] + x - 1);
			}
		}
		int s1, s2;
		printf("Case #%d: ", k2++);
		if (res == 1e9 + 7)
			printf("-1\n");
		else printf("%d\n", res);
	}
}

上一题

© 2025 nowcoder.com