ACM初步

---第二講簡單數(shù)據(jù)處理問題計(jì)算機(jī)科學(xué)與工程學(xué)院開胃羹1、integer整數(shù)2、positive正的3、negative(adj)負(fù)的;(n)負(fù)數(shù)4、factorial(n)階乘;(adj)因子的，階乘的5、digital(n)數(shù)字;(adj)數(shù)字的ACM數(shù)學(xué)題特點(diǎn)分析:題意容易理解算法相對(duì)簡單（有些很難的?。。┚幊瘫容^容易ACM/ICPC入門練習(xí)的好選擇下面，分類介紹：最大公約數(shù)、最小公倍數(shù)(hdoj_1108、1019)gcd(a,b)=gcd(a,bmoda)gcd(a1,a2,a3)=gcd(gcd(a1,a2),a3)gcd(a1,a2,a3,a4)=gcd(gcd(a1,a2,a3),a4)lcm(a,b)=a*b/gcd(a,b)1008:Elevator電梯問題：Hdoj-1008問題描述

在城市的高層建筑物中只有一部電梯，由N個(gè)正整數(shù)組成一個(gè)請(qǐng)求列表，列表中的數(shù)字表示電梯將在哪層停，電梯按列表順序依次?？俊ｋ娞菝可闲幸粚有枰?秒時(shí)間，每下行一層需要花4秒時(shí)間，電梯每停一次需要用時(shí)5秒。對(duì)于給定的請(qǐng)求列表，計(jì)算完成所有請(qǐng)求需要花費(fèi)的時(shí)間，電梯從第0層開始，完成所有請(qǐng)求后又回到第0層。輸入

輸入包括多組測試數(shù)據(jù)，每組測試數(shù)據(jù)占一行，其中第一個(gè)正整數(shù)N，表示該請(qǐng)求列表中有N個(gè)數(shù)據(jù)，接下來是N個(gè)整數(shù)；如果N=0，則表示輸入結(jié)束。輸出

對(duì)每組測試數(shù)據(jù)，輸出完成列表所有請(qǐng)求的總時(shí)間，每個(gè)結(jié)果占一行。#include<stdio.h>intmain(){ inti,n,tm,from,to;

while(1) { scanf("%d",&n); if(n==0)break; tm=0; from=0; for(i=0;i<n;i++) { scanf("%d",&to); if(from<to)tm+=(to-from)*6+5; elsetm+=(from-to)*4+5; from=to; } printf("%d\n",tm); }

return0; }發(fā)工資咯Hdoj_2021/showproblem.php?pid=2021#include<stdio.h>intmain(){ intn,m,count,c100,c50,c10,c5,c2,c1; while(1) { scanf("%d",&n); if(n==0)break; count=0; for(;n>0;n--) { scanf("%d",&m); c100=m/100; c50=m%100/50; c10=m%100%50/10; c5=m%100%50%10/5; c2=m%100%50%10%5/2; c1=m%100%50%10%5%2; count+=c100+c50+c10+c5+c2+c1; } printf("%d\n",count); } return0;}數(shù)根：Hdoj-1013問題描述：一個(gè)正整數(shù)的數(shù)根可以這樣求得：計(jì)算該整數(shù)的各位數(shù)字之和，如果結(jié)果值是單個(gè)數(shù)字的數(shù)，那么這個(gè)數(shù)就是所求數(shù)根；如果結(jié)果值是由兩位或兩位以上的數(shù)字組成的數(shù)，則繼續(xù)計(jì)算各位數(shù)字的和，直到結(jié)果值只有一位數(shù)字為止。 例如：正整數(shù)24,2+4=6，則6為24的根。 又如：正整數(shù)39,3+9=12，由于12不是單個(gè)數(shù)字組成的數(shù)，所以繼續(xù)計(jì)算，1+2=3，所以39的根為3.輸入：輸入包括多組測試數(shù)據(jù)，每組測試數(shù)據(jù)包括一個(gè)正整數(shù)，并且占一行，輸入數(shù)據(jù)為0時(shí)，表示輸入結(jié)束。輸出：對(duì)于每組測試數(shù)據(jù)，給出對(duì)應(yīng)輸出，并且每組輸出占一行。#include<stdio.h>intmain(){ longsum,n; while(1) { scanf("%ld",&n);

if(n==0)break; do{ sum=0; while(n>0) { sum+=n%10; n/=10; } n=sum; }while(n>=10); printf("%ld\n",sum); } return0; }數(shù)根：Hdoj-1018問題描述：大數(shù)的位數(shù) 在很多應(yīng)用中會(huì)涉及大數(shù)的位數(shù)問題，例如在數(shù)據(jù)傳輸、密碼等應(yīng)用中?，F(xiàn)在給出一個(gè)整數(shù)，你來確定這個(gè)數(shù)的階乘的位數(shù)。輸入： 輸入包含多行數(shù)據(jù)，第一行為整數(shù)n，表示共有n組測試數(shù)據(jù)，接下來的n行中，每行為一個(gè)大于等于1并且小于等于pow(10,7)的整數(shù)。

