TC SRM 585

DIV 2 1000PT  EnclosingTriangleColorful

問有多少個三角形包含了所有的黑色的點

先是兩兩枚舉出所有點對，判斷所有的黑點是否在同一側

然後枚舉所有三角形，O(1)判斷

預處理O(m*m*n),枚舉O(m*m*m)

[cpp]
const int N = 305; 
bool upleft[N][N],upright[N][N],downleft[N][N],downright[N][N]; 
bool updown_toleft[N][N],updown_toright[N][N],leftright_toup[N][N],leftright_todown[N][N]; 
class EnclosingTriangleColorful { 
public: 
int xmul(int x0,int y0,int x1,int y1,int x2,int y2){ 
    return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0); 
} 
int getNumber(int m, vector <int> x, vector <int> y) { 
    int n=x.size(); 
    for(int i=1;i<m;i++){ 
        for(int j=1;j<m;j++){ 
            bool f1=true,f2=true; 
            for(int k=0;k<n;k++){ 
                if(xmul(i,m,0,j,x[k],y[k])<0) 
                    f1=false; 
                if(xmul(i,m,m,j,x[k],y[k])>0) 
                    f2=false; 
            } 
            upleft[i][j]=f1;upright[i][j]=f2; 
        } 
    } 
    for(int i=1;i<m;i++){ 
        for(int j=1;j<m;j++){ 
            bool f1=true,f2=true; 
            for(int k=0;k<n;k++){ 
                if(xmul(i,0,0,j,x[k],y[k])>0) 
                    f1=false; 
                if(xmul(i,0,m,j,x[k],y[k])<0) 
                    f2=false; 
            } 
            downleft[i][j]=f1;downright[i][j]=f2; 
        } 
    } 
    for(int i=1;i<m;i++){ 
        for(int j=1;j<m;j++){ 
            bool f1=true,f2=true; 
            for(int k=0;k<n;k++){ 
                if(xmul(i,m,j,0,x[k],y[k])<0) 
                    f1=false; 
                if(xmul(i,m,j,0,x[k],y[k])>0) 
                    f2=false; 
            } 
            updown_toright[i][j]=f1;updown_toleft[i][j]=f2; 
        } 
    } 
    for(int i=1;i<m;i++){ 
        for(int j=1;j<m;j++){ 
            bool f1=true,f2=true;; 
            for(int k=0;k<n;k++){ 
                if(xmul(0,i,m,j,x[k],y[k])<0) 
                    f1=false; 
                if(xmul(0,i,m,j,x[k],y[k])>0) 
                    f2=false; 
            } 
            leftright_toup[i][j]=f1;leftright_todown[i][j]=f2; 
        } 
    } 
    int ans=0; 
    for(int i=1;i<m;i++)  //up  
        for(int j=1;j<m;j++){   //left  
            for(int k=1;k<m;k++){  //right  
                if(upleft[i][j]&&upright[i][k]&&leftright_toup[j][k]){ 
                    // cout<<i<<" "<<j<<" "<<k<<" "<<leftright[j][k]<<endl;  
                    ans++; 
                } 
            } 
        } 
    for(int i=1;i<m;i++)  //up  
        for(int j=1;j<m;j++){   //down  
            for(int k=1;k<m;k++){  //right  
                if(updown_toright[i][j]&&upright[i][k]&&downright[j][k]){ 
                    // cout<<i<<" "<<j<<" "<<k<<endl;  
                    ans++; 
                } 
            } 
        } 
    for(int i=1;i<m;i++)  //up  
        for(int j=1;j<m;j++){   //left  
            for(int k=1;k<m;k++){  //down  
                if(upleft[i][j]&&updown_toleft[i][k]&&downleft[k][j]){ 
                    // cout<<i<<" "<<j<<" "<<k<<endl;  
                    ans++; 
                } 
            } 
        } 
    for(int i=1;i<m;i++)  //down  
        for(int j=1;j<m;j++){   //left  
            for(int k=1;k<m;k++){  //right  
                if(downleft[i][j]&&downright[i][k]&&leftright_todown[j][k]){ 
                    // cout<<i<<" "<<j<<" "<<k<<endl;  
                    ans++; 
                } 
            } 
        } 
    return ans; 
} 
 
 
}; 

