簡單計算題二

第三講

簡單計算題（二）ACM算法與程序設(shè)計2023/5/152關(guān)于本次比賽電子科技大學(xué)第十三屆程序設(shè)計競賽暨西南地區(qū)高校邀請賽參賽選手來自電子科技大學(xué)在讀學(xué)生（包括本科生、碩士和博士）決賽會邀請來自西南地區(qū)高校的ACM-ICPC專業(yè)隊伍參加，但不參與校內(nèi)評獎2023/5/153關(guān)于本次比賽報名報名時間：3月27日晚9點截止。

務(wù)必保證填寫的個人信息真實，被拒絕參賽的隊伍可能是因為填寫信息有誤或不完整。通過審核的隊伍用注冊的帳號和密碼登錄CDOJ參加比賽。若有任何疑問/尋求組隊可以在的此次競賽專區(qū)發(fā)貼。2023/5/154關(guān)于本次比賽初賽時間：3月28號星期六上午9：00～晚上9：00初賽采用網(wǎng)絡(luò)賽形式，地址初賽排名約前50左右的隊伍有機(jī)會晉級決賽The13thUESTCProgrammingContestWarmup1 2012-03-2109:00:00~21:00:00The13thUESTCProgrammingContestWarmup2 2012-03-2616:20:00~21:20:00初賽期間，我們給使用電腦不方便的同學(xué)開放科研2號樓208作為比賽機(jī)房。初賽后公布所有選手代碼，供交流和學(xué)習(xí)。嚴(yán)查作弊，組委會判定代碼雷同的選手將取消其成績。2023/5/155關(guān)于本次比賽決賽時間：4月4日星期四13：00–18：00地點：清水河校區(qū)科A227、229決賽會邀請來自西南地區(qū)高校的ACM/ICPC專業(yè)隊伍參加。外校隊伍不參與校內(nèi)評獎2023/5/156關(guān)于本次比賽獎項設(shè)置

1.晉級決賽的同學(xué)將獲得紀(jì)念T-shirt 2.獲獎隊員發(fā)給證書，作為學(xué)校評定獎學(xué)金加分與創(chuàng)新學(xué)分的依據(jù)。

3.比賽成績會作為校ACM-ICPC隊員選拔的重要依據(jù)

4.表現(xiàn)突出的選手，將有機(jī)會代表電子科技大學(xué)參加2015年四川省大學(xué)生程序設(shè)計競賽。

校賽后請各位報名參加比賽的同學(xué)將你們的比賽賬號和隊員姓名在課堂上進(jìn)行登記；根據(jù)初賽和決賽所完成的題目數(shù)量進(jìn)行打分，分?jǐn)?shù)成績將作為各位同學(xué)中期測試成績，約占期末總成績的20%，希望大家都能努力拼一把！校賽往年題目精選CDOJ_10048球勝負(fù)(eight)

Description8球是一種臺球競賽的規(guī)則。臺面上有7個紅球、7個黃球以及一個黑球，當(dāng)然還有一個白球。對于本題，我們使用如下的簡化規(guī)則：紅、黃兩名選手輪流用白球擊打各自顏色的球，如果將該顏色的7個球全部打進(jìn)，則這名選手可以打黑球，如果打進(jìn)則算他勝。如果在打進(jìn)自己顏色的所有球之前就把黑球打進(jìn)，則算輸。如果選手不慎打進(jìn)了對手的球，入球依然有效。現(xiàn)在給出打進(jìn)的球（白球除外）的順序，以及黑球由哪方打進(jìn)，你的任務(wù)是判定哪方是勝者。

假設(shè)不會有一桿同時打進(jìn)一顆黑球和其他彩球。Input

輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)第一行是一個整數(shù)N(1<=N<=15)，表示打進(jìn)的球的個數(shù)，N=0表示結(jié)束。隨后有一行，包含N個字符，依序表示打進(jìn)的是何種球。如果是’B’，表示是紅方打進(jìn)的黑球，如果是’L’，表示是黃方打進(jìn)的黑球。如果是’Y’則表示是黃球，’R’表示紅球。字符間沒有空格。

所有輸入都滿足如下條件：最后一顆球打進(jìn)時這局比賽正好結(jié)束，而且打進(jìn)的紅球和黑球都不超過7個。Output

對每組數(shù)據(jù)，輸出一行。如果紅方勝，輸出’Red’；黃方勝，輸出’Yellow’。SampleInput5

RYRRB

9

RRRRYRRRB

0SampleOutputYellow

