您的位置: 首页  >  IT文章  >  Codeforces Beta Round #98 (Div. 2)(A-E)

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

分类: IT文章 • 2024-06-16 07:41:31

A

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 105
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 char s[N];
18 int main()
19 {
20     int i,j,k;
21     cin>>s;
22     k = strlen(s);
23     int ans = 1,g=1;
24     for(i = 1; i < k ;i++)
25     {
26         if(s[i]!=s[i-1])
27         {
28             g = 1;
29             ans++;
30         }
31         else g++;
32         if(g>5)
33         {
34             g = 1;
35             ans++;
36         }
37         //cout<<ans<<" "<<g<<" "<<s[i]<<endl;
38     }
39     cout<<ans<<endl;
40     return 0;
41 }
View Code

B

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 5050
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 int a[N],f[N];
18 int main()
19 {
20     int i,j,n,k;
21     cin>>n;
22     for(i =1;i <= n; i++)cin>>a[i];
23     for(i = 1;i <= n ;i++)
24     {
25         f[a[i]] = 1;
26     }
27     int ans=0;
28     for(i = 1; i<=  n; i++)
29     if(!f[i]) ans++;cout<<ans<<endl;
30     return 0;
31 }
View Code

C

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 #include<cmath>
 8 #include<queue>
 9 #include<set>
10 using namespace std;
11 #define N 100010
12 #define LL long long
13 #define INF 0xfffffff
14 const double eps = 1e-8;
15 const double pi = acos(-1.0);
16 const double inf = ~0u>>2;
17 struct node
18 {
19     int x,y;
20 }p[N];
21 bool cmp(node a,node b)
22 {
23     return a.x<b.x;
24 }
25 int main()
26 {
27     int i,j,n;
28     cin>>n;
29     for(i = 1; i <= n ;i++)
30     cin>>p[i].x>>p[i].y;
31     sort(p+1,p+n+1,cmp);
32     int mm = 0,ans=0;
33     for(i = 1; i <= n ;i ++)
34     {
35         if(p[i].y<mm)
36         ans++;
37         mm = max(mm,p[i].y);
38 
39     }
40     cout<<ans<<endl;
41     return 0;
42 }
View Code

D

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

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 using namespace std;
 11 #define N 505
 12 #define LL long long
 13 #define INF 0xfffffff
 14 const double eps = 1e-8;
 15 const double pi = acos(-1.0);
 16 const double inf = ~0u>>2;
 17 char s[N];
 18 int dp[505][505],o[505][505],e[505][505];
 19 int p[505];
 20 int dfs(int i,int j)
 21 {
 22     int a,b;
 23     int o1 = 0;
 24     int ii = i,jj = j;
 25     while(ii<jj)
 26     {
 27         if(s[ii]!=s[jj]) o1++;
 28         ii++,jj--;
 29     }
 30     return o1;
 31 }
 32 int main()
 33 {
 34     int i,j,n,kk,k,g;
 35     for(i = 0 ;i <= 500 ; i++)
 36         for(j = 0 ; j <=500 ; j++)
 37         dp[i][j] = INF;
 38     cin>>s;
 39     kk = strlen(s);
 40     cin>>k;
 41     for(i = 0 ;i < kk ;i++)
 42         for(j = i ; j < kk ;j++)
 43         o[i][j] = dfs(i,j);
 44     for(i = 0; i < kk; i++)
 45         {
 46             dp[i][1] = o[0][i];
 47         }
 48     for(i = 0 ;i < kk ;i++)
 49         for(j = 2 ; j <= min(i+1,k) ; j++)
 50         for(g = 0 ; g < i ; g++)
 51         {
 52             if(dp[i][j]>dp[g][j-1]+o[g+1][i])
 53             {
 54                 dp[i][j] = dp[g][j-1]+o[g+1][i];
 55                 e[i][j] = g;
 56             }
 57         }
 58     int minz = INF,x;
 59     for(i = 1 ; i <= k ;i++)
 60     {
 61         if(minz>dp[kk-1][i])
 62         {
 63             minz = dp[kk-1][i];
 64             x = i;
 65         }
 66     }
 67     cout<<minz<<endl;
 68     if(x==1)
 69     {
 70         for(i = 0;  i < kk/2 ; i++)
 71         printf("%c",s[i]);
 72         for(i = (kk-1)/2 ; i >= 0 ; i--)
 73         printf("%c",s[i]);
 74         return 0;
 75     }
 76     g = 0;
 77     int ki = kk-1;
 78     while(x!=1)
 79     {
 80         ki = e[ki][x];
 81         p[g++] = ki;
 82         x--;
 83     }
 84     sort(p,p+g);
 85     for(i = 0 ;i <= p[0]/2 ; i++)
 86     printf("%c",s[i]);
 87     if(p[0])
 88     {
 89         for(i = (p[0]-1)/2 ; i >= 0 ; i--)
 90         printf("%c",s[i]);
 91     }
 92     for(i = 0 ; i < g-1 ;i++)
 93     {
 94         printf("+");
 95         for(j = p[i]+1 ;j <= p[i]+(p[i+1]-p[i]+1)/2 ; j++)
 96         cout<<s[j];
 97         for(j = p[i]+(p[i+1]-p[i])/2 ;j >= p[i]+1 ; j--)
 98         cout<<s[j];
 99     }
100     if(p[g-1]+1<kk)
101     printf("+");
102     for(i = p[g-1]+1 ; i <= p[g-1]+(kk-p[g-1])/2 ; i++)
103     cout<<s[i];
104     for(i = p[g-1]+(kk-p[g-1]-1)/2 ; i >= p[g-1]+1 ; i--)
105     cout<<s[i];
106     cout<<endl;
107     return 0;
108 }
View Code

