[ACM] 10696

看板C_and_CPP作者bleed1979 (十三)時間14年前 (2009/10/02 08:48)推噓2(2推 0噓 11→)

留言13則, 3人參與討論串1/1

我改了標題並增加了前面這段話為的是讓程式撰寫者明白, 寫程式是為自己的進步而寫, 追快不是那麼重要如果原本你已解完此題, 可以跳過此篇文章但如果你追求速度上的稱勝, 也許可以參考文章改良我的寫法 Bleed ※ 引述《ssagit (ssagit)》之銘言： : 標題: Re: ACM 10696 ... 迴圈只比遞迴快1秒 : 時間: Fri Jul 7 03:57:04 2006 : 推 ssagit:重新看了一下這一題的排名, 板上另一位強者只花0.057秒, 07/08 00:50 : → ssagit:不知道他願不願意分享是用什麼方法寫出來的.... 07/08 00:51 嗯　我把速度提升到0.024s　應該是我的極限了程式碼的link：http://codepad.org/IpmR8gdJ 這樣的code在時間上0.024s到0.032s都有可能還是得倚賴機judge system的狀況 #include <stdio.h> int main() { char a[11],b[30]; char *p,*q,*r,*s; b[0]='f'; b[1]='9'; b[2]='1'; b[3]='('; for (p=a,s=b+4;(*p=getchar())!=48;p=a,s=b+4) { for (*s++=*p++;(*p=getchar())!=10;*s++=*p++) ; r=p-1; *s++=')'; *s++=' '; *s++='='; *s++=' '; if (p-a>=3 && !(p-a==3 && a[0]==49 && a[1]==48 && a[2]==48)) { for (p-=2;p>=a && *p<49;p--) ; *p++-=1; for (q=a;*q==48 && q<p;q++) ; while (q<p) *s++=*q++; for (;p<r;p++) *s++='9'; *s++=*r; } else { *s++='9'; *s++='1'; } *s=0; puts(b); } return(0); } 講解一下程式碼 [解題] f91這個function 在 > 101的情況下　結果為輸入值減10 在 < 101的情況下　結果皆為91 在 = 101的情況下　以上兩個情況皆適用(101-10=91) 這個程式碼使用大數的方式解題 [程式解讀] 首先必須了解ascii code值為48,49和10的意思至於為什麼不打'0','1',和'\n' 我只是單純覺得code可以少一個字元而已 (請注意new line在不同平台上可能會是不同的值) char a[11],b[30]; char *p,*q,*r,*s; a是讀入測資的array b是輸出答案的array p,q,r,s都是pointer 以10010000為例, 減10會變成10009990 下圖代表各pointer的起始位置 s和q | q | p | p | | r | | r | | | | | | f91(10010000) = 10009990 b[0]='f'; b[1]='9'; b[2]='1'; b[3]='('; b的前4位元是永遠不變, 所以在迴圈外就定好值 for (p=a,s=b+4;(*p=getchar())!=48;p=a,s=b+4) p指向a的開頭, s指向'('的後面, 所以是b+4 *p先抓輸入值的第一個字元, 確定不是'0'後才跑迴圈作運算最後又要把p和s回復到原本的位置, 預備下一次跑迴圈作運算 for (*s++=*p++;(*p=getchar())!=10;*s++=*p++) ; 因為*p在一開始已經得到一個確定不是'0'的字元所以*s++=*p++ 接下來*p繼續抓值, 只要該行不是換行就一直assign給s, 即存入b陣列 r=p-1; 當*p等於換行字元時, 而*r是此輸入測資的個位數, 所以是p-1 *s++=')'; *s++=' '; *s++='='; *s++=' '; 這4個字元會隨著輸入測資的長度變動所以每跑一次迴圈都需要更新位置 if (p-a>=3 && !(p-a==3 && a[0]==49 && a[1]==48 && a[2]==48)) 根據剛才已定義好的解題法則大於等於3位數的輸入測資除了100以外, f91 function的結果都是減10 所以在此判斷出 if是三位數含以上且不等於100, 則做減10的動作 for (p-=2;p>=a && *p<49;p--) ; 減10的意思就是將10位數的ascii code值減1 所以一開始將p的位置往前移兩位如果該位置的值是小於'1'的, 就要往前面借位, 即p-- *p++-=1; 確定該位置已經大於等於1後, 就把該值減1, 並將p往後移一位 for (q=a;*q==48 && q<p;q++) ; q指標開始從a的開頭找起, 如果是'0'的就必須過濾掉並將指標往後移一位置這麼做的原因是因為1000-10可能為0990, 但我們只需要990, 所以要做濾'0'的動作 while (q<p) *s++=*q++; q定位好後, 就把從q到p之前的所有字元都存入b陣列 for (;p<r;p++) *s++='9'; 因為借位的關係, 再把p到r之前的字元都存入'9' *s++=*r; 最後再把輸入值的最後一個字元*r存入即可完成 else { *s++='9'; *s++='1'; } 根據剛才已定義好的解題法則條件不成立即<101的情況都存入'91' *s=0; puts(b); 最後補上字串結束字元0, 輸出即為答案我已儘可能的說明解題流程, 希望對初學者會有幫助 Bleed -- World of bleed1979 http://bleed1979.myweb.hinet.net/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.32.177.97

→

VictorTom

10/02 09:42, , 1^F

10/02 09:42, 1^F

→

VictorTom

10/02 09:43, , 2^F

10/02 09:43, 2^F

※ 編輯: bleed1979 來自: 114.32.177.97 (10/02 18:54)

推

bc5678

10/03 01:55, , 3^F