Codeforces Round ＃750 (Div. 2)(A,B,C,D,F1)

A. Luntik and Concerts

Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1582/problem/A The question :a The value is 1,b The value is 2,c The value is 3, give abc Number , Split it in two , Find the minimum difference between the two ( The absolute value ).

Ideas : Direct summation , Odd output 1, Even output 0 that will do . because 321 Can be randomly assigned to achieve equilibrium ( Just type a few watches ).

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int a,b,c;
    cin>>a>>b>>c;
    b*=2,c*=3;
    int ans=a+b+c;
    if(ans%2)
        cout<<"1\n";
    else
        cout<<"0\n";
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. Luntik and Subsequences

Problem - B - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1582/problem/B The question : Give you an array , Ask how many specific arrays can be formed , A specific array satisfies its own sum and is one less than the original array .

Ideas : In the array are n individual 1 when , We can get rid of this n individual 1 Any one of , There is n Seed selection . When it contains 0 when , No matter which one is removed 1, We're talking about this 0 Both are selected and not selected , Directly use the array 1 Multiply the number of 2 Of 0 Several times of .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int x,n,cnt1=0,cnt0=0;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        if(x==1)
            cnt1++;
        if(x==0)
            cnt0++;
    }
    int ans=cnt1*pow(2,cnt0);
    printf("%lld\n",ans);
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. Grandma Capa Knits a Scarf

Problem - C - Codeforceshttps://codeforces.com/contest/1582/problem/C The question : Give you a string , You can choose a character ( Lowercase letters ), Delete the character of any number in the string , Ask to delete at least a few characters to make the string become palindromes .

Ideas : enumeration 26 Lowercase letters , Determine which letter to delete each time . Then double pointer simulation , Traverse from both sides to the middle , When the two pointers point to the same letter, continue to traverse , Different. See if you can delete the specified letter to make it the same . After the simulation, judge it .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int f=0;
    int n,ans=1e9;
    string s,ss;
    scanf("%d",&n);
    cin>>s;
    for(int i=0;i<26;i++)
    {
        char ch='a'+i;
        ss="";
        for(int i=0;i<s.size();i++)
        {
            if(s[i]!=ch)
                ss+=s[i];
        }
        string s1=ss;
        reverse(ss.begin(),ss.end());
        if(ss!=s1)
        {
            continue;
        }
        int tt=0;
        
        int l=0,r=s.size()-1;
        while(l<r)
        {
            while(s[l]!=s[r])
            {
                if(s[l]!=ch&&s[r]==ch)
                    r--,tt++;
                else if(s[l]==ch&&s[r]!=ch)
                    l++,tt++;
                if(l>r)
                    break;
            }
            l++;
            r--;
        }
        ans=min(ans,tt);
        f=1;
    }
    if(f==0)
        printf("-1\n");
    else
        printf("%d\n",ans);
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D. Vupsen, Pupsen and 0

Problem - D - Codeforceshttps://codeforces.com/contest/1582/problem/D The question : Give you one that does not contain 0 Array of a, It is required to construct an array with the same length b, Give Way a[i]*b[j] After the sum is 0.b Also cannot contain 0.

Ideas : We only need to take two array elements a[i],a[j], Give Way b[i]=a[j],b[j]=-a[i] that will do . But when the array length is odd , Consider the last remaining or optional three numbers , If we combine two of the three numbers and follow the above method, we should pay attention to , The sum of two combined numbers cannot be 0!, Otherwise, the newly constructed array will contain 0 了 .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
const int N =5e5+10,mod=998244353;
int a[100005];
int b[100005];
void solve()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    if(n%2==0)
    {
        for(int i=1;i<=n;i+=2)
        {
            b[i]=-a[i+1];
            b[i+1]=a[i];    
        }
    }
    else
    {
        for(int i=1;i<=n-3;i+=2)
        {
            b[i]=-a[i+1];
            b[i+1]=a[i];    
        }
            if(a[n]+a[n-1]!=0)
            {
                b[n]=-a[n-2];
                b[n-1]=-a[n-2];
                b[n-2]=a[n]+a[n-1];
            }
            else if(a[n]+a[n-2]!=0)
            {
                b[n]=-a[n-1];
                b[n-1]=a[n]+a[n-2];
                b[n-2]=-a[n-1];
            }
            else if(a[n-2]+a[n-1]!=0)
            {
                b[n]=a[n-2]+a[n-1];
                b[n-1]=-a[n];
                b[n-2]=-a[n];
            }
        
    }
    for(int i=1;i<=n;i++)
        printf("%d ",b[i]);
    printf("\n");
    // int sum=0;
    // for(int i=1;i<=n;i++)
    //     sum+=a[i]*b[i];
    // cout<<"qwq   "<<sum<<"\n";
    return;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

F1. Korney Korneevich and XOR (easy version)

Problem - F1 - Codeforceshttps://codeforces.com/contest/1582/problem/F1

The question : Give you an array , Ask for an XOR and after taking out a non decreasing subarray x, Find out all you can get x.

Ideas : Ask for doubt and peace ,a[i] Value <500, So XOR and Max can be 512. We just need to open one f Array , To record XOR and as i( Subscript ) When , The last digit of this non decreasing group can be placed , Then enumerate violence , See the code for detailed comments :

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
int a[100005];
using namespace std;
const int N =5e5+10,mod=998244353;
int f[600];
// Subscript i Indicates that the XOR and sum of the array are i, What is stored in it is the minimum number of the XOR and the end of the lower array 
vector<int>ans;
void solve()
{
    int n;
    scanf("%d",&n);
    f[0]=0;
    for(int i=1;i<=512;i++)
        f[i]=1000;
// initialization 
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]); 
    }
    for(int i=1;i<=n;i++)
    {
        f[a[i]]=min(f[a[i]],a[i]);
       // XOR and can be directly himself 
        for(int j=0;j<=512;j++)
        {
            if(a[i]>=f[j])
                f[j^a[i]]=min(f[j^a[i]],a[i]);
        // If the current number is greater than XOR and j The end of the array of is even larger , Then connect , And refresh the last bit , If XOR comes out , Just look at the number and at the end of the XOR a[i] Size , Judge a[i] Connected or not non decreasing Group . On the contrary, connect directly a[i], Because what goes against XOR must be a[i] ending .   
        }
    }
    for(int i=0;i<=512;i++)
    {
        if(f[i]!=1000)
            ans.push_back(i);
    }
// Save the refreshed XOR and 
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)
    {
        printf("%d ",ans[i]);
    }
    return ;
}
signed main()
{
    solve();
    return 0;
}

brush !