[NKU]sweet ＠ Google && TopCoder && CodeForces

繼天津賽區銅了之后，本想在成都賽區保銅爭銀，竟然鐵了……真沒想到……

開始開題，由于天津賽區因讀題不當，略有悲劇，我們表示修改讀題策略……我敲完.vimrc，開始看ABC；SXJ去看中間DEFG，DON去看 HIJK，看過來后發現C是水的……上之……同時分DON過來重讀下，DON發現一個小細節，我修正后，此時15Min，1A……然后DON表示J貌似是個KM，但是他沒想好權值怎么去賦，SXJ表示D是個計算幾何，一個光線，進一個三角棱鏡折射兩次，問和X軸交不交，盡管一般來講計算幾何不能輕易開，但是DON日常是搞圖形學的，別說一個棱鏡了，一堆東西連反射帶折射他都能給搞出來……于是果斷開敲，我稍加思考就想明白了J……此時全場仍然只有C的粉紅氣球，只有電子科大過了C和F……我和SXJ在看F、G等其他題目，F題意是這樣，給你10000個拋物線（A>0）和直線f(x)，定義 F(x)＝max(f(x))讓你求［0，1000］中F（x）的最小值……當時肯定果斷想二分答案然后驗證……但是想了若干方法也驗證不了……G見到有人過了，但是我們完全沒想法……這時DON敲好了D，提交，WA……然后改，交，WA……于是我上去敲J，過了，此時146Min,1A……

我們在YY F和G中封了榜……封榜前Rank76，估計要鐵了……DON這時開始枚舉G題的思路：SCC、網絡流……突然他說：2－SAT，我當時已經想到了一個類似2－SAT的建圖方法，聽他一說才恍然大悟……悲劇的是我從未寫過2－SAT……自己的模板是肯定沒有，好在找到了彭哥的模板……但是這模板又沒注釋，令人很內傷……于是我先敲主干部分，DON研究建圖怎么用……經研究終于把樣例數據過了……快樂的提交……WA……還有10Min時，我陡然發現，這個題目有可能是要指定某個量的取值的……我當時的處理是譬如這個量一定取1，則讓0->0連邊，我當時考慮：0->0意味著：有了0，則不能有 0，這是個矛盾……于是這個量只能取1，感覺這個邏輯有點怪但是沒錯……其實悲劇在了：連了邊，要SCC的，自環相當于沒加邊……據說應該是 1－>0連邊，這樣意味取了1則不能取0，這邏輯順而且對……交上去，果不其然WA了……然后枚舉精度水了下D，一路WA……STOP……

賽后，我們在賓館里見到了NKU教主，上上任會長，現中科院參賽隊員刁哥……刁哥表示：F是個三分法……因為函數F（x）是凹的……G應該如上建圖……
晚上也沒心情領獎，AC去領了鐵牌證回來，告訴我們：D題我們是全場第一個提交，只錯了一組Case的小數點后第三位精度……
我曾經學過些化學……我當時陡然想到了發現Ar的“第三位小數的勝利”，這樣看來我們這次，鐵的直接原因之一就是這詭異的“第三位小數的失敗”……
鐵的直接原因之二就是我最后時期突然頭腦一亂，絕殺不中……否則還是能保個銅的……

回來路上，我們分析，這次鐵并不意外，因為F題2了，真沒辦法；沒寫過2－SAT，G也是真沒辦法，D出了這么個悲劇，也是真沒辦法……E是個暴力搜索，沒開的確可惜，但是卡了這么多題，是沒有魄力再開了……沒開也正常這暴露了我們隊伍的隱患……DON是十分擅長幾何的，SXJ擅長DP、組合計數和數論，但是D悲劇了，SXJ擅長的沒在簡單題中出現……我是各種東西都知道點的那種，但是我要是再不知道，譬如這次得的2－SAT，的確就悲劇了……這都TMD 賴我，2－SAT這種比較裸的模型題，我平時都是不搞的……誰知道這回反被搞了一下……
另：分析推理能力仍然有待提高……我們卡的F和G，其實有幾個思路已經很接近答案了，但是單獨走其中一個思路都是走不到答案的，需要結合起來，才能自己推理出來…………

