《简单计算题（二）ppt课件.ppt》由会员分享，可在线阅读，更多相关《简单计算题（二）ppt课件.ppt（55页珍藏版）》请在三一办公上搜索。
1、第三讲,简单计算题（二）,ACM算法与程序设计,数学科学学院：汪小平,CDOJ_1365 木杆上的蚂蚁http:/,Description在一根细木杆上，有一些速度相同蚂蚁，它们有的往左走，有的往右走，木杆很细，只允许一只蚂蚁通过，所以当两只蚂蚁碰头的时候，它们会掉头继续前进，直到走出边界，掉下木杆。已知木杆的长度和每只蚂蚁的名字、位置和初始方向，问依次掉下木杆的蚂蚁花费的时间以及它的名字。,Input 输入包含多组测试数据。 第一行包含一个整数T(T = 20)，代表测试数据组数。 每组测试数据的第一行包含两个整数N L，表示有N只蚂蚁(N = 100)，木杆长度为L(L = 1000)。假
2、设蚂蚁每秒前进一个单位距离，掉头转向的时间忽略不计。 以下N行，每行依次为蚂蚁的名字（长度不超过10，仅由英文字母组成），初始位置p（0 p L，整数，表示蚂蚁离木杆最左端的距离），初始方向（一个字符，L表示向左，R表示向右），以单个空格分隔，数据保证初始不会有两只蚂蚁在同一个位置。,Output 对于第k组测试数据，首先输出一行为“Case #k:”。 然后输出N行，给出依次掉下木杆的蚂蚁花费的时间以及它的名字，以单个空格分隔。 （按照掉下木杆的先后顺序输出，数据保证不会有两支蚂蚁同时掉下木杆）。Sample Input22 5GG 1 LMM 3 R2 5GG 1 RMM 2 L,Samp
3、le OutputCase #1:1 GG2 MMCase #2:2 GG4 MM,#include #include /因为要用sort算法#define N 100using namespace std; /必须引用名字空间stdstruct ant_type int pos; char name11; antsN;struct event_type int drop_time; char dir; eventsN;bool cmp_ant(const ant_type,bool cmp_event(const event_type ,sort(ants, ants + n, cmp_an
4、t); sort(events, events + n, cmp_event); printf(Case #%d:n, k); L = 0; R = n - 1; for (i = 0; i n; i+) if (eventsi.dir = L) printf(%d %sn, eventsi.drop_time, antsL.name); L+; else printf(%d %sn, eventsi.drop_time, antsR.name); R-; return 0;,往届校赛题目精选,CDOJ_1004 8球胜负(eight) http:/,Description 8球是一种台球竞赛
5、的规则。台面上有7个红球、7个黄球以及一个黑球，当然还有一个白球。对于本题，我们使用如下的简化规则：红、黄两名选手轮流用白球击打各自颜色的球，如果将该颜色的7个球全部打进，则这名选手可以打黑球，如果打进则算他胜。如果在打进自己颜色的所有球之前就把黑球打进，则算输。如果选手不慎打进了对手的球，入球依然有效。 现在给出打进的球（白球除外）的顺序，以及黑球由哪方打进，你的任务是判定哪方是胜者。假设不会有一杆同时打进一颗黑球和其他彩球。,Input 输入包含多组数据。每组数据第一行是一个整数N(1=N=15)，表示打进的球的个数，N=0表示结束。随后有一行，包含N个字符，依序表示打进的是何种球。如果是
6、B，表示是红方打进的黑球，如果是L，表示是黄方打进的黑球。如果是Y则表示是黄球，R表示红球。字符间没有空格。 所有输入都满足如下条件：最后一颗球打进时这局比赛正好结束，而且打进的红球和黑球都不超过7个。Output 对每组数据，输出一行。如果红方胜，输出Red；黄方胜，输出Yellow。,Sample Input 5RYRRB9RRRRYRRRB0Sample Output YellowRed,2008年校赛最简单的题目。只需要判断最后一个球是谁打进的，然后统计这个人自己的球是不是已经全部打进了，就可以得到答案。,#include #include int main() char str30;
7、 int i,n,cnt,k; bool flag; while (1) scanf(%d, /否则黄方胜 ,else/最后一个球是黄方打进的黑球 cnt=0; for (i=0;ik;i+) if (stri=Y) cnt+; /统计黑球之前进了几个黄球 if (cnt=7) flag=false; /进了7个红球则黄方胜 else flag=true; /否则红方胜 if (flag) printf(Redn); else printf(Yellown); return 0;,CDOJ_1005 点球大战(penalty) http:/,Description 在足球比赛中，有不少赛事，例
8、如世界杯淘汰赛和欧洲冠军联赛淘汰赛中，当比赛双方经过正规比赛和加时赛之后仍然不分胜负时，需要进行点球大战来决定谁能够获得最终的胜利。点球大战的规则非常简单，两方轮流派出球员罚点球，每方各罚5个。当5轮点球结束以后如果仍然不分胜负，则进入一轮定胜负的阶段。两方各派一名球员罚点球，直到有一方罚进而另一方没有进为止。 在北美职业冰球联赛中，也有点球大战。与足球的规则不同的是，它只先罚3轮点球，随后就进入一轮定胜负的阶段，而其他的规则完全一样。 在本题中，输入将给出每次点球是否罚进，而你的任务则是输出一个“比分板”。,Input 输入包含多组数据。每组数据的第一行包含一个整数N(1=N=18)，表示双
9、方总共罚了多少个点球，N=0表示输入结束。随后有N行，每行是一个如下形式的字符串： XXXX good：表示这个点球罚进 或者XXXX no good：表示这个点球没有罚进 其中XXXX表示球员名字（全部由字母和空格组成，保证不会出现歧义） 每一行保证不超过100个字符。 XXXX和good以及XXXX和no、no和good之间保证有且只有1个空格。good、no good都是小写。本题是大小写相关的。 数据不保证点球大战一定结束，也不保证在结束以后立即结束这组数据（即：不用判断点球大战是否结束，只用把罚进的点球往比分上加即可）。Output 对每组数据，输出一个比分板。一个点球如果罚进，则在
10、对应的地方标上O，如果没有进则标上X。先罚球的队伍的信息在上面，后罚的在下面。最右边标上两队的比分。具体格式参考样例输出。注意如果一轮点球只罚了一个，则后面那个点球对应的地方写上-。,Sample Input 6Riise goodBallack goodGerrard no goodLampard no goodFernando Torres goodMalouda good9Christiano Ronaldo no goodMessi no goodGiggs goodAbidal no goodCarrick goodRonaldinho goodRooney goodHenry no
11、 goodTevez good0Sample Output 1 2 3 ScoreO X O 2O X O 21 2 3 4 5 ScoreX O O O O 4X X O X - 1,名字可以包含空格，甚至可以包含no、good（事实上，大部分数据都包含no和good中的至少一个），所以此题比较好的处理方法是找跳过名字，直接找倒数第二个单词，看它是不是no，是就是没踢进，反之就是踢进；数据可能很诡异，比如有两种特殊情况，一种是只有一个good，另一种是直接no good。这两组数据不是太满足题意（第一组名字为空，第二组有歧义）空格数要和样例输出一样，否则很可能会被判为“格式错误”(Prese
12、ntation Error)。,#include #include bool judge(char *str) int pos=strlen(str)-1; while (strpos!= ) pos-;/从一行字符串的最后开始向前寻找第一个空格 strpos=0; pos-; while (strpos!= ) pos-;/继续向前寻找第二个空格 if (strcmp(str+pos+1,no)=0) return 0; return 1;,参考源代码,int main() int i,j,n; while (1) scanf(%d, ,参考源代码,int cnt2=0;/存放两队点球比分
13、for (i=0;i(n+1)/2;i+) printf(%d ,i+1);/输出点球进行的回合数量，之间空格隔开 printf(Scoren); for (i=0;i2;i+) for (j=0;j(n+1)/2;j+) if (boardji=1) printf(O ); cnti+; else if (boardji=2) printf(X ); else printf(- ); printf(%dn,cnti); return 0;,CDOJ_1048 Clock http:/,Description Clock is invented by ancient Arabic engine
14、ers and which contributes to build the concept of accurate time for us human beings and even could be essential tool that widely used in industry, business and our routine lives. Nevertheless, the ideology of clock turns out to be quite simply that even make sense to little kids. We could hardly ima
15、gine that how do Arabic wisdom come up with such idea to indicate time only by two or three fingers.,The other day, hhb are asking lxh and Hysramp to play his newly invented game describe as follow. hhb randomly change the time of his lovely alarm clock then ask lxh and Hysramp to tell the degree be
16、tween hour finger and minute finger. lxh seems quite gifted playing it while Hysramp does not. When Hysramp fails to answer hhb, hhb smiles to Hysramp. And Hysramp smiles to you, an ace programmer.,Input The first line of the input contains one integer T, which indicate the number of test cases. Eac
17、h test case contains one indicating the time on hhbs clock in the form of HH:MM. (0=HH 24, 0=MM 60)Output One line for each test case contains only one number indicating the answer. An integer or an irreducible fraction indicated the degree between hour finger and minute finger.,Sample Input 100:00S
18、ample Output 0,怎么才能计算出时针和分针之间的夹角?直接算注意：1、答案是整数或不可约分数 2、答案在0, 180之间,#includeint main()int t,p, hh,mm, sh,sm, res;scanf(%d,CDOJ_1049 Flagstonehttp:/,Description In the Qingshuihe Campus of UESTC, the most annoy problem to students are the flagstone path on the lawn. The designer seems so stupid that t
19、he flagstone path often make students step in the gap. Now a perfect step is wanted in order to not step in any gaps and step on every flagstone. The step length is required to be constant while the length of the flagstone and gap are given different. The problem is asking you to tell the minimum le
20、ngth of the perfect step. To simplify the question, the foot is considered to be a point and the very beginning is the fore edge of the first flagstone, which also means the first flagstone has already been stepped on.,Input The first line of the input contains one integer T, which indicate the numb
21、er of test cases. In each test case, the first line contains an integer N(2=N=1e5), indicating the number of flagstone. Following N lines, and each line is the length of one flagstone. And the following N-1 lines are the length of the gaps. All data is integer. All the length will be a positive inte
22、ger, and the sum of them will fit in a 32bit signed integer.Output One line for each test case contains only one number indicating the answer. One real number indicating the perfect step length should be accurate to two digits after the radix point. If it is impossible to find out a perfect step, ju
23、st output “impossible” !,Sample Input 2 21020531020551000Sample Output 15.00impossible,每个石板踏且仅踏一次 对于第 i 块石板，一定是踏了 i - 1 步到达的。设第 i 块石板的左边界和右边界离起点的距离分别为L和R，可以确定步长必须在区间L / (i - 1), R / (i - 1)之内。问题转化为求多个区间的交。如果交集为空，则答案为impossible，否则输出交区间的左界。,#includeint a100001;int b100001;int main()int t,p;int n,i;dou
24、ble h,l;double hh,ll;double s;scanf(%d,s=0;l=a1+b1;h=a1+b1+a2;for (i=1;il) l=ll;if (hhh) h=hh;if (l=h) printf(%.2lfn,l);else printf(impossiblen);return 0;,CDOJ_1043 输出前m大的数据 http:/,Problem Description 给你n个整数，请按从大到小的顺序输出其中前m大的数。Input 每组测试数据有两行，第一行有两个数n,m(0n,m1000000)，第二行包含n个各不相同，且都处于区间-500000,500000的
25、整数。Output 对每组测试数据按从大到小的顺序输出前m大的数。,Sample input: 5 3 3 -35 92 213 -644 Sample output: 213 92 3,常规的思想是？常规的结果是？数据的特点是？加速的方法是？如果数据可以重复呢？,用最好的排序TLE各不相同 HASH处理冲突,#include #include #define N 1000000int aN;int main(void) int i,j,n,m,t; while(scanf(%d%d,CDOJ_1010 最短路http:/,Description 在每年的校赛里，所有进入决赛的同学都会获得一件
26、很漂亮的T-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？,Input 输入包括多组数据。每组数据第一行是两个整数N、M（N=100，M=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1=A,B=N,1=C=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。 Output 对
27、于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间,Sample Input 2 11 2 33 31 2 52 3 53 1 20 0 Sample Output 3 2,Dijkstra算法,Dijkstra算法能求一个顶点到另一顶点最短路径。它是由Dijkstra于1959年提出的。实际它能出始点到其它所有顶点的最短路径。 Dijkstra算法是一种标号法：给赋权图的每一个顶点记一个数，称为顶点的标号（临时标号，称T标号，或者固定标号，称为P标号）。T标号表示从始顶点到该标点的最短路长的上界；P标号则是从始顶点到该顶点的最短路长。 Dijkstra算法步骤如下：,Dijkstra
28、算法,-固定编号，下标表示前趋顶点,-临时编号，下标表示前趋顶点,解最短路问题的基本方法-Dijkstra算法,把以顶点及其前趋顶点作为端点的边作为一个集合，该边集导出的子图是一个生成树。,该生成树是否是最小生成树？,#include using namespace std;int map110110;/存放邻接矩阵#define INF 10000000 /表示无穷int main() int n,m; while (1) scanf(%d%d, /全标为,for (int ct0=0;ct0m;ct0+) int a,b,c; scanf(%d%d%d,for (int ct1=0;ct1n;ct1+) if (fct1=0 /表示已找到至某一个路口的最短路,for (int ct1=0;ct1=INF)/至赛场的距离为无穷 printf(Impossiblen); else printf(%dn,disn-1); return 0;,