Red2008年校賽最簡單的題目。只需要判斷最后一個球是誰打進(jìn)的，然后統(tǒng)計這個人自己的球是不是已經(jīng)全部打進(jìn)了，就可以得到答案。#include<stdio.h>#include<string.h>intmain(){intn;while(1){scanf("%d",&n);if(n==0)break;charstr[30];scanf("%s",str);intl=strlen(str)-1;//統(tǒng)計打進(jìn)球的數(shù)量

boolflag;if(str[l]=='B')//判斷最后一個球是不是紅方打進(jìn)的黑球

{intrc=0;for(intct0=0;ct0<l;ct0++)if(str[ct0]=='R')rc++;//統(tǒng)計黑球之前進(jìn)了幾個紅球

if(rc==7)flag=1;//進(jìn)了7個紅球則紅方勝elseflag=0;//否則黃方勝

}else//最后一個球是黃方打進(jìn)的黑球

{intrc=0;for(intct0=0;ct0<l;ct0++)if(str[ct0]=='Y')rc++;//統(tǒng)計黑球之前進(jìn)了幾個黃球

if(rc==7)flag=0;//進(jìn)了7個紅球則黃方勝

elseflag=1;//否則紅方勝

}if(flag)printf("Red\n");elseprintf("Yellow\n");}return0;}CDOJ_1005點球大戰(zhàn)(penalty)

Description

在足球比賽中，有不少賽事，例如世界杯淘汰賽和歐洲冠軍聯(lián)賽淘汰賽中，當(dāng)比賽雙方經(jīng)過正規(guī)比賽和加時賽之后仍然不分勝負(fù)時，需要進(jìn)行點球大戰(zhàn)來決定誰能夠獲得最終的勝利。點球大戰(zhàn)的規(guī)則非常簡單，兩方輪流派出球員罰點球，每方各罰5個。當(dāng)5輪點球結(jié)束以后如果仍然不分勝負(fù)，則進(jìn)入一輪定勝負(fù)的階段。兩方各派一名球員罰點球，直到有一方罰進(jìn)而另一方?jīng)]有進(jìn)為止。在北美職業(yè)冰球聯(lián)賽中，也有點球大戰(zhàn)。與足球的規(guī)則不同的是，它只先罰3輪點球，隨后就進(jìn)入一輪定勝負(fù)的階段，而其他的規(guī)則完全一樣。在本題中，輸入將給出每次點球是否罰進(jìn)，而你的任務(wù)則是輸出一個“比分板”。Input

輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第一行包含一個整數(shù)N(1<=N<=18)，表示雙方總共罰了多少個點球，N=0表示輸入結(jié)束。隨后有N行，每行是一個如下形式的字符串：

XXXXgood：表示這個點球罰進(jìn)

或者XXXXnogood：表示這個點球沒有罰進(jìn)

其中XXXX表示球員名字（全部由字母和空格組成，保證不會出現(xiàn)歧義）

每一行保證不超過100個字符。

XXXX和good以及XXXX和no、no和good之間保證有且只有1個空格。

good、nogood都是小寫。本題是大小寫相關(guān)的。

數(shù)據(jù)不保證點球大戰(zhàn)一定結(jié)束，也不保證在結(jié)束以后立即結(jié)束這組數(shù)據(jù)（即：不用判斷點球大戰(zhàn)是否結(jié)束，只用把罰進(jìn)的點球往比分上加即可）。Output

對每組數(shù)據(jù)，輸出一個比分板。一個點球如果罰進(jìn)，則在對應(yīng)的地方標(biāo)上’O’，如果沒有進(jìn)則標(biāo)上’X’。先罰球的隊伍的信息在上面，后罰的在下面。最右邊標(biāo)上兩隊的比分。具體格式參考樣例輸出。注意如果一輪點球只罰了一個，則后面那個點球?qū)?yīng)的地方寫上’-’。SampleInput6

Riisegood

Ballackgood

Gerrardnogood

Lampardnogood

FernandoTorresgood

Maloudagood

9

ChristianoRonaldonogood

Messinogood

Giggsgood

Abidalnogood

Carrickgood

Ronaldinhogood

Rooneygood

Henrynogood

Tevezgood

0SampleOutput123Score

OXO2

OXO2

12345Score

XOOOO4

