# USACO 2020 December Contest, Gold ## [Problem 2. Bovine Genetics](http://www.usaco.org/current/index.php?page=viewproblem2&cpid=1066) ### Description 今天有一個由 'A' , 'C' , 'G' , 'T' 所組成的字串 $S$,並做一次以下操作: 1. 如果有相鄰兩個相同字母,就把他們切開 2. 反轉切出來的每一段 3. 再把他們接起來 比如說 "AGGCTTT" -> "AG|GCT|T|T" -> "GA|TCG|T|T" -> "GATCGTT" 不過題目問的是,給一個做完操作的字串 $T$ ,請問有幾種可能的初始字串 $S$ $T$ 中有些字元可能是 '?' ,表示那個位置可以是 'A' , 'C' , 'G' , 'T' 任意一種字元 ### Scoring: 25% : $|S|\le 10$ 50% : $|S|\le10^2$ 100% : $|S|\le10^5$ ### Hint :::spoiler hint 1 相鄰的兩塊在初始序列 $S$ 中,連接的位置字元是相同的 ::: :::spoiler hint 2 切出來的每一塊中,都不會有相鄰兩個字元是相同的 ::: ::: spoiler hint 3 可以 dp 嗎? 狀態? 轉移? ::: ::: spoiler hint 4 <font size=7>$dp[i][x]=$</font> <font size=4>在初始序列 <font size=7>$S$</font> 中的第 <font size=7>$i$</font> 個位置是 <font size=7>$x$</font> 的方法數</font> ::: ::: spoiler hint 5 通常這種切切切的,轉移都是枚舉上一個切割點 ::: ::: spoiler hint 6 <font size=7>$dp[i][x]= \Sigma(dp[j][y]\times f[j+1][i][x][y])(1\le x<i)$</font> <font size=7>$f[l][r][x][y]=$</font> <font size=4>在 <font size=7>$T$</font> 中的 <font size=7>$l$</font> ~ <font size=7>$r$</font> 這段自成一塊且開頭為 <font size=7>$x$</font> 結尾為 <font size=7>$y$</font> 的方法數 </font> ::: ::: spoiler hint 7 啊要怎麼求 $f$ ::: ::: spoiler hint 8 是不是又可以 dp 了 ::: ::: spoiler hint 9 用 hint 2 的結論,應該可以輕鬆的推出轉移式 ::: ::: spoiler hint 10 <font size=7>$f$</font> 的初始狀態就是 <font size=7>$f[i][i][x][x]=(s[i]$</font> 可不可能是 <font size=7>$x)(1\le i\le |S|)$</font> <font size=7>$f[l][r][x][y]= \Sigma(f[l][r-1][x][z])(z\neq x , l<r )$</font> ::: 到這裡你應該已經會 50 分了 複雜度:$O(N^2)$ 或 $O(N^3)$ ### Solution ::: spoiler hint 11 50 分的 dp 是用拉的(用前面的答案算出當前答案), 如果用推的(將當前答案貢獻給後面的答案),會變什麼樣? ::: ::: spoiler hint 12 更精確的說,誰能接受當前答案的貢獻 ::: ::: spoiler hint 13 如果我們已經知道當前的答案 那麼轉移看起來會像醬 -> "X|Y.....X" (分隔線前是 $S$,分隔線後是 $T$) 我們知道第一個 'X' 的答案,那麼第二個 'X' 的位置以 'Y' 結尾的答案, 將可以接受當前答案的貢獻("X|Y.....X" -> "X|X.....Y") ::: ::: spoiler hint 14 在轉移中,重要的似乎只有三個位置 ::: ::: spoiler hint 15 新狀態! 假設有個切割點長成醬 -> "X|Y...Z" <font size=7>$dp[i][x][y][z]=$</font> <font size=4>上面那個 'Z' 的位置在 <font size=7>$i$</font> , 且在 <font size=7>$S$</font> 中 'X' 那個位置是 <font size=7>$x$</font> 、在 <font size=7>$T$</font> 中 'Y' 那個位置是 <font size=7>$y$</font> , 'Z' 那個位置是 <font size=7>$z$</font> 的方法數</font> ::: ::: spoiler hint 16 新切一刀時,切割點中的 'Y' , 'Z' 會在同一個位置,而 'Z' 之後會慢慢往後 ::: ::: spoiler hint 17 因為 hint 1,所以如果要新切一刀,將會從 <font size=7>$dp[i][y][x][y]=$</font> 轉移給下一個位置, ::: ::: spoiler hint 18 如果只是把 'Z' 往後移,那麼只要注意 hint 2 就可以了 詳細的轉移可以參 Sample Code ::: 這麼一來,我們就得到了一個滿分解 複雜度:$O(N)$ ::: spoiler 100% Sample Code ```cpp= #include<iostream> #include<string> #define ll long long #define DB double #define FOR(i,a,b) for(int i=a;i<b;i++) #define MOD (ll)(1e9+7) using namespace std; ll dp[100005][4][4][4]; int id[300]; string s; int main(){ id['A']=0; id['G']=1; id['C']=2; id['T']=3; cin>>s; FOR(x,0,4)if(id[s[0]]==x||s[0]=='?'){ FOR(y,0,4) dp[0][y][x][x]=1; } FOR(i,1,s.size()){ FOR(z,0,4)if(id[s[i]]==z||s[i]=='?'){ FOR(x,0,4)FOR(y,0,4) dp[i][x][z][z]=(dp[i][x][z][z]+dp[i-1][y][x][y])%MOD; } FOR(z,0,4)if(id[s[i]]==z||s[i]=='?'){ FOR(x,0,4)FOR(y,0,4){ FOR(t,0,4)if(t!=z) dp[i][x][y][z]=(dp[i][x][y][z]+dp[i-1][x][y][t])%MOD; } } } ll ans=0; FOR(x,0,4)FOR(y,0,4) ans=(ans+dp[s.size()-1][x][y][x])%MOD; cout<<ans<<endl; } ``` ::: ## [Problem 3. Square Pasture](http://www.usaco.org/current/index.php?page=viewproblem2&cpid=1067) ::: spoiler 100% Sample Code ```cpp= //記得跳題 #include<iostream> #include<algorithm> #include<vector> #include<set> #define ll long long #define FOR(i,a,b) for(int i=a;i<b;i++) #define pb push_back #define F first #define S second using namespace std; int n,ans; vector<pair<int,int> > pt; bool cmp(pair<int,int> a,pair<int,int> b){ return a.S<b.S; } int main(){ cin>>n; FOR(i,0,n){ int x,y; cin>>x>>y; pt.pb({x,y}); } sort(pt.begin(),pt.end()); FOR(i,0,n)FOR(j,0,i){ int len=pt[i].F-pt[j].F; int r=max(pt[i].S,pt[j].S),l=min(pt[i].S,pt[j].S); if(len<r-l) continue; set<int> tmp; tmp.insert(0); FOR(k,0,n)if(pt[k].F<pt[i].F&&pt[k].F>pt[j].F){ if(pt[k].S<r&&pt[k].S>l) continue; if(pt[k].S<r-len||pt[k].S>l+len) continue; if(pt[k].S<l){ tmp.insert(pt[k].S-(r-len)+1); } else{ if(pt[k].S-r>len-(r-l)) continue; tmp.insert(pt[k].S-r); } } ans+=tmp.size(); } sort(pt.begin(),pt.end(),cmp); FOR(i,0,n)FOR(j,0,i){ int len=pt[i].S-pt[j].S; int r=max(pt[i].F,pt[j].F),l=min(pt[i].F,pt[j].F); if(len<=r-l) continue; set<int> tmp,pos; FOR(k,0,n) if(pt[k].S<pt[i].S&&pt[k].S>pt[j].S) pos.insert(pt[k].F); pos.insert(r); pos.insert(l); if(!pos.count(r-len)) tmp.insert(0); FOR(k,0,n)if(pt[k].S<pt[i].S&&pt[k].S>pt[j].S){ if(pt[k].F<=r&&pt[k].F>=l) continue; if(pt[k].F<r-len||pt[k].F>l+len) continue; if(pt[k].F<l){ if(pos.find(pt[k].F+len+1)!=pos.end()&&pos.find(pt[k].F+1)!=pos.end()) continue; tmp.insert(pt[k].F-(r-len)+1); } else{ if(pos.find(pt[k].F-len)!=pos.end()) continue; tmp.insert(pt[k].F-r); } } ans+=tmp.size(); } ans+=n; cout<<ans+1<<endl; } ``` :::