oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1344 DP題，一開始我只想到$2 \cdot 4^5 N$的作法，但估了一估感覺不是很能跑，而且code也不是很好寫，後來聽了講解之後才知道狀態其實可以比我預期的少。 狀態是$dp[i][a_1][a_2][b_1][b_2]$，代表要處理第$i$個餐點，而先前第一區已有$a_1, a_2$號餐點，而第二區則有$b_1, b_2$號餐點，那轉移其實也還好，就是$dp[i+1][a_2][type(str_i)][b_1][b_2] = dp[i][a_1][a_2][b_1][b_2]+G(type(str_i), a_1, a_2)$(轉給第二區也是同樣的方式)，其中G函數為計算那三個中的種類的函數。 #include <bits/stdc++.h> using namespace std; const int N = 100001; char str[N]; int dp[2][4][4][4][4], toId[256]; inline int G(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); memset(dp, -1, sizeof(dp)); toId[(int)'M']=1; toId[(int)'B']=2; toId[(int)'F']=3; int n; cin>>n; cin>>str; dp[0][0][0][0][0]=0; int pos=0; for(int i=0;i<n;i++){ for(int a=0;a<4;a++){ for(int b=0;b<4;b++){ for(int c=0;c<4;c++){ for(int d...

題目連結: http://tioj.infor.org/problems/1271 應該很明顯可以用持久化資料結構做掉，如果知道有rope這東東的話可以直接拿來用，這題就被秒掉了。不過我們還是該秉持個手寫資料結構，所以我就寫了個持久化treap，而因為我每次插入的時候都保證key是遞增的，所以可以不用寫split把它拆掉再合起來，算是一個小常數優化(?，不過注意一下因為treap並不是保證logN的，所以有可能有幾條太長的路徑，導致MLE掉，這裡可能要多試幾次，或者直接用個7122這神秘數字避免(? #include "lib1271.h" #include <random> #include <ctime> #include <algorithm> #define copyNode(a,b) a->l=b->l;\ a->r=b->r;\ a->val=b->val;\ a->pri=b->pri;\ a->key=b->key; #define N 1000000 std::minstd_rand rd(7122); struct Treap{ int key; unsigned short pri; char val; Treap *l, *r; Treap(){} Treap(char c,int k){ pri=rd(); key=k; val=c; l=r=nullptr; } }; int sizes[N+1]={0}; Treap* treaps[N+1]={nullptr}; int opt=0; Treap...

題目連結: http://tioj.infor.org/problems/1839 經典的二分搜題，對於每個門都二分搜一次他的開關是哪一個，記錄下來並使他保持開著的狀況，如此便可以往下繼續走下去，一次檢驗出一個門，所以複雜度是$O(n^2 log n)$，不過該怎麼二分搜呢?不妨每次都反轉一串開關(已知道的就不要轉)，看結果有沒有變成跟上一次不一樣(這裡的不一樣指的是說有沒有動到你要問的那個人)，也就是說如果按下去發現原本只能通到i，但現在可以走到i+1之類的，那你剛剛必定按到i了，反之如果現在可以到達i+1你按完之後只能到i那，也是有按到的，所以依此性質就可以二分搜每個門對應到的開關是誰，同時也知道如何開關才好。 p.s沒看到多筆測資害我被梗了一下下ww #include "lib1839.h" #define N 5000 int MAP[N+5], OPENED[N+5]; inline void SWAP(int,int); int main(){ while(1){ int n=Initialize(); for(int i=0;i<n;++i) MAP[i]=-1; for(int i=0;i<n;++i){ int sks = tryCombination(OPENED);if(sks==-1)sks=n; bool preSAME = (sks==i); int l=0, r=n;bool ff=(sks>i); while(r-l>1){ int mid=(l+r)/2; SWAP(l,mid); int kawaii=tryCombination(OPENED);if(kawaii==-1)kawaii=n; bool curSAME = (kawaii==i); ...