# 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;
}
```
:::