寫在前面

• 這是我第一次做BestCoder, 熟悉了一下BestCoder的模式.
• BC上并不是只能看英文, 后面的Chinese view下的鏈接是中文題目
• 交的次數(shù)是會影響得分的. 所以有了把握再交. 至少樣例要過吧.
• 一定要考慮所有特殊情況, 因為有許多積極的Hacker正等著你上鉤. 即使交過Accepted之后一旦被Hack成功一分都沒有. 唉…
• 我的第一次BestCoder比賽就以兩個題被Hack兩個題不會結(jié)束了.
• 感覺BestCoder的比賽還是很刺激的. 拼手速, 拼細(xì)心, 拼代碼能力.
• 題目: http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=571

---

賽后題解

• 第一題字符串, 但我發(fā)現(xiàn)我字符串的基本功還是不行啊, 做了近一個小時(一開始不知道有中文題面, 到處找翻譯也費了不少時間), 還是看別人代碼打的.

  • 不能輸出前導(dǎo)零
  • 結(jié)果是0也不能不輸出
  • 被hack后改呀改, 終于發(fā)現(xiàn)我在輸出時如果數(shù)字大于10也用的+’0’輸出…

• 第二題倒是挺順利的想到解法. 首先, 拐點一定是1或者n. 把1作為拐點時, 假設(shè)1在第i個位置上, 除了1之外還有n-1個數(shù)字, 1的左面可以從n-1個數(shù)字中任選i-1個數(shù)字, 而且有且只有一種排法(遞減), 選完左側(cè)右側(cè)也就確定了, 且也只有一種排法(遞增). 而把n當(dāng)作拐點的排法總數(shù)和1時相等, 同時要注意到1, 2, …, n 和 n, n-1, …, 1 的排列被計算了兩次. 總結(jié)果要減去2. 那么總的排法就是

  ans=2?∑i=0n?1C(n?1,i)?2=2?2n?1?2=2n?2
  如果在比賽時想到這里就提交, 你會發(fā)現(xiàn)你A了, 但如果你在Hack的時間時去群里看一下, 就會發(fā)現(xiàn)事情并不單純.
  • 當(dāng)n = 1時, 總的排法應(yīng)該是 1 而不是 2^1 - 2 = 0. 全部遞增的序列和全部遞減的序列并沒有被算兩次. 因為它一共就一個序列.
    所以要加特判, n=1時輸出 1
    完了嗎? 沒有…(hack好強大)
  • 因為數(shù)據(jù)范圍很大, 10^18, long long ? 但是乘法時可能溢出, 所以還需要寫快速乘, 在矩陣乘法的題里曾用到過. 我當(dāng)時猶豫要不要寫, 但看到第一次提交AC后就沒有寫. 我當(dāng)時還不知道hack有多強大.
    到這里, 所有問題應(yīng)該都解決了吧?
    唉, 又調(diào)了好半天. 各種習(xí)慣不好導(dǎo)致的錯誤
  • 首先 n=1 時不能簡單的輸出1, 因為m還可能等于1
  • 然后, 記得把所有變量都開long long
  • 最后一個是我犯的錯誤, 在快速冪和快速乘的時候我先把傳入的兩個參數(shù)都模了…&%#……

• A, B題都是基礎(chǔ)的東西, 但掌握的都不好

• 覺得做BestCoder很刺激樣子.

• 第三題后來看別人的代碼弄明白了. 用map實現(xiàn)的DP

  • 先按照解決問題最早開始的時間先后排序
  • 用 map<int, long long> f[2] 來記錄狀態(tài). map是當(dāng)前時間到最大分?jǐn)?shù)的映射. f[2] 是滾動數(shù)組.
  • 如果選擇放棄解決當(dāng)前的問題, 就從上個狀態(tài)的時間轉(zhuǎn)移到當(dāng)前狀態(tài)的時間即可, 分?jǐn)?shù)不變.
  • 如果選擇解決當(dāng)前問題, 就從上個狀態(tài)的一個時間(pre_t)轉(zhuǎn)移到當(dāng)前狀態(tài)的一個合法時間, 分?jǐn)?shù)加上當(dāng)前問題的分?jǐn)?shù). 這里需要考慮哪個時間是合法的, 如果pre_t加上任務(wù)所需時間早于最早完成時間, 就轉(zhuǎn)移到最早完成時間, 否則轉(zhuǎn)移到pre_t加上任務(wù)所需時間.
  • 用迭代器遍歷map需要滿足map里至少有一個元素吧. 所以先插入一個(0, 0)預(yù)處理.
  • 用map實現(xiàn)的狀壓感覺好厲害…
  • 還有記得該開long long的時候就開… 又在這里卡了一陣

---

賽后代碼

A: https://code.csdn.net/snippets/619782
B: https://code.csdn.net/snippets/619742
C: https://code.csdn.net/snippets/619822

---

比賽結(jié)果

被hack的很慘, 其實還是自己弱

總結(jié)

以上是生活随笔為你收集整理的BestCoder-Round#33的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。