const int N = 305;
bool upleft[N][N],upright[N][N],downleft[N][N],downright[N][N];
bool updown_toleft[N][N],updown_toright[N][N],leftright_toup[N][N],leftright_todown[N][N];
class EnclosingTriangleColorful {
public:
int xmul(int x0,int y0,int x1,int y1,int x2,int y2){
 return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}
int getNumber(int m, vector <int> x, vector <int> y) {
 int n=x.size();
 for(int i=1;i<m;i++){
  for(int j=1;j<m;j++){
   bool f1=true,f2=true;
   for(int k=0;k<n;k++){
    if(xmul(i,m,0,j,x[k],y[k])<0)
     f1=false;
    if(xmul(i,m,m,j,x[k],y[k])>0)
     f2=false;
   }
   upleft[i][j]=f1;upright[i][j]=f2;
  }
 }
 for(int i=1;i<m;i++){
  for(int j=1;j<m;j++){
   bool f1=true,f2=true;
   for(int k=0;k<n;k++){
    if(xmul(i,0,0,j,x[k],y[k])>0)
     f1=false;
    if(xmul(i,0,m,j,x[k],y[k])<0)
     f2=false;
   }
   downleft[i][j]=f1;downright[i][j]=f2;
  }
 }
 for(int i=1;i<m;i++){
  for(int j=1;j<m;j++){
   bool f1=true,f2=true;
   for(int k=0;k<n;k++){
    if(xmul(i,m,j,0,x[k],y[k])<0)
     f1=false;
    if(xmul(i,m,j,0,x[k],y[k])>0)
     f2=false;
   }
   updown_toright[i][j]=f1;updown_toleft[i][j]=f2;
  }
 }
 for(int i=1;i<m;i++){
  for(int j=1;j<m;j++){
   bool f1=true,f2=true;;
   for(int k=0;k<n;k++){
    if(xmul(0,i,m,j,x[k],y[k])<0)
     f1=false;
    if(xmul(0,i,m,j,x[k],y[k])>0)
     f2=false;
   }
   leftright_toup[i][j]=f1;leftright_todown[i][j]=f2;
  }
 }
 int ans=0;
 for(int i=1;i<m;i++)  //up
  for(int j=1;j<m;j++){   //left
   for(int k=1;k<m;k++){  //right
    if(upleft[i][j]&&upright[i][k]&&leftright_toup[j][k]){
     // cout<<i<<" "<<j<<" "<<k<<" "<<leftright[j][k]<<endl;
     ans++;
    }
   }
  }
 for(int i=1;i<m;i++)  //up
  for(int j=1;j<m;j++){   //down
   for(int k=1;k<m;k++){  //right
    if(updown_toright[i][j]&&upright[i][k]&&downright[j][k]){
     // cout<<i<<" "<<j<<" "<<k<<endl;
     ans++;
    }
   }
  }
 for(int i=1;i<m;i++)  //up
  for(int j=1;j<m;j++){   //left
   for(int k=1;k<m;k++){  //down
    if(upleft[i][j]&&updown_toleft[i][k]&&downleft[k][j]){
     // cout<<i<<" "<<j<<" "<<k<<endl;
     ans++;
    }
   }
  }
 for(int i=1;i<m;i++)  //down
  for(int j=1;j<m;j++){   //left
   for(int k=1;k<m;k++){  //right
    if(downleft[i][j]&&downright[i][k]&&leftright_todown[j][k]){
     // cout<<i<<" "<<j<<" "<<k<<endl;
     ans++;
    }
   }
  }
 return ans;
}

};
DIV1 250 PT TrafficCongestion

一棵滿二叉樹，問有多少條不相交的路徑，遍歷所有的點

觀察奇偶的最優解，得到遞推式，兩個奇的合成偶的，無法合並原來的路徑，還得單獨考慮根，所以是兩倍加1

兩個偶的，有一條路徑可以合並，所以是兩倍減1

比賽的時候。。。沒考慮到0的情況。。。23333

[cpp]
int dp[1000005]; 
class TrafficCongestion { 
public: 
int theMinCars(int treeHeight) { 
    dp[0]=1; 
    for(int i=1;i<=treeHeight;i++) 
        if(i&1) dp[i]=(dp[i-1]*2-1)%MOD; 
    else dp[i]=(dp[i-1]*2+1)%MOD; 
    return dp[treeHeight]; 
} 
 
 
}; 

int dp[1000005];
class TrafficCongestion {
public:
int theMinCars(int treeHeight) {
    dp[0]=1;
    for(int i=1;i<=treeHeight;i++)
     if(i&1) dp[i]=(dp[i-1]*2-1)%MOD;
    else dp[i]=(dp[i-1]*2+1)%MOD;
    return dp[treeHeight];
}

};
DIV1 500PT LISNumber

