《简单计算题三.ppt》由会员分享，可在线阅读，更多相关《简单计算题三.ppt（41页珍藏版）》请在三一办公上搜索。
1、第三讲,简单计算题（二）,ACM算法与程序设计,初赛完成情况统计,通过4题：Team280110 通过3题：8311，Wzlxdzjy，xygy8860 通过2题：Supermokey369，zhlean，2804302029，clstone,wulidianzixueyuan通过1题：w180285，Taozle123，JAG未过题：zhengguifu，wanglikai91，luojiangbo,fuhang8902317,Ants Run!,Description Professor Yang likes to play with ants when he is free.What?A
2、re you asking why he plays with ants instead of others?Ah,because ant is the only non-plant living thing which can be found in Qingshuihe Campus of UESTC apart from human beings.This time,Professor Yang caught several ants after finishing his lecture for freshmen.At the beginning of the game,he puts
3、 N ants around a plate and numbers them in clockwise order.The ants are so obedient that they run clockwise under the guide of Professor Yang on the boundary of the plate which is a circle.When one ant catches up with its previous ant,the game is over.Knowing the speed of ants,Professor Yang wants y
4、ou to help him to adjust the distance between adjacent ants to make the game last longer.,Input The first line of the input is T(no more than 10000),which stands for the number of test cases you need to solve.Each test case begins with“N R”(without quotes)representing the number of ants participatin
5、g the game is N and the radius of the circle is R cm.The next line lists N integers and the i-th number is the speed(cm/s)of the i-th ant in clockwise direction.All numbers are positive integer not larger than 20.Output If the game can last forever,print“Inf”in a single line,otherwise please output
6、the longest time in seconds each game can last,which should be printed accurately rounded to three decimals.,Sample Input 23 11 1 13 13 2 1Sample Output Inf3.142,在样例中，3只蚂蚁连环追,第一只追第二只第二只追第三只第三只追不上第一只所有蚂蚁都是相同速度则inf最最关键的是Pi，如何计算（造成Wrong Answer的主要原因）acos(-1.0),#include#include doublepi=acos(-1.0);intv30
7、;intmain()intt,p,n,i;doubler;scanf(%d,Archimedes,Description Mr.Wang has got a ball made of a certain kind of metal(assume the ball is uniform density).He wants to find out what the metal is by calculating the density of the ball.Mr.Wang follows the story of Archimedes and crown.By putting the ball
8、in the liquid(assume the liquid is deep enough).Mr.Wang can measure the height h indicated in the image.And the density of the liquid is d,the radius of the ball is R.Now Mr.Wang asks you to simply tell the density of the ball.You can assume the density of the ball is no greater than the liquid.h me
9、asures the height from the bottom of the ball to the liquid surface.,Input The input has many test cases.The first line is an integer T indicating the number of test cases.Following T lines there are three real numbers h,R,d.(0 h=100,0 R=50,0 d=100)Output For each test case,output one line with the
10、answer,the density of the ball.round to 0.01.Please refer to the sample output.,Sample Input 29 9 19 8 1Sample Output 0.500.59,整理得:,最最关键的是若小球不是漂浮，而是悬浮在水中（造成Wrong Answer的主要原因）,#include#include double r;int main()int t,p;double h,d,v;scanf(%d,Flagstone Walk,Description There is a long flagstone walk o
11、n the way from the dormitory to the main hall.This flagstone walk has N lines and four flagstones arranged in each line.Hongshu always start from rightmost flagstone of the first line.In order to make this walk funny,he would always step onto the left or right flagstone in the next line if there is.
12、For example,if Hongshu stands at the second rightmost flagstone of the third line,he would choose to step to the first or third rightmost one of the forth line.Note that Hongshu has only one choice when he is at the corner of one line.,Because Hongshu has to go to the main hall every day,he wants to
13、 know how many different ways to step across the flagstone walk.Can you help him?,Input The first line of the input is an integer T(T=20),which stands for the number of test cases you need to solve.Each case consists of an integer N(1=N=20)on a single line,which stands for the length of the walk.Out
14、put For each case,print the number of ways on a single line.,Sample Input 3 2 3 4 Sample Output 1 2 3,DP11=1 DP22=DP31+DP11=1DP33=DP42+DP22=1DP13=DP22=1DP44=DP33=1DP24=DP33+DP13=2,DP11=1DP 1 i=DP 2 i 1 DP 2 i=DP 1 i 1+DP 3 i 1 DP 3 i=DP 2 i 1+DP 4 i 1 DP 4 i=DP 3 i 1,1,1,1,1,1,1,2,#include intmain()
15、inti,j,k,n,m,tot,a2121;scanf(%d,思考：此题的输出结果有没有什么规律,CDOJ_1043 输出前m大的数据 http:/,Problem Description 给你n个整数，请按从大到小的顺序输出其中前m大的数。Input 每组测试数据有两行，第一行有两个数n,m(0n,m1000000)，第二行包含n个各不相同，且都处于区间-500000,500000的整数。Output 对每组测试数据按从大到小的顺序输出前m大的数。,Sample input:5 3 3-35 92 213-644 Sample output:213 92 3,HDOJ_1425 sort,
16、常规的思想是？常规的结果是？数据的特点是？加速的方法是？如果数据可以重复呢？,用最好的排序TLE各不相同 HASH处理冲突,#include#include#define N 1000000int aN;int main(void)int i,j,n,m,t;while(scanf(%d%d,Fly Through,Description The home of flower fairies is being devastated by a monster called Littlefatcat.They have to leave the place where their generati
17、ons lived with no other choices.CC,the greatest investigator of flower fairies,found a paradise in the west and will lead all the flower fairies there.This paradise is full of flowers and safe from attack of Littlefatcat.However,there are lots of huge rocks on the way to the paradise.,Flower fairies
18、 are of different levels which are determined by their power.Fairies of higher level will fly higher.A fairy will persist in flying at the height corresponding to his or her level for honor and self-respect.Also,rocks on the way have specific height.When the route of a fairy hit a rock,the fairy wil
19、l have to use magic to fly through the rock.Being aware of the height of all rocks and the specific height each fairy can fly at,CC want to know how many rocks each fairy will fly through.,fly through,Input The first line will be“N M”(without quotes),representing for the numbers of rocks and fairies
20、.The following line will give N numbers,giving the height of the rocks from the east to west.Then M lines followed.On the i-th line,a number representing the specific height of fairy numbered i can fly at will be given.All numbers are positive and not bigger than 100000.Output Please output the numb
21、er of rocks each fairy has to fly through in order to get to the paradise in a single line.,Sample Input 5 31 2 3 4 5246Sample Output 420,这个问题相当于问在一组数中有多少个是大于等于i的。All numbers are positive and not bigger than 100000.Time Limit:1000ms.普通的方法可能会导致Time Limit Exceed，时间复杂度应该控制在O(nlogn)。方法：先排序，再二分法找插入位置 STL
22、。看看专业队员的编程,#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include,这就是专业级别的事先准备工作,usingnamespacestd;intdata100005;intmain()/全程STL intn,m;while(scanf(%d%d,The lower_bound()
23、algorithm compares a supplied value to elements in a sorted sequence and returns the first position in the container at which value can be inserted without violating the containers ordering.,再来看看哈希的实现,#include#include inta100001,b100001;intmain()intn,m,i,j;memset(b,0,10001*sizeof(int);scanf(%d%d,人见人
24、爱AB,求AB的最后三位数表示的整数（1=A,B=10000）2 3 12 6 8 984,快速求幂,3 999=3*3*3*3 3 2=3*33 4=(3 2)*(3 2)3 8=(3 4)*(3 4)3 16=(3 8)*(3 8)3 32=(3 16)*(3 16)3 64=(3 32)*(3 32)3 128=(3 64)*(3 64)3 256=(3 128)*(3 128)3 512=(3 256)*(3 256),3 999=3(512+256+128+64+32+4+2+1)=(3 512)*(3 256)*(3 128)*(3 64)*(3 32)*(3 4)*(3 2)*3
25、惊人的发现：999对应的2进制数：1111100111,参考程序：int modexp(int a,int b,int n)int t=1;while(b!=0)if(b%2=1)/if(b,http:/,CDOJ_1010 最短路http:/,Description 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？,Input 输入包括多组数据。每组数据第一行是两个整数N、M（N=100，M=10000），N表示成都的大街上有几个路口
26、，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1=A,B=N,1=C=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。输入保证至少存在1条商店到赛场的路线。Output 对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间,Sample Input 2 11 2 33 31 2 52 3 53 1 20 0 Sample Output 3 2,#include using namespace std;int map110110;/存放邻接矩阵#de
27、fine 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,/表示未被访问的路口,dis0=0;for(int ct0=0;ct0n;ct0+)int minp=-1;int mind=INF;for(int ct1=0;ct1n;ct1+)if(fct1=0/若已走到赛场则结束,fminp=1;/表示已找到至某一个路口的最短路 for(int ct1=0;ct1=INF)/至赛场的距离为无穷 printf(Impossiblen);else printf(%dn,disn-1);return 0;,
