安徽省2013年“京胜杯”university生程序的的设计竞赛题目与解题汇报.doc

2013 安徽省省赛题解2013.05.302013 安徽省省赛裁判出题组安徽省 2013 年“京胜杯”大学生程序设计竞赛Ａ．单词反转Time limit 1sＰｒｏｂｌｅｍ　　Ｄｅｓｃｒｉｐｔｉｏｎ给你一些英文句子，请将这些句子中的每个英语单词反转，然后再将其输出．这里听说的英语单词仅由大小写英文字母组成．Ｉｎｐｕｔ多个英文句子，每句占一行，且每句不超过８０个字符．Ｏｕｔｐｕｔ按题目要求输出Ｓａｍｐｌｅ　ＩｎｐｕｔＨｅｌｌｏ　ｗｏｒｌｄ！Ｈａｐｐｙ　ｐｒｏｇｒａｍｍｉｎｇ，ｈａｐｐｙ　ｌｉｆｅ！Ｓａｍｐｌｅ　ＯｕｔｐｕｔｏｌｌｅＨ　ｄｌｒｏｗ！ｙｐｐａＨ　ｇｎｉｍｍａｒｇｏｒｐ，ｙｐｐａｈ　ｅｆｉｌ！Ｂ．等差数列ｔｉｍｅ　ｌｉｍｉｔ　１ｓＰｒｏｂｌｅｍ　Ｄｅｓｃｒｉｐｔｉｏｎ有一个长度为Ｎ（１＜＝Ｎ＜＝１０００００）的整数序列ｓ［］ ，在这个序列上定义了两种操作：Ａｄｄ　Ｌ　Ｒ　Ａ　Ｄ：对于每一个ｉ（Ｌ＜＝ｉ＜＝Ｒ） ，Ｓ［ｉ］＋＝Ａ＋（ｉ－Ｌ）＊Ｄ，也就是在子序列Ｓ［Ｌ，Ｒ］加上首项Ａ，公差为Ｄ的等差数列：Ｑｕｅｒｙ　Ｌ　Ｒ：询问［Ｌ，Ｒ］区间内最长的等差数列的长度，亦即寻找最大的ｌｅｎ，使Ｓ［ｉ］ ，Ｓ［ｉ＋１］ ， ． ． ． ，Ｓ［ｉ＋ｌｅｎ－１］ （Ｌ＜＝ｉ＜＝Ｒ，Ｌ＜＝ｉ＋ｌｅｎ－１＜＝Ｒ）构成等差数列。

Ｉｎｐｕｔ多组测试数据每组测试数据的第一行为两个正整数Ｎ（１＜＝Ｎ＜＝１０００００）和Ｍ（１＜＝Ｍ＜＝１００００） ，分别代表序列的长度和操作个数，接下来有Ｍ行，每行代表一个操作，操作具体含义见题目描述其中，０＜＝Ｌ＜＝Ｒ＜Ｎ，０＜＝Ａ＜＝１０００００，０＜＝Ｄ＜＝１０．Ｏｕｔｐｕｔ对于每组测试数据，首先输出组号然后对于每次询问，输出所求结果详见样例输出Ｓａｍｐｌｅ　Ｉｎｐｕｔ５　３Ａｄｄ　１　４　１　１Ｑｕｅｒｙ　０　４Ｑｕｅｒｙ　２　３１０　４Ａｄｄ　０　９　１　１Ａｄｄ　４　９　１　１Ｑｕｅｒｙ　０　９Ｑｕｅｒｙ　５　５Ｓａｍｐｌｅ　ＯｕｔｐｕｔＣａｓｅ＃１：５２Ｃａｓｅ＃２：７１Ｃ．进程调度ｔｉｍｅ　Ｌｉｍｉｔ　１ｓＰｒｏｂｌｅ　Ｄｅｓｃｒｉｐｔｉｏｎ操作系统的一个重要功能是进行进程调度，其进程调度的算法有多种，其中最简单的调度算法是先进先出服务（ＦＣＦＳ）算法，该算法的思想是：先进入就绪队列的先执行，后进入的后执行，同一时刻进入就绪队列的执行时间少的先执行我们认为某一进程一旦开始执行，就一直占用处理机，直到执行结束而一旦处理机被其它进程占用，就绪队列中的进程就必须等待当某一进程执行结束后，队列中排在最前面的进程就会立即执行。