從大到小插入到序列當中，dp[i][j]表示考慮了i種數，目前LISnumber為j的數目。

那麼考慮i-1的時候，有cnt[i-1]個這樣的數。

如果新增了k個lisnumber。那麼剩下的cnt[i-1]-k個數插入進去是沒有產生lisnumber的。

只要插入點在原來的lis起點的前面，才不會新增。

也就是在原來的j個lis前面選出cnt[i-1]-k個位置，插入這些數，不產生lisnumber。

剩下的k個數，插入是要新增lisnumber的。位置包括之前的那cnt[i-1]-k個位置，序列的末端以及每個lis的中間sum-t。

這一部分轉化為k個相同的物品放入到cnt[i-1]-k+1+sum-t個不同的容器中的方案數，DP解決。

[cpp]
const int MOD = 1000000007; 
LL c[40*40][40*40]; 
LL dp[40][1300]; 
LL a[40*40][40]; 
class LISNumber { 
public: 
    LL PowMod(LL a,LL b){ 
        LL ret=1; 
        while(b){ 
            if(b&1) ret=((LL)ret*a)%MOD; 
            a=((LL)a*a)%MOD; 
            b>>=1; 
        } 
        return ret; 
    } 
    int count(vector <int> cardsnum, int K){ 
        int n=cardsnum.size(); 
        memset(dp,0,sizeof(dp)); 
        memset(a,0,sizeof(a)); 
        for(int i=1;i<=36*36;i++){ 
            c[i][0]=c[i][i]=1; 
            for(int j=1;j<i;j++) 
                c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD; 
        } 
        a[0][0]=1LL; 
        for(int i=0;i<=37*37;i++){ 
            for(int j=0;j<=37;j++){ 
                for(int k=0;k<=37&&j+k<=37;k++){ 
                    a[i+1][j+k]=(a[i+1][j+k]+a[i][j])%MOD; 
                } 
            } 
        } 
        LL sum=cardsnum[n-1]; 
        dp[n-1][cardsnum[n-1]]=1LL; 
        for(int i=n-2;i>=0;i--){ 
            for(int j=0;j<=sum&&j<=K;j++){ 
                if(dp[i+1][j]==0) continue; 
                for(int k=0;k<=cardsnum[i]&&j+k<=K;k++){ 
                    if(k+j<cardsnum[i]) continue; 
                    int t=cardsnum[i]-k; 
                    LL tmp=((LL)c[j][t]*(LL)a[t+1+(sum-j)][k])%MOD; 
                    dp[i][j+k]=(dp[i][j+k]+(LL)dp[i+1][j]*tmp)%MOD; 
                } 
            } 
            sum+=cardsnum[i]; 
        } 
        return (int)dp[0][K]; 
    } 
 
 
}; 

const int MOD = 1000000007;
LL c[40*40][40*40];
LL dp[40][1300];
LL a[40*40][40];
class LISNumber {
public:
 LL PowMod(LL a,LL b){
  LL ret=1;
  while(b){
   if(b&1) ret=((LL)ret*a)%MOD;
      a=((LL)a*a)%MOD;
   b>>=1;
  }
  return ret;
 }
 int count(vector <int> cardsnum, int K){
  int n=cardsnum.size();
  memset(dp,0,sizeof(dp));
  memset(a,0,sizeof(a));
  for(int i=1;i<=36*36;i++){
   c[i][0]=c[i][i]=1;
   for(int j=1;j<i;j++)
    c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
  }
  a[0][0]=1LL;
  for(int i=0;i<=37*37;i++){
   for(int j=0;j<=37;j++){
    for(int k=0;k<=37&&j+k<=37;k++){
     a[i+1][j+k]=(a[i+1][j+k]+a[i][j])%MOD;
    }
   }
  }
  LL sum=cardsnum[n-1];
  dp[n-1][cardsnum[n-1]]=1LL;
  for(int i=n-2;i>=0;i--){
   for(int j=0;j<=sum&&j<=K;j++){
    if(dp[i+1][j]==0) continue;
    for(int k=0;k<=cardsnum[i]&&j+k<=K;k++){
     if(k+j<cardsnum[i]) continue;
     int t=cardsnum[i]-k;
     LL tmp=((LL)c[j][t]*(LL)a[t+1+(sum-j)][k])%MOD;
     dp[i][j+k]=(dp[i][j+k]+(LL)dp[i+1][j]*tmp)%MOD;
    }
   }
   sum+=cardsnum[i];
  }
  return (int)dp[0][K];
 }

};