当前位置:首页 > 图论 > 拓扑排序 > 正文
洛谷P7077函数调用(CSP2020)
1347+

题目大意:有n个操作,包括单点加、全部乘、组合操作,按照一定的顺序调用,最终的结果是怎样的?

题目描述

函数是各种编程语言中一项重要的概念,借助函数,我们总可以将复杂的任务分解成一个个相对简单的子任务,直到细化为十分简单的基础操作,从而使代码的组织更加严密、更加有条理。然而,过多的函数调用也会导致额外的开销,影响程序的运行效率。

某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类:

  1. 将数据中的指定元素加上一个值;
  2. 将数据中的每一个元素乘以一个相同值;
  3. 依次执行若干次函数调用,保证不会出现递归(即不会直接或间接地调用本身)。

在使用该数据库应用时,用户可一次性输入要调用的函数序列(一个函数可能被调用多次),在依次执行完序列中的函数后,系统中的数据被加以更新。某一天,小 A 在应用该数据库程序处理数据时遇到了困难:由于频繁而低效的函数调用,系统在执行操作时进入了无响应的状态,他只好强制结束了数据库程序。为了计算出正确数据,小 A 查阅了软件的文档,了解到每个函数的具体功能信息,现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。

输入格式

第一行一个正整数 ,表示数据的个数。
第二行 个整数,第 个整数表示下标为 的数据的初始值为
第三行一个正整数 ,表示数据库应用程序提供的函数个数。函数从 编号。
接下来 行中,第 )行的第一个整数为 ,表示 号函数的类型:

  1. ,接下来两个整数 分别表示要执行加法的元素的下标及其增加的值;
  2. ,接下来一个整数 表示所有元素所乘的值;
  3. ,接下来一个正整数 表示 号函数要调用的函数个数,
    随后 个整数 依次表示其所调用的函数的编号。

行一个正整数 ,表示输入的函数操作序列长度。
个整数 ,第 个整数表示第 个执行的函数的编号。

输出格式

一行 个用空格隔开的整数,按照下标 的顺序,分别输出在执行完输入的函数序列后,数据库中每一个元素的值。答案对 取模。

输入输出样例

输入 #1
3
1 2 3
3
1 1 1
2 2
3 2 1 2
2
2 3
输出 #1
6 8 12
输入 #2
10
1 2 3 4 5 6 7 8 9 10
8
3 2 2 3
3 2 4 5
3 2 5 8
2 2
3 2 6 7
1 2 5
1 7 6
2 3
3
1 2 3
输出 #2
36 282 108 144 180 216 504 288 324 360
输入 #3
见附件中的 call/call3.in
输出 #3
见附件中的 call/call3.ans

说明/提示

【样例 #1 解释】

号函数功能为将 的值加一。 号函数功能为所有元素乘 号函数将先调用 号函数,再调用 号函数。

最终的函数序列先执行 号函数,所有元素的值变为

再执行 号函数时,先调用 号函数,所有元素的值变为 。再调用 号函数,所有元素的值变为

【数据范围】

测试点编号 其他特殊限制
函数调用关系构成一棵树
不含第 类函数或不含第 类函数
函数调用关系构成一棵树
不含第 类函数或不含第 类函数
函数调用关系构成一棵树

对于所有数据:

解题思路

暴力计算,依次调用对应的函数操作,遇到加直接加,遇到乘全部成,遇到函数递归执行,25分。

不难发现,全部乘太慢,能不能留到最后乘?这样对加有什么影响?对于加来说,前面的乘操作是多乘的,最后要初回去,可以用逆元70分!

或者倒着来,从后往前,遇到乘号,先记下来需要累乘ji;遇到加号要加x,那么共加x*ji,因为该加数需要乘后面的数据,这样75分!

由于所有函数拆开了,调用的加、乘次数实在是太多了,所以需要合并,不能逐个操作,这时需要用标记下放。

1、预处理每个操作需要乘多少(f),总共需要乘多少,之后不需要再管乘法了!

2、从后往前遍历每个操作,那么该操作里面的加,不是加1次,而是加ji次(ji是后面需要乘的次数)

3、按照拓扑序进行标记下放:操作a调用操作b,a被调用c次,如果b是a的最后一个操作,那么b被调用c次;如果不是,那么b后面那些操作共乘x,b相当于被多调用c*x次,因为调用b后,后面调用了乘x!

注意:拓扑序可以用1到m,也可以用调用的具体函数,但是入度为零不能重复入队,不然标记下放多次会导致出错。

程序实现

倒序执行所有操作,暴力75分:

洛谷P7077函数调用(CSP2020):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!