一个进程从进入就绪队列到执行完毕所用的时间为其周转时间，即周转时间＝等待时间＋执行时间现在给你若干进程到达就绪队列的时间以及每个队列的执行时间，请编程计算这些进程的平均周转时间Ｉｎｐｕｔ多组测试数据每组测试数据的第一行为一个正整数Ｎ（Ｎ＜＝１０００） ，表示要处理的进程数目接下来有Ｎ行，每行有两个正整数Ａｉ（Ａｉ＜＝１０００）和Ｅｉ（Ｅｉ＜＝１０００） ，分别表示一个进程到达就绪队列的时刻和执行该进程所需的时间Ｏｕｔｐｕｔ对于每组测试数据，输出平均周转时间，结果保留４位小数Ｓａｍｐｌｅ　Ｉｎｐｕｔ４１　１３　３２　２４　４Ｓａｍｐｌｅ　Ｏｕｔｐｕｔ３.５００Ｈｉｎｔ进程１等待时间为０，执行时间为１，其周转时间为０＋１＝１进程３等待时间为０，执行时间为２，其周转时间为０＋２＝２进程２等待时间为１，执行时间为３，其周转时间为１＋３＝４进程４等待时间为３，执行时间为４，其周转时间为３＋４＝７故平均周转时间为（１＋２＋４＋７）／４＝３．５００Ｄ．进击的巨人题目描述：艾伦作为第１０４期训练兵团卒业生于的ＮＯ．５，其它他还有一个特殊能力（主角光环）在艾伦怀有强烈意志时进行自我伤害，就能变身为最大１５米级的巨人，现在巨人已经突破了赛罗之墙，如果不用巨大的石头堵上这堵墙的缺口的话，人类的领地就会进一步缩小，我们用一个二维坐标（Ｘ０，Ｙ０）表示巨人化的艾伦的初始位置，然后用（ｘ１，ｙ１）以及Ｒ表示石块的以及（我们假设这个石块是圆形的） ，然后用２个点（ｘ２，ｙ２） ， （ｘ３，ｙ３）表示罗塞之墙的缺口（一条线段） ，现在当务之急就是要把石块尽快搬到缺口处才行。

也就是要求所走的路径是从初始点到石块再到缺口处的距离之和最小缺口肯定在石块外输入：多组数据输入，每组数据先是２个实数（ｘ０，ｙ０） ，然后再是ｘ１，ｙ１，Ｒ，接着再是ｘ２，ｙ２，ｘ３，ｙ３.输出：对于每组数据，输出最短的路径的长度（结果保留２位小数）样例输入：１　１０　０　１１　０　２　０１　１０　０　１１　－１　１　－２样例输出：１. ００２. ００Ｅ．巨人的进击题目描述：悠长的历史之中，人类层一度因被巨人捕食而崩溃面临着生存危机而残存下来的人类建造了三重巨大防护墙，这在１００年内防止了巨人的入侵不过，作为“和平”的代价，人类也失去了到墙壁外面去的“自由” 正在人们安逸了１００年之际，一个前所未有的超大型巨人出现了！那一天，人类终于回想起了，曾经一度被我们所支配的恐怖，还有被囚禁于鸟笼中那份屈辱，五年前，艾伦－耶格尔目睹母亲遭巨人吞食后，立誓要消灭所有的巨人而现在超大型巨人又再次出现在艾伦的面前，并破坏了罗塞之墙，现在必须要尽快堵上这个缺口，现在我们已知缺口是一个凸多边形， （不要在意这些细节） ，我们必须要尽可能的把缺口堵上，那么得用多大的石块（石块假设是圆形的） 输入：多组测试数据，每组给出一个ｎ表示凸多边形的定点个数，然后再给出这些凸多边形的顶点的位置（ｘｉ，ｙｉ） 。

