Codeforces Beta Round #98 (Div. 2)(A-E)

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 105

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 char s[N];

 int main()

 {

     int i,j,k;

     cin>>s;

     k = strlen(s);

     int ans = ,g=;

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

     {

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

         {

             g = ;

             ans++;

         }

         else g++;

         if(g>)

         {

             g = ;

             ans++;

         }

         //cout<<ans<<" "<<g<<" "<<s[i]<<endl;

     }

     cout<<ans<<endl;

     return ;

 }

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 5050

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int a[N],f[N];

 int main()

 {

     int i,j,n,k;

     cin>>n;

     for(i =;i <= n; i++)cin>>a[i];

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

     {

         f[a[i]] = ;

     }

     int ans=;

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

     if(!f[i]) ans++;cout<<ans<<endl;

     return ;

 }

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 100010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 struct node

 {

     int x,y;

 }p[N];

 bool cmp(node a,node b)

 {

     return a.x<b.x;

 }

 int main()

 {

     int i,j,n;

     cin>>n;

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

     cin>>p[i].x>>p[i].y;

     sort(p+,p+n+,cmp);

     int mm = ,ans=;

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

     {

         if(p[i].y<mm)

         ans++;

         mm = max(mm,p[i].y);

     }

     cout<<ans<<endl;

     return ;

 }

dp 先预处理出来i-j距离回文串所差的步数然后D出1-k所需最少的步数记录一下路径最后输出

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 505

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 char s[N];

 int dp[][],o[][],e[][];

 int p[];

 int dfs(int i,int j)

 {

     int a,b;

     int o1 = ;

     int ii = i,jj = j;

     while(ii<jj)

     {

         if(s[ii]!=s[jj]) o1++;

         ii++,jj--;

     }

     return o1;

 }

 int main()

 {

     int i,j,n,kk,k,g;

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

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

         dp[i][j] = INF;

     cin>>s;

     kk = strlen(s);

     cin>>k;

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

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

         o[i][j] = dfs(i,j);

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

         {

             dp[i][] = o[][i];

         }

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

         for(j =  ; j <= min(i+,k) ; j++)

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

         {

             if(dp[i][j]>dp[g][j-]+o[g+][i])

             {

                 dp[i][j] = dp[g][j-]+o[g+][i];

                 e[i][j] = g;

             }

         }

     int minz = INF,x;

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

     {

         if(minz>dp[kk-][i])

         {

             minz = dp[kk-][i];

             x = i;

         }

     }

     cout<<minz<<endl;

     if(x==)

     {

         for(i = ;  i < kk/ ; i++)

         printf("%c",s[i]);

         for(i = (kk-)/ ; i >=  ; i--)

         printf("%c",s[i]);

         return ;

     }

     g = ;

     int ki = kk-;

     while(x!=)

     {

         ki = e[ki][x];

         p[g++] = ki;

         x--;

     }

     sort(p,p+g);

     for(i =  ;i <= p[]/ ; i++)

     printf("%c",s[i]);

     if(p[])

     {

         for(i = (p[]-)/ ; i >=  ; i--)

         printf("%c",s[i]);

     }

     for(i =  ; i < g- ;i++)

     {

         printf("+");

         for(j = p[i]+ ;j <= p[i]+(p[i+]-p[i]+)/ ; j++)

         cout<<s[j];

         for(j = p[i]+(p[i+]-p[i])/ ;j >= p[i]+ ; j--)

         cout<<s[j];

     }

     if(p[g-]+<kk)

     printf("+");

     for(i = p[g-]+ ; i <= p[g-]+(kk-p[g-])/ ; i++)

     cout<<s[i];

     for(i = p[g-]+(kk-p[g-]-)/ ; i >= p[g-]+ ; i--)

     cout<<s[i];

     cout<<endl;

     return ;

 }

元音-1 辅音+2 开数组sum[i]存前i项和也就是找最大段(i,j)使sum[j]-sum[i]>=0

这样只存下降的sum数组即可因为上升的的某个g事不需要的二分查找第一个小于等于sun[i]的位置取最大

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 200010

 #define LL long long

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 char s[N];

 int sum[N];

 struct node

 {

     int a,po;

 }p[N];

 int bfind(int l,int h,int k)

 {

     int m;

     while(l<h)

     {

         m = (l+h)>>;

         if(p[m].a<k)

         h = m;

         else if(p[m].a>k)

         l = m+;

         else return p[m].po;

     }

     return p[l].po;

 }

 int judge(char c)

 {

     if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')

     return ;

     if(c=='A'||c=='E'||c=='I'||c=='O'||c=='U')

     return ;

     return ;

 }

 int main()

 {

     int i,j,k;

     cin>>s;

     k = strlen(s);

     int g = ;

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

     {

         if(i==)

         {

             if(judge(s[i]))

             sum[] = -;

             else

             sum[] = ;

             p[++g].a = sum[i];

             p[g].po = i;

         }

         else

         {

             if(judge(s[i]))

             sum[i] = sum[i-]-;

             else

             sum[i] = sum[i-]+;

             if(sum[i]<p[g].a)

             {

                 p[++g].a = sum[i];

                 p[g].po = i;

             }

         }

     }

     int ans=,cnt=;

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

     {

         if(sum[i]>=)

         {

             ans = i+;

             cnt = ;

         }

         else

         {

             int o = i-bfind(,g,sum[i]);

             //cout<<o<<" "<<i<<" "<<bfind(1,g,sum[i])<<endl;

             if(o>ans)

             {

                 ans = o;

                 cnt = ;

             }

             else if(o==ans)

             cnt++;

         }

     }

     if(ans)

     cout<<ans<<" "<<cnt<<endl;

     else

     puts("No solution");

     return ;

 }

巴特西

Codeforces Beta Round #98 (Div. 2)(A-E)

最新文章

热门文章