---
# System prepended metadata

title: 'USACO 2020 December Contest, Gold'

---

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