清北考前刷题day6下午好

/*

贪心 负数一定不取

枚举最高位是1 且答案取为0的 位置， 更新答案。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

#define N 100010

using namespace std;

int n;

ll a[N],ans,sum[N];

char s[N];

ll read()

{

    ll x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int main()

{

    freopen("maximum.in","r",stdin);

    freopen("maximum.out","w",stdout);

    scanf("%d",&n);

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

    {

        a[i]=read();

        sum[i]=sum[i-];

        if(a[i]>)sum[i]=sum[i-]+a[i];

    }

    scanf("%s",s+);

    ll c=;

    for(int i=n; i>=; i--)

      if(s[i]=='')

      {

          ans=max(ans,c+sum[i-]);

          c+=max(a[i],0LL);

      }

    ans=max(ans,c);

    printf("%I64d\n",ans);

    return ;

}

/*

15暴力

*/

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 1010

using namespace std;

int n,k;

int l,r,mid;

int num[N],tmp[N];

int ans;

int minn(int a,int b,int i)

{

    if(a<b) return tmp[i-];

    else return tmp[i-]+mid;

}

bool check()

{

    int sum=;

    for(int i=; i<=n; i++)    tmp[i]=num[i];

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

        if(abs(tmp[i]-tmp[i-])>mid)

        {

            if(tmp[i+]>tmp[i]) tmp[i]=max(tmp[i],tmp[i-]+mid);

            else tmp[i]=minn(abs(tmp[i-]-tmp[i+]),tmp[i-]+mid-tmp[i+],i);

            sum++;

        }

    if(sum>k)    return false;

    else return true;

}

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=; i<=n; i++)    scanf("%d",&num[i]);

    l=;

    r=;

    while(l<=r)

    {

        mid=(l+r)/;

        if(check())    ans=mid,r=mid-;

        else l=mid+;

    }

    printf("%d",ans);

}

不会分块

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <ctime>

using namespace std;

const int maxn = ;

const int len = ;

int n, A, B,m;

int a[maxn],b[maxn],l[maxn],r[maxn],lb[maxn],tot;

int answer[][];

int rt[][maxn], lt[][maxn],d[maxn];

//int root[maxn*len], ll[maxn*len], rr[maxn*len],data[maxn*len];

int find(int x)

{

    for (int l = , r = m; l < r;)

    {

        int mid = (l + r) / ;

        if (b[mid] == x) return mid;

        if (b[mid]>x) r = mid;

        else l = mid + ;

    }

    return -;

}

/*int build(int l, int r)

{

 if (l == r)

 {

  tot++;

  ll[tot] = rr[tot] = 0;

  data[tot] = d[l];

  return tot;

 }

 tot++;

 int tmp = tot;

 ll[tmp] = build(l, (l + r) / 2);

 rr[tmp] = build((l + r) / 2 + 1, r);

 data[tmp] = min(data[ll[tmp]], data[rr[tmp]]);

 return tmp;

}

int change(int i, int l, int r,int x)

{

 if (l == x && r == x)

 {

  tot++;

  ll[tot] = rr[tot] = 0;

  data[tot] = n + 1;

  return tot;

 }

 tot++;

 int tmp = tot;

 ll[tot] = ll[i];

 rr[tot] = rr[i];

 if (l <= x && x <= (l + r) / 2) ll[tmp] = change(ll[i], l, (l + r) / 2, x);

 else rr[tmp] = change(rr[i], (l + r) / 2 + 1, r, x);

 data[tmp] = min(data[ll[tmp]], data[rr[tmp]]);

 return tmp;

}

int check(int i, int l, int r, int x, int &ans)

{

 if (l > x) return 0;

 if (1 <= l && r <= x)

 {

  ans = min(ans, data[i]); return 0;

 }

 check(ll[i], l, (l + r) / 2, x, ans);

 check(rr[i], (l + r) / 2 + 1, r, x, ans);

 return 0;

}*/

int main()

