AtCoder Beginner Contest 255

C - ±1 Operation 1

Title Description ：

I'll give you an arithmetic sequence , The first item is A, The tolerance is D, The number of items is N, ask X And here N What is the minimum absolute value of the number difference in the item

Ideas ：

Two minutes , Find the two nearest to him , Just find a minimum

Note that the tolerance may be negative , So we can discuss it according to the situation , Or you can put this N If you look backward at the number, it becomes an equal difference sequence with a positive tolerance

Be careful , If you find greater than or equal to after two points x The position of is the first item or n+1 term , The answer is determined by only one number , Otherwise, take the minimum value of the left and right , We need a special verdict

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, a, d, x;

ll f(ll n){
    
    return a + (n - 1) * d;
}

void work(){
    
    cin >> x >> a >> d >> n;
    ll l = 1, r = n;
    while(l <= r){
    
        ll mid = (l + r) / 2;
        if(d >= 0){
    
            if(f(mid) > x)r = mid - 1;
            else if(f(mid) < x)l = mid + 1;
            else {
    
                cout << 0 << endl;
                return;
            }
        }
        else{
    
            if(f(mid) < x)r = mid - 1;
            else if(f(mid) > x)l = mid + 1;
            else {
    
                cout << 0 << endl;
                return;
            }
        }
    }
    if(d >= 0){
    
        ll id = l - 1;
        if(!id)cout << a - x << endl;
        else if(id == n)cout << x - f(n) << endl;
        else{
    
            cout << min(x - f(id), f(id + 1) - x) << endl;
        }
    }
    else{
    
        ll id = r + 1;
        if(id == 1)cout << x - a << endl;
        else if(id == n + 1)cout << f(n) - x << endl;
        else{
    
            cout << min(f(id - 1) - x, x - f(id)) << endl;
        }
    }
}


int main(){
    
    io;
    work();
    return 0;
}

D - ±1 Operation 2

Title Description ：

Here's your number A, Several inquiries , Every time you ask for a number X, You can add or subtract one several times to any number in the sequence , Ask will array A All the figures of become X How many operations are needed

Ideas ：

Maintain a prefix and after sorting , For each X, We divide the array into smaller than X The sum of numbers is greater than or equal to X Number of numbers , Answer these two parts separately , You only need to know the number of numbers and the sum of numbers , So maintain a prefix and

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m, k, x;
ll tr[MAX];
ll sum[MAX];

ll getsum(ll l, ll r){
    
    return sum[r] - sum[l - 1];
}

void work(){
    
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    sort(tr + 1, tr + 1 + n);
    for(int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + tr[i];
    tr[n + 1] = 1e18;
    for(int i = 1; i <= m; ++i){
    
        cin >> x;
        ll id = upper_bound(tr + 1, tr + 2 + n, x) - tr;
        if(id == 1 || id == n + 1){
    
            cout << abs(n * x - getsum(1, n)) << endl;
        }
        else{
    
            cout << (id - 1) * x - getsum(1, id - 1) + getsum(id, n) - (n - id + 1) * x << endl;
        }
    }
}


int main(){
    
    io;
    work();
    return 0;
}

E - Lucky Numbers

Title Description ：

Here you are. N-1 A digital S[i], as well as M A digital X[i], Now define the array A Satisfy A[i] + A[i + 1] = S[i],i=1,2,...,N-1, Asking when M Numbers in the array A How many times does it appear in

Ideas ：

It's not hard to find out , When A[1] After fixing , Array A It's fixed , So we have to find a way to A[i] use A[1] Express it

A[2] = S[1] - A[1]

A[3] = S[2] - A[2] = S[2] - S[1] + A[1]

A[4] = S[3] - A[3] = S[3] - S[2] + S[1] - A[1]

We set up B[i] = S[i] - B[i], i >= 2, B[1] = 0

therefore $A[i]=B[i]+(-1{)}^{i+1}\ast A[1]$

We put A[1] separate from , You can get $A[1]=(-1{)}^{i+1}\ast (A[i]-B[i])$

Because what we want is A[i] = X[j], So for each of us i, Enumerate each X[j], Calculate what you want A[i] = X[j] when A[1] Value , We use it map Save the quantity , Last run map, Find the output with the largest second key value , Remember to drive longlong

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m, k, x;
ll s[MAX];
ll br[MAX];

void work(){
    
    cin >> n >> m;
    for(int i = 1; i < n; ++i){
    
        cin >> s[i];
    }
    for(int i = 2; i <= n; ++i){
    
        br[i] = s[i - 1] - br[i - 1];
    }
    map<ll, ll>mp;
    for(int j = 1; j <= m; ++j){
    
        cin >> x;
        for(int i = 1; i <= n; ++i){
    
            ++mp[(x - br[i]) * (i % 2 == 0 ? -1 : 1)];
        }
    }
    ll ans = 0;
    for(auto [x, y] : mp)ans = max(ans, y);
    cout << ans << endl;
}


int main(){
    
    io;
    work();
    return 0;
}