9.24-9.25是大連地區賽,之前似乎是因為我們sdu在之前的網絡賽中表現不錯,結果我們竟然獲得了兩個正式隊名額,於是峰哥非常囧的找我和 dxh詢問二隊組隊方案.最後在"有名額浪費掉那純屬半禿"的原則指導下,找到張夢馳神牛隨便湊了個隊,準備去大連打醬油.於是我和dxh兩個大一的就能 夠在開學還沒多久之後就可以參加Regional了……這樣山大就兩個正式隊,一個旅遊隊,雖然我覺得我們隊更像是旅遊的…… 去acm官網註冊的時候,我們因為我們的隊名起了爭執.dxh認為"WrongAnser"這個名字不錯,結果當場被峰哥卷了.最後我表示"SuperBrother"這個當隊名就不錯,不過結果是我被峰哥和dxh鄙了,半禿度+1. 去 大連買的是9.23下午4點的灰機.我坐飛機的第一次就這樣獻給了海南航空公司.之後去大連理工,報到,辦手續.順便說一下貌似很多人都喜歡把大連理工叫 做"大工",不解釋……住處"略"坑爹,坑爹到我只好蹭dxh的無線網卡上網.面對著我用掉的20+M流量我表示壓力很大…… 因為是純屬打 醬油的二隊,所以晚上玩的很嗨,一直到半夜.第二天下午有熱身賽,我們第一次接觸到了比賽場地.機器用的吾半禿10.10,配備 code::blocks,Eclipse和Netbeans.機子的運算速度很快,實際測試了一下發現一億次整數運算0.2s就跑完,浮點運算3.Xs 就跑完,然後測了一下,發現跑一億次java.math.BigInteger也是各種無壓力,3.Xs直接完成.然後看到c和c++的編譯指令都有 -o2優化,只能說"I'm SO HAPPY~~".熱身賽比賽中間有人提交Clarification詢問內存限制,回覆是只要不把評測機總內存吃掉就大丈夫，並且聲稱評測機和比賽機配 置一樣.此時已經很明顯了,時間和空間複雜度都不會卡常數和低階項,基本上只要能有合適的想法,能寫對,就能ac.順縣說下我們在c13處,c12就是中 山大學.熱身賽的時候thu某支隊費了力氣ak掉四道題,把sjtu壓了下去,結果很快中山大學也ak了,又把thu的那隻隊伍壓倒第二去了囧……表示坐 在中山大學主力隊伍後面的我們感到亞歷山大. "熱身賽你們ak個毛啊,這樣很掉rp的知道不"---熱身賽后某神牛的憤怒. 順便說下之前我們一直認為一個隊180大洋的伙食費絕對足夠,結果由於本人這個大吃貨,面對著9.23晚上第一頓飯就吃掉50大洋的情況,我們最後果斷找張洋那個隊來接濟了我們9.25的早飯……以後組acm隊的時候一定要考慮到隊員的飯量問題啊TAT. 9.25 9:00-14:00正式比賽.和熱身賽不同的是氣球的展示位置變了…… 比賽開始后我們速度開始分頭讀題,於是乎我果斷跑去看H,I和J.然後我發現H題是個計算幾何我表示此時只能仰天召喚mj神牛.I題讓你求比n小並且和n 互質的所有數的四次方的和,看到n<=10^8,再看到1000組測試數據,表示果斷蛋疼.J題讀題花的時間最長.一開始照著題目描述發現樣例貌似 說的不對勁,然後我發現白色部份必須是正方形Orz...然後我列了兩個整數方程之後就表示不可做,扔了……事實證明這是我比賽時候一個相當大的失誤.我 應該早點發現這可能和二分圖最小覆蓋有聯繫,並且說出來……我半禿.此時張夢馳發現D是一道大水的模擬,於是dxh果斷上去coding.但是幾個模擬規 則著實噁心到了我們,於是在WA了好幾次后我們才把D題掉ac掉了... 此時張夢馳發現C題可能可做,於是我去看C題了,結果除了猜想從中 間按按鈕一定不會最優就沒別的成果了.然後dxh發現G題果斷是個trie圖,然後我們三個都不會寫……翻閱模板,結果發現模板裏面什麽都有就是沒 trie圖的……然後dxh看C,我掃了一眼F.我一看:我艸?這種題我在vijos上還做過呢,不就是200棵線段樹么,種了!然後我生成自己線段樹比 較穩定,所以我就上去敲F了,可是沒想到,這是我杯具的開始……開橋之後才發現自己好長時間沒敲手生了不知道多少,看到的模板的別人的,自己根本不習慣這 個寫……好在這題不難,死磕了半個小時之後程序基本完工.敲樣例上去測試結果發現自己RTE,用gdb調了一段時間后dxh表示自己要上機敲C,於是我打 印下來代碼自己看.dxh敲完之後調試過了樣例,submit之後返回RTE,於是dxh下機,我上去再去調試F...這樣的循環很快以dxh因為某個很 奇怪的改動而ac掉C結束,於是接下來dxh和張夢馳開始對E,G,I感興趣,我則在苦逼地調試F.基本上比賽下半段的時間全給我用來調試了,可是我的結 果不是RTE就是WA,一直到比賽結束都沒AC...其中有幾次因為過於緊張,犯了很多低級錯誤,結果使我們隊增加了好多罰時……嘛不過最後也沒ac,這 些罰時也無所謂了╮(╯_╰)╭ 比賽的最後階段,我們聽到c12的中山大學說了一句I用匈牙利可做,然後沒多久我們就聽到了中山那一隊里ac題的歡呼聲,我們看著中山那一隊升起的8個氣球,表示亞歷山大…… 這次比賽峰哥那一隊確實囧了.最後拿了個銅回來,這讓最後一次參加acm的冰哥和遠哥情何以堪...... 整場比賽場內場外只有一個人注意到我們隊的奇葩的名字……我表示我囧. 比賽結束后sdu全員在旁邊的一家上校餐廳里呆到晚上,然後坐車去的機場,凌晨回到學校,通宵玩遊戲玩到現在,然後開始寫這些東西,一直寫到現在.