鐵了之后，肯定很不爽……畢竟我是第二年第四場……刁哥、AC哥往年的情況都是Ag的……這次竟然鐵回去了……
刁哥教育我說：其實鐵了也好，銅對你們也沒意義，還能刺激刺激……明年人都退了，就得我們扛著了，要大力加強訓練、培養新人
SXJ表示安慰：不能以成敗論英雄，雖說今年的成績和去年持平，但是要看到一年來還是進步了，至少現在是一卡能卡2～3道了……已經不是去年一道一道做，保了Cu等吃飯的情況了……

我表示：NKU->HOT明年會回來的！

487做的不錯……
第一題是這么一個題，給出一個序列N（N<=50），你可以選擇距離恰好為L的兩個數，取出來求和（每個數只能用一次），求取法讓和最大
乍一看有點蒙，實際上，這N個數可以按照對L＋1同余分類，這樣就分出了若干類，然后每類里數肯定<=25，在2S的時間內用2^25的方法搜索即可……
水了這么一道，rating->1535，黃了……
489的300是這么個問題：給你N類球（N<=50），和一張N＊N的轉移表，某臺機器的功能就是：扔進若干球（數量不定，每個球都屬于這N類），隨機取兩個出來，根據轉移表合成出一個……直到只有一個球，問對于給定的輸入，輸出能否確定……
聽起來很玄的題…我當時猜測的結論是：由少許幾個球的情況可以產生所有情況，于是就枚舉＋驗證，剛開始猜測的是3～4個，結果4個TLE，3個大概過了……水了下，對了……
經刁哥教育，我明白了，這個東西實際上是這個意思，如果這個東西滿足結合律，則順序無關緊要了，可以直接從頭到尾合并算出……也就確定了……于是檢驗結合律相當于檢驗arr[i][arr[j][k]]==arr[arr[i][j]][k]……

500是個規律題……但是我沒找到規律……悲劇了……
rating-=13，1522……

Day-1之報道

早上去西南村取錢，順便吃早點……正當我猶豫今天吃什么的時候，一扭頭看見一條大漢……定睛一看原來是去年的班導二人……乍一驚，食欲全無……

去天南門下集結隊員，發現帶著綠色胸卡的TJU的志愿者MM匯合……志愿者MM昨天聲音聽起來不錯，但是發現真人遠沒有YY的那么軟……萬惡的FFT……

隊員集結完畢，同志們表示騎車前往報到地點，我懶得去拿了……于是一路小跑，距離倒是不遠，一路跑到啟元大酒店，交RMB報到，兩隊瓜分了各種道具……

途中，我們研究了下人民群眾的RP，貌似我和SXJ近期RP較高，適合抽簽，結果拿到冊子一看，座位已經定了……Orz……

然后，拿著TJU的臨時飯卡（內含180RMB），我們原路返回，到了我們最熟悉的天大學四（學四賣代金券），樓下超市刷卡，樓上吃飯刷卡，才花了30左右，貌似收不回成本了……

在吃飯之余，我們召開了例行的作戰會議，商議了一些策略……由于今年NKU->HOT III的成員都是拿過銅打過鐵的老同志了，也沒啥新動靜，無非是開局趕緊刷水，中期跟風或者根據國情開題，后期都不會了就吃飯或者繼續做題……

貌似NB學校的NB隊伍都來了，而且這是第二場，基本都不是旅游的……這……

下午去做模電實驗……誰見過報到之后還要上課的……終于學會了示波器怎么用……

期間，短信說：教練辛老師親自到場督戰……據班導說辛老師親自督戰RP都好……

外加我近期RP較高（天天開會，外加頭疼了2天，丟了水卡，見到了張水卡沒私吞等等……）、SXJ的RP也不錯，希望能有奇跡出現……

Day0之熱身賽

早上7：00左右醒來，發現DON發來短信說昨天的志愿者妹子有事來不了，換了個妹子……說8：20天南門集合……趕緊通知，通知完補一覺……

