abc136

第一次打ABC

题目简单，但我菜

E - Max GCD

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

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

check(x)

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

维护一个前缀和，即满足$sum[i]==(n-i) imes 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[505];
ll B[505];

ll K;ll N;
bool check(ll x)
{
    ll t=0;
    for(int i=1;i<=N;i++){
        B[i]=(A[i-1])%x;
    }
    sort(B+1,B+N+1);
    for(int i=1;i<=N;i++){
        B[i]+=B[i-1];
    }
    for(int i=0;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=0;
    for(int i=0; i<N; i++)
    {
        sc(A[i]);
        t+=A[i];
    }
    sort(A,A+N);
    ll ans=1;
    ll x;
    for(ll i=1; i*i<=t; i++)
    {
        if(t%i==0)
        {
            x=t/i;
            if(check(x))
            {
                ans=x;
                break;
            }
            else if(check(i))
            {
                ans=i;
            }

        }
    }
    cout<<ans<<'
';
}

D - Gathering Children

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

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 #define pair<int,int> P
 4 #define sc(N) scanf("%lld",&N);
 5 using namespace std;
 6 int N;
 7 string s;
 8 int A[100005];
 9 
10 int main()
11 {
12     cin>>s;
13     int n=s.length();
14     int j=0;
15     for(int i=0; i<n;)
16     {
17        // cout<<i<<endl;
18         if(s[i]=='R')
19         {
20             while(s[i+j]=='R')
21             {
22                 j++;
23             }
24 
25             int k=i+j;i=i+j;
26             while(j>0)
27             {
28                 if(j&1)A[k-1]++;
29                 else A[k]++;
30                 j--;
31             }
32 
33         }
34         else
35         i++;
36 
37     }
38 
39 
40      for(int i=n-1; i>=0;)
41     {
42         //cout<<i<<endl;
43         j=0;
44         if(s[i]=='L')
45         {
46             while(s[i-j]=='L')
47             {
48                 j++;
49             }
50             //i=i-j;
51             int k=i-j;i=i-j;
52             while(j>0)
53             {
54                 if(j&1)A[k+1]++;
55                 else A[k]++;
56                 j--;
57             }
58 
59 
60         }
61         else
62         i--;
63 
64     }
65     for(int i=0;i<n;i++){
66         cout<<A[i]<<' ';
67     }
68     cout<<'
';
69 
70 }