2009、安徽省选定的第一天.docVIP

1．行星序列（seq） “神州“载人飞船的发射成功让小可可非常激动，他立志长大后要成为一名宇航员假期一始，他就报名参加了“小小宇航员夏令营”，在这里小可可不仅学到了丰富的宇航知识，还参与解决了一些模拟飞行中发现的问题，今天指导老师交给他一个任务，在这次模拟飞行的路线上有N个行星，暂且称它们为一个行星序列，并将他们从1至n标号，在宇宙未知力量的作用下这N个行星的质量是不断变化的，所以他们对飞船产生的引力也会不断变化，小可可的任务就是在飞行途中计算这个行星序列中某段行星的质量和，以便能及时修正飞船的飞行线路，最终到达目的地，行星序列质量变化有两种形式： 1，行星序列中某一段行星的质量全部乘以一个值 2，行星序列中某一段行星的质量全部加上一个值 由于行星的质量和很大，所以求出某段行星的质量和后只要输出这个值模P的结果即可，小可可被这个任务难住了，聪明的你能够帮他完成这个任务吗？ 输入：第一行两个整数N和P（1＜＝p＜＝1000000000）； 第二行含有N个非负整数，从左到右依次为a1，a2，…………，an（0＜＝ai＜。100000000，1＜＝i＜＝n），其中ai表示第i个行星的质量： 第三行有一个整数m，表示模拟行星质量变化以及求质量和等操作的总次数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：1 t g c 表示把所有满足t＜＝i＜＝g的行星质量ai改为ai＊c 操作2：2 t g c 表示把所有满足t＜＝i＜＝g的行星质量ai改为ai＋c 操作3：3 t g 表示输出所有满足t＜＝i＜＝g的ai的和模p的值 其中：1＜＝t＜＝g＜＝N，0＜＝c＜ 注：同一行相邻的两数之间用一个空格隔开，每行开头和末尾没有多余空格 输出：对每个操作3，按照它在输入中出现的顺序，依次一行输出一个整数表示所求行星质量和 样例： 输入： 7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7 输出： 2 35 8 样例说明：略 提示： 100％的数据中，M，N＜＝100000 40％的数据中，M，N＜＝10000 （Neilc-lc 提醒你，直接模拟可能是一个点都过不去，加上每次mod的优化，可以过3到4个点……正解是用线段树来做） Timelimit:3000ms 2．同类分布（self） 在模拟飞行的过程中，小可可发现在一个未知星球周围分布着许多同类的小行星带，而这些小行星带的分布非常有规律，经过研究发现实些小行星带到未知星球的距离为x（x为非负整数）与如下的函数有一定的关系： dsum（x）=0 （x=0） dsum（x）=dsum【x div 10】+x mod 10 （x0) 即x可以被dsum（x）整除。小可可非常希望能研究出距离这个未知星球的某一区域内小行星带的分布规律，具体来说，就是在与未知行星距离a和b的范围内分布了多少个小行星带，你能帮助他解决这个问题吗？ 输入：输入文件仅一行，包含两个正整数a和b（a=b). 输出：输出文件中仅包含一个整数，表示［a，b］内分布多少个小行星带。 样例1: 输入：1 10 输出：10 样例2： 输入：1234567912345679 1234567912346789 输出：37 提示：100％的数据中，a，b不超过100000000000000000（10的18次方）； 30％的数据中，b－a不超过1000000 Timelimit:5000ms 3．最小截断 宇宙旅行总是出现一些意想不到的问题，这次小可可所驾驶的宇宙飞船所停的空间站发生了故障，这个宇宙空间站非常大，它由N个子站组成，子站之间有M条单向通道，假设其中第i（1＜＝i＜＝M）条单向通道连接了xi，yi两个中转站，那么xi子站可以通过这个通道到达yi子站，如果截断这条通道，需要代价ci。现在为了将故障的代价控制到最小，小可可必须想出一个截断方案，使a站不能到达b子站，并且截断的代价之和最小。我们称之为最小截断，小可可很快解决了这个故障，但是爱思考的小可可并不局限于此，为了今后更方便的解决同类故障，他考虑对每条单向通道： 1，是否存在一个最小代价路径截断方案，其中该通道被切断？ 2，是否对任何一个最小代价路径切断方案，都有该通道被切断？ 聪明的你能帮小可可解决他的疑问吗？ 输入：第一行有4个整数，依次为N，M，a和b； 第二行到第(m+1)行每行3个正整数x，y，c表示x子站到y子站之间有单