8：30左右把人集合齊了，妹子比昨天的軟……

然后開幕式，各種套話完畢后，參賽隊員代表發言……由于兩個隊友都沒來，搞得我只能上網……

代表妹子：男同胞們舉起手來，震動整個世界，女同胞們舉起手來，震動身邊的男同胞們……哥WS+XE的笑了……

然后的阿里巴巴講座我也沒聽……去聽教練會了，明確了各種問題

中午繼續揮霍，吃喝，小睡一下……

下午熱身賽，4個題都很水……面對著闊別已久的PC2，我先交一題，過了……

然后同志們想了想D……貌似有點集體犯2……實際上就是枚舉么……

然后開始各種胡搞，測的TLE>WA，棧大小8M，代碼長度貌似沒限制（千萬別變成打表大賽啊……），但是編譯如果時間太長算CE……等等……期間順便把B過了

然后教練辛老師親自前來督戰，譴責了我們不切干凈的行為，我們表示：上次在上海切的太干凈，結果鐵了……為了RP……

然后拍照，走人……

揮霍揮霍，然后回來睡了一小覺，洗洗，看了看2SAT，下動畫看動畫……

Day 1之正賽

早上，按照預定計劃，三食一樓集合吃飯……

然后走進體育場……一路無話，8：40

WC一下 ，里面爆滿……好容易排到了，放松下心情，然后進到會場

9：00，正式開賽，按照賽前的研究，我調機器，讀AB，敲完.vimrc之后，我看了下A，數據老長，貌似不可做，于是看B，發現貌似有點水，刷刷刷敲完，RUN ID#3，WA……然后發現題讀錯了……接下來一直沒有動靜……這時SXJ說E是卡特蘭數，告訴了我題意，敲敲敲……發現用java預處理組合數（10000以內）內存會爆……SXJ想了個O（N）時空復雜度的方法，敲敲敲敲……期間修正了i和n寫反的一個小錯誤，然后過了樣例和手寫數據……接下來測試極限數據，貌似要3S的樣子……不敢交了，寫了個打表（昨天上機測試結果，程序代碼長度無上限），但是經估算要打幾小時……于是我抱著試一試的態度交了一個，居然過了……Ctrl-C掉打表程序……

然后DON告訴我A是個簡單題，直接枚舉2^23，加點小剪，過了……

然后SXJ告訴我E是個簡單題，求10000個string（len<=30）中，前綴是XXX的有多少，但是XXX不老老實實告訴你，需要對每個YYY翻譯出它的Ascll碼，得到XXX，然后用string進去二分……ural做過類似的，XXX定左邊，XXX（'z'+1）定右邊，過了……

此時Rank14，據SXJ說他此時想到Ag基本定了，我自己倒是沒想太多，只是覺得手非常順，還能再過……誰知道到后面就再也沒有做出題來……
 
I貌似是個相當簡單的區間問題，有N個人（N<=60），每個人給出自己的排名區間【L，R】，求有多少個人給出的信息是真的……從左掃到右即可貪出，但是要求取的Ans個人字典序最大，為了這個字典序我們可是要了命了……先是貪心求解然后循環調整，WA，然后用費用流，把最大的加權為2^60，第二2^59以下以此類推……這樣肯定就是字典序……然后TLE……到最后也沒過……

C我沒有細看……SXJ飛速搞了一下，TLE……聽說這是個KM……直接DP肯定對不了了……

期間封榜了，當時Rank33……貌似還是Ag的線……

事后驚聞一堆3題的人爬上去，把我們踩到Cu了……

After Days

從結果上來講，沒比去年有啥進展……算是比較失敗……說是郁悶吧……畢竟沒啥發揮失常的地方，說值了吧……畢竟還能再出……

從過程上來講，有一些問題還是值得想一想。

