abc136

第一次打ABC

题目简单，但我菜

可以任选两个数，一个减去1，一个加上1，可以操作$0,\cdots,K$次，求操作后数组最大GCD

枚举数组之和的因子，试图找到符合题意的最大因子

check(x)

对x取模，然后排下序，前面的减到0后面的加到x，枚举分界点，看能不能找到减去的与加上的相等的位置

维护一个前缀和，即满足$sum[i]==(n-i)\times x-sum[n]+sum[i]$的位置

#include<bits/stdc++.h>

typedef long long ll;

#define pair<int,int> P

#define sc(N) scanf("%lld",&N);

using namespace std;

ll A[];

ll B[];

ll K;ll N;

bool check(ll x)

{

    ll t=;

    for(int i=;i<=N;i++){

        B[i]=(A[i-])%x;

    }

    sort(B+,B+N+);

    for(int i=;i<=N;i++){

        B[i]+=B[i-];

    }

    for(int i=;i<=N;i++){

        if(B[i]==x*(N-i)-B[N]+B[i]){

            if(B[i]<=K)return true;

        }

        if(B[i]>K)return false;

    }

    return false;

}

int main()

{

    sc(N);

    sc(K);

    ll t=;

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

    {

        sc(A[i]);

        t+=A[i];

    }

    sort(A,A+N);

    ll ans=;

    ll x;

    for(ll i=; i*i<=t; i++)

    {

        if(t%i==)

        {

            x=t/i;

            if(check(x))

            {

                ans=x;

                break;

            }

            else if(check(i))

            {

                ans=i;

            }

        }

    }

    cout<<ans<<'\n';

}

D - Gathering Children

给一个一堆’L‘,'R'的字符串s，每个位置站一个小人，按着脚下’L‘，’R‘的方向来走，求10^100步后，每个位置有多少小人

 #include<bits/stdc++.h>

 typedef long long ll;

 #define pair<int,int> P

 #define sc(N) scanf("%lld",&N);

 using namespace std;

 int N;

 string s;

 int A[];

 int main()

 {

     cin>>s;

     int n=s.length();

     int j=;

     for(int i=; i<n;)

     {

        // cout<<i<<endl;

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

         {

             while(s[i+j]=='R')

             {

                 j++;

             }

             int k=i+j;i=i+j;

             while(j>)

             {

                 if(j&)A[k-]++;

                 else A[k]++;

                 j--;

             }

         }

         else

         i++;

     }

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

     {

         //cout<<i<<endl;

         j=;

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

         {

             while(s[i-j]=='L')

             {

                 j++;

             }

             //i=i-j;

             int k=i-j;i=i-j;

             while(j>)

             {

                 if(j&)A[k+]++;

                 else A[k]++;

                 j--;

             }

         }

         else

         i--;

     }

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

         cout<<A[i]<<' ';

     }

     cout<<'\n';

 }

巴特西

abc136

最新文章

热门文章