ACM初步-簡(jiǎn)單數(shù)據(jù)處理問(wèn)題

ACM初步

---第二講簡(jiǎn)單數(shù)據(jù)處理問(wèn)題計(jì)算機(jī)科學(xué)與工程學(xué)院開(kāi)胃羹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ì)簡(jiǎn)單（有些很難的?。。┚幊瘫容^容易ACM/ICPC入門(mén)練習(xí)的好選擇下面，分類(lèi)介紹：最大公約數(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電梯問(wèn)題：Hdoj-1008問(wèn)題描述

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

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

對(duì)每組測(cè)試數(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問(wèn)題描述：一個(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.輸入：輸入包括多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)包括一個(gè)正整數(shù)，并且占一行，輸入數(shù)據(jù)為0時(shí)，表示輸入結(jié)束。輸出：對(duì)于每組測(cè)試數(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問(wèn)題描述：大數(shù)的位數(shù) 在很多應(yīng)用中會(huì)涉及大數(shù)的位數(shù)問(wèn)題，例如在數(shù)據(jù)傳輸、密碼等應(yīng)用中。現(xiàn)在給出一個(gè)整數(shù)，你來(lái)確定這個(gè)數(shù)的階乘的位數(shù)。輸入： 輸入包含多行數(shù)據(jù)，第一行為整數(shù)n，表示共有n組測(cè)試數(shù)據(jù)，接下來(lái)的n行中，每行為一個(gè)大于等于1并且小于等于pow(10,7)的整數(shù)。

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

2 10 20

輸出樣例：

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

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

5003 150300 100200 470471輸出樣例：

298問(wèn)題描述：會(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)過(guò)37，這時(shí)就產(chǎn)生了循環(huán)。設(shè)計(jì)一個(gè)程序，對(duì)給定的一個(gè)數(shù)，打印出到出現(xiàn)循環(huán)為止的所有數(shù)。輸入： 輸入包括多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)占一行并且只有一個(gè)正整數(shù)m（m<10,000,000），當(dāng)m=0時(shí)表示輸入結(jié)束。輸出： 對(duì)每組測(cè)試數(shù)字輸出一行結(jié)果，結(jié)果中包括到第一次產(chǎn)生循環(huán)時(shí)的所有整數(shù)。輸入樣例：

1234 0輸出樣例：

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

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