安徽省2013年“京胜杯”大学生程序设计竞赛题目及解题报告.doc

2013 安徽省省赛题解 2013.05.30 2013 安徽省省赛裁判出题组 安徽省安徽省 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 GAlice bool isChar(char ch) return ( (ch = A -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; segmaxn 1; build(l, mid, rt r) return ; if (l = segrt.l segrt.rvalue += d; return ; pushDown(rt); int mid = (segrt.l + segrt.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 = segrt.l 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 (seglch.rvalue = segrch.lvalue) mlen = max(mlen, min(seglch.rlen, mid - l + 1) + min(segrch.llen, r - mid); return mlen; int main() /freopen(“W.等差数列.in“, “r“, stdin); /freopen(“W.等差数列.out“, “w“, stdout); int n, m; char op10; int L, R; int A, D; int tcase = 0; while (scanf(“%d%d“, printf(“Case #%d:n“, tcase); build(1, n - 1, 1); for (int i = 0; i #include #include using namespace std; const int maxn = 1010; struct Proc int a, e; pmaxn; int n; bool cmp(Proc p1, Proc p2) if (p1.a != p2.a) return p1.a #include #include #include #define EPS 1e-6 #define PI acos(-1.0) using namespace std; struct point double x,y,r; start,line2,cir; double cross(const point double dis(const point point rorate (const point ans.x = p.x + p.r*cos(angle); ans.y = p.y + p.r*sin(angle); return ans; double dot(const point double dis_line(const point else return min(dis(line0,p),dis(line1,p); return 0; double thr_search(double angle, double st)/主要的部分，三分的程序 point temp1, temp2; double l(st),r(angle),mid1,mid2; while (fabs(r - l) EPS) mid1 = (r + l)/2; mid2 = (mid1 + r)/2; temp1 = rorate(cir,mid1); temp2 = rorate(cir,mid2); if (dis_line(temp1) + dis(temp1,start) #include #include #include #include #include using namespace std; #define MAXN 110 #define eps 1e-10 #define zero(x) (x)0?(x):-(x) eps; struct Convex int n; pt pMAXN; ; struct Plane/半平面,a,b 构成直线,side 表示在哪个面 pt a,b,side; ; /* *ret.x-u1.x=t(u2.x-u1.x) *ret.y-u1.y=t(u2.y-u1.y) *ret.x-v1.x=tt(v2.x-v1.x) *ret.y-v1.y=tt(v2.y-v1.y) *解以上方程可得线段交点 ret */ pt intersection(pt u1, pt u2, pt v1, pt v2) pt ret = u1; double t = (u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x) /(u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x); ret.x += (u2.x - u1.x)*t; ret.y += (u2.y - u1.y)*t; return ret; Convex src,ans; Convex Half_Plane(Convex c, Plane pl)/半平面交,一条直线切割凸包 int i,j; double r1,r2; Convex ans,ans1; ans.n = 0; for(i = 0; i maxd) maxd = d; double l,r,mid,k,ansd; l = 0;r = maxd/2; ansd = 0; while(l + eps #include #include #include using namespace std; vector tab10; void ini() tab0.push_back( ); tab1.push_back(,); tab1.push_back(.); tab1.push_back(!); char temp = a; for (int i(2),j(0); i= a)return 0; if (a = | a = , | a = . | a = !)return 0; if (a = A)return 1; if (a = 0)return 2; int get_key(char a, int int main() int n,cm,ca; while(cinncmca) if(n = 0) cout 2 * cm) if(ca cm) cout= (cm / winner + 1 ) * winner) cout= (cm / draw + 1) * winner)/cm cout #include #include #include using namespace std; / #define MAXN 9999 #define MAXSIZE 10 #define DLEN 4 class BigNum private: int a500; / int len; / public: BigNum() len = 1;memset(a,0,sizeof(a); / BigNum(const int); /int BigNum(const char*); / BigNum(const BigNum / BigNum / friend istream / friend ostream / bool operator(const int /int bool operator=(const BigNum / bool operator=(const int /int void print(); / ; BigNum:BigNum(const int b) /int int c,d = b; len = 0; memset(a,0,sizeof(a); while(d MAXN) c = d - (d / (MAXN + 1) * (MAXN + 1); d = d / (MAXN + 1); alen+ = c; alen+ = d; BigNum:BigNum(const char*s) / int t,k,index,l,i; memset(a,0,sizeof(a); l=strlen(s); len=l/DLEN; if(l%DLEN) len+; index=0; for(i=l-1;i=0;i-=DLEN) t=0; k=i-DLEN+1; if(k(istream int i = -1; inch; int l=strlen(ch); int count=0,sum=0; for(i=l-1;i=0;) sum = 0; int t=1; for(int j=0;j=0;j+,i-,t*=10) sum+=(chi-0)*t; b.acount=sum; count+; b.len =count+; return in; ostream i-) cout.width(DLEN); cout.fill(0); cout len ? T.len : len; for(i = 0 ; i MAXN) t.ai + 1+; t.ai -=MAXN+1; if(t.abig != 0) t.len = big + 1; else t.len = big; return t; BigNum BigNum:operator-(const BigNum bool flag; BigNum t1,t2; if(*thisT) t1=*this; t2=T; flag=0; else t1=T; t2=*this; flag=1; big=t1.len; for(i = 0 ; i i) t1.aj- += MAXN; t1.ai += MAXN + 1 - t2.ai; else t1.ai -= t2.ai; t1.len = big; while(t1.alen - 1 = 0 big-; if(flag) t1.abig-1=0-t1.abig-1; return t1; BigNum BigNum:operator*(const BigNum int i,j,up; int temp,temp1; for(i = 0 ; i MAXN) temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); up = temp / (MAXN + 1); ret.ai + j = temp1; else up = 0; ret.ai + j = temp; if(up != 0) ret.ai + j = up; ret.len = i + j; while(ret.aret.len - 1 = 0 return ret; BigNum BigNum:operator/(const int int i,down = 0; for(i = len - 1 ; i = 0 ; i-) ret.ai = (ai + down * (MAXN + 1) / b; down = ai + down * (MAXN + 1) - ret.ai * b; ret.len = len; while(ret.aret.len - 1 = 0 return ret; BigNum BigNum:operator*(const int return *this*b; BigNum BigNum:operator+(const int return *this + b; int BigNum:operator %(const int for (i = len-1; i=0; i-) d = (d * (MAXN+1)% b + ai)% b; return d; BigNum BigNum:operator(const int int i; if(n1) t=*this; for( i=1;i(const BigNum if(len T.len) return true; else if(len = T.len) ln = len - 1; while(aln = T.aln if(ln = 0 else return false; else return false; bool BigNum:operator (const int return *thisb; bool BigNum:operator=(const BigNum if(len != T.len) return false; else ln = len - 1; while(ln = 0 if(ln = 0) return false; else return true; bool BigNum:operator =(const int return *thisb; void BigNum:print() int i; cout = 0 ; i-) cout.width(DLEN); cout.fill(0); cout snn) if(nn0=-) flag=0; n=BigNum(nn+1); else flag=1; n=BigNum(nn); len = s.size(); x = toNum(s); if(flag int map5151,t5151; long long s5151; int dir42=-1,0,1,0,0,-1,0,1; int n,m; struct pp int x,y; ; queue que; int flag9999; void bfs() pp a,b; int dx,dy,i,spend; a.x=n-1;a.y=m-1; tn-1m-1=mapn-1m-1; que.push(a); while(!que.empty() b=que.front(); que.pop(); for(i=0;i=0 if(x=n-1 flagxy+; sxy=0; for(i=0;i=0 return sxy; int main() int i,j; while(cinnm) for(i=0;imapij; tij=-1; while(!que.empty() que.pop(); memset(s,-1,sizeof(s); memset(flag,0,sizeof(flag); bfs(); dfs(0,0); cout b 设 f（x，y）表示某人看到的两个数是 x 和 y，他所能判断自己的数是什么至少经过的轮数 显然 f(x,y) = f(y,x) 现在分别站在 1，2，3 角度来讨论这个问题 1 需要 f(b,a+b) 轮才能判断 2 需要 f(a,a+b) 轮才能判断 3 要 f(a,b)轮 现在 3 假设自己是 a-b 那么在 3 的世界中的 1 会在第 f(b,a-b)轮给出判断 在 3 的世界中的 2 会在第 f(a,a-b)轮给出判断 所以 3 一定会在 min(f(b,a-b),f(a,a-b)+1 轮给出判断 可以得到 f(a,b) = min(f(b,a-b),f(a,a-b)+1 所以 f(b,a+b) = min(