{

    double ti = clock();

    freopen("sequence.in", "r", stdin);

    freopen("sequence.out", "w", stdout);

    scanf("%d%d%d", &n, &A, &B);

    a[] = ;

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

    {

        char c;

        for (scanf(" %c", &c); c != 'A' && c != 'B'; scanf(" %c", &c));

        if (c == 'A') a[i] = a[i - ] + B;

        else a[i] = a[i - ] - A;

    }

    for (int i = ; i <= n; i++) b[i] = a[i];

    sort(b, b + n + );

    m = unique(b, b + n + ) - b;

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

    {

        a[i] = find(a[i]);

        if (a[i] == -)

        {

            printf("???\n");

            return ;

        }

    }

    n++;

    int k = n / len;

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

    {

        int ans = ;

        tot++;

        for (int j = i*len; j < n; j++)

        {

            if (j%len == )

            {

                answer[i][j / len] = ans;

            }

            if (lb[a[j]] != tot)

            {

                lb[a[j]] = tot;

                l[a[j]] = j;

            }

            ans = max(ans, j - l[a[j]]);

        }

    }

    for (int i = ; i < n; i++) r[i] = -;

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

    {

        r[a[i]] = i;

        if (i%len == len - )

        {

            int tmp = i / len;

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

                rt[tmp][j] = r[j];

        }

    }

    for (int i = ; i < n; i++) l[i] = -;

    for (int i = n - ; i >= ; i--)

    {

        l[a[i]] = i;

        if (i%len == )

        {

            int tmp = i / len;

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

                lt[tmp][j] = l[j];

        }

    }

    int q;

    scanf("%d", &q);

    int ans = ;

    for (; q; q--)

    {

        int L, R;

        scanf("%d%d", &L, &R);

        L--;

        int kl = L / len, kr = R / len;

        ans = ;

        if (kl == kr)

        {

            tot++;

            for (int i = L; i <= R; i++)

            {

                if (lb[a[i]] != tot)

                {

                    lb[a[i]] = tot;

                    l[a[i]] = i;

                }

                ans = max(ans, i - l[a[i]]);

            }

        }

        else

        {

            ans = answer[kl + ][kr];

            tot++;

            int tmp = min(n, (kl + )*len);

            for (int i = L; i < tmp; i++)

            {

                if (lb[a[i]] != tot)

                {

                    lb[a[i]] = tot;

                    l[a[i]] = i;

                    ans = max(ans, rt[kr - ][a[i]] - i);

                }

            }

            tmp = min(R + , n);

            for (int i = kr*len; i < tmp; i++)

            {

                if (lb[a[i]] != tot)

                {

                    if (lt[kl + ][a[i]] != -) ans = max(ans, i - lt[kl + ][a[i]]);

                }

                else ans = max(ans, i - l[a[i]]);

            }

        }

        printf("%d\n", ans);

    }

    /*int q;

    for (scanf("%d", &q); q; q--)

    {

     // if (q % 5000 == 0) cerr << q << endl;

     int L, R;

     tot++;

     scanf("%d%d", &L, &R);

     int ans = 0;

     for (int i = L - 1; i <= R; i++)

     {

      if (lb[a[i]] != tot)

      {

       lb[a[i]] = tot;

       l[a[i]] = i;

      }

      ans = max(ans, i - l[a[i]]);

     }

     printf("%d\n", ans);

    }*/

    /*for (int i = 0; i <= n; i++)

    {

     if (lb[a[i]] == 0)

     {

      lb[a[i]] = 1;

      l[a[i]] = i;

      d[i] = n + 1;

     }

     else

     {

      r[l[a[i]]] = i;

      d[i] = i - l[a[i]];

      l[a[i]] = i;

     }

    }

    root[0] = build(1, n);

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

    {

     if (r[i-1] != 0) root[i] = change(root[i - 1], 1, n, r[i-1]);

     else root[i] = root[i - 1];

    }

    int q;

    for (scanf("%d", &q); q; q--)

    {

     int L, R;

     scanf("%d%d", &L, &R);

     L--;

     int ans = n + 1;

     check(root[L], 1, n, R, ans);

     if (ans == n + 1) printf("-1\n"); else printf("%d\n", ans);

    }*/

    /* int q;

     int tans = 0;

     for (scanf("%d", &q); q; q--)

     {

      int L, R;

      scanf("%d%d", &L, &R);

      L--;

      tot++;

      int ans = n + 1;

      for (int i = L; i <= R; i++)

      {

       if (lb[a[i]] != tot)

       {

        lb[a[i]] = tot;

        l[a[i]] = i;

       }

       else

       {

        ans = min(ans, i - l[a[i]]);

        l[a[i]] = i;

       }

      }

      if (ans == n + 1) printf("-1\n"); else  {

       printf("%d\n", ans);

       tans = max(tans, ans);

      }

     }

     cerr << clock()-ti << " "<<tans<<" "<<A<<" "<<B<<endl;*/

    return ;

}

std

巴特西

清北考前刷题day6下午好

最新文章

热门文章