賽后我們討論，最影響當場發揮和決策一點就是，我們壓根就沒有料想到自己能一度到達第14的位置，那時依然用跟風的方法，但是實際上前面的隊伍都是NB的，再跟的話不見的好使……后面有些隊伍也過了CI，我們當然相信自己能跟出來，結果卻沒有。我覺得如果去做B，沒準可以做出來（應該是枚舉邊+樹形DP，樹形DP暑假練過，壓力不大），事后一聽有個數據結構的，線段樹套Set的類似寫法我也干過（ural某題是要前10，這個要前100），沒準也能做；而跟風的題，盡管過的多但是并不見的合乎我們國情……

當然硬實力不足是根本原因，畢竟兩個流、匹配相關題目都卡了，這不是偶然的這是必然的……功夫要下在平時……

總之還是要感謝TJU給了個額外名額，讓我們在享受這“千年等一會”主場作戰的機會同時練了練兵，避免了在SCU一錘子買賣……看Mr.Yu忙來忙去也沒啥機會當面道謝……當然拿個小Cu也不太好意思露頭了……

11月3日，NKU->HOT IV開往川大賽區，到時候好運吧……

485做出一題，486作出兩題但是被系統掛掉一道……

485 250：
給出一個正數等差序列（長度>=4，<=50），但序列某位如果是偶數，則把他一直除2直到是奇數
給你的是改造后的序列
求該序列，如果多解則輸出字典序最小的
乍一看沒想法，實際上可以這么分析，這個問題和奇偶性密切相關
我們分析：
首項為偶，公差為偶 -> 可以同除2，得到的答案一定不是字典序最小，可舍
首項為奇，公差為偶：奇奇奇奇……
首項偶，公差奇：偶奇偶奇……
都是奇：奇偶奇偶
總之，都有兩個奇數項，是和原序列相同的，這樣的話咱就枚舉那兩個，產生數列并且更新答案就行……

rank:1283->1338，小漲一點

486
1：給出一個數A，讓你由若干步A+=A A-=A A*=A A/=A 得到B，如果多解要字典序最小
這個題目我實現時有點2B，A-=A實際是廢的（1000000000>=A，B>=1），得到0就產生不了別的了；A/=A實際上只要一次（只是產生1，晚用不如早用），看某個小鬼子的代碼，就是用＋＝和＊＝去DFS擴展A，或者用＋＝和＊＝去DFS擴展1，然后求字典序最小的解輸出……我的BFS寫的貌似正確，也沒人敢Cha，實際上簡單的1->2就把我掛了……學習、增加經驗了……

2：這題背景是Qsort，給你了這么個定義：選定基準P之后，這次的代價分為2部分：（有多少個本該<P的東西在P后＋有多少個本該>P的東西在P前）＋（左右兩部分遞歸求代價），給的數組范圍是50，并且元素個數不相同
一時沒有想到好的做法，后來看人知道可以DP……實際上我用MAP水了一下……因為數字的絕對大小無關緊要，我們可以把這些數離散成1～N的，然后枚舉基準P，統計第一部分，并分出左右兩部分，接下來離散左右兩部分到1～left.size(),1~right.size()，并遞歸求解……
為啥離散到1～n而不直接搞呢……是為了記憶化搜索，因為對1～n的一個排列，這個值是固定的，所以我用了一個Map<string,double>，把狀態塞進string里進行記憶化搜索，竟然過了……

rank:1338->1416，又小漲一點

總的來講，近日在TC上表現不錯……我要一點一點向上爬……
另：TC可以學習他人的代碼，的確很有益
另：我有時感覺有的人代碼的確有錯，實際上系統測試下來真有錯，但是沒敢Cha，也沒想好怎么構造讓他掛的數據，Cha人能力也要提高，只指望寫有時還是無力的……

就這樣我又回到了Div1……我很欣慰
但是今天的TC題目貌似很給力……

250：求區間【L，R】內所有（x^2）各位的和==（x各位的和）^2的數……
手寫一個暴力打表算法，得出結論：這種數字每位只可能是0123……而且總數不多（7000個左右），而且還有規律：各位的和不能超過一定值……
最后直接WS的交了表……不過打了表也可以搞出一個簡單的DFS

