Prize

NC206699. Prize

描述

某彩票站年终为了答谢彩民，推出了一个重磅活动。

每个彩民把自己一年内购买过的号码随机组成一个长度为 N 的数字字符串然后进行兑奖，彩票站规定中奖号码的位数为 M。

为了让彩民能拿到更多的奖金，所以中奖号码的每一位并不是固定的，中奖号码的每一位最少有1种取值(0 - 9中的任意一个)，最多有10种取值(0 - 9共10个数字)。如果数字字符串中连续 M 个字符与中奖号码一致，那么就能兑换1元的奖金，但如果字符串中的某些字符已经被兑换，那么它们就不能再被用来兑换。

给你一个彩民的字符串和中奖号码，请你帮助彩民判断他是否能获得奖金，如果能的话输出最多能获得的奖金数，否则输出字符串"Failed to win the prize"。

输入描述

第一行输入两个正整数 N，M，为字符串的长度和中奖号码的位数 (1 ≤ N ≤ 2000000，1 ≤ M ≤ 800，M ≤ N)
第二行输入一个长度为 N 只包含数字的字符串
接下来 M 行，每行先输入一个正整数 Num (1 ≤ Num ≤ 10)，代表第 i (1 ≤ i ≤ M) 位中奖号码的取值种数；然后输入 Num 个整数(范围[0, 9])，代表第 i 位中奖号码的可能取值，数据不保证这 Num 个整数互不相同

输出描述

如果彩民能获得奖金，则输出彩民最多能得到的奖金数；否则输出字符串"Failed to win the prize"

示例1

输入:

10 2
1234784840
4 1 2 3 4
8 1 2 3 4 5 6 7 8

输出:

说明:

中奖号码共两位，第一位取值范围是[1, 4]，第二位取值范围是[1, 8]

如果不考虑某些字符是否被兑换，那么符合中奖号码的字符串有"12"，"23"，"34"，"47"，"48"共五种

使用最优策略，选择"12"，"47"，"48"共三种，来保证字符串中所有字符只被兑换一次，结果为3

示例2

输入:

9 1
123456789
1 0

输出:

Failed to win the prize

示例3

输入:

10 1
1111111111
1 1

输出:

原站题解

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

C++14(g++5.4) 解法, 执行用时: 290ms, 内存消耗: 4560K, 提交时间: 2020-06-15 12:39:42

#include<bits/stdc++.h>
using namespace std;
int num[808][10], N, M, cnt, a, ans;
string s;
int main()
{
	cin >> N >> M >> s;
	for(int i = 0; i < M; i++)
		for(cin >> cnt; cnt--; )
			cin >> a, num[i][a] = 1;
	for(int i = 0, j; i + M - 1 < s.size(); i++)
	{
		for(j = M-1; j >= 0 && num[j][s[i+j]-'0']; j--);
		if(j < 0)
			ans++, i += M-1;
	}
	if(ans)
		cout << ans;
	else
		cout << "Failed to win the prize";
}

C++11(clang++ 3.9) 解法, 执行用时: 63ms, 内存消耗: 4472K, 提交时间: 2020-06-19 18:42:54

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

bitset<800>t,a[10];
char R[2000005];
int main()
{
    int i,j,x,n,m,ans=0;
    scanf("%d%d%s",&n,&m,R);
    for(i=0;i<m;i++)
    {
    	scanf("%d",&j);
    	while(j--)scanf("%d",&x),a[x][i]=1;
	}
	for(i=0;i<n;i++,t<<=1)
	{
		t[0]=1,t&=a[R[i]-'0'];
		if(t[m-1])ans++,t.reset();
	}
	if(ans)printf("%d\n",ans);
	else printf("Failed to win the prize\n");
}

上一题

下一题

详情