2013安徽省省赛题解2013.05.302013安徽省省赛裁判出题组目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc357703215"A.单词反转PAGEREF_Toc357703215\h1HYPERLINK\l"_Toc357703216"B.等差数列PAGEREF_Toc357703216\h3HYPERLINK\l"_Toc357703217"C.进程调度PAGEREF_Toc357703217\h8HYPERLINK\l"_Toc357703218"D.进击的巨人PAGEREF_Toc357703218\h10HYPERLINK\l"_Toc357703219"E.巨人的进击PAGEREF_Toc357703219\h12HYPERLINK\l"_Toc357703220"F.闪光的指压师PAGEREF_Toc357703220\h16HYPERLINK\l"_Toc357703221"G.Alice&MarisaPAGEREF_Toc357703221\h19HYPERLINK\l"_Toc357703222"H.排列的前后PAGEREF_Toc357703222\h21HYPERLINK\l"_Toc357703223"I.散步PAGEREF_Toc357703223\h32HYPERLINK\l"_Toc357703224"J.IQtest?和K.IQtest2PAGEREF_Toc357703224\h35HYPERLINK\l"_Toc357703225"L.theendoftheworldPAGEREF_Toc357703225\h37题目地址：HYPERLINK"http://wenku.baidu.com/view/e97bfd5ac850ad02de8041ee.html"http://wenku.baidu.com/view/e97bfd5ac850ad02de8041ee.htmlA.单词反转Solution:简单的字符串处理，只要将一句话中的单词反转输出，其余字符原样输出即可。Code：#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;boolisChar(charch){return((ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z'));}intmain(){strings="";stringword="";charch;intcnt=0;while(true){getline(cin,s);if(s.size()==0){break;}word="";inti,j,k;for(i=0;i<s.size();){if(isChar(s[i])){word="";word+=s[i];for(j=i+1;j<s.size();++j){if(isChar(s[j])){word+=s[j];}else{break;}}for(k=word.size()-1;k>=0;--k){cout<<word[k];}if(j>=s.size()){break;}else{cout<<s[j];}i=j+1;}else{cout<<s[i];i++;}}cout<<endl;}return0;}B.等差数列Solution:首先所说明一下，这题原定的时限是1s，比赛时为了降低难度将时限改为了10s。比赛时用O(n^2)的算法是可以过的。要想在ls的时限下过这道题，就要用线段树。考虑以下数列a：1234681012我们将数列a的相邻两项相减得到数列b:_1112222观察发现，要想求数列a的区间[L,R]上的最长等差数列的长度，只要求数列b的区间[L+1,R]上的最长连续相同数值的长度再加1。现在将a[1,4]加上一个首项为A=2，公差为D=1的等差数列后，a为：14681181012而这时的b为：_3223-322相当于将b[1]加上A=2，将b[2,4]加上D=1，将b[5]加上-(A+(R-1)*D)=-5。Code:#include<iostream>#include<cstring>#include<cstdio>usingnamespac