Codeforces Round #138 (Div. 1)

记得以前做过当时好像没做对就是找个子串满足括号的匹配 []最多的

开两个栈模拟标记下就行

 #include <iostream>

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 #include<stdlib.h>

 #include<cmath>

 #include<vector>

 #include<queue>

 #include<stack>

 using namespace std;

 #define N 100010

 char s[N];

 char st[N];

 int sn[N][];

 int main()

 {

     int i,k,top=;

     cin>>s;

     k = strlen(s);

     sn[][] = -;sn[][] = -;

     for(i =  ;i < k ;i++)

     {

         if(s[i]=='('||s[i]=='[')

          {

              st[++top] = s[i];

              sn[top][] = i;

              sn[top][] = ;

              sn[top][] = i;

          }

         else

         {

             if(s[i]==')')

             {

                 if(top&&st[top]=='(')

                 {

                    top--;

                    sn[top][] += sn[top+][];

                    sn[top][] = i;

                 }

                 else

                 {

                     st[++top] = s[i];

                     sn[top][] = i;

                     sn[top][] = ;

                     sn[top][] = i;

                 }

             }

             else

             {

                 if(top&&st[top]=='[')

                 {

                    top--;

                    sn[top][] += sn[top+][]+;

                    sn[top][] = i;

                 }

                 else

                 {

                     st[++top] = s[i];

                     sn[top][] = i;

                     sn[top][] = ;

                     sn[top][] = i;

                 }

             }

         }

     }

     int maxz=,x=;

     for(i =  ; i <= top ; i++)

     {

         if(maxz<sn[i][])

         {

             maxz = sn[i][];

             x = i;

         }

     }

     cout<<maxz<<endl;

     for(i = sn[x][]+ ; i <= sn[x][] ; i++)

     cout<<s[i];

     puts("");

     return ;

 }

这题。。描述的很抽象。按我的话来说就是对于每一个s[i]总能找到一个子串包含它而且与t串相等 t串还必须包含了s串的所有字母

做法：开个标记数组标记每个字母向前以及向后最大的匹配位置是否大于等于t串的长度

 #include <iostream>

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 #include<stdlib.h>

 #include<cmath>

 #include<vector>

 #include<queue>

 #include<stack>

 using namespace std;

 #define N 200010

 char s[N],t[N];

 int o[N],f[],w[N];

 int main()

 {

     int i,j,k,tk;

     while(cin>>s)

     {

         memset(o,,sizeof(o));

         memset(w,,sizeof(w));

         memset(f,,sizeof(f));

         k = strlen(s);

         cin>>t;

         tk = strlen(t);

         for(i = tk- ; i >=  ; i--)

         {

             f[t[i]-'a'] = ;

         }

         for(i = k- ; i >=  ; i--)

         {

             if(!f[s[i]-'a']) break;

         }

         if(i!=-||s[]!=t[])

         {

             puts("No");

             continue;

         }

         j =  ;

         for(i =  ; i < k ;i++)

         {

             if(s[i]==t[j])

             {

                 j++;

                 o[i] = j;

                 f[s[i]-'a'] = j;

             }

             else

             {

                 o[i] = f[s[i]-'a'];

             }

         }

         memset(f,,sizeof(f));

         j = tk-;

         for(i = k- ; i >= ;i--)

         {

             if(s[i]==t[j])

             {

                 j--;

                 w[i] = tk--j;

                 f[s[i]-'a'] = tk--j;

             }

             else

             {

                 w[i] = f[s[i]-'a'];

             }

         }

         for(i =  ; i < k ;i++)

         {

             if(o[i]+w[i]<=tk) break;

             //cout<<o[i]<<" "<<w[i]<<endl;

         }

         if(i==k)

         puts("Yes");

         else  puts("No");

     }

     return ;

 }

C 数论题

无奈数论太差研究题解研究了好久。。可以推公式我把具体的推法写一下具体公式是对于第i个数来说 k次转换的结果是 c(k+j-1,j)个a[j]之和（j<=i) 就是当前的数是由多个个a[j]组成的

比如 a[i]都为1 n为5 吧初始为 1 1 1 1 1

就可以推了 k=1时第一个数 1　　　　　=1　　　　　　　　　　　k = 2 第一个数 1　　　　　=1 ===》 1

　　　　　　　　　第二个数 1 1 （代表1个a[1] 1个a[j]） =2 第二个数 2 1 （代表2个a[1] 1个a[j]） =3 ===》 3 1

　　　　　　　　　第三个数 1 1 1 = 3 +(2,1) ===> 第三个数 3 2 1 = 6 ===》 6 3 1

　　　　　　　　　第四个数　1 1 1 1 = 4 +(3,2,1) ====> 第四个数　4 3 2 1 = 10 ====》 10 6 3 1

　　　　　　　　　第五个数 1 1 1 1 1 =5 +(4,3,2,1)====> 第五个数 5 4 3 2 1 = 15 =====》 15 10 6 3 1

差不多基本可以看下了题解说可以看出规律为。。。说实话我没看出来。。。不过我验证了它的规律。。。对于k此操作对应的用去a[j]的个数为o[j] = c(k+j-1,j);

注意这里不要用反例如上面最后一组是15个a[0] 10个a[1]..1个a[4]

另外一些数论的知识因为涉及到组合数又涉及到取余所以涉及到了逆元对于除法的逆元 a/b = ab^-1%mod b^-1为其逆元

逆元又涉及到一递推公式 i的逆元 nv[i]=(-MOD/i*nv[MOD%i]); 验证：两边同乘i nv[i]*i = (-mod/i*nv[mod%i])*i; 逆元性质 a*nv[a]%MOD=1　1 = (-mod/i)*i*1/(mod%i)

so　i*(-MOD/i) == (MOD%i)%MOD

-(MOD-MOD%i) == (MOD%i)%MOD 这个式子显然成立证完

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 2010

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 #define LL long long

 #define mod 1000000007

 LL a[N],v[N],o[N];

 LL cn(int n,int m)

 {

     int i;

     LL s = ;

     for(i =  ; i <= m ;i++)

     {

         s = ((s*v[i])%mod*(n-i+))%mod;//除法取余 乘其逆元

     }

     return s;

 }

 int main()

 {

     int i,j,n,k;

     cin>>n>>k;

     for(i = ; i < n ; i++)

     cin>>a[i];

     if(k==)

     {

         for(i =  ; i< n ;i++)

         cout<<a[i]<<" ";

         puts("");

         return ;

     }

     v[] = v[] = ;

     for(i = ; i < n ; i++)

     v[i] = ((-mod/i*v[mod%i])%mod+mod)%mod;

     for(i =  ; i < n ;i++)

     {

         o[i] = cn(i+k-,i);

     }

     for(i =  ; i < n; i++)

     {

         LL ans=;

         for(j =  ;  j <= i ; j++)

         ans=(ans+a[j]*o[i-j])%mod;

         cout<<ans<<" ";

     }

     puts("");

     return ;

 }

巴特西

Codeforces Round #138 (Div. 1)

最新文章

热门文章