（逆时针给出）输出：对于每组数据，给出最大的石块的半径（结束保留２位小数）样例输入：４０　０１　０１　１０　１样例输出：０. ５０Ｆ．闪光的指压师题目描述：桐奈是未来道具研究所的研究员 No.005，有重度的依存症，她沉默寡言到了与别人的交流全部都要通过短信的地步（就算对方在眼前） ，她打字的速度是连眼睛都跟不上的杰出的特技她对的操作可谓是了如指掌（不是现在的智能机 ） ，我们已知的每个按键有不同的含义：按键 1： ， ！ 按键 2：a b c 按键 3： d e f按键 4： g h I 按键 5：j k l 按键 6： m n o按键 7： p q r s 按键 8： t u v 按键 9： w x y z按键 0：空格 按键#：数字和拼音切换按键 ok：（仅对一个按键下有多个字符含义时才会用到，按键 0 用到因为它在拼音模式下只有空格这个含义而在数字含义下仅代表 0，按键#用不到，以及数字输入法下的 0 到 9 键）最初是拼音输入法，我们知道这个每次只能输入单个字符，如果要输入数字 9997，就要按下按键#，然后我们按下按键 9 三次和按键 7 一次，如果要输入 cd，先按下按键 2 三次，然后按下 ok 键，接着按下按键 3 一次，再按下按键 ok 即可，也可以先按下按键 2 三次，然后再按下按键3（因为按下其他按键就表示你已经确定了要输入按键 2 下的第几个字符了，这里表示按键2 下的第三个字符） ，这样就输入了 c，最后按下按键 ok 就输入了 d，很明显后者需要的操作要少一些，现在桐奈要发送一系列的信息，她想要尽可能快的输入这些信息（就是操作尽可能少） ，那么该怎么办呢？还要注意在切换输入法的时候，例如 a1，只需按下按键 2一次，然后按下#键一次（因为切换了输入法，故接下来的按键内容与上次肯定不同，所以判定你已经确定了按键 2 下的第几个字符了） ，然后按下按键 1 即可；也可以按下按键 2 一次，然后按下 ok 键，然后再按下按键#一次，接着按下按键 1 即可，不过后者操作要多一次。

输入：多组测试数据，每组输入只有一行字符，字符仅包含， a 到 z 0 到 9 以及空格输出：每一行输出相应的按键样例输入：21412 fs f32 23jkljsf j32样例输出：#21412#033377770333#32#0#23#5ok55ok555ok5777733305#32 G．Alice&MarisaProblem DescriptionAlice 和 Marisa 是一对好 CPAlice 和 Marisa 都要向同一个商人 Reimu 购买节操Reimu手中有 N 份节操，她会将它们一份份地卖给他们， Alice 和 Marisa 通过竞价的方式来决定节操的归属具体的过程如下：Reimu 首先指定其中一个人开始报价，之后两人轮流报价，要求是一定要比对方报的价格更高任何时候，如果一个人不愿出价或者出不起价时，可以宣布弃权，则对手以最后一次报的价格将节操买下当然，如果两个人都没钱，Reimu是不会卖节操的首先报价至少为 1，并且只能报整数的价钱Alice 和 Marisa 特别爱攀比，因此她们都希望能比对方买到更多的节操Alice 和 Marisa 各自带了 CA 和 CM 的钱用于竞拍节操。

此外，Marisa 和 Reimu 有很不错的私人关系，因此Reimu 总会让 Marisa 先报价现在请问，在 Alice 和 Marisa 都用最优策略的情况下，谁能买到更多的节操？假设双方都知道对方手中的现金数量，以及 Reimu 将要拍卖的节操数量NInput 本题有多组数据每组数据为一行三个用空格隔开的整数 N，CM，CA，表示节操的数量，以及双方带的现金0#include #include using namespace std;bool isChar(char ch){return ( (ch >= 'A' && ch = 'a' && ch = 0; --k) {cout= s.size()) {break;} else {cout#include #include using namespace std;const int maxn = 100010;struct Node {int l, r, rt;int llen, rlen; // 区间左（右）端点开始的连续数列长度int mlen; // 区间最长连续数列的长度long long lvalue, rvalue; // 区间左（右）端点数列的值 int len(){return r - l + 1;}}seg[maxn> 1;build(l, mid, rt r) {return ; }if (l == seg[rt].l && r == seg[rt].r) {if (seg[rt].mlen == seg[rt].len()) {seg[rt].lvalue += d;seg[rt].rvalue += d;return ;}}pushDown(rt);int mid = (seg[rt].l + seg[rt].r) / 2;int lch = rt mid) {update(l, r, rch, d);} else {update(l, mid, lch, d);update(mid + 1, r, rch, d);}pushUp(rt);}int query(int l, int r, int rt){if (l > r) {return 0; }if (l == seg[rt].l && r == seg[rt].r) {return seg[rt].mlen;}pushDown(rt);int lch = (rt > 1;if (r mid) {return query(l, r, rch);} else {int mlen;mlen = max(query(l, mid, lch), query(mid + 1, r, rch));if。