E

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

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

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 using namespace std;
 11 #define N 200010
 12 #define LL long long
 13 #define INF 0xfffffff
 14 const double eps = 1e-8;
 15 const double pi = acos(-1.0);
 16 const double inf = ~0u>>2;
 17 char s[N];
 18 int sum[N];
 19 struct node
 20 {
 21     int a,po;
 22 }p[N];
 23 int bfind(int l,int h,int k)
 24 {
 25     int m;
 26     while(l<h)
 27     {
 28         m = (l+h)>>1;
 29         if(p[m].a<k)
 30         h = m;
 31         else if(p[m].a>k)
 32         l = m+1;
 33         else return p[m].po;
 34     }
 35     return p[l].po;
 36 }
 37 int judge(char c)
 38 {
 39     if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
 40     return 1;
 41     if(c=='A'||c=='E'||c=='I'||c=='O'||c=='U')
 42     return 1;
 43     return 0;
 44 }
 45 int main()
 46 {
 47     int i,j,k;
 48     cin>>s;
 49     k = strlen(s);
 50     int g = 0;
 51     for(i = 0; i < k ;i++)
 52     {
 53         if(i==0)
 54         {
 55             if(judge(s[i]))
 56             sum[0] = -1;
 57             else
 58             sum[0] = 2;
 59             p[++g].a = sum[i];
 60             p[g].po = i;
 61         }
 62         else
 63         {
 64             if(judge(s[i]))
 65             sum[i] = sum[i-1]-1;
 66             else
 67             sum[i] = sum[i-1]+2;
 68             if(sum[i]<p[g].a)
 69             {
 70                 p[++g].a = sum[i];
 71                 p[g].po = i;
 72             }
 73         }
 74     }
 75     int ans=0,cnt=0;
 76     for(i = 0 ; i < k ;i++)
 77     {
 78         if(sum[i]>=0)
 79         {
 80             ans = i+1;
 81             cnt = 1;
 82         }
 83         else
 84         {
 85             int o = i-bfind(1,g,sum[i]);
 86             //cout<<o<<" "<<i<<" "<<bfind(1,g,sum[i])<<endl;
 87             if(o>ans)
 88             {
 89                 ans = o;
 90                 cnt = 1;
 91             }
 92             else if(o==ans)
 93             cnt++;
 94         }
 95     }
 96     if(ans)
 97     cout<<ans<<" "<<cnt<<endl;
 98     else
 99     puts("No solution");
100     return 0;
101 }
View Code

相关推荐