4.4 竞赛题目选讲
競(jìng)賽題目選講
這里的題目可能和大家在做的實(shí)驗(yàn)項(xiàng)目有些不太一樣，希望大家根據(jù)自己的需要閱讀本章節(jié)。
4-2 劊子手游戲 (UVA 489)
書上的題面少了一些很重要的東西，真正的題面請(qǐng)點(diǎn)開這里
分析：根據(jù)我還沒有過四級(jí)的英語來看，大致的意思是這樣的。就是給你兩個(gè)字符串，第一個(gè)字符串為計(jì)算機(jī)想出的字符串，第二個(gè)為玩家猜的。按照第二個(gè)字符串的字符順序每次猜第二個(gè)字符串的一個(gè)字符，如果第一個(gè)字符串里有這個(gè)字符，所有該字符會(huì)顯現(xiàn)出來，而你最多猜錯(cuò)6次。如果猜錯(cuò)超過六次，即算輸，如果所有的字符顯現(xiàn)出來，即算贏(根據(jù)給出的代碼來看，如果你猜了重復(fù)的字符，那么第二次猜即會(huì)被判做猜錯(cuò)了)。如果猜的字符的數(shù)量不能夠保證你錯(cuò)了超過6次，也不能猜完所有的字符，那么即被判做放棄了。
這個(gè)問題本質(zhì)上還是非常簡(jiǎn)單的，就是用計(jì)算機(jī)把流程模擬一遍即可，大致的框架如下：
#include<stdio.h> #include<string.h> void guess(char ch){} int main( ){char s1[200],s2[200];scanf("%s%s",s1,s2);for (int i=0;i<strlen(s2);i++){guess(s2[i]);}return 0; }接下來我們只需要考慮怎么樣編譯guess函數(shù)，這里我考慮增加兩個(gè)變量，第一個(gè)為left(剩余需要猜的字符)，第二個(gè)為chance(還能猜幾次)
于是完整代碼如下：
這是按照書上的思路寫的(代碼是我自己寫的，所以有錯(cuò)誤也不要覺得奇怪)。
4-3 救濟(jì)金發(fā)放 (UVA 133)
n個(gè)人站成一圈以逆時(shí)針的順序標(biāo)記1-n (1–>2–>3···–>n–>1)，兩個(gè)人同時(shí)開始發(fā)救濟(jì)金，在每一輪中，官員A從1開始逆時(shí)針數(shù)，數(shù)k個(gè)就停下來。官員B從從n開始順時(shí)針數(shù)，數(shù)m個(gè)停下來。接下來被官員選中的人(可為一個(gè)人或者兩個(gè)人)離開隊(duì)伍。輸入n，k，m，輸出每一輪離開隊(duì)伍的人。
樣例：
輸入：10 4 3
輸出：4 8 9 5 3 1 2 6 10 7
分析：我們先看一下這個(gè)這個(gè)樣例是怎么得到的：
第一輪A：1–>2–>3–>4 此時(shí)A在5，剩余1,2,3,5,6,7,8,9,10
第一輪B：10–>9–>8 此時(shí)B在7，剩余1,2,3,5,6,7,9,10
第二輪A：5–>6–>7–>9 此時(shí)A在10，剩余1,2,3,5,6,7,10
第二輪B：7–>6–>5 此時(shí)B在3，剩余1,2,3,6,7,10
第三輪A：10–>1–>2–>3 此時(shí)A在6，剩余1,2,6,7,10
第三輪B：3–>2–>1 此時(shí)B在10，剩余2,6,7,10
第四輪A：6–>7–>10–>2 此時(shí)A在7，剩余6,7,10
第四輪B：10–>7–>6 此時(shí)B在10，剩余7,10
第五輪A：10–>7–>10–>7 此時(shí)A在10，剩余7
第五輪B：10–>7–>10 剩余7
第六輪：7
但是我們可以發(fā)現(xiàn)了一個(gè)問題就是，在第三輪的時(shí)候，第三個(gè)人其實(shí)已經(jīng)被選擇離開了，然而此時(shí)B點(diǎn)人的時(shí)候還是點(diǎn)到了第三個(gè)人，也就是說每一輪點(diǎn)人，我們都是先點(diǎn)人，再把人帶走。
事實(shí)上這道題也是一道非常簡(jiǎn)單的模擬題，模擬每一輪即可，但是這里有一個(gè)問題，就是怎么處理已經(jīng)離隊(duì)的人。
這里提供兩種處理方法：
第一種：將離隊(duì)的人進(jìn)行標(biāo)記
#include<stdio.h> int main(){int n,a[200],k,m,b[200]={0},tot=0,l=0,r=n-1,kk,mm,t,p1,p2;//tot表示離隊(duì)人數(shù),l表示A的位置，r為B位置,kk為A數(shù)到第幾個(gè)，mm為B數(shù)到第幾個(gè) scanf("%d%d%d",&n,&k,&m);for (int i=0;i<n;i++) a[i]=i+1;while (tot<n){kk=0,mm=0;//進(jìn)行一輪操作 while (kk<k){if (b[l]!=1) kk++;if (kk==k){b[l]=2;p1=l;}//kk等于k的時(shí)候，a[l]即為正在離隊(duì)的人 l=(l+1+n)%n;//往下一個(gè)開始數(shù) }while (mm<m){if (b[r]!=1) mm++; if (mm==m){b[r]=2;p2=r;} r=(r-1+n)%n;//往下一個(gè)開始數(shù)}//p1,p2分別為正在離隊(duì)的人位置 //確認(rèn)數(shù)到的是否是一個(gè)人if (p1!=p2){printf("%d %d ",a[p1],a[p2]);b[p1]--;b[p2]--; tot+=2;}else{printf("%d ",a[p1]);b[p1]--;tot+=1;}} return 0; }至于這里賦值2和賦值1有什么區(qū)別，請(qǐng)大家自行思考。
第二種：直接刪除離隊(duì)的人
這就涉及到編寫刪除數(shù)組元素的函數(shù)：
void del(int *a,int n,int p){for (int i=p;i<n-1;i++) a[i]=a[i+1]; }事實(shí)上對(duì)于刪除數(shù)組的一個(gè)元素，我們將后面的元素依次賦值到前一個(gè)元素，補(bǔ)掉中間被刪除的空即可。
其余的代碼自行思考補(bǔ)全
4-4 信息解碼 (UVA 213)
這個(gè)題面相當(dāng)之ex
分析：就是說給你多個(gè)字符串，第一個(gè)字符串的每一位字符，對(duì)應(yīng)一個(gè)01串，即為每個(gè)字符對(duì)應(yīng)的編碼。剩下的多個(gè)字符串拼接在一起為一個(gè)新的字符串，這個(gè)新的字符串即為我們的編碼文本，我們通過一定的方式(這個(gè)方式還蠻陰間的)對(duì)這個(gè)編碼文本進(jìn)行解碼。
例如樣例中的：
TNM(空格)AEIOU
0010101100011
1010001001110110011
11000
T對(duì)應(yīng)的編碼為0，N為00，M為01，空格為10，A為000，E為001，I為010，O為011，U為100。
(這個(gè)編碼怎么處理我會(huì)在后面進(jìn)行介紹)
這里的編碼文本即為：
0010101100011101000100111011001111000
首先最后的三位表示編碼結(jié)束，所以是不記在里面的。剩下的編碼文本可以分為很多個(gè)小節(jié)，每個(gè)小節(jié)以三位數(shù)字代表這個(gè)小節(jié)中每個(gè)編碼的長(zhǎng)度(010，即代表每個(gè)編碼長(zhǎng)度為2)，然后是各個(gè)字符的編碼，最后以編碼長(zhǎng)度*1作為結(jié)尾。
我們把編碼文本分解一下就是：
001(編碼長(zhǎng)度為1)0(T)1(小節(jié)結(jié)束)011(編碼長(zhǎng)度為3)000(A)111(小節(jié)結(jié)束)010(編碼長(zhǎng)度為2)00(N)10(空格)01(M)11(小節(jié)結(jié)束)011(編碼長(zhǎng)度為3)001(E)111(小節(jié)結(jié)束)000(編碼結(jié)束)
整個(gè)編碼解碼的結(jié)果如下
TAN ME
流程過了一遍，感覺這個(gè)問題的難度還是比較一般的，首先我們把輸入和存儲(chǔ)編碼的準(zhǔn)備工作做好：
#include<stdio.h> int main(){char s[100],ch;gets(s);int a[2000],tot=0;do{ch=getchar(); if (ch!='\n'){tot++;a[tot]=(int)ch-48;}}while (ch!=EOF);return 0; }這個(gè)輸入無法理解的自己去參考3.5。接下來我們將編碼分段：
while (x<=tot-4){//由于最后三位一定為0所以不用考慮 len=a[x]*4+a[x+1]*2+a[x+2];//前三位為小節(jié)長(zhǎng)度 x+=3;int flag;//用于判斷是否全部為1 do{flag=1;for (int i=1;i<=len;i++) flag*=a[x+i-1];x+=len;//如果不是全部為1 if (flag==0){} }while(flag==0);}現(xiàn)在我們對(duì)每一段編碼進(jìn)行解碼:
if (flag==0){int t=1,bm=0;//bm即為該段編碼對(duì)應(yīng)第幾個(gè)字符 for (int i=1;i<=len;i++){t*=2;bm=bm+a[x+len-i]*t/2;}bm+=t-len-1;//這一整段即為數(shù)學(xué)公式 printf("%c=",s[bm]);for (int i=1;i<=len;i++) printf("%d",a[x+i-1]);printf("\n"); }假如我們給一段01101的編碼，我們知道他的長(zhǎng)度為5，然后我們可以通過歸納法總結(jié)到n個(gè)0的編碼代表的數(shù)值是2n-n-1，于是我們只需要將01101當(dāng)作二進(jìn)制轉(zhuǎn)化為10進(jìn)制的數(shù)值加上5個(gè)0代表的數(shù)值，即可得到這段編碼的數(shù)值。
完整代碼如下：
4-5 追蹤電子表格的單元格 (UVA 512)
題面
分析：首先第一件事還是要將這道題給讀懂。這道題是什么意思呢，就是首先告訴你有一個(gè)r行c列的二維表，然后進(jìn)行n次操作。操作的格式如下：
#mermaid-svg-cutsBLwZ77j7SHHa .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-cutsBLwZ77j7SHHa .label text{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .node rect,#mermaid-svg-cutsBLwZ77j7SHHa .node circle,#mermaid-svg-cutsBLwZ77j7SHHa .node ellipse,#mermaid-svg-cutsBLwZ77j7SHHa .node polygon,#mermaid-svg-cutsBLwZ77j7SHHa .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-cutsBLwZ77j7SHHa .node .label{text-align:center;fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .node.clickable{cursor:pointer}#mermaid-svg-cutsBLwZ77j7SHHa .arrowheadPath{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-cutsBLwZ77j7SHHa .flowchart-link{stroke:#333;fill:none}#mermaid-svg-cutsBLwZ77j7SHHa .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-cutsBLwZ77j7SHHa .edgeLabel rect{opacity:0.9}#mermaid-svg-cutsBLwZ77j7SHHa .edgeLabel span{color:#333}#mermaid-svg-cutsBLwZ77j7SHHa .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-cutsBLwZ77j7SHHa .cluster text{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-cutsBLwZ77j7SHHa .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-cutsBLwZ77j7SHHa text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-cutsBLwZ77j7SHHa .actor-line{stroke:grey}#mermaid-svg-cutsBLwZ77j7SHHa .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-cutsBLwZ77j7SHHa .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-cutsBLwZ77j7SHHa #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-cutsBLwZ77j7SHHa .sequenceNumber{fill:#fff}#mermaid-svg-cutsBLwZ77j7SHHa #sequencenumber{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa #crosshead path{fill:#333;stroke:#333}#mermaid-svg-cutsBLwZ77j7SHHa .messageText{fill:#333;stroke:#333}#mermaid-svg-cutsBLwZ77j7SHHa .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-cutsBLwZ77j7SHHa .labelText,#mermaid-svg-cutsBLwZ77j7SHHa .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-cutsBLwZ77j7SHHa .loopText,#mermaid-svg-cutsBLwZ77j7SHHa .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-cutsBLwZ77j7SHHa .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-cutsBLwZ77j7SHHa .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-cutsBLwZ77j7SHHa .noteText,#mermaid-svg-cutsBLwZ77j7SHHa .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-cutsBLwZ77j7SHHa .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-cutsBLwZ77j7SHHa .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-cutsBLwZ77j7SHHa .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-cutsBLwZ77j7SHHa .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa .section{stroke:none;opacity:0.2}#mermaid-svg-cutsBLwZ77j7SHHa .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-cutsBLwZ77j7SHHa .section2{fill:#fff400}#mermaid-svg-cutsBLwZ77j7SHHa .section1,#mermaid-svg-cutsBLwZ77j7SHHa .section3{fill:#fff;opacity:0.2}#mermaid-svg-cutsBLwZ77j7SHHa .sectionTitle0{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .sectionTitle1{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .sectionTitle2{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .sectionTitle3{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-cutsBLwZ77j7SHHa .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa .grid path{stroke-width:0}#mermaid-svg-cutsBLwZ77j7SHHa .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-cutsBLwZ77j7SHHa .task{stroke-width:2}#mermaid-svg-cutsBLwZ77j7SHHa .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa .taskText:not([font-size]){font-size:11px}#mermaid-svg-cutsBLwZ77j7SHHa .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-cutsBLwZ77j7SHHa .task.clickable{cursor:pointer}#mermaid-svg-cutsBLwZ77j7SHHa .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-cutsBLwZ77j7SHHa .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-cutsBLwZ77j7SHHa .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-cutsBLwZ77j7SHHa .taskText0,#mermaid-svg-cutsBLwZ77j7SHHa .taskText1,#mermaid-svg-cutsBLwZ77j7SHHa .taskText2,#mermaid-svg-cutsBLwZ77j7SHHa .taskText3{fill:#fff}#mermaid-svg-cutsBLwZ77j7SHHa .task0,#mermaid-svg-cutsBLwZ77j7SHHa .task1,#mermaid-svg-cutsBLwZ77j7SHHa .task2,#mermaid-svg-cutsBLwZ77j7SHHa .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-cutsBLwZ77j7SHHa .taskTextOutside0,#mermaid-svg-cutsBLwZ77j7SHHa .taskTextOutside2{fill:#000}#mermaid-svg-cutsBLwZ77j7SHHa .taskTextOutside1,#mermaid-svg-cutsBLwZ77j7SHHa .taskTextOutside3{fill:#000}#mermaid-svg-cutsBLwZ77j7SHHa .active0,#mermaid-svg-cutsBLwZ77j7SHHa .active1,#mermaid-svg-cutsBLwZ77j7SHHa .active2,#mermaid-svg-cutsBLwZ77j7SHHa .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-cutsBLwZ77j7SHHa .activeText0,#mermaid-svg-cutsBLwZ77j7SHHa .activeText1,#mermaid-svg-cutsBLwZ77j7SHHa .activeText2,#mermaid-svg-cutsBLwZ77j7SHHa .activeText3{fill:#000 !important}#mermaid-svg-cutsBLwZ77j7SHHa .done0,#mermaid-svg-cutsBLwZ77j7SHHa .done1,#mermaid-svg-cutsBLwZ77j7SHHa .done2,#mermaid-svg-cutsBLwZ77j7SHHa .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-cutsBLwZ77j7SHHa .doneText0,#mermaid-svg-cutsBLwZ77j7SHHa .doneText1,#mermaid-svg-cutsBLwZ77j7SHHa .doneText2,#mermaid-svg-cutsBLwZ77j7SHHa .doneText3{fill:#000 !important}#mermaid-svg-cutsBLwZ77j7SHHa .crit0,#mermaid-svg-cutsBLwZ77j7SHHa .crit1,#mermaid-svg-cutsBLwZ77j7SHHa .crit2,#mermaid-svg-cutsBLwZ77j7SHHa .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-cutsBLwZ77j7SHHa .activeCrit0,#mermaid-svg-cutsBLwZ77j7SHHa .activeCrit1,#mermaid-svg-cutsBLwZ77j7SHHa .activeCrit2,#mermaid-svg-cutsBLwZ77j7SHHa .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-cutsBLwZ77j7SHHa .doneCrit0,#mermaid-svg-cutsBLwZ77j7SHHa .doneCrit1,#mermaid-svg-cutsBLwZ77j7SHHa .doneCrit2,#mermaid-svg-cutsBLwZ77j7SHHa .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-cutsBLwZ77j7SHHa .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-cutsBLwZ77j7SHHa .milestoneText{font-style:italic}#mermaid-svg-cutsBLwZ77j7SHHa .doneCritText0,#mermaid-svg-cutsBLwZ77j7SHHa .doneCritText1,#mermaid-svg-cutsBLwZ77j7SHHa .doneCritText2,#mermaid-svg-cutsBLwZ77j7SHHa .doneCritText3{fill:#000 !important}#mermaid-svg-cutsBLwZ77j7SHHa .activeCritText0,#mermaid-svg-cutsBLwZ77j7SHHa .activeCritText1,#mermaid-svg-cutsBLwZ77j7SHHa .activeCritText2,#mermaid-svg-cutsBLwZ77j7SHHa .activeCritText3{fill:#000 !important}#mermaid-svg-cutsBLwZ77j7SHHa .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-cutsBLwZ77j7SHHa g.classGroup text .title{font-weight:bolder}#mermaid-svg-cutsBLwZ77j7SHHa g.clickable{cursor:pointer}#mermaid-svg-cutsBLwZ77j7SHHa g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-cutsBLwZ77j7SHHa g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-cutsBLwZ77j7SHHa .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-cutsBLwZ77j7SHHa .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-cutsBLwZ77j7SHHa .dashed-line{stroke-dasharray:3}#mermaid-svg-cutsBLwZ77j7SHHa #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa .commit-id,#mermaid-svg-cutsBLwZ77j7SHHa .commit-msg,#mermaid-svg-cutsBLwZ77j7SHHa .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-cutsBLwZ77j7SHHa g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-cutsBLwZ77j7SHHa g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-cutsBLwZ77j7SHHa g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-cutsBLwZ77j7SHHa .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-cutsBLwZ77j7SHHa .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-cutsBLwZ77j7SHHa .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-cutsBLwZ77j7SHHa .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-cutsBLwZ77j7SHHa .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-cutsBLwZ77j7SHHa .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-cutsBLwZ77j7SHHa .edgeLabel text{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-cutsBLwZ77j7SHHa .node circle.state-start{fill:black;stroke:black}#mermaid-svg-cutsBLwZ77j7SHHa .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-cutsBLwZ77j7SHHa #statediagram-barbEnd{fill:#9370db}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-state .divider{stroke:#9370db}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-cutsBLwZ77j7SHHa .note-edge{stroke-dasharray:5}#mermaid-svg-cutsBLwZ77j7SHHa .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-cutsBLwZ77j7SHHa .error-icon{fill:#522}#mermaid-svg-cutsBLwZ77j7SHHa .error-text{fill:#522;stroke:#522}#mermaid-svg-cutsBLwZ77j7SHHa .edge-thickness-normal{stroke-width:2px}#mermaid-svg-cutsBLwZ77j7SHHa .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-cutsBLwZ77j7SHHa .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-cutsBLwZ77j7SHHa .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-cutsBLwZ77j7SHHa .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-cutsBLwZ77j7SHHa .marker{fill:#333}#mermaid-svg-cutsBLwZ77j7SHHa .marker.cross{stroke:#333}:root { --mermaid-font-family: "trebuchet ms", verdana, arial;}#mermaid-svg-cutsBLwZ77j7SHHa {color: rgba(0, 0, 0, 0.75);font: ;}EXDCDRICIR命令輸入四個(gè)數(shù)字r1,c1,r2,c2交換r1行c1列的單元格和r2行c2列的單元格輸入A和A個(gè)數(shù)字刪除這A列輸入A和A個(gè)數(shù)字刪除這A行輸入A和A個(gè)數(shù)字添加這A列輸入A和A個(gè)數(shù)字添加這A行接下來輸入q個(gè)查詢，對(duì)于每一個(gè)輸入的r，c輸入原本r行c列的格子在經(jīng)過n次操作后變?yōu)榱四膫€(gè)位置的格子。
這道題，依舊是一個(gè)思想非常簡(jiǎn)單，編寫起來比較復(fù)雜的模擬題。我們這里考慮用結(jié)構(gòu)體去存儲(chǔ)n次操作。
#include<stdio.h> struct Command{//結(jié)構(gòu)體的編譯我們一般首字母用大寫 char c[5];//用于放操作類型int r1,c1,r2,c2;//交換操作需要用到的變量int a,x[21];//其他操作用到的變量 }; int main(){int r,c,n;Command t[30]; scanf("%d%d%d",&r,&c,&n);for (int i=0;i<n;i++){scanf("%s",t[i].c);if (t[i].c[0]='E'){//交換操作 scanf("%d%d%d%d",&t[i].r1,&t[i].c1,&t[i].r2,&t[i].c2); }else{//其他操作 scanf("%d",&t[i].a)for (int j=0;j<t[i].a;j++) scanf("%d",&t[i].x[j]);}}return 0; }結(jié)構(gòu)體還不會(huì)用的好好看前兩章的講解吧。接下來分別編譯各個(gè)操作對(duì)某個(gè)單元格影響的函數(shù)(相當(dāng)復(fù)雜)：
int s(int *r0,int *c0){//注意這里用的是指針 for (int i=0;i<n;i++){if (t[i].c[0]=='E'){//交換函數(shù) if (t[i].r1==*r0**t[i].c1==*c0){//如果參與了交換 *r0=t[i].r2;*c0=t[i].c2;//*+指針變量表示以這個(gè)指針變量對(duì)應(yīng)存儲(chǔ)空間內(nèi)的值 }else if (t[i].r2==*r0**t[i].c2==*c0){*r0=t[i].r1;*c0=t[i].c1;}}else{int dc=0,dr=0;//dc,dr分別表示行和列的變化量 for (int j=0;j<t[i].s;j++){int x=t[i].x[j];if (t[i].c[0]='I'){//插入 if (t[i].c[1]=='R'&&x<=*r0) dr++; //單元格所在的行數(shù)增加了 if (t[i].c[1]=='C'&&x<=*c0) dc++;//單元格所在的列數(shù)增加了 }else{//刪除if (t[i].c[i]=='R'&&x==*r0) return 0; if (t[i].c[i]=='C'&&x==*c0) return 0;//刪除的時(shí)候直接給你把這個(gè)單元格刪了 if (t[i].c[1]=='R'&&x<=*r0) dr--;//單元格所在的行數(shù)增加了 if (t[i].c[1]=='C'&&x<=*c0) dc--;//單元格所在的列數(shù)增加了 } }*r0+=dr;*c0+=dc; }}return 1; }0即為這個(gè)單元格已經(jīng)沒有了，1的話就輸出原本那個(gè)單位格的地址里現(xiàn)在放的值。(這個(gè)題的代碼我是直接解釋的書本上的代碼，因?yàn)槿绻约簩懘_實(shí)容易發(fā)生很多意想不到的問題，如果大家寫出了更好的方法歡迎與我溝通交流)
4-6 師兄幫幫忙 (UVA 12412)
題面
分析：這道題與其說是研究算法的題目，不如說是一道大學(xué)編程教材的作業(yè)題(圖書管理系統(tǒng))。由于本專欄主要介紹的是算法相關(guān)的知識(shí)(大概)，所以不在一些繁瑣的模擬問題上花費(fèi)太多的時(shí)間(我懶)。基于前面的題已經(jīng)耗費(fèi)了大量的精力編譯了很多的模擬問題，這道題便不再做編譯(我懶)，留給大家自己思考。
事實(shí)上這一道題的操作和數(shù)據(jù)庫(kù)感覺有不小的關(guān)系，有興趣的可以嘗試一下
吐個(gè)槽：
接下來的第五章是一些關(guān)于c++和stl的知識(shí) (我們?cè)趘s中也是可以c++的，而且好像zxy特別允許我們用c++的一些東西去處理問題)，同時(shí)我也會(huì)和大家一起學(xué)習(xí)一些常用的stl算法和容器。那么就我個(gè)人的理解而言，算法是什么呢？算法是我們解決問題使用的數(shù)學(xué)方法。那對(duì)于一些問題，我們明明已經(jīng)能夠解決了，為什么還要學(xué)習(xí)別的算法呢？
事實(shí)上很多算法雖然能夠解決問題，但會(huì)花費(fèi)大量的時(shí)間，或者占用大量的內(nèi)存。于是我們需要思考出更加優(yōu)秀的算法去節(jié)省出我們的時(shí)間和空間。然而大多時(shí)候，時(shí)間和空間總有一個(gè)是要犧牲的。
例如排序算法：我們熟知的希爾排序(插入排序的優(yōu)化)的時(shí)間復(fù)雜度為o(nlog2n)(插入排序?yàn)閛(n2))，而計(jì)數(shù)排序僅為o(n+k)。那我們?yōu)槭裁此械呐判虿欢加糜?jì)數(shù)排序呢？首先，計(jì)數(shù)排序?qū)τ跀?shù)據(jù)差距非常大的值的排序，會(huì)占用大量的空間。第二，如果我們要得到排序后的數(shù)在原本數(shù)組中的位置，當(dāng)然還是可以用計(jì)數(shù)排序，但無疑會(huì)占用更多的空間。
也就是說對(duì)于一個(gè)問題，我們首先要解決這個(gè)問題，然后綜合考慮不同算法的代碼的時(shí)間復(fù)雜度和空間復(fù)雜度。那么還有什么要考慮的呢？很多人認(rèn)為是代碼的可讀性和更加貼近于你熟悉的方法，但我個(gè)人覺得是思想的適用性。比如一個(gè)問題，你明明可以直接dfs解決了，但你覺得dfs思考起來你覺得無法理解，于是你先廣度遍歷了第二層的結(jié)點(diǎn)，在繼續(xù)dfs。你覺得這樣好像使這個(gè)你原本陌生的算法和問題變得更加熟悉了。實(shí)際上是破壞了這個(gè)算法的適用性，因?yàn)檫@個(gè)算法原本可能是一個(gè)很直接的思考流程，可以套用任何其他的問題，但你這樣一改，反而使這個(gè)算法從一條直線饒了好幾個(gè)圈，影響了類似問題的處理。
所以在我看來：可以處理問題>時(shí)間復(fù)雜度和空間復(fù)雜度>思想的直接性和適用性>代碼的可讀性
以上觀點(diǎn)僅為個(gè)人看法
總結(jié)
以上是生活随笔為你收集整理的4.4 竞赛题目选讲的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： c语言kill暂停和恢复进程,Linux
- 下一篇： jquery之onblur事件