550：有4種顏色的塊，每當L個顏色相同的連在一起，就會立刻消掉……問長度為N的序列，有多少種方法可以把它消光（L<=10,N<=1000）
顯然的結論：N%L！=0則無解（L個連在一起會立刻消掉）
我想的是先DP由N/L塊拼成N的可能性，然后再染色……但是貌似這么計數有重復……
其實思路和答案已經很接近了……

rank+=33，現在1283……爭取趕快爬到黃的……

天津賽區的比賽在即……
NKU->HOT III表示不打無準備之仗，加緊訓練……

昨天做了去年寧波的題，今天做了去年武漢的題……效果是在我們預計之上的……
做了做這些題，underdog的感覺少了不少……但是各種教訓也很多，我覺得比較重要的一環就在我這……如果我能干凈利落的切掉水題，進可留時間做難題，退可保罰時少……但是我貌似和其他隊主敲相比還是有一定差距，在這個階段速度并不高，表現也并不是十分穩定……這樣的話，進難題可能做不完，退可能由于罰時多而名次下降，吉兇就難料了……所以要針對性的訓練一下……近日還是上Ural做點簡單題，練練速度和正確率吧……

傳送門：
1019：直線染色，離散化后直接做
1028：經典問題，先按x坐標第一關鍵字，y坐標第二關鍵字排序，然后線段樹/樹狀數組/平衡樹都行
1037：優先隊列維護靠前的空間，單調隊列維護刪除
1067：改造版Trie+DFS
1090：經典逆序對問題，樹狀數組/線段樹/歸并排序
1097：離散化后暴力
1100：惟一的玄機就是stable_sort
1126：固定的一個序列里面RMQ，S-T/優先隊列/線段樹……
1147：開1000個線段樹硬搞，n^2logn，空間卡的很緊
1220：貌似簡單的問題，1000個棧，操作100000次就是push和pop，
很容易想到的裸做法是：int data[100000] 表示每個數據，int fa[100000]表示每點在棧里的父親，int top[1000]表示1000個棧頂坐標
但是內存卡的很死很死，開200000個int是超的……
鑒于fa里的數據大小<=100000<17Bit，int的前15個Bit實際上浪費了，壓縮一下，將100000個int壓成了100000*17/32=52000個大概，過了
1306：求序列中位數，但是不給你存下所有數的空間，用一個大小為N/2+1的堆搞定……
1316：BST里插入刪除Rank
1350：純水
1414：用set和lower_bound水……
1439：初始一個集合1000000000個數，10000個操作：刪除和查詢第k大，由于操作不多，反其道而行之，用BST存儲刪除的值，查詢第k大時應用二分+BST的rank
1470：三維樹狀數組
1471：樹上兩點間距離，DFS+LCA
1494：沒讀懂，上網查的，原來是判斷一個序列能否由一個棧以及12345.....n的序列生成……直接搞
1521：Joesph問題，可線段樹解決（忘了數學方法了）
1523：K-逆序對問題，按照他的定義，重復使用經典逆序對算法就行
1542：先把字符串排序，然后對一個前綴，用二分定區間，然后在區間里面線段樹，線段樹里存10個最大頻率，我優化到了0.3S左右……求更快
1613：給你一個序列以及若干查詢，問某數是否在區間【L，R】間出現過
STL的應用：map<int,set<int> >,對每個數維護一個出現集合，然后對每個查找，如果該數不在Map里，肯定沒有，如果在的話，在set里進行lower_bound，查找出現集合和區間【L，R】有沒有交
想法其實沒錯，但是TLE了，后觀察到這東西本來插入時是1～N走的，本來就有單調性，不用Set，用vector就行，改后AC
1628：30000*30000的地圖里，分布著60000個黑點，求空白線段數量，vector+二分，注意題意：答案為1*L和L*1(L>=2)的塊數+1*1的塊數
1650：按照題意用set、map之類的模擬水過
1654：給一個字符串，每次都消掉兩個相鄰且相同的字母，求最后得到的串，其實就是括號匹配，一個棧搞定
1671：給出一個圖，給出一系列邊，按順序拆掉，問每拆掉一個邊后圖里有幾個聯通塊
逆向思考，用并查集維護，把沒拆的邊先加入圖里，然后倒著來，一一加上邊，維護聯通塊個數

