打卡信奥刷题（1801）用C++信奥 P8893 「UOI-R1」智能推荐

P8893 「UOI-R1」智能推荐

题目背景

数据已加强。

题目描述

现在有 $N$ 道题。

天数的编号从 $0$ 开始，每一天你可以做若干道题，你只能做以前推荐过的或者当天推荐的题（每道题只可以做一次）。第一天，智能推荐会推荐 $p$ 道题。

推荐规则如下：

对于第 $i$ 道题，如果有可能被推荐的话，就会有一个题目集合 $s_i$。当且仅当你把 $s_i$ 中每一道题都做出来并且其中有一道题是当天做的，那么下一天就会推荐第 $i$ 题。

你想做完第 $K$ 道题，问至少第几天你才能满足愿望？

输入格式

第一行三个整数 $N,K,p$，含义如题目所述。

第二行 $p$ 个整数，表示第一天推荐的题的题号。

第三行一个整数 $R$，表示有 $R$ 条推荐规则。

接下来 $R$ 行，每行包含一条规则，每行格式如下：

一个整数 $v_i$，表示要推荐的题的题号。接着一个整数 $s_i$，表示要使得这道题被推荐，一共要做的题目数量。接下来 $s_i$ 个整数 $p_i$，表示要做的每道题。

输出格式

一个整数表示最少第几天才能满足愿望。

如无论如何，第 $K$ 题都无法完成，则输出 -1。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

1 1 1
1
0

输出 #2

0

输入输出样例 #3

输入 #3

7 7 2
1 2
2
3 2 1 2
6 2 1 2

输出 #3

-1

输入输出样例 #4

输入 #4

见文件附件的 rec4.in

输出 #4

见文件附件的 rec4.ans

说明/提示

【样例解释 #1】

第 $0$ 天推了第 $1,2$ 题，都做了。

第 $1$ 推了第 $3$ 题，做了。

第 $2$ 推了第 $4$ 题，做了。

第 $3$ 推了第 $5$ 题，也就是第 $K$ 题，做了。

第 $3$ 天即可做完第 $K$ 题目。

【样例解释 #2】

第 $0$ 天推了第 $1$ 题，也就是第 $K$ 题，做了。
第 $0$ 天就做完了。

【数据范围】

以下记 $\left|s_i\right|$ 表示推荐规则中第 $i$ 条规则中，如果 $v_i$ 被推荐，要做的所有题。

对于 $30\%$ 的数据，保证 $1\le N\le 100$。

对于 $50\%$ 的数据，保证没有环。

对于 $100\%$ 的数据，保证 $1\le K,s_i,p_i,v_i\le N\le 5\times 10^3$，$0\le R\le 5\times 10^3$。$|s_i|$ 互不相同，且对于每一个 $|s_i|$ 都有 $p_i$ 互不相同，$v_i$ 互不相同。

C++实现

#include
using namespace std;
const int N=5005;
int n,k,r,day,vis[N],t[N];
int w,nw,ok[N],nok[N];
vector int> relat[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>k>>nw;
	for(int i=1;inw;i++) cin>>nok[i];
	cin>>r;
	for(int i=1,x,y;ir;i++){
		cin>>x>>t[x];
		for(int j=1;jt[x];j++){
			cin>>y;
			relat[y].push_back(x);
		}
	}
	while(1){
		w=nw;nw=0;
		for(int i=1;iw;i++)
			ok[i]=nok[i];
		if(!w){
			cout"-1n";
			return 0;
		}
		for(int i=1;iw;i++){
			vis[ok[i]]=1;
			for(int j=0,l=relat[ok[i]].size();jl;j++){
				t[relat[ok[i]][j]]--;
				if(!t[relat[ok[i]][j]]){
					nok[++nw]=relat[ok[i]][j];
				}
			}
		}
		if(vis[k]) break;
		day++;
 	}
	coutday'n';
	return 0;
}

后续：

接下来我会不断用C++来实现信奥比赛中的算法题、C++考级编程题实现、白名单赛事考题实现，感兴趣的请关注，我后续将继续分享相关内容

文章来源于互联网:打卡信奥刷题（1801）用C++信奥 P8893 「UOI-R1」智能推荐

相关推荐: AIGC重复率检测的算法和原理是什么？

写论文的都来抄作业！50个顶级工具网站+使用指南，建议点赞+收藏-CSDN博客 一个网站，轻松降低论文重复率和AIGC率！-CSDN博客 各大AIGC检测系统报告格式与内容特点详解（含实测分析+推荐系统入口） 这个问题非常关键！随着AIGC（AI生成内容）越来…