暑假集训test-8-29-白红宇

暑假集训test-8-29

阅读量：5322 次

发布时间：2019-06-14

本文共 5129 字，大约阅读时间需要 17 分钟。

今天瓜成一坨了。

瓜的说不出话来。

直接退役算了我。

傻逼题，但是我傻逼地敲了一个线段树合并，然后把空间炸了，只剩20分，

直接dfs维护子树大小，子树中最大最小值即可统计答案。

1 //Achen 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #define Formylove return 013 #define For(i,a,b) for(int i=(a);i<=(b);i++)14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)15 const int N=1000007; 16 typedef long long LL;17 typedef double db;18 using namespace std;19 int n,rt,fa[N];20 21 template
                
                 void read(T &x) {22 char ch=getchar(); x=0; T f=1;23 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();24 if(ch=='-') f=-1,ch=getchar();25 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;26 }27 28 int ecnt,fir[N],nxt[N],to[N];29 void add(int u,int v) {30 nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;31 }32 33 int ans;34 int mi[N],mx[N],sgrt[N],sz[N];35 void dfs(int x) {36 mi[x]=mx[x]=x;37 sz[x]=1; 38 for(int i=fir[x];i;i=nxt[i]) {39 dfs(to[i]);40 sz[x]+=sz[to[i]];41 mi[x]=min(mi[x],mi[to[i]]);42 mx[x]=max(mx[x],mx[to[i]]);43 }44 if(sz[x]==mx[x]-mi[x]+1) ans++;45 }46 47 #define ANS48 int main() {49 #ifdef ANS50 freopen("A.in","r",stdin);51 freopen("A.out","w",stdout);52 #endif53 read(n);54 For(i,2,n) {55 int u,v;56 read(u); read(v);57 fa[v]=u; add(u,v);58 }59 For(i,1,n) if(!fa[i]) rt=i;60 dfs(rt);61 printf("%d\n",ans);62 Formylove;63 }

View Code

我已经菜到连f[i][j]表示放完前i个数，最后一个放的数是前i个数中第j大的的方案数的dp都想不出来了。。。

上午一直在瞎yy一个三方的垃圾算法，以为t1t3稳了这题大概要T一些点，结果T1爆空间T3没拍写挂了，这题却tmd水过去了。。大概就是从小的往大的连边，这个图的拓扑序的数目就是答案，发现这个图很特殊，可以区间dp，f[l][r]表示把l~r取完的方案数，组合数转移，写的是记忆化搜索。

1 //Achen 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #define Formylove return 013 #define For(i,a,b) for(register int i=(a);i<=(b);i++)14 const int N=1007,p=1000000007;15 typedef long long LL;16 typedef double db;17 using namespace std;18 char s[N];19 int n,a[N];20 LL f[N][N],C[N][N];21 vector
                
                 vc[N]; 22 23 template
                 
                  void read(T &x) {24 char ch=getchar(); x=0; T f=1;25 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();26 if(ch=='-') f=-1,ch=getchar();27 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;28 }29 30 void pre() {31 For(i,1,n) {32 For(k,i+1,n-1) if(a[k]!=1&&a[k+1]!=-1) 33 vc[i].push_back(k); 34 }35 }36 37 LL dfs(int l,int r) {38 if(l>=r) return 1;39 if(f[l][r]==-1) {40 LL rs=0;41 42 int k=l;43 int ltot=k-l,rtot=r-k;44 if(a[k+1]!=-1)45 rs=(rs+dfs(l,k-1)*dfs(k+1,r)%p*C[ltot+rtot][ltot]%p)%p;46 k=r;47 ltot=k-l,rtot=r-k;48 if(a[k]!=1)49 rs=(rs+dfs(l,k-1)*dfs(k+1,r)%p*C[ltot+rtot][ltot]%p)%p;50 int up=vc[l].size();51 For(j,0,up-1) {52 if(vc[l][j]>=r) break;53 k=vc[l][j];54 ltot=k-l,rtot=r-k;55 rs=(rs+dfs(l,k-1)*dfs(k+1,r)%p*C[ltot+rtot][ltot]%p)%p;56 }57 f[l][r]=rs;58 } 59 return f[l][r];60 }61 62 #define ANS63 int main() {64 #ifdef ANS65 freopen("B.in","r",stdin);66 freopen("B.out","w",stdout);67 #endif68 scanf("%s",s);69 n=strlen(s);70 For(i,0,n-1) {71 if(s[i]=='D') a[i+2]=-1;72 else if(s[i]=='I') a[i+2]=1;73 else a[i+2]=0;74 }75 ++n;76 For(i,0,n) C[i][0]=1;77 For(i,1,n) For(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p; 78 memset(f,-1,sizeof(f));79 pre();80 dfs(1,n);81 printf("%lld\n",f[1][n]);82 Formylove;83 }84 /*85 IIDD?DD??I86 */

View Code

先dp出lcs,f[i][j]表示a的前i个字符和b的前j个字符的lcs.

再dp答案。g[i][j]表示a的前i个字符中长度为f[i][j]并且在b的前j个字符中出现过子序列个数。

两种转移

1、不选a[i],

　　如果f[i-1][j]==f[i][j]

　　　　g[i][j]+=g[i-1][j]

2、选a[i]

　　找到b的前j个字符中最靠后的一个和a[i]相等的字符b[k],

　　如果f[i-1][k-1]+1==f[i][j]

　　　　g[i][j]+=g[i-1][k-1];

1 //Achen 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               12 #define Formylove return 013 #define For(i,a,b) for(int i=(a);i<=(b);i++)14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)15 const int N=1007,p=1e9+7;16 typedef long long LL;17 typedef double db;18 using namespace std;19 int n,m,f[N][N];20 LL g[N][N]; 21 char a[N],b[N];22 23 template
                
                 void read(T &x) {24 char ch=getchar(); x=0; T f=1;25 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();26 if(ch=='-') f=-1,ch=getchar();27 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;28 }29 30 #define ANS31 int main() {32 #ifdef ANS33 freopen("C.in","r",stdin);34 freopen("C.out","w",stdout);35 #endif36 scanf("%s",a);37 scanf("%s",b);38 n=strlen(a); m=strlen(b);39 For(i,0,max(n,m)) g[i][0]=g[0][i]=1;40 For(i,1,n) For(j,1,m) {41 if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;42 else f[i][j]=max(f[i-1][j],f[i][j-1]);43 }44 For(i,0,max(n,m)) g[i][0]=g[0][i]=1;45 For(i,1,n) {46 int k=0;47 For(j,1,m) {48 if(a[i-1]==b[j-1]) k=j; 49 if(f[i][j]==f[i-1][j]) g[i][j]=g[i-1][j];50 if(k&&f[i-1][k-1]+1==f[i][j]) g[i][j]=(g[i][j]+g[i-1][k-1])%p;51 }52 }53 printf("%lld\n",g[n][m]);54 Formylove;55 }56 /*57 ab58 aa59 */

View Code

转载于:https://www.cnblogs.com/Achenchen/p/9555106.html

你可能感兴趣的文章