ahoi 2009.doc

AHOI2009一试试题1，行星序列（seq）“神州“载人飞船的发射成功让小可可非常激动，他立志长大后要成为一名宇航员假期一始，他就报名参加了“小小宇航员夏令营”，在这里小可可不仅学到了丰富的宇航知识，还参与解决了一些模拟飞行中发现的问题，今天指导老师交给他一个任务，在这次模拟飞行的路线上有N个行星，暂且称它们为一个行星序列，并将他们从1至n标号，在宇宙未知力量的作用下这N个行星的质量是不断变化的，所以他们对飞船产生的引力也会不断变化，小可可的任务就是在飞行途中计算这个行星序列中某段行星的质量和，以便能及时修正飞船的飞行线路，最终到达目的地，行星序列质量变化有两种形式：1，行星序列中某一段行星的质量全部乘以一个值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 表示把所有满足tig的行星质量ai改为aic 操作3：3 t g 表示输出所有满足tig的ai的和模p的值 其中：1tgN，0c10000000 注：同一行相邻的两数之间用一个空格隔开，每行开头和末尾没有多余空格输出：对每个操作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，N100000 40的数据中，M，N100002，同类分布（self）在模拟飞行的过程中，小可可发现在一个未知星球周围分布着许多同类的小行星带，而这些小行星带的分布非常有规律，经过研究发现实些小行星带到未知星球的距离为x（x为非负整数）与如下的函数有一定的关系：dsum(x)0 x=0;dsum(x/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的数据中，ba不超过10000003，最小截断（mincut）宇宙旅行总是出现一些意想不到的问题，这次小可可所驾驶的宇宙飞船所停的空间站发生了故障，这个宇宙空间站非常大，它由N个子站组成，子站之间有M条单向通道，假设其中第i（1iM）条单向通道连接了xi，yi两个中转站，那么xi子站可以通过这个通道到达yi子站，如果截断这条通道，需要代价ci。现在为了将故障的代价控制到最小，小可可必须想出一个截断方案，使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 7 1 6 1 2 3 1 3 2 2 4 4 2 5 1 3 5 5 4 6 2 5 6 3输出：1 01 00 01 00 01 01 0提示：100的数据中，N4000，M60000 70的数据中，N1000，M40000 40的数据中，n200，M2000AHOI2009二试试题1：飞行棋（Fly）在经过地“小小宇航员夏令营”的学习以及模拟飞行实验后，小可可明白宇航员并不是那么容易当的，除了需要强健的身体，丰富的经验以及灵活的应变能力以外，缜密的思维也是不可少的，为了早日实现自己的宇航员的梦想，小可可决定在平时就开始锻炼利用棋类游戏来锻炼自己的思维。小可可发明一种飞行棋，棋盘是一个圆周形，在圆周形上有若干个点，已知这些点与点之间的弧长，弧长均为正整数，并且依圆弧顺序排列，飞行棋的规则是找出这些点中有没有可以围成矩形的，在最短时间内找出所有不重复矩形的玩家胜出。输入：第一行为正整数N，表示棋盘上点的个数，接下来n行分别为这N个点所分割的各个圆弧的长度。输出：所构成的不重复的矩形。样例： 输入： 8 1 2 2 3 1 1 3 3 输出： 32;中国象棋（Cchess） 这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！ 输入：一行包含两个整数N，M，之间由一个空格隔开。 输出：总共的方案数，由于该值可能很大，只需给出方案数模9999973的结果。 样例： 输入： 1 3 输出： 7 样例说明： 除了3个格子里都塞满了炮以外，其它方案都是可行的，所以一共有2*2*2-1=7种方案。 提示：100%的数据中N和M不超过100 50%的数据中N和M至少有一个娄不超过8 30%的数据中N和M均不超过63:跳棋（checher） 象棋的问题被小可可轻松解决了，下面小可可邀请你一起来研究另一个难题，这次与跳棋有关，问题是这样的：在一个1行N列（N是奇数）的棋盘上，在K个格子是红色的，这种情况下，在开始移动之前，你可以棋盘的任何空位上放棋子。在游戏开始后，你只可以随时在一个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子就被吃掉了，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。现在你和小可可要解答以下两个问题：1.移动开始前至少要放多少棋子才能完成任务？2.如果使移动开始前放的棋子数要求尽量少，那么在移动过程中最少需要放多少个棋子才能完成任务？这是你和小可可合作解决的最后一个问题了，共同努力吧！关于规则的补充说明：1.只能往空位上放棋子，不管是移动开始前还是在移动过程中。2.移动开始前棋盘最左端的那个原始棋子绝对不能被吃掉。输入：第一行一个正奇数N 第二行有N个整数，如果第i个整数是