Table of contents

A. Image

B. Deadly Laser

C. Min-Max Array Transformation

D. Maximum AND

A. Image

The meaning of the question: four grids, each grid has a lowercase letter, you can choose at most two identical letters to transform each time, ask to make all the letters the same, at least a few steps.

Idea: Use set to store letters, and then use set size-1. Because when there is only one letter, it can be known as 0, and all cases with two types are nothing more than 2+2 and 3+1, and only one step is required. Yes, the case of three letters is 2+1+1, which requires two steps, and the case of four letters is 1+1+1+1, which requires three steps.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
string a,a1;
set<char>se;
void solve()
{
    se.clear();
    cin>>a>>a1;
    a+=a1;
    for(int i=0;i<a.size();i++)
        se.insert(a[i]);
    cout<<se.size()-1<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. Deadly Laser

The meaning of the question: ask how many steps it takes to go from the upper left corner (1,1) to the lower right corner (n,m). The difference is that there is a laser cannon that can destroy all people on the road with a distance k from the Manhattan. It takes a few steps to get there.

Idea: If it can be reached, it must be n+m-2 steps, and consider the situation that cannot be reached. Our worst case is to walk close to the side, either the upper side plus the right side, or the left side plus the lower side, only need to consider from the The turret extends two walls to see if you can block the above two situations. There are four blocking methods.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int n,m,x,y,d;
    cin>>n>>m>>x>>y>>d;
    int lx=x-d,dx=x+d;
    int ly=y-d,dy=y+d;
    if(lx<=1&&dx>=n||ly<=1&&dy>=m||ly<=1&&lx<=1||dx>=n&&dy>=m)
    {
        cout<<"-1"<<endl;
        return ;
    }
    cout<<n+m-2<<endl;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. Min-Max Array Transformation

The meaning of the question: give you a non-decreasing array a. Add a di to each element ai to get a new array bi (not necessarily non-decreasing), then sort in non-decreasing order, and find a and a in the case of legal construction b arrays are matched, each with the maximum and minimum values ​​of di.

Idea: The minimum value is easy to find, just find the first element b[j] greater than a[i] in the b array, and use b[j]-a[i] to be the minimum value of the current di. The maximum value is a little more difficult. We know that the pair of the last bit is roughly fixed, so we traverse it backwards. We record the element index in the largest b array that can currently match the a array is p. When a[ When i]>b[i-1], then the legal maximum value in the interval from i to p is b[p]-a[i]. At this time, it will be because a[i]>b[i-1 ] and the rule does not hold, directly update p to i-1, and continue to match.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =2e5+10,mod=998244353;
int a[N],b[N],c[N],d[N];
void solve()
{
    int n,l,r,mid;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=1;i<=n;i++)
    {
        l=1,r=n;
        while(l<r)
        {
            mid=(l+r)/2;
            if(b[mid]>=a[i])
                r=mid;
            else
                l=mid+1;
        }
        cout<<b[l]-a[i]<<" ";
    }
    cout<<endl;

    int p=n;
    for(int i=n;i>=1;i--)
    {
        c[i]=b[p]-a[i];
        if(a[i]>b[i-1])
            p=i-1;
    }
    for(int i=1;i<=n;i++)
        cout<<c[i]<<" ";
    cout<<endl;
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

 

D. Maximum AND

The meaning of the question: give you two arrays a,b.b arrays can be arranged at will, ci=ai^bi, ans=c1&c2&c3&c4...cn, find the maximum value of ans.

Idea: Greedy enumerate the high bits, if the number of 0s in a is equal to the number of 1s in b, judge whether the previous number position of ans is 1, and set the bit to 1 if it is established.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =1e5+10,mod=998244353;
int a[N],b[N];
void solve()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=29;i>=0;i--)
    {
        map<int,int>ma;
        ans^=(1<<i);
        for(int i=1;i<=n;i++)
        {
            ma[a[i]&ans]++;
            ma[(~b[i])&ans]--;
        }
//Here, by inverting the a element and the b element & ans, two effects can be achieved: 1. The current digit in the element of the a array is 0
//It is equal to the number of 1s on the number of elements in group b. 2. The a and b that have previously matched the digits satisfy the condition. Because ans contains the previous
//The digit set to 1. When the current state meets the conditions, ++, -- cancel
        int f=0;
        for(int i=1;i<=n;i++)
        {
            if(ma[a[i]&ans])
            {
                f=1;
                break;
            }
        }
        if(f)//If there is no offset, it means illegal, f=1, this bit is not 1
            ans^=(1<<i);
    }
    cout<<ans<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}