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题意:a值为1,b值为2,c值为3,给出abc数量,分成两份,求两份最小的差(绝对值).

思路:直接求总和,奇数输出1,偶数输出0即可.因为321可以随机分配达到平衡(打几个表就知道了).

#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题意:给你一个数组,问可以组成多少个特定数组,特定数组满足自己本身的和与原来数组比差一.

思路:数组里有n个1时,我们可以去掉这n个1中任意一个,就有n种选法.当含有0时,不论去掉哪个1,我们对于这个0都是由选与不选两种情况,直接用数组里1的个数乘以2的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>
#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题意:给你一个字符串,你可以选择一种字符(小写字母),删除字符串中任一个数的该字符,问最少删除几个字符可以让字符串变成回文.

思路:枚举26个小写字母,每次确定要对哪个字母进行删除.然后进行双指针模拟,从两边往中间遍历,当两者指针所指的字母相同就继续遍历,不相同看是否可以删除指定的字母来让它变成相同的.一直模拟完进行判断即可.

#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题意:给你一个不含有0的数组a,要求再构造一个相同长度的数组b,让a[i]*b[j]求和之后为0.b同样不能含有0.

思路:我们只需要取两个数组元素a[i],a[j],让b[i]=a[j],b[j]=-a[i]即可.但是当出现数组长度是奇数时,要考虑最后剩下或者任取的三个数字的情况,如果我们把三个数中取两个数合并并且按照上文的方法合并要注意,合并的两个数和不能为0!,不然新构造的数组就包含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

题意:给你一个数组,要求出取出一个非递减的子数组以后的一个异或和x,求出所有可以得到的x.

思路:求疑惑和,a[i]的值<500,所以异或和最大可以为512.我们只需要开一个f数组,去记录异或和为i(下标)的时候,这个非递减数组的最后一位放得什么即可,然后又枚举暴力,详细注释看代码:

#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];
//下标i表示数组异或和为i,里面存的是该异或和下数组末尾接的最小是多少
vector<int>ans;
void solve()
{
    int n;
    scanf("%d",&n);
    f[0]=0;
    for(int i=1;i<=512;i++)
        f[i]=1000;
//初始化
    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]);
       //异或和可以直接是他本身
        for(int j=0;j<=512;j++)
        {
            if(a[i]>=f[j])
                f[j^a[i]]=min(f[j^a[i]],a[i]);
        //如果当前的数字比异或和为j的数组的末尾还要大,那么就连接上去,并且对末位进行刷新即可,如果异或出来过,就看原来已经异或出来的末尾的数字和a[i]的大小,判断a[i]连接上去了还是不是非递减数组.反之直接连接a[i],因为违背异或出来的肯定是a[i]结尾.   
        }
    }
    for(int i=0;i<=512;i++)
    {
        if(f[i]!=1000)
            ans.push_back(i);
    }
//把刷新过得异或和存进去
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++)
    {
        printf("%d ",ans[i]);
    }
    return ;
}
signed main()
{
    solve();
    return 0;
}

刷!