CodeForces 558A，B

客官°小女子只卖身不卖艺 2022-08-18 11:59 19阅读 0赞

[CodeForces 558A][]

题意：给定一些苹果树的位置和树上的苹果数，然后一个人站在原点，每次碰到苹果就往相反的方向走，问能得到的最大苹果数。

思路：直接模拟即可。先假设往左走，然后再假设往右走。遍历一遍即可。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=205;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,n) for (int i=s;i>=n;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    struct node
    {
        int x,a;
    }g[M];
    bool cmp(node A,node B){
        return A.x<B.x;
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        ft(i,1,n) scanf("%d %d",&g[i].x,&g[i].a);
        sort(g+1,g+1+n,cmp);
        g[0].a=g[0].x=0;
        g[n+1].a=g[n+1].x=0;
        int t=1,ans=0,s=0;
        ft(i,2,n){
          if (g[i-1].x<0&&g[i].x>0){ t=i;break;}
        }
        if (t==1){
            if (g[1].x>0) printf("%d\n",g[1].a);
            else printf("%d\n",g[n].a);
            return 0;
        }
        s=g[t].a;
        for (int p=t-1,q=t+1;;p--,q++)
        {
            if (g[p].a) s+=g[p].a;
            else  break;
            if (g[q].a) s+=g[q].a;
            else break;
        }
        ans=g[t-1].a;
        for (int p=t-2,q=t;;p--,q++)
        {
            if (g[q].a) ans+=g[q].a;
            else break;
            if (p<0) break;
            if (g[p].a) ans+=g[p].a;
            else break;
        }
         ans=max(ans,s);
        printf("%d\n",ans);
    }

[CodeForces 558][CodeForces 558A]B

题意：在不改变整个数组出现最多的数的次数的条件下使区间尽量小。

思路：在输入的时候，记录某个数的左右区间。然后遍历，当某个数的出现次数等于最大值时就缩减。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000+5;
    const int M=1e5+5;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,n) for (int i=s;i>=n;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int n,v[M];
    int ct[N];
    struct node
    {
        int x,y;
    }g[N];
    int main()
    {
        scanf("%d",&n);
        cls(ct,0);
        ft(i,1,n) {
            scanf("%d",&v[i]);
            int t=v[i];
            if (ct[t]==0)g[t].x=i;
            g[t].y=i;
            ct[t]++;
        }
    
        int mx=0;
        ft(i,1,n) mx=max(mx,ct[v[i]]);
    
        int al=1,ar=n;
        ft(i,1,N){
            if (ct[i]==mx){
                int ti=g[i].x,tj=g[i].y;
                if (tj-ti<ar-al)
                {
                    al=ti;ar=tj;
                }
            }
        }
        printf("%d %d\n",al,ar);
    }

[CodeForces 558A]: http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=192660