XXOX-1名字可以包含空格，甚至可以包含no、good（事實上，大部分?jǐn)?shù)據(jù)都包含no和good中的至少一個），所以此題比較好的處理方法是找跳過名字，直接找倒數(shù)第二個單詞，看它是不是no，是就是沒踢進(jìn)，反之就是踢進(jìn)；數(shù)據(jù)出的很詭異，還有兩種特殊情況，一種是只有一個good，另一種是直接nogood。這兩組數(shù)據(jù)不是太滿足題意（第一組名字為空，第二組有歧義）空格數(shù)要和樣例輸出一樣，否則很可能會被判為“格式錯誤”(PresentationError)。#include<iostream>booljudge(char*str){intl=strlen(str);intpos=l-1;while(str[pos]!='')pos--;//從一行字符串的最后開始向前尋找第一個空格

str[pos]='\0';intnpos=pos-1;while(str[npos]!='')npos--;//繼續(xù)向前尋找第二個空格

if(strcmp(str+npos+1,"no")==0)return0;//比較從npos+1所指向的空格后的第一個字符開始到

//“\0”之間的字符串是否等同“no”return1;}參考源代碼intmain(){intn;while(1){scanf("%d",&n);if(n==0)break;intgg[15][2]={0};//至多15個回合，每回合兩隊各罰一次

charstr[110];gets(str);//掃描雙方罰點球的人數(shù)

for(intct0=0;ct0<n;ct0++){gets(str);//掃描一行罰點球信息

if(judge(str))//判斷是否踢進(jìn)點球

gg[ct0/2][ct0%2]=1;//1或2表示踢進(jìn)，否則為0elsegg[ct0/2][ct0%2]=2;}intcct[2]={0};//存放兩隊點球比分

for(intct0=0;ct0<(n+1)/2;ct0++)printf("%d",ct0+1);//輸出點球進(jìn)行的回合數(shù)量，之間空格隔開printf("Score\n");for(intct0=0;ct0<2;ct0++){for(intct1=0;ct1<(n+1)/2;ct1++){if(gg[ct1][ct0]==1){printf("O");cct[ct0]++;}elseif(gg[ct1][ct0]==2)printf("X");elseprintf("-");}printf("%d\n",cct[ct0]);}}return0;}CDOJ_1048Clock

Description

ClockisinventedbyancientArabicengineersandwhichcontributestobuildtheconceptofaccuratetimeforushumanbeingsandevencouldbeessentialtoolthatwidelyusedinindustry,businessandourroutinelives.Nevertheless,theideologyofclockturnsouttobequitesimplythatevenmakesensetolittlekids.WecouldhardlyimaginethathowdoArabicwisdomcomeupwithsuchideatoindicatetimeonlybytwoorthreefingers.Theotherday,hhbareaskinglxhandHysramptoplayhisnewlyinventedgamedescribeasfollow.hhbrandomlychangethetimeofhislovelyalarmclockthenasklxhandHysramptotellthedegreebetweenhourfingerandminutefinger.lxhseemsquitegiftedplayingitwhileHysrampdoesnot.WhenHysrampfailstoanswerhhb,hhbsmilestoHysramp.AndHysrampsmilestoyou,anaceprogrammer.Input

ThefirstlineoftheinputcontainsoneintegerT,whichindicatethenumberoftestcases.Eachtestcasecontainsoneindicatingthetimeonhhb’sclockintheformofHH:MM.(0<=HH<24,0<=MM<60)Output

Onelineforeachtestcasecontainsonlyonenumberindicatingtheanswer.Anintegeroranirreduciblefractionindicatedthedegreebetweenhourfingerandminutefinger.SampleInput1

00:00SampleOutput0怎么才能計算出時針和分針之間的夾角?直接算注意：1、答案是整數(shù)或不可約分?jǐn)?shù)2、答案在[0,180]之間#include<stdio.h>intmain(){ intt,p,hh,mm,sh,sm,res; scanf("%d",&t); for(p=1;p<=t;p++) { scanf("%d:%d",&hh,&mm); if(hh>=12) hh=hh-12; sh=hh*60+mm; sm=mm*12; if(sh>sm)res=sh-sm; elseres=sm-sh; if(res>=360)res=720-res; if(res%2==0)printf("%d\n",res/2); elseprintf("%d/2\n",res); } return0;}CDOJ_1049Flagstone