[img src="http://catf.me/photos/e9d355df14a043138212c556c587b191.jpg" width="640" height="574"]

RT.之前北京賽區網絡賽Problem B([link url="http://boj.me/problem/ProblemSet/B.pdf)"]扯到小圓臉,Problem D([link url="http://boj.me/problem/ProblemSet/D.pdf)"]扯到FXTZ.這次又在SGU上看到某人(http: //acm.sgu.ru/teaminfo.php?id=015656),昵稱大亮啊!而且這個sgu id看上去應該是很早註冊的了(我09年初註冊的sgu,結果id是020695...)

你哥我淪落到開vpn來上blogger了,杯具啊! 最近做狀壓動規做上癮了.hdu3920.一看就知道這不是個禿論. 方程:dp[s|(1<<i)|(1<<j)]=dp[s]+min(cost(i,j)); 注意幾點 1.顯然當確定要消去i點和j點的時候,就應該貪心地先消去里起始點最近的點 2.轉移時可以限制i是按照標號順序可以被消去的第一個點,然後直接只枚舉j.這樣狀態不會減少,轉移複雜度大大減少. 3.這狀態轉移方程的拓撲關係比較混亂,所以可以根據這個轉移方程建立一個有向圖然後廣搜一遍. source code: #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <iostream> using namespace std; #define maxn 21 #define clr(a) memset(a,0,sizeof(a)) #define inf (1000000000) const int maxs=(1<<20); struct point{ double x,y; }; point p[maxn]; point st; double dp[maxs]; int q[maxs+2]; double tmpd; int testcase,ff,rr,n,s; inline double sqr(double a){ return a*a; } inline double dis(point a,point b){ return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); } bool compare(const point &a,const point &b){ return dis(st,a)<dis(st,b); } int main(){ freopen("in.txt","r",stdin); scanf("%d",&testcase); for(int ttestcase=1;ttestcase<=testcase;++ttestcase){ printf("Case #%d: ",ttestcase); scanf("%lf%lf",&st.x,&st.y); scanf("%d",&n),n+=n; for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p,p+n,compare); s=(1<<n); for(int i=1;i<s;i++) dp[i]=inf; dp[0]=0,ff=1,rr=0,q[1]=0; for(int tmp,i,j,tmps;rr<ff;){ tmp=q[++rr]; for(i=0;i<n;i++) if(!(tmp&(1<<i))) break; for(j=i+1;j<n;j++) if(!(tmp&(1<<j))){ tmps=(tmp|(1<<i)|(1<<j)); tmpd=dp[tmp]+dis(st,p[i])+dis(p[i],p[j]); if(dp[tmps]>tmpd){ if(dp[tmps]>=inf) q[++ff]=tmps; dp[tmps]=tmpd; } } } printf("%.2lf\n",dp[s-1]); } fclose(stdin); return 0; }

[link url="http://www001.upp.so-net.ne.jp/dassai/suishi/suishi_yomi.htm"] 出師表　三國志　蜀書　卷五　諸葛亮伝 （臣亮言う）先帝創業未（いま）だ半ばならざるに中道に崩 [img src="http://www001.upp.so-net.ne.jp/dassai/kanjigif/016408.gif" width="24" height="24"] （ほうそ）したまう。今、天下三分して益州疲弊せり。これ誠に危急存亡の秋（とき）なり。 然れども侍衛の臣内に懈（おこた）らず、忠志の士身を外に忘るる者は蓋（けだ）し先帝の殊遇を追いて之を陛下に報ぜんと欲するなり。誠に宜しく聖聴を開張し、以て先帝の遣德を光（かがや）かし、志士の気を恢弘（かいこう）すべし。宣しく妄りに自ら菲薄（ひはく）し、喩（たとえ）を引いて義を失い、以て忠諌の路を塞ぐべからざるなり。 宮中・府中倶（とも）に一体爲（た）り。臧否（ぞうひ）を陟罰（ちょくばつ）するに宜（よろ）しく異同あるべからず。若（も）し奸（かん）を作（な）し、科（とが）を犯し、及び忠善を爲す者有らば、宣しく有司に付して其の刑賞を論じ、以て陛下平明の理を昭（あきらか）にすべし。宜しく偏私（へんし）して内外をして法を異（こと）にせしむべからざるなり。 侍中・侍郎の郭攸之（かくゆうし）・費 [img src="http://www001.upp.so-net.ne.jp/dassai/kanjigif/034453.gif" width="24" height="24"] （ひい）・董允（とういん）等は、これ皆な良実、志慮忠純なり。是（ここ）を以ちて先帝簡抜して以て陛下に遣（のこ）せり。愚、以爲（おもえらく）、宮中の事は事大小と無く悉（ことごと）く以て之に咨（はか）り、然る後に施行せば必ず能く闕漏（けつろう）を稗補（ひほ）し広く益する所有るなり。将軍の向寵（しょうちょう）は性行淑均（しゅくきん）にして軍事に暁暢（ぎょうちょう）す。昔日に試用せられ先帝之を称して能（のう）と曰（い）えり。是（ここ）を以ちて衆議して寵を挙げて督（とく）と爲す。愚、以爲（おもえら）く、営中の事は悉く以って之に咨（はか）れば必ず能く行陣をして和睦し優劣をして所を得しめんと。 賢臣に親しみ小人を遠ざけしは此れ先漢の興隆せし所以（ゆえん）なり。小人に親しみ賢臣を遠ざけしは此れ後漢の傾頽（けいたい）せし所以なり。先帝在（あ）りし時、臣と此の事を論ずる毎（たび）に未だ嘗（かつ）て桓霊に歎息痛恨せずんばあらざりき。侍中・尚書・長史・参軍、此れ悉く貞亮（ていりょう）にして節に死するの臣なり。願わくば陛下之に親しみ之を信ぜよ。則ち漢室の隆（さかん）なること日を計りて待つべきなり。 臣、本（もと）布衣（ふい）にして躬（みずか）ら南陽に耕し、荀（いやしく）も性命を乱世に全うせんとして聞達（ぶんたつ）を諸侯に求めず。先帝、臣の卑鄙（ひい）なるを以てせず、猥（みだり）に自ら枉屈（おうくつ）して三たび臣を草廬の中に顧み、臣に諮（はか）るに当世の事を以てす。是（これ）に由（よ）りて感激し遂に先帝に許すに駆馳（くち）を以てす。後、傾覆（けいふく）に値（あ）い、任を敗軍の際に受け、命を危難の間に奉ず。爾来二十有一年。先帝、臣の謹慎なるを知る。故に崩ずるに臨み臣に寄するに大事を以てしたまえり。命を受けて以来、夙夜（しゅくや）憂歎（ゆうたん）し託付の效あらずして以て先帝の明を傷（そこな）うことを恐る。故に五月、瀘（ろ）を渡り深く不毛に入れり。今、南方已に定まり甲兵已に足る。当に三軍を奨率し北のかた中原を定むべし。庶（こいねが）わくば駑鈍（どどん）を竭（つく）し奸凶を壤除（じょうじょ）し漢室を興復し旧都に還さんことを。此れ臣が先帝に報い而して陛下に忠なる所以の職分なり。損益を斟酌し忠言を進め尽すに至りては、則ち攸之（ゆうし）・ [img src="http://www001.upp.so-net.ne.jp/dassai/kanjigif/034453.gif" width="24" height="24"] （い）・允（いん）の任なり。願わくば陛下、臣に託するに討賊・興復の效を以てせよ。效あらずんば則ち臣の罪を治め以て先帝の霊に告げ、若し興德の言無くんば則ち攸之（ゆうし）・ [img src="http://www001.upp.so-net.ne.jp/dassai/kanjigif/034453.gif" width="24" height="24"] （い）・允（いん）等の慢を責め、以て其の咎（とが）を彰（あらわ）せ。陛下も亦た宣しく自ら謀り、以て善道を諮諏（ししゅ）し、雅言を察納し深く先帝の遣詔を追うべし。 臣、恩を受くるの感激に勝（た）えず。今、遠く離るるに当り表に臨みて涕（なみだ）零（お）ちて言う所を知らず。

[link url="http://gnaggnoyil.blogspot.com/2011/09/maze.html"] HDU4035,11號網絡賽的MAZE,這道遞推因為我把幾個區域變量【優化】到了全局結果一直WA,然後我就禿了…… 算法: 這個禿雖然是個無根樹,但是由於樹根是確定的了,所以實質上就是個有根樹.設e[i]是以點i為子樹走出迷宮所需的數學期望,那麼可以【得知】,對於任意 一個e[i],其結果一定是一個關於e[1],e[fa[i]]的一次多項式,即我們這裡可以設 e[i]=r[i]*e[1]+x[i]*e[fa[i]]+a[i].那麼對於任意一個點i,都有e[i]=k[i]*e[1]+tmp[i]* (e[fa[i]]+sum(e[j],j為i的兒子)+1),其中tmp[i]=(1-k[i]-e[i])/cnt[i],cnt[i]即點i的 度..又因為e[fa[j]]=e[i],j是i的兒子,所以,我們可以發現,e[i]中的三個係數r[i],x[i]和a[i]都可以由i的兒子節點們 給遞推出來.這樣遞推到最後,這種會發現e[1]=r[1]*e[1]+a[1],此時就相當於解一個關於e[1]的一元一次方程,解出來即可. source code: #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #define maxn 10010 #define eps (1e-10) #define clr(a) memset(a,0,sizeof(a)) struct edge{ int vt,next; }; edge e[maxn*5]; double K[maxn],E[maxn],r[maxn],x[maxn],a[maxn],tmp[maxn]; int fa[maxn],cnt[maxn],st[maxn]; bool vis[maxn]; int testcase,n,tot,p,q; double ttmp; bool flag; int sig(double x){ return (x>eps)-(x<-eps); } int addedge(int u,int v){ e[++tot].vt=v,e[tot].next=st[u],st[u]=tot; return 0; } int dfs1(int u){ cnt[u]=0; for(int i=st[u];i!=0;i=e[i].next){ ++cnt[u]; if(!vis[e[i].vt]) vis[e[i].vt]=true,fa[e[i].vt]=u,dfs1(e[i].vt); } tmp[u]=(1-K[u]-E[u])/cnt[u]; return 0; } int dfs2(int u){ if(vis[u]) return 0; vis[u]=true; r[u]=x[u]=a[u]=0; double R=0,X=0,A=cnt[u]; for(int i=st[u];i!=0;i=e[i].next){ if(e[i].vt==fa[u]) continue; dfs2(e[i].vt); R+=r[e[i].vt],X+=x[e[i].vt],A+=a[e[i].vt]; } R*=tmp[u],X*=tmp[u],A*=tmp[u]; if(sig(ttmp=1-X)==0) flag=false; if(flag) r[u]=(K[u]+R)/ttmp,x[u]=tmp[u]/ttmp,a[u]=A/ttmp; return 0; } int main(){ scanf("%d",&testcase); for(int ttestcase=1;ttestcase<=testcase;++ttestcase){ printf("Case %d: ",ttestcase); clr(st); scanf("%d",&n); tot=0; for(int i=1;i<n;i++){ scanf("%d%d",&p,&q); addedge(p,q),addedge(q,p); } for(int i=1;i<=n;i++){ scanf("%lf%lf",K+i,E+i); K[i]/=100.0,E[i]/=100.0; } flag=true; clr(vis),vis[1]=true; dfs1(1); clr(vis),vis[1]=true; for(int i=2;i<=n;i++) dfs2(i); if(!flag){ printf("impossible\n"); continue; } double X=0,A=0; for(int i=st[1];i!=0;i=e[i].next) X+=x[e[i].vt]+r[e[i].vt],A+=a[e[i].vt]+1; X*=tmp[1],A*=tmp[1]; if(sig(ttmp=1-X)==0){ printf("impossible\n"); continue; } printf("%.6lf\n",A/ttmp); } return 0; }

本來指望把sgu502當作水題刷一下的,結果事實證明無論你在本機上測試多么沒問題,上sgu必須把數組開的足夠大,否則就等著RTE吧. #include <cstdio> #include <cstring> #include <cstdlib> #define maxn 19 #define maxs (1<<18) int dp[maxs][19]; int dt[maxn]; char str[255]; int n,s; bool search(int a,int b){ if(a==0) return b==0; if(dp[a][b]==0) return false; if(dp[a][b]==1) return true; for(int ta,tb,i=1;i<=n;i++){ if((a&(1<<(i-1)))==0) continue; ta=a^(1<<(i-1)),tb=(b-dt[i]+17)*12%17; if((ta==0)&&(dt[i]==0)) continue; if(search(ta,tb)) return dp[a][b]=1,true; } return dp[a][b]=0,false; } int print(int a,int b){ if(a==0) return 0; for(int ta,tb,i=1;i<=n;i++) if((a&(1<<(i-1)))!=0){ ta=a^(1<<(i-1)),tb=(b-dt[i]+17)*12%17; if((ta==0)&&(dt[i]==0)) continue; if(search(ta,tb)) return print(ta,tb),printf("%d",dt[i]),0; } return 0; } int main(){ scanf("%s",str); n=strlen(str); if(n==18){ printf("-1\n"); return 0; } for(int i=1;i<=n;i++) dt[i]=str[i-1]-'0'; s=(1<<n)-1; for(int i=0;i<=s;i++) for(int j=0;j<17;j++) dp[i][j]=-1; if(search(s,0)) print(s,0); else printf("-1"); printf("\n"); return 0; }