輸出： 對(duì)應(yīng)每個(gè)輸入數(shù)據(jù)輸出一個(gè)結(jié)果，并且每個(gè)結(jié)果占一行。輸入樣例：

2 10 20

輸出樣例：

7 19問題分析：數(shù)學(xué)知識(shí)：一個(gè)數(shù)N，取其以10為底的對(duì)數(shù)并取整，得到的值為整數(shù)N的位長減1。

n!=1*2*...*n log10(n!)=log10(1)+log10(2)+...+log10(n)#include<stdio.h>#include<math.h>intmain(){ longn,i,m; doublesum;

while(scanf("%d",&n)!=EOF) { for(;n>0;n--) { scanf("%ld",&m); sum=1.0; for(i=1;i<=m;i++)sum+=log10(i); printf("%ld\n",(long)sum); } }

return0;}問題描述：路邊的樹 長度為L的路邊有一排樹，相鄰樹之間的間隔都是1米。我們可以把馬路看成一個(gè)數(shù)軸，馬路的一端在數(shù)軸0的位置，另一端在L的位置；數(shù)軸上的每個(gè)整數(shù)點(diǎn)，即0,1,2，...，L，都種有一棵樹。 現(xiàn)在馬路上有一些區(qū)域要用來建地鐵，這些區(qū)域用它們在數(shù)軸上的起始點(diǎn)和終止點(diǎn)表示。 已知有M個(gè)區(qū)域需要修建地鐵，區(qū)域之間可能有重合的部分?，F(xiàn)在要把這些區(qū)域中的樹（包括區(qū)域端點(diǎn)處的兩棵樹）移走。你的任務(wù)是計(jì)算將這些樹都移走后，馬路上還有多少棵樹。輸入： 輸入包含多組測試數(shù)據(jù)，每組測試數(shù)據(jù)的第一行有兩個(gè)整數(shù)L（1<=L<=10000）和M（1<=M<=100），L代表馬路的長度，M代表區(qū)域的數(shù)目，L和M之間用一個(gè)空格隔開。接下來的M行，每行包含兩個(gè)不同的整數(shù)，用一個(gè)空格隔開，表示一個(gè)區(qū)域的起始點(diǎn)和終止點(diǎn)的坐標(biāo)。

輸出： 對(duì)于每組測試數(shù)據(jù)，輸出包括一行，這一行只包含一個(gè)整數(shù)，表示馬路上剩余的樹的數(shù)目。輸入樣例：

5003 150300 100200 470471輸出樣例：

298問題描述：會(huì)繞圈的數(shù)

任意一個(gè)正整數(shù)，把它的每一位數(shù)字都平方后相加得到一個(gè)數(shù)；將這個(gè)數(shù)的每一位數(shù)字再平方相加；依次進(jìn)行就會(huì)產(chǎn)生循環(huán)現(xiàn)象。例如：1234。

1^2+2^2+3^2+4^2=1+4+9+16=30 3^2+0^2=9+0=9 9^2=81 8^2+1^2=64+1=65 6^2+5^2=36+25=61 6^2+1^2=36+1=37 3^2+7^2=9+49=58 5^2+8^2=25+64=89 8^2+9^2=64+81=145 1^2+4^2+5^2=1+16+25=42 4^2+2^2=16+4=20 2^2+0^2=4+0=4 4^2=16 1^2+6^2=1+36=37

由于前面已經(jīng)出現(xiàn)過37，這時(shí)就產(chǎn)生了循環(huán)。設(shè)計(jì)一個(gè)程序，對(duì)給定的一個(gè)數(shù)，打印出到出現(xiàn)循環(huán)為止的所有數(shù)。輸入： 輸入包括多組測試數(shù)據(jù)，每組測試數(shù)據(jù)占一行并且只有一個(gè)正整數(shù)m（m<10,000,000），當(dāng)m=0時(shí)表示輸入結(jié)束。輸出： 對(duì)每組測試數(shù)字輸出一行結(jié)果，結(jié)果中包括到第一次產(chǎn)生循環(huán)時(shí)的所有整數(shù)。輸入樣例：

1234 0輸出樣例：

1234309816561375889145422041637問題分析： 兩個(gè)關(guān)鍵問題： （1）對(duì)一個(gè)整數(shù)求其各位數(shù)字的平方和； （2）在已經(jīng)產(chǎn)生的結(jié)果中查找當(dāng)前值是否已經(jīng)出現(xiàn)過。問題描述：競賽排名

4名同學(xué)同時(shí)參加了競賽，公布成績后發(fā)現(xiàn)4名同學(xué)的成績彼此互不相同。 甲說：我成績最好，乙成績最差，丙排第三。 乙說：我成績最好，甲成績最差，丙排第二，丁排第三。