T1 cowjog

FJ的奶牛們出去鍛煉它們的蹄子！FJ有N頭奶牛慢跑在一條無限長的單行路上。每頭奶牛在賽道上的獨特位置開始，并且一些奶牛們慢跑速度不同。路上只有一個車道，奶牛不能相互穿過。
當快牛追上來另一頭牛，她放慢腳步，以避免撞到其它牛，成為相同的跑步組的一部分。奶牛們將會跑T分鐘.請幫助FJ確定T分鐘后到底有多少組牛在慢跑。
兩個奶牛應該被考慮到在同一組的一個部分，如果他們在T分鐘時在相同的位置。

比賽時想到了后面的牛能追上前面的牛，記錄連續的，斷了就答案加一。喜提\(6pts\)。這種方法不知道為什么錯了。。。
正確的解法應該是直接考慮奶牛們的最終位置，最后按序號再掃一遍并記錄就好了。
最后因為T都是1e9級別的了，那么直接開longlong還不夠（數據太水，不開也行），用無符號的能多塞下一位。

T2 learn

FJ已經認真閱讀了關于機器學習的所有要點，通過這些既可以分析數據又可以獲知大量有趣且意想不到的信息（他甚至已經命名為“智能區域”！）。FJ決定運用這個智能區域對他現有的牛群建立一個自動分類器，可以猜測一頭牛是否有斑點。
不幸的是，FJ沒有做好對他的奶牛數據的及時跟蹤。對于他的N頭奶牛，他所知道的是每頭奶牛的重量，但他卻想了解每頭奶牛是否有斑點，但每一頭牛都有不同的重量。根據這個數據，他建立了所謂的“近鄰”。猜測某一頭奶牛是否有斑點，FJ首先找到和奶牛C體重最接近的奶牛C'，如果奶牛C有斑點，則判定C'也有斑點。如果C'位于兩頭分別有無斑點的奶牛的正中間，則C'可能有也可能無斑點。
FJ想將這套系統在他買的奶牛身上試驗一下。當測量了這些新奶牛的體重后，他知道這些奶牛的體重位于A和B之間(含)。請根據FJ智能系統提供的信息，確定這些奶牛中最多有多少頭會有斑點。需要注意的是，分類器只決定使用FJ的現有奶牛數據，沒有任何新的奶牛。還注意到，因為A和B都是相當大的。

考場上只討論了兩種情況。喜提\(6pts\)
“S”映射為1,“NS”映射為0。主要就是開結構體存，先對體重排序，從第2個開始看前面。

• \((e[i].type)xor( e[i-1].type)==1\)：各占一半
• \((e[i].type)and(e[i-1].type)==1\)：相同，全是有斑點的
  剩余的情況都是跟邊界\([A,B]\)相關的處理。

T3 Marathon

FJ對于她的奶牛的不佳健康狀況不滿意，所以準備讓她們編組做不同的體育運動。他的奶牛貝茜被編入跑步班，在那里，她會通過市中心附近FJ的農場跑馬拉松！馬拉松路線由N個被訪問的順序的檢查點組成，其中檢查點1是起始位置，檢查點N為終點。
貝茜應該要跑過所有這些檢查站，但是作為一頭懶牛（233333），她決定跳過K個檢查點來抄近道，然而她不能跳過檢查點1和N，因為顯而易見的這樣太明顯了（FJ要知道這事，貝茜可就慘了??）。請幫助貝茜找出至多跳過K個檢查點能偷的最大的懶。
由于這個路線是在城市中的街道中進行的，兩個檢查點位置分別為（X1，Y1）和（X2，Y2）的距離由下式給出|X1-X2|+|Y1-Y2|。

總之就是一道dp，狀態不難想，\(dp[i][j]\)表示前i個檢查點，跳過j個的最小距離。
初始化\(dp[i][0]\)，顯然就是直接累加路徑長度，其余賦INT_MAX
轉移，所有路過的點考慮進行轉移：
\(dp[i][j]=min(dp[i][j],dp[i-l-1][j-l]+dis(i-l-1,i))\)
三重循環，加個讀優也就過了

T4 Piggy Pack

Bessie和她的姐姐Elsie在不同的田塊吃草，晚上她們都返回牛棚休息。作為聰明的奶牛，她們想設計一個方案使得步行消耗的能量最少。
Bessie從一個田塊到相鄰的田塊要耗費B個單位的能量，Elsie從一個田塊到相鄰的田塊要耗費E個單位的能量。然而當Bessie和Elsie處于同一個田塊時，Bessie用背馱著Elsie一起走，從一個田塊到相鄰的田塊要耗費P個單位的能量。如果P小于B+E,則被認為是比較適用的；如果P非常小，那么最佳的方案就是盡快使得Bessie和Elsie在某一田塊相遇；當然如果P非常大，那么則盡可能使得Bessie和Elsie分開走。另一方面，她們對“背馱式”很不高興，她們不明白為什么這種豬用來馱運的方式會被認為是優秀的方法。
給出B,E和P,幫助她們姐倆找出從牧場到牛棚的花費能量最小的方案。

其實這道題就是bfs，而且很水，考場上前面花了大部分時間（包括神游），后面思考了一下有了思路，但沒有實現（哭死，而且被lzx同學否決了。。。
我們只需要知道他們在哪個點開始互相踩背使得總路徑最短就可以了。所以我們先bfs點1的最短路，點2的最短路，再在反圖上bfs n的最短路分別為\(b_1[N],b_2[N],b_3[N]\)
最后，枚舉點，計算\(min(d_1[u]*B+d_2[u]*E+d_3[u]*P)\)，完結。