BNU 第十一届北京师范大学程序设计竞赛

阅读量：5299 次

发布时间：2019-06-14

本文共 7380 字，大约阅读时间需要 24 分钟。

北师大校赛，下午2点才开始做，做了1个半点AC了3道，结束后又AC了1道~~

A. BNU ACM校队时间安排表

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format:

%lld Java class name:

Main

Font Size:

ICPC，全称国际大学生程序设计竞赛，由美国计算机协会（ACM）主办。它是一项非常公平的比赛，广受世界各地大学生的喜爱。ACM每年在各大洲会举办区域赛，表现优异的学校将有资格参加世界总决赛。

ACM-ICPC自1996年踏上中国大陆，只在上海大学设立赛点。从2008年开始，每年在中国大陆有五个赛区举办区域赛。BNU也从2002年开始组建了ACM校队，通过老师和同学的不懈努力，BNU的ACM成绩也在逐年进步。

每年BNU校队都会举办一系列的培训以及比赛，吸引优秀的同学参赛（易大神牛为此还搭建了我们学校的神OJ）。校队各项活动的时间大致安排如下：

时间	活动	英文名称
11月-12月	ACM基础培训（面向全校本科生）	Basic Training
12月	新生赛（面向全校本科一年级的同学）	Rookie Contest
2月-4月	春季培训（面向全校学生）	Spring Training
4月	校赛（面向全校本科生和硕士研究生）	BNU Contest
7月	实践周（面向全校本科生）	Practice Week
7月-8月	暑期训练（面向校队）	Summer Training
9月-11月	区域赛（校队）	Regional Contest

小胖是BNU ACM校队的脑残粉，他掌握了校队各项活动的时间，同学们对校队的活动安排有什么疑问都会找他。比如昨天大钰儿问他，校队5月份有什么安排，今天浪哥问他暑假7月份要做什么，等等等等。随着想加入校队的人数越来越多，询问也越来越多，小胖就写了个程序，自动回答这些询问。

Input

输入第一行有一个整数T（1<=T<=100），表示询问的个数。

接下来有T行，每一行一个整数M（1<=M<=12），代表询问的月份M。

Output

对于每一个询问，输出若干行，表示该月的活动，每一行代表一个活动的英文名称。如果某个月有多项活动，则按照上表给出的顺序输出。如果某个月没有活动，则输出一行Unknown。

Sample Input

Sample Output

UnknownBasic Training Regional ContestPractice Week Summer Training 水题一道，会编程就能过，10分钟只能AC

[C++]

