簡單計算題二

第三講

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

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

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

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

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

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

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

假設不會有一桿同時打進一顆黑球和其他彩球。Input

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

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

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

RYRRB

9

RRRRYRRRB

0SampleOutputYellow

Red2008年校賽最簡單的題目。只需要判斷最后一個球是誰打進的，然后統(tǒng)計這個人自己的球是不是已經全部打進了，就可以得到答案。#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)計打進球的數(shù)量

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

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

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

}else//最后一個球是黃方打進的黑球

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

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

elseflag=1;//否則紅方勝

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

Description

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

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

XXXXgood：表示這個點球罰進

或者XXXXnogood：表示這個點球沒有罰進

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

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

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

good、nogood都是小寫。本題是大小寫相關的。

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

對每組數(shù)據(jù)，輸出一個比分板。一個點球如果罰進，則在對應的地方標上’O’，如果沒有進則標上’X’。先罰球的隊伍的信息在上面，后罰的在下面。最右邊標上兩隊的比分。具體格式參考樣例輸出。注意如果一輪點球只罰了一個，則后面那個點球對應的地方寫上’-’。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（事實上，大部分數(shù)據(jù)都包含no和good中的至少一個），所以此題比較好的處理方法是找跳過名字，直接找倒數(shù)第二個單詞，看它是不是no，是就是沒踢進，反之就是踢進；數(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))//判斷是否踢進點球

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

for(intct0=0;ct0<(n+1)/2;ct0++)printf("%d",ct0+1);//輸出點球進行的回合數(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ù)或不可約分數(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步到達的。設第i塊石板的左界和右界離起點的距離L,R，可以確定步長必須在區(qū)間[L/(i-1),R/(i-1)]之內。問題轉化為求多個區(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%的期中測試成績還有什么好擔心的。希望在下周一的網(wǎng)絡賽場上見到教室中的每一位同學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ī)的結果是？數(shù)據(jù)的特點是？加速的方法是？如果數(shù)據(jù)可以重復呢？用最好的排序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]++;//下標對應數(shù)+N/2，元素值存儲重復次數(shù)

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

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

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

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

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

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

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

輸入包括多組數(shù)據(jù)。每組數(shù)據(jù)第一行是兩個整數(shù)N、M（N<=100，M<=10000），N表示成都的大街上有幾個路口，標號為1的路口是商店所在地，標號為N的路口是賽場所在地，M則表示在成都有幾條路。N=M=0表示輸入結束。接下來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;}}