跳转至

2021-02-16-2月16日题解

A题

image-20210216212608839

题解

给除指定下标以外的数做加法，相当于给这个数做减法，所以将这些数全变为0即可。

代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("%d\n",n);
        for(int i=1;i<=n;i++)
            printf("%d ",i);
        printf("\n");
    }
    return 0;
}

B题

image-20210216212850286

题解

改变相邻两个数的正负号，求求和后的最大值，可以发现，如果有偶数个负数，我们可以将其全部转为正数，如果有奇数个负数，则一定会有一个负数，将这个负数控制为最小即可。

代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[30][30]={0};
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int sum=0,min1=99999999,ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]),ans+=(int)abs(a[i][j]);
                if(a[i][j]<0)
                    sum++;
                min1=min(min1,(int)fabs(a[i][j]));
            }
        }
        if(sum%2==0)
            printf("%d\n",ans);
        else{
            ans-=2*min1;
            printf("%d\n",ans);
        }
    }
    return 0;
}

C题

image-20210216213136488

题解

可以发现如果原数组中有大于W/2且小于W的数时可以直接将其输出，反之则排序后从小到大相加即可。

代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll n,val;
};
node a[200500]={0};
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,m;
        scanf("%lld%lld",&n,&m);
        ll mid=m/2;
        if(m%2!=0)
            mid++;
        ll flag=-1;
        for(ll i=1;i<=n;i++)
        {
            scanf("%lld",&a[i].val);
            a[i].n=i;
            if(a[i].val>=mid&&a[i].val<=m)
                flag=i;
        }
        if(flag!=-1)
        {
            printf("1\n%lld\n",flag);
            continue;
        }
        sort(a+1,a+n+1,[](node a,node b){return a.val<b.val;});
        ll sum=0;
        flag=-1;
        for(ll i=1;i<=n;i++)
        {
            sum+=a[i].val;
            if(sum>=mid&&sum<=m)
            {
                flag=i;
                break;
            }
            if(sum>m)
                break;
        }
        if(flag!=-1)
        {
            printf("%lld\n",flag);
            for(ll i=1;i<=flag;i++)
            {
                printf("%lld ",a[i].n);
            }
            printf("\n");
        }
        else
        {
            printf("-1\n");
        }
    }
    return 0;
}

D题

image-20210216213404055

题解

动态规划，dp[i][j]代表最后一个字母为a[i]和b[j]时的最大值，则可以得到以下递推公式

if a[i]==b[j] :

​ dp[i][j]=max(dp[i-1][j-1]+2,dp[i][j]) \\相同时LSA加1，同时两个串的长度增加1

else :

​ dp[i][j]=max(dp[i][j-1]-1,dp[i-1][j]-1) \\不同时只能由两边转移过来，并且长度加1

其中dp[i][j]最小为0，最后取最大值即为答案。

代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[5050][5050]={0};
char a[5050]={0};
char b[5050]={0};
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j])
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+2);
            else
                dp[i][j]=max(dp[i][j-1],dp[i-1][j])-1;
            dp[i][j]=max(dp[i][j],0);
        }
    }
    int max1=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            max1=max(max1,dp[i][j]);
        }
    }
    printf("%d\n",max1);
    return 0;
}

H题

image-20210216213935402

题解

奇偶矩阵（比赛时差一点想出，但是还差一点点，额）

image-20210216214635241

可以发现如果控制标记的点与周围的点数值不同时即可满足题目的要求（每对相邻的点数值各不相同）。

容易发现这些标注的点横纵坐标之和均为偶数，其余未标注的点和均为奇数。

这是我们只需要控制标注的点所对应的数值均为偶数，未标记点的数值均为奇数，这样就可以实现各不相同了。

代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200][200]={0};
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if((i+j)%2!=a[i][j]%2)
                    a[i][j]++;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                printf("%d ",a[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}