全国赛省选题day

1、1行星序列（seq）“神州“载人飞船的发射成功让小可可非常激动，他立志长大后要成为一名宇航员假期一始，他就报名参加了“小小宇航员夏令营”，在这里小可可不仅学到了丰富的宇航知识，还参与解决了一些模拟飞行中发现，今天指导老师交给他一个任务，在这次模拟飞行的路线上有 N 个行星，暂且称它们为一个行星序列，并将他们从 1 至 n 标号，在宇宙未知力量的作用下这 N 个行星的质量是不断变化的，所以他们对飞船产生的引力也会不断变化，小可可的任务就是在飞行途中计算这个行星序列中某段行星的质量和，以便最终到达目的地，行星序列质量变化有两种形式： 1，行星序列中某一段行星的质量全部乘以一个值2，行星序列中某一段

2、行星的质量全部加上一个值修正飞船的飞行线路，由于行星的质量和很大，所以求出某段行星的质量和后只要输出这个值模 P 的结果即可，小可可被这个任务难住了，聪明的你能够帮他完成这个任务吗？输入：第一行两个整数N 和P（1p1000000000）；第二行含有 N 个非负整数，从左到右依次为 a1，a2，an（0ai。100000000，1in），其中 ai 表示第i 个行星的质量：第三行有一个整数m，表示模拟行星质量变化以及求质量和等操作的总次数。从第四行开始每行描述一个操作，输入的操作有以下三种形式：操作 1：1 t g c 表示把所有满足tig 的行星质量ai 改为 aic操作 2：2 t g c

3、 表示把所有满足tig 的行星质量ai 改为 aic操作 3：3 t g 表示输出所有满足tig 的ai 的和模 p 的值其中：1tgN，0c10000000注：同一行相邻的两数之间用一个空格隔开，每行开头和末尾没有多余空格输出：对每个操作 3，按照它在输入中出现的顺序，依次一行输出一个整数表示所求行星质量和样例：输入：7 431 2 3 4 5 6 751 2 5 53 2 42 3 7 93 1 33 4 7输出：2358样例说明：略提示： 100的数据中，M，N100000 40的数据中，M，N10000（Neilc-lc 提醒你，直接模拟可能是一个点都过不去，加上每次 mod 的优化，

4、可以过 3 到 4 个点正解是用线段树来做）2同类分布（self）在模拟飞行的过程中，小可可发现在一个未知星球周围分布着许多同类的小行星带，而这些小行星带的分布非常有规律，经过研究发现实些小行星带到未知星球的距离为x（x 为非负整数）与如下的函数有一定的关系：dsum(x)0 x=0;dsum(x/10)+x mod 10 x0即x 可以被dsum（x）整除。小可可非常希望能研究出距离这个未知星球的某一区域内小行星带的分布规律，具体来说，就是在与未知行星距离 a 和b 的范围内分布了多少个小行星带，你能帮助他解决这个问题吗？输入：输入文件仅一行，包含两个正整数a 和 b（a=b).输出：输出文

5、件中仅包含一个整数，表示a，b内分布多少个小行星带。样例 1:输入：1 10输出：10样例 2：输入：1234567912345679 1234567912346789输出：37提示：100的数据中，a，b 不超过30的数据中，ba 不超过 1000000（10 的 18 次方）；3最小截断宇宙旅行总是出现一些意想不到，这次小可可所驾驶的宇宙飞船所停的空间站发生了故障，这个宇宙空间站非常大，它由 N 个子站组成，子站之间有 M条单向通道，假设其中第 i（1iM）条单向通道连接了 xi，yi 两个中转站，那么 xi 子站可以通过这个通道到达 yi 子站，如果截断这条通道，需要代价 ci。现在为了

6、将故障的代价控制到最小，小可可必须想出一个截断方案，使 a 站不能到达b 子站，并且截断的代价之和最小。称之为最小截断，小可可很快解决了这个故障，但是爱思考的小可可并不局限于此，为了今后更方便的解决同类故障，他考虑对每条单向通道： 1，是否存在一个最小代价路径截断方案，其中该通道被切断？2，是否对任何一个最小代价路径切断方案，都有该通道被切断？聪明的你能帮小可可解决他的疑问吗？输入：第一行有 4 个整数，依次为N，M，a 和b；第二行到第(m+1)行每行 3 个正整数x，y，c 表示 x 子站到 y 子站之间有单向通道相连，单向通道的起点是 x 终点是y，切断它的代价是 c（1c10000）；两个子站之间可能有多条通道直接连接。输出：对每一个单向通道，按输入的顺序，依次输出一行包含两个非 0 即 1 的整数，分别表示对问题一和问题二的回答（其中 1 表示是，0 表示否）。每行两个整数之间用一个空格分隔开。样例：输入：6 72 5