DescriptionIntheQingshuiheCampusofUESTC,themostannoyproblemtostudentsaretheflagstonepathonthelawn.Thedesignerseemssostupidthattheflagstonepathoftenmakestudentsstepinthegap.Nowaperfectstepiswantedinordertonotstepinanygapsandsteponeveryflagstone.Thesteplengthisrequiredtobeconstantwhilethelengthoftheflagstoneandgaparegivendifferent.Theproblemisaskingyoutotelltheminimumlengthoftheperfectstep.Tosimplifythequestion,thefootisconsideredtobeapointandtheverybeginningistheforeedgeofthefirstflagstone,whichalsomeansthefirstflagstonehasalreadybeensteppedon.InputThefirstlineoftheinputcontainsoneintegerT,whichindicatethenumberoftestcases.Ineachtestcase,thefirstlinecontainsanintegerN(2<=N<=1e5),indicatingthenumberofflagstone.FollowingNlines,andeachlineisthelengthofoneflagstone.AndthefollowingN-1linesarethelengthofthegaps.Alldataisinteger.Allthelengthwillbeapositiveinteger,andthesumofthemwillfitina32bitsignedinteger.OutputOnelineforeachtestcasecontainsonlyonenumberindicatingtheanswer.Onerealnumberindicatingtheperfectsteplengthshouldbeaccuratetotwodigitsaftertheradixpoint.Ifitisimpossibletofindoutaperfectstep,justoutput

“impossible”!SampleInput22

10

20

5

3

10

20

5

5

1000SampleOutput15.00

impossible每個石板踏且僅踏一次對于第i塊石板，一定是踏了i-1步到達(dá)的。設(shè)第i塊石板的左界和右界離起點的距離L,R，可以確定步長必須在區(qū)間[L/(i-1),R/(i-1)]之內(nèi)。問題轉(zhuǎn)化為求多個區(qū)間的交。如果交集為空，則答案為impossible，否則輸出交區(qū)間的左界。#include<stdio.h>inta[100001];intb[100001];intmain(){ intt,p; intn,i; doubleh,l; doublehh,ll; doubles; scanf("%d",&t); for(p=1;p<=t;p++) { scanf("%d",&n); for(i=1;i<=n;i++) scanf(“%d”,&a[i]);//n塊石板 for(i=1;i<n;i++) scanf(“%d”,&b[i]);//n-1個間隔 s=0; l=a[1]+b[1];//第二塊左邊界 h=a[1]+b[1]+a[2];//第二塊右邊界 for(i=1;i<n;i++) { s=s+a[i]+b[i]; ll=s/(double)i;//第i塊步長左區(qū)間 hh=(s+a[i+1])/(double)i;//第i塊右區(qū)間 if(ll>l)l=ll; if(hh<h)h=hh;//計算步長區(qū)間的交集 } if(l<=h)printf(“%.2lf\n”,l);//交集存在 elseprintf("impossible\n"); } return0;}這些題目都是近幾年的初賽題目，大家覺得難度如何？太簡單了！?。τ谖覀児x課的那20%的期中測試成績還有什么好擔(dān)心的。希望在下周一的網(wǎng)絡(luò)賽場上見到教室中的每一位同學(xué)CDOJ_1043輸出前m大的數(shù)據(jù)

ProblemDescription

給你n個整數(shù)，請按從大到小的順序輸出其中前m大的數(shù)。Input

每組測試數(shù)據(jù)有兩行，第一行有兩個數(shù)n,m(0<n,m<1000000)，第二行包含n個各不相同，且都處于區(qū)間[-500000,500000]的整數(shù)。Output

對每組測試數(shù)據(jù)按從大到小的順序輸出前m大的數(shù)。

Sampleinput:533-3592213-644Sampleoutput:213923HDOJ_1425

sort

常規(guī)的思想是？常規(guī)的結(jié)果是？數(shù)據(jù)的特點是？加速的方法是？如果數(shù)據(jù)可以重復(fù)呢？用最好的排序TLE各不相同HASH處理沖突#include<stdio.h>#include<string.h>#defineN1000000inta[N];intmain(void){inti,j,n,m,t;while(scanf("%d%d",&n,&m)==2){memset(a,0,N*sizeof(int));for(i=0;i<n;i++){scanf("%d",&t);a[t+N/2]++;//下標(biāo)對應(yīng)數(shù)+N/2，元素值存儲重復(fù)次數(shù)

}for(t=0,i=N-1;t<m&&i>=0;){if(a[i]>0)//對應(yīng)有數(shù)

{printf("%d",i-N/2);//打印對應(yīng)的數(shù)

t++;//計數(shù)器增加

if(--a[i]==0)i--;}elsei--;}printf("\n");}return0;}Hash表簡介——基本原理

哈希表（散列表）的基本原理： 使用一個下標(biāo)范圍比較大的數(shù)組來存儲元素，一般通過設(shè)計一個函數(shù)（哈希函數(shù)，即散列函數(shù)），使得每個元素的關(guān)鍵字都與一個函數(shù)值（即數(shù)組下標(biāo)）相對應(yīng)，然后用該數(shù)組單元來存儲對應(yīng)元素。Hash表簡介——函數(shù)構(gòu)造無定式，方法很多最常見的方法：除余法 H(k)=kmodp