傳送門：
http://acm.timus.ru/problemset.aspx?space=1&tag=structure

1028：經典問題，先按x坐標第一關鍵字，y坐標第二關鍵字排序，然后線段樹/樹狀數組/平衡樹都行
1037：優先隊列維護靠前的空間，單調隊列維護刪除
1067：改造版Trie+DFS
1090：經典逆序對問題，樹狀數組/線段樹/歸并排序
1100：惟一的玄機就是stable_sort
1126：固定的一個序列里面RMQ，S-T/優先隊列/線段樹……
1220：貌似簡單的問題，1000個棧，操作100000次就是push和pop，
很容易想到的裸做法是：int data[100000] 表示每個數據，int fa[100000]表示每點在棧里的父親，int top[1000]表示1000個棧頂坐標
但是內存卡的很死很死，開200000個int是超的……
鑒于fa里的數據大小<=100000<17Bit，int的前15個Bit實際上浪費了，壓縮一下，將100000個int壓成了100000*17/32=52000個大概，過了
1316：BST里插入刪除Rank
1350：純水
1439：初始一個集合1000000000個數，10000個操作：刪除和查詢第k大，由于操作不多，反其道而行之，用BST存儲刪除的值，查詢第k大時應用二分+BST的rank
1470：三維樹狀數組
1471：樹上兩點間距離，DFS+LCA
1494：沒讀懂，上網查的，原來是判斷一個序列能否由一個棧以及12345.....n的序列生成……直接搞
1521：Joesph問題，可線段樹解決（忘了數學方法了）
1523：K-逆序對問題，按照他的定義，重復使用經典逆序對算法就行
1613：給你一個序列以及若干查詢，問某數是否在區間【L，R】間出現過
STL的應用：map<int,set<int> >,對每個數維護一個出現集合，然后對每個查找，如果該數不在Map里，肯定沒有，如果在的話，在set里進行lower_bound，查找出現集合和區間【L，R】有沒有交
想法其實沒錯，但是TLE了，后觀察到這東西本來插入時是1～N走的，本來就有單調性，不用Set，用vector就行，改后AC
1628：30000*30000的地圖里，分布著60000個黑點，求空白線段數量，vector+二分，注意題意：答案為1*L和L*1(L>=2)的塊數+1*1的塊數
1671：給出一個圖，給出一系列邊，按順序拆掉，問每拆掉一個邊后圖里有幾個聯通塊
逆向思考，用并查集維護，把沒拆的邊先加入圖里，然后倒著來，一一加上邊，維護聯通塊個數


Data Struct那個分類里的簡單題基本就完了，剩下的就得費些工夫了……

由于上次杯具了，這次又回到了熟悉的Div2，又能找找當教主的感覺了……

Div2第一題：給出一個大小<=8的集合，對該集合的非空子集元素求平均數，然后再求個平均數……
這個題其實有簡單數學方法，相加求平均就行……
但是我當時感覺直接暴力，不會出錯……干凈利索，于是就寫了個直接方法。

Div2第二題：類似Joesph的問題，大小10000，直接拿昨天寫的線段樹改改過了……

然后就不做了……

Rating上漲回到1250，又成藍人了…爭取早日進黃……

另：我越發感到，有時題朦朦朧朧地做不出來，貌似是差一點，實際上是差很多……
不過要往好的方面想，貌似差一點，證明這個東西你還是有望搞出來，不是全然無處下手的沒有希望
所以我感覺近日就是要LevelUp一樣的感覺……不知道真正LevelUp的時候，在今年還是明年……

今天SRM481……

第一題把一個continue寫成了break，然后讓一個小鬼子cha了……杯具了……

第二題意念AC了，但是半小時寫不完…也就不寫了……

在哀嘆又要回Div2的同時，我表示要從中吸取教訓……
這一陣的訓練，過于注重提升絕對難度，對代碼的絕對實現能力并沒有太大訓練，這就導致了一些問題意念AC而實際AC不了的情況發生……
接下來要針對性的稍加訓練了………