1 #include
       
         2  3 using namespace std; 4  5 int main() 6 { 7     int t; 8     cin>>t; 9 10     while(t--)11     {12         int temp;13         cin>>temp;14         switch(temp)15         {16             case 1:cout<<"Unknown"<

C. Adidas vs Adivon

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format:

%lld Java class name:

Main

Font Size:

“我们坐在高高的土堆上面，听妈妈讲阿迪王的事情。我出生在一个不太普通的家庭，妈妈会预知术，在我小的时候，妈妈就常跟我说：‘在未来的世界，有一种叫阿迪王的东西成为比石油、黄金还重要的东西……’那时，我痴痴地听着，一听就到半夜，听到入迷，任由鼻涕流到自己的嘴里。长大后，我终于知道阿迪王是什么东西。它是对于亿万人来说比自身生命还重要的神物……”

就我所知，一双普通的阿迪王人造革鞋的日常维护费就很惊人了，有些亿万富翁购买了阿迪王的产品后因为不堪负担产品的日常维护费用而宣布个人破产。

“I'm coming!!!”

但是，Adidas这个从来没有听过的牌子居然告Adivon商标侵权了！！这是Adivon粉丝们不能容忍的！！！所以在一个夜黑风高的晚上，一位高贵的Adivon粉丝与另一位Adidas屌丝约战于华山之巅。作为21世纪的新青年，他们选择了智力对抗，来一局博弈定胜负。

他们拿出了一张长和宽都是正整数的纸片，每次，当前一方可以选择将纸片水平或竖直撕成相等的两半（平行于长边或宽边），扔掉一半。但是要求撕完后剩下的那部分纸片长和宽依旧是正整数。直到有一方不能再撕，该方即输掉这场博弈。

Adivon的粉丝那是相当大度的，所以每次都是Adidas屌丝先手。

Input

第一行一个整数N(2<=N<=2000)，表示他们进行了多少局博弈。

接下来N行，每行两个正整数L和H（1<=L,H<=1000000），表示该局纸片的初始长宽。

Output

对于每一局游戏，输出一行，如果Adivon粉丝胜利则输出"Adivon prevails"，否则Adivon粉丝将发动神技，改变游戏结局，此种情况输出"Adidas loses".

Sample Input

21 22 2

Sample Output

Adidas losesAdivon prevails 博弈问题，最初看题以为很难做，后来发现很简单，只要计算一下每个边可以对折多少次，最后判断两个边对折次数的和的奇偶性即可

[C++]

1 #include
        
          2  3 using namespace std; 4  5 int main() 6 { 7     int n; 8     cin>>n; 9     while(n--)10     {11         long l,h;12         int ll=0,hh=0;13         cin>>l>>h;14         while(l%2==0)15         {16             ll++;17             l/=2;18         }19         while(h%2==0)20         {21             hh++;22             h/=2;23         }24         if((ll+hh)%2==0)25             cout<<"Adivon prevails"<

H. 硬币水题II

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format:

%lld Java class name:

Main

Font Size:

小胖有一个正反面不对称的硬币。如果抛一次这个硬币，它的正面朝上的概率为p，反面朝上的概率为1-p。现在，小胖想用这个硬币来产生等概率的决策（50%对50%）。当然，只抛一次是不行的。小胖的策略是这样的：每一次决策，需要抛硬币两次，如果都是正面朝上或者都是反面朝上，那么就重新再做一次决策；如果是一正一反，那么如果第一次是正面朝上，就说抛了正面，如果第一次是反面朝上，那么就视为抛了反面。这样，就能得到一个公平的决策了。

现在问题是，给定一个p，小胖平均要抛多少次，才能得到一个决策呢（即不用再抛了）？

Input

第一行包含一个整数N（N<=100），表示测试数据的个数。

接下来包括N行，每行一个测试数据，包括一个3位的浮点数p（0<p<1）。

Output

对每一个测试数据，输出一行，包括一个浮点数，表示小胖抛硬币的平均次数。

结果保留两位小数。

Sample Input

30.5000.8000.300

Sample Output

4.006.254.76 简单的数学题，概率计算问题~~~

[C++]

1 #include
         
           2 #include
          
            3 #include
           
             4  5 using namespace std; 6  7 int main() 8 { 9     int t;10     cin>>t;11     while(t--)12     {13         double p,x;14         cin>>p;15         x=1/(p*(1-p));16         printf("%.2lf\n",x);17     }18 19     return 0;20 }

L. 斩

Time Limit: 1000ms

Case Time Limit: 1000ms

Memory Limit: 65536KB

64-bit integer IO format:

%lld Java class name:

Main

Font Size:

在电影里面，我们经常可以看到武士们拔出刀，然后一刀斩下去，结果………………………………一张纸片被砍成了两半，囧…………

而在本题中，我们需要计算一下被斩下去较小的那一部分的面积。

我们假设纸片是矩形的，平行于坐标轴的，武士砍纸片的轨迹是一条直线。

Input

第一行一个整数N(2<=N<=350)，表示数据组数。

接下来一行，每行7个整数，x_l,y_l,x_r,y_r,a,b,c ，表分别表示矩形左下角坐标(x_l,y_l)，右上角坐标(x_r,y_r)，以及轨迹方程ax+by+c=0。整数的绝对值均小于200。

Output

对于每一组数据，输出一个三位小数，表示砍后较小那部分的面积。数据保证这个面积大于0.001。

Sample Input

31 1 3 3 -1 1 01 1 3 4 -1 1 01 2 3 4 -1 1 0

Sample Output

2.0002.0000.500 人生第一道计算几何题，题目看起来真的很简单，不过写起来要考虑浮点数精度问题，代码还真不短,比赛结束之前没能写完，结束后提交WA两次后终于AC 易错点：注意判断直线与矩形的交点在矩形顶点的情况。

[C++]

1 #include
          
            2 #include
           
             3 #include
            
              4  5 using namespace std; 6  7 //求以(x0,y0),(x1,y1),(x2,y2)为顶点的三角形面积函数 8 double St(double x0,double y0,double x1,double y1,double x2,double y2) 9 {10     return fabs(x0*y1+x2*y0+x1*y2-x2*y1-x0*y2-x1*y0)/2;11 }12 13 //判断两个浮点数是否相等14 bool e(double a,double b)15 {16     if(fabs(a-b)<1e-9)17         return true;18     return false;19 }20 21 //判断浮点数a是否小于浮点数b22 bool f(double a,double b)23 {24     if(a
             
              1e-9)25         return true;26     return false;27 }28 29 //求以a,b为边长的矩形面积30 double Sx(double a,double b)31 {32     return fabs(a*b);33 }34 35 int main()36 {37     int t;38     cin>>t;39     while(t--)40     {41         double xl,yl,xr,yr,a,b,c;42         double xdown,ydown,xleft,yleft,xright,yright,xup,yup;43 44         cin>>xl>>yl>>xr>>yr>>a>>b>>c;45         46         //求直线与矩形四条边所在直线的交点47         xdown=(-b*yl-c)/a;48         ydown=yl;49         xup=(-b*yr-c)/a;50         yup=yr;51         xleft=xl;52         yleft=(-a*xl-c)/b;53         xright=xr;54         yright=(-a*xr-c)/b;55 56         //判断交点位置情况57         if(e(xl,xdown)&&e(yl,ydown))58         {59             if(e(xr,xup)&&e(yl,yup))60                 printf("%.3lf\n",St(xl,yl,xl,yr,xr,yr));61             else if(f(xl,xup)&&f(xup,xr))62                 printf("%.3lf\n",St(xl,yl,xl,yr,xup,yup));63             else64                 printf("%.3lf\n",St(xl,yl,xr,yl,xright,yright));65         }66         else if(e(xl,xleft)&&e(yr,yleft))67         {68             if(e(xdown,xr)&&e(ydown,yl))69                 printf("%.3lf\n",St(xl,yr,xr,yr,xr,yl));70             else if(f(xl,xdown)&&f(xdown,xr))71                 printf("%.3lf\n",St(xl,yr,xl,yl,xdown,ydown));72             else73                 printf("%.3lf\n",St(xl,yr,xr,yr,xright,yright));74         }75         else if(f(xl,xdown)&&f(xdown,xr)&&f(yl,yleft)&&f(yleft,yr))76             printf("%.3lf\n",St(xl,yl,xdown,ydown,xleft,yleft));77         else if(f(yl,yleft)&&f(yleft,yr)&&f(xl,xup)&&f(xup,xr))78             printf("%.3lf\n",St(xl,yr,xleft,yleft,xup,yup));79         else if(f(xl,xup)&&f(xup,xr)&&f(yl,yright)&&f(yright,yr))80             printf("%.3lf\n",St(xr,yr,xup,yup,xright,yright));81         else if(f(yl,yright)&&f(yright,yr)&&f(xl,xdown)&&f(xdown,xr))82             printf("%.3lf\n",St(xr,yl,xright,yright,xdown,ydown));83         else if(f(yl,yleft)&&f(yleft,yr)&&f(yl,yright)&&f(yright,yr))84         {85             double s1=Sx(xr-xl,(yleft+yright)/2-yl);86             double s2=Sx(xr-xl,yr-yl)-s1;87             printf("%.3lf\n",f(s1,s2)?s1:s2);88         }89         else90         {91             double s1=Sx(yr-yl,(xup+xdown)/2-xl);92             double s2=Sx(xr-xl,yr-yl)-s1;93             printf("%.3lf\n",f(s1,s2)?s1:s2);94         }95     }96 97     return 0;98 }