(p一般選取適當(dāng)大的素數(shù))常用的經(jīng)典字符串Hash后面介紹Hash表簡介——沖突由于不能夠保證每個元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因此很有可能出現(xiàn)如下情況：“對于不同的元素關(guān)鍵字，Hash函數(shù)計算出了相同的函數(shù)值”，這就是產(chǎn)生了所謂的“沖突”。換句話說，就是Hash函數(shù)把不同的元素分在了相同的下標(biāo)單元。Hash表簡介——沖突解決 方法很多～ 常用方法：線性探測再散列技術(shù) 即：當(dāng)h(k)位置已經(jīng)存儲有元素的時候，依次探查(h(k)+i)modS,i=1,2,3…，直到找到空的存儲單元為止。其中，S為數(shù)組長度。 特別地，如果將數(shù)組掃描一圈仍未發(fā)現(xiàn)空單元，則說明哈希表已滿，這會帶來麻煩，但是，該情況完全可以通過擴(kuò)大數(shù)組范圍來避免。Hash表簡介——基本操作Hash表初始化（0或-1或其它）哈希函數(shù)運算插入元素（包含沖突解決）定位（需考慮可能沖突的情況）總結(jié)：Hash函數(shù)評價標(biāo)準(zhǔn)：低沖突率易于編碼Hash函數(shù)特點：優(yōu)點：數(shù)據(jù)存儲和查找效率高 （幾乎是常數(shù)時間）缺點：消耗較多內(nèi)存（內(nèi)存很便宜哪～）Hash主要應(yīng)用：查找元素是否屬于集合搜索中的狀態(tài)表示

整數(shù)Hash

例1(HDOJ-1496Equations)Considerequationshavingthefollowingform:a*x12+b*x22+c*x32+d*x42=0

a,b,c,dareintegersfromtheinterval[-50,50]andanyofthemcannotbe0.Itisconsiderasolutionasystem(x1,x2,x3,x4)thatverifiestheequation,xiisanintegerfrom[-100,100]andxi!=0,anyi∈{1,2,3,4}.Determinehowmanysolutionssatisfythegivenequation.HDOJ-1496題目分析題意簡單（類似“百錢買百雞”問題）傳統(tǒng)方法是（幾重循環(huán)）？復(fù)雜度？上述方法如何判斷兩端相等？（查找？）可行方案（兩重循環(huán)＋Hash存儲查找）Hash表大?。縃DOJ-1496參考代碼（1）//bylinle#include"stdio.h"#include"memory.h"intpin[101];inthash[2000003];intmain(){inta,b,c,d;inti,j,sum;for(i=1;i<101;i++)pin[i]=i*i;while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF){……}}if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)){printf("0\n");continue;}memset(hash,0,sizeof(hash));for(i=1;i<=100;i++)for(j=1;j<=100;j++)hash[a*pin[i]+b*pin[j]+1000000]++;sum=0;for(i=1;i<=100;i++)for(j=1;j<=100;j++)sum+=hash[-(c*pin[i]+d*pin[j])+1000000];printf("%d\n",sum*16);CDOJ_1010最短路

Description

在每年的校賽里，所有進(jìn)入決賽的同學(xué)都會獲得一件很漂亮的t-shirt。但是每當(dāng)我們的工作人員把上百件的衣服從商店運回到賽場的時候，卻是非常累的！所以現(xiàn)在他們想要尋找最短的從商店到賽場的路線，你可以幫助他們嗎？Input

輸入包括多組數(shù)據(jù)。每組數(shù)據(jù)第一行是兩個整數(shù)N、M（N<=100，M<=10000），N表示成都的大街上有幾個路口，標(biāo)號為1的路口是商店所在地，標(biāo)號為N的路口是賽場所在地，M則表示在成都有幾條路。N=M=0表示輸入結(jié)束。接下來M行，每行包括3個整數(shù)A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A與路口B之間有一條路，我們的工作人員需要C分鐘的時間走過這條路。

輸入保證至少存在1條商店到賽場的路線。

Output

對于每組輸入，輸出一行，表示工作人員從商店走到賽場的最短時間SampleInput

21

123

33

125

235

312

00

SampleOutput3

2#include<iostream>usingnamespacestd;intmap[110][110];//存放鄰接矩陣#defineINF10000000//表示無窮intmain(){intn,m;while(1){scanf("%d%d",&n,&m);if(n==0&&m==0)break;for(intct0=0;ct0<110;ct0++){for(intct1=0;ct1<110;ct1++){map[ct0][ct1]=INF;}}