題目: https://codeforces.com/contest/983/problem/B MySol: https://codeforces.com/contest/983/submission/51883938 我是智障的一千種理由 其中之一是我根本無法多看題目一眼然後看出性質 看完這題後很明顯可以感覺到如果我能夠O(1)弄出[l, r]的答案的話,那麼隨便弄弄就可以求出所有答案了。 理由是按照長度做DP,就可以維護在[l, r]內的最佳答案了。 然後我的思路就跑到了要如何O(1)呢?我馬上就想到了巴斯卡三角形 每格被算到的次數剛好是巴斯卡三角耶,成功把算出區間的複雜度弄到O(N)了,因為可以O(N^2)預處理楊輝三角形 然後就不會了QQ 看解之後馬上就察覺到了,[l, r]的答案 = [l, r - 1]^[l + 1, r]的答案,我根本智障 上面那個式子看起來很顯然,對吧? 嗯...,我也是這麼覺得的,那麼,一開始沒看出來的我是智障這件事就沒有爭議了,